1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195

/************************************************************************************
TerraLib  a library for developing GIS applications.
Copyright � 20012007 INPE and Tecgraf/PUCRio.
This code is part of the TerraLib library.
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
You should have received a copy of the GNU Lesser General Public
License along with this library.
The authors reassure the license terms regarding the warranties.
They specifically disclaim any warranties, including, but not limited to,
the implied warranties of merchantability and fitness for a particular purpose.
The library provided hereunder is on an "as is" basis, and the authors have no
obligation to provide maintenance, support, updates, enhancements, or modifications.
In no event shall INPE and Tecgraf / PUCRio be held liable to any party for direct,
indirect, special, incidental, or consequential damages arising out of the use
of this library and its documentation.
*************************************************************************************/
// include/gra_algo.h
#ifndef GRAPH_ALGORITHMS_H
#define GRAPH_ALGORITHMS_H
#include <dynpq.h>
#include <graph.h>
#include <limits>
#include <iostream>
namespace br_stl {
template<class GraphType, class EdgeType>
void Dijkstra(
GraphType& Gr,
std::vector<EdgeType>& Dist,
std::vector<int>& Pred,
int Start) {
/* The algorithm proceeds in such a way that the distances are
estimated and the estimates gradually improved. The distance to
the starting point is known (0). For all other vertices, the
worst possible estimate is entered.*/
Dist = std::vector<EdgeType>(Gr.size(),
TeMAXFLOAT); // as good as infinity
Dist[Start] = (EdgeType)0;
/* The predecessor vector too is initialized with `impossible'
values. Subsequently, a dynamic priority queue is defined and
initialized with the distance vector: */
Pred = std::vector<int>(Gr.size(), 1);
dynamic_priority_queue<EdgeType> Q(Dist);
// In the next step, all vertices are extracted one by one from
// the priority queue, and precisely in the order of the estimated
// distance towards the starting vertex. Obviously, the starting
//vertex is dealt with first. No vertex is looked at twice.
int u;
while(!Q.empty()) {
u = Q.topIndex(); // extract vertex with minimum
Q.pop();
// Now, the distance estimates for all neighboring vertices of
// u are updated. If the previous estimate of the distance
// between the current neighbor of u and the starting vertex
// (Dist[Neighbor]) is worse than the distance between vertex u
// and the starting vertex (Dist[u]) plus the distance between
// u and the neighboring vertex (dist), the estimate is
// improved: this process is called relaxation. In this case,
// the path from the starting vertex to the neighbor cannot be
// longer than (Dist[u] + dist). In this case, u would have to
// be regarded as predecessor of the neighbor.
// improve estimates for all neighbors of u
typename GraphType::Successor::const_iterator
I = Gr[u].second.begin();
while(I != Gr[u].second.end()) {
int Neighbor = (*I).first;
EdgeType dist = (*I).second;
// relaxation
if(Dist[Neighbor] > Dist[u] + dist) {
// improve estimate
Q.changeKeyAt(Neighbor, Dist[u] + dist);
// u is predecessor of the neighbor
Pred[Neighbor] = u;
}
++I;
}
}
return;
}
template<class GraphType>
bool topoSort(
GraphType& G,
std::vector<int>& Result) {
assert(G.isDirected()); // let's play this safe!
int ResCounter = 0;
Result = std::vector<int>(G.size(), 1);
/* The vector Result takes the indices of the correspondingly
distributed vertices. The counter ResCounter is the position in
Result where the next entry belongs. */
vector<int> PredecessorCount(G.size(), 0);
int VerticesWithoutSuccessor = 0;
/* For each vertex, the vector PredecessorCount counts how many
predecessors it has. There are vertices without successors,
whose number is kept in VerticesWithoutSuccessor. Furthermore,
the algorithm remains stable if the precondition that a graph
must not have cycles is violated. The variable
VerticesWithoutSuccessor is used to recognize this situation
(see below). */
/*
for(size_t iv = 0; iv < G.size(); ++iv) {
if(G[iv].second.size() > 0) { // is predecessor
typename GraphType::Successor::const_iterator I =
G[iv].second.begin();
while(I != G[iv].second.end())
// update number of predecessors
++PredecessorCount[(*I++).first];
}
else { // Vertex is no predecessor, that is, without successor
// an excessively high number of predecessors is used
// for later recognition
PredecessorCount[iv] = G.size(); // too many!
++VerticesWithoutSuccessor;
}
}
*/
/* The dynamic priority queue is initialized with the vector of
numbers of predecessors. At the beginning of the queue we find
those vertices that have no predecessors and therefore are to
be processed next. Only the vertices which are predecessors
themselves, that is that have successors are processed. The
subsequent loop is terminated when the queue only contains
successor vertices which themselves are not predecessors. Their
number of predecessors can never be 0 because further above
they were initialized with too high a value.*/
/*
dynamic_priority_queue<int> Q(PredecessorCount);
// process all predecessors
while(Q.topKey() == 0) {
// determine vertex with predecessor number 0
int oV = Q.topIndex();
Q.pop();
Result[ResCounter++] = oV;
// In order to ensure that this vertex without predecessors oV
// is no longer considered in the next cycle, the number of
// predecessors of all its successors is decreased by 1.
typename GraphType::Successor::const_iterator
I = G[oV].second.begin();
while(I != G[oV].second.end()) {
// decrease number of predecessors with
// changeKeyAt()}. Do not change directly!
int V = (*I).first;
Q.changeKeyAt(V, PredecessorCount[V] 1);
++I;
}
}
// Now, all vertices without successors are entered. As a
// countercheck, the variable VerticesWithoutSuccessor is
// decreased. If the queue contains too many vertices, an error
// message is displayed.
while(!Q.empty()) {
Result[ResCounter++] = Q.topIndex();
Q.pop();
VerticesWithoutSuccessor;
}
if(VerticesWithoutSuccessor < 0)
std::cerr << "Error: graph contains a cycle!\n";
return VerticesWithoutSuccessor == 0;
*/
return 1;
}
} // namespace br_stl
#endif
