| TerraLib 4.1

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Examples

- File List
- File Members

E:/Projetos_Primeiro_Semestre_2012/TerraView/terralib/src/terralib/kernel/Gra_algo.h
Go to the documentation of this file.

    00001 /************************************************************************************
    00002 TerraLib - a library for developing GIS applications.
    00003 Copyright � 2001-2007 INPE and Tecgraf/PUC-Rio.
    00004
    00005 This code is part of the TerraLib library.
    00006 This library is free software; you can redistribute it and/or
    00007 modify it under the terms of the GNU Lesser General Public
    00008 License as published by the Free Software Foundation; either
    00009 version 2.1 of the License, or (at your option) any later version.
    00010
    00011 You should have received a copy of the GNU Lesser General Public
    00012 License along with this library.
    00013
    00014 The authors reassure the license terms regarding the warranties.
    00015 They specifically disclaim any warranties, including, but not limited to,
    00016 the implied warranties of merchantability and fitness for a particular purpose.
    00017 The library provided hereunder is on an "as is" basis, and the authors have no
    00018 obligation to provide maintenance, support, updates, enhancements, or modifications.
    00019 In no event shall INPE and Tecgraf / PUC-Rio be held liable to any party for direct,
    00020 indirect, special, incidental, or consequential damages arising out of the use
    00021 of this library and its documentation.
    00022 *************************************************************************************/
    00023
    00024 //  include/gra_algo.h
    00025 #ifndef GRAPH_ALGORITHMS_H
    00026 #define GRAPH_ALGORITHMS_H
    00027 #include "dynpq.h"
    00028 #include "graph.h"
    00029 #include <limits>
    00030 #include <iostream>
    00031
    00032 namespace br_stl {
    00033
    00034 template<class GraphType, class EdgeType>
    00035 void Dijkstra(
    00036        GraphType& Gr,
    00037        std::vector<EdgeType>& Dist,
    00038        std::vector<int>& Pred,
    00039        int Start) {
    00040     /* The algorithm proceeds in such a way that the distances are
    00041        estimated and the estimates gradually improved. The distance to
    00042        the starting point is known (0). For all other vertices, the
    00043        worst possible estimate is entered.*/
    00044
    00045     Dist = std::vector<EdgeType>(Gr.size(),
    00046           TeMAXFLOAT); // as good as infinity
    00047     Dist[Start] = (EdgeType)0;
    00048
    00049     /* The predecessor vector too is initialized with `impossible'
    00050        values. Subsequently, a dynamic priority queue is defined and
    00051        initialized with the distance vector: */
    00052
    00053            Pred = std::vector<int>(Gr.size(), -1);
    00054     dynamic_priority_queue<EdgeType> Q(Dist);
    00055
    00056     // In the next step, all vertices are extracted  one by one from
    00057     //  the priority queue, and precisely in the order of the estimated
    00058     // distance towards the starting vertex. Obviously, the starting
    00059     //vertex is dealt with first. No vertex is looked at twice.
    00060
    00061     int u;
    00062     while(!Q.empty()) {
    00063        u = Q.topIndex();   // extract vertex with minimum
    00064        Q.pop();
    00065
    00066        // Now, the distance estimates for all neighboring vertices of
    00067        //  u are updated. If the previous estimate of the distance
    00068         //  between the current neighbor of u and the starting vertex
    00069        //   (Dist[Neighbor]) is worse than the distance between vertex u
    00070         //  and the starting vertex (Dist[u]) plus the distance between
    00071        //   u and the neighboring vertex (dist), the estimate is
    00072         //  improved: this process is called relaxation. In this case,
    00073         //  the path from the starting vertex to the neighbor cannot be
    00074         //  longer than (Dist[u] + dist). In this case, u would have to
    00075         //  be regarded as predecessor of the neighbor.
    00076
    00077         // improve estimates for all neighbors of u
    00078         typename GraphType::Successor::const_iterator
    00079                    I = Gr[u].second.begin();
    00080
    00081         while(I != Gr[u].second.end()) {
    00082             int Neighbor = (*I).first;
    00083             EdgeType dist = (*I).second;
    00084
    00085             // relaxation
    00086             if(Dist[Neighbor] > Dist[u] + dist) {
    00087                // improve estimate
    00088                Q.changeKeyAt(Neighbor, Dist[u] + dist);
    00089                // u is predecessor of the neighbor
    00090                Pred[Neighbor] = u;
    00091             }
    00092             ++I;
    00093         }
    00094     }
    00095            return;
    00096 }
    00097
    00098 template<class GraphType>
    00099 bool topoSort(
    00100        GraphType& G,
    00101        std::vector<int>& Result) {
    00102     assert(G.isDirected());           // let's play this safe!
    00103     int ResCounter = 0;
    00104     Result = std::vector<int>(G.size(), -1);
    00105
    00106     /* The vector Result takes the indices of the correspondingly
    00107        distributed vertices. The counter ResCounter is the position in
    00108        Result where the next entry belongs. */
    00109
    00110     vector<int> PredecessorCount(G.size(), 0);
    00111     int VerticesWithoutSuccessor = 0;
    00112
    00113     /* For each vertex, the vector PredecessorCount counts how many
    00114        predecessors it has. There are vertices without successors,
    00115        whose number is kept in VerticesWithoutSuccessor. Furthermore,
    00116        the algorithm remains stable if the precondition that a graph
    00117        must not have cycles is violated. The variable
    00118        VerticesWithoutSuccessor is used to recognize this situation
    00119        (see below). */
    00120
    00121     /*
    00122            for(size_t iv = 0; iv < G.size(); ++iv) {
    00123         if(G[iv].second.size() > 0) {    // is predecessor
    00124            typename GraphType::Successor::const_iterator I =
    00125                 G[iv].second.begin();
    00126            while(I != G[iv].second.end())
    00127                // update number of predecessors
    00128                ++PredecessorCount[(*I++).first];
    00129         }
    00130         else  { // Vertex is no predecessor, that is, without successor
    00131              // an excessively high number of predecessors is used
    00132              // for later recognition
    00133              PredecessorCount[iv] =   G.size(); // too many!
    00134              ++VerticesWithoutSuccessor;
    00135         }
    00136     }
    00137            */
    00138
    00139     /* The dynamic priority queue is initialized with the vector of
    00140        numbers of predecessors. At the beginning of the queue we find
    00141        those vertices that have no predecessors and therefore are to
    00142        be processed next. Only the vertices which are predecessors
    00143        themselves, that is that have successors are processed. The
    00144        subsequent loop is terminated when the queue only contains
    00145        successor vertices which themselves are not predecessors. Their
    00146        number of predecessors can never be 0 because further above
    00147        they were initialized with too high a value.*/
    00148
    00149     /*
    00150            dynamic_priority_queue<int> Q(PredecessorCount);
    00151
    00152     // process all predecessors
    00153     while(Q.topKey() == 0) {
    00154         // determine vertex with predecessor number 0
    00155        int oV = Q.topIndex();
    00156        Q.pop();
    00157
    00158        Result[ResCounter++] = oV;
    00159
    00160        // In order to ensure that this vertex without predecessors oV
    00161         //  is no longer considered in the next cycle, the number of
    00162        //   predecessors of all its successors is decreased by 1.
    00163
    00164        typename GraphType::Successor::const_iterator
    00165              I = G[oV].second.begin();
    00166        while(I != G[oV].second.end()) {
    00167           // decrease number of predecessors with
    00168           // changeKeyAt()}. Do not change directly!
    00169           int V = (*I).first;
    00170           Q.changeKeyAt(V, PredecessorCount[V] -1);
    00171           ++I;
    00172        }
    00173     }
    00174
    00175     // Now, all vertices without successors are entered. As a
    00176     //   countercheck, the variable VerticesWithoutSuccessor is
    00177     //   decreased. If the queue contains too many vertices, an error
    00178     //   message is displayed.
    00179
    00180     while(!Q.empty()) {
    00181          Result[ResCounter++] = Q.topIndex();
    00182          Q.pop();
    00183          --VerticesWithoutSuccessor;
    00184     }
    00185
    00186     if(VerticesWithoutSuccessor < 0)
    00187        std::cerr << "Error: graph contains a cycle!\n";
    00188     return VerticesWithoutSuccessor == 0;
    00189            */
    00190            return;
    00191 }
    00192
    00193 } // namespace br_stl
    00194 #endif
    00195

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines