1.1 --- a/demo/grid_graph_demo.cc Fri Nov 04 13:53:22 2005 +0000
1.2 +++ b/demo/grid_graph_demo.cc Fri Nov 04 14:48:10 2005 +0000
1.3 @@ -45,7 +45,7 @@
1.4
1.5 for (GridGraph::Node node = stop;
1.6 node != start; node = bfs.predNode(node)) {
1.7 - path[bfs.pred(node)] = true;
1.8 + path[bfs.predEdge(node)] = true;
1.9 }
1.10
1.11 graphToEps(filtered, "grid_graph.eps").scaleToA4().
2.1 --- a/lemon/belmann_ford.h Fri Nov 04 13:53:22 2005 +0000
2.2 +++ b/lemon/belmann_ford.h Fri Nov 04 14:48:10 2005 +0000
2.3 @@ -503,8 +503,8 @@
2.4 if(reached(t)) {
2.5 p.clear();
2.6 typename Path::Builder b(p);
2.7 - for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
2.8 - b.pushFront(pred(t));
2.9 + for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
2.10 + b.pushFront(predEdge(t));
2.11 b.commit();
2.12 return true;
2.13 }
2.14 @@ -529,7 +529,7 @@
2.15 /// \pre \ref run() must be called before using
2.16 /// this function.
2.17 /// \todo predEdge could be a better name.
2.18 - Edge pred(Node v) const { return (*_pred)[v]; }
2.19 + Edge predEdge(Node v) const { return (*_pred)[v]; }
2.20
2.21 /// \brief Returns the 'previous node' of the shortest path tree.
2.22 ///
2.23 @@ -537,7 +537,7 @@
2.24 /// tree, i.e. it returns the last but one node from a shortest path from
2.25 /// the root to \c /v. It is INVALID if \c v is unreachable from the root
2.26 /// or if \c v=s. The shortest path tree used here is equal to the
2.27 - /// shortest path tree used in \ref pred(). \pre \ref run() must be
2.28 + /// shortest path tree used in \ref predEdge(). \pre \ref run() must be
2.29 /// called before using this function.
2.30 Node predNode(Node v) const {
2.31 return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]);
3.1 --- a/lemon/bfs.h Fri Nov 04 13:53:22 2005 +0000
3.2 +++ b/lemon/bfs.h Fri Nov 04 14:48:10 2005 +0000
3.3 @@ -620,8 +620,8 @@
3.4 if(reached(t)) {
3.5 p.clear();
3.6 typename P::Builder b(p);
3.7 - for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
3.8 - b.pushFront(pred(t));
3.9 + for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
3.10 + b.pushFront(predEdge(t));
3.11 b.commit();
3.12 return true;
3.13 }
3.14 @@ -648,7 +648,7 @@
3.15 ///\pre Either \ref run() or \ref start() must be called before using
3.16 ///this function.
3.17 ///\todo predEdge could be a better name.
3.18 - Edge pred(Node v) const { return (*_pred)[v];}
3.19 + Edge predEdge(Node v) const { return (*_pred)[v];}
3.20
3.21 ///Returns the 'previous node' of the shortest path tree.
3.22
3.23 @@ -659,7 +659,7 @@
3.24 ///It is INVALID if \c v is unreachable from the root(s) or
3.25 ///if \c v itself a root.
3.26 ///The shortest path tree used here is equal to the shortest path
3.27 - ///tree used in \ref pred().
3.28 + ///tree used in \ref predEdge().
3.29 ///\pre Either \ref run() or \ref start() must be called before
3.30 ///using this function.
3.31 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
4.1 --- a/lemon/dfs.h Fri Nov 04 13:53:22 2005 +0000
4.2 +++ b/lemon/dfs.h Fri Nov 04 14:48:10 2005 +0000
4.3 @@ -642,8 +642,8 @@
4.4 if(reached(t)) {
4.5 p.clear();
4.6 typename P::Builder b(p);
4.7 - for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
4.8 - b.pushFront(pred(t));
4.9 + for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
4.10 + b.pushFront(predEdge(t));
4.11 b.commit();
4.12 return true;
4.13 }
4.14 @@ -670,7 +670,7 @@
4.15 ///\pre Either \ref run() or \ref start() must be called before using
4.16 ///this function.
4.17 ///\todo predEdge could be a better name.
4.18 - Edge pred(Node v) const { return (*_pred)[v];}
4.19 + Edge predEdge(Node v) const { return (*_pred)[v];}
4.20
4.21 ///Returns the 'previous node' of the %DFS tree.
4.22
4.23 @@ -681,7 +681,7 @@
4.24 ///It is INVALID if \c v is unreachable from the root(s) or
4.25 ///if \c v itself a root.
4.26 ///The %DFS tree used here is equal to the %DFS
4.27 - ///tree used in \ref pred().
4.28 + ///tree used in \ref predEdge().
4.29 ///\pre Either \ref run() or \ref start() must be called before
4.30 ///using this function.
4.31 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
5.1 --- a/lemon/dijkstra.h Fri Nov 04 13:53:22 2005 +0000
5.2 +++ b/lemon/dijkstra.h Fri Nov 04 14:48:10 2005 +0000
5.3 @@ -733,8 +733,8 @@
5.4 if(reached(t)) {
5.5 p.clear();
5.6 typename P::Builder b(p);
5.7 - for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
5.8 - b.pushFront(pred(t));
5.9 + for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
5.10 + b.pushFront(predEdge(t));
5.11 b.commit();
5.12 return true;
5.13 }
5.14 @@ -759,7 +759,7 @@
5.15 ///\ref predNode(). \pre \ref run() must be called before using
5.16 ///this function.
5.17 ///\todo predEdge could be a better name.
5.18 - Edge pred(Node v) const { return (*_pred)[v]; }
5.19 + Edge predEdge(Node v) const { return (*_pred)[v]; }
5.20
5.21 ///Returns the 'previous node' of the shortest path tree.
5.22
5.23 @@ -767,7 +767,7 @@
5.24 ///i.e. it returns the last but one node from a shortest path from the
5.25 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
5.26 ///\c v=s. The shortest path tree used here is equal to the shortest path
5.27 - ///tree used in \ref pred(). \pre \ref run() must be called before
5.28 + ///tree used in \ref predEdge(). \pre \ref run() must be called before
5.29 ///using this function.
5.30 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
5.31 G->source((*_pred)[v]); }
6.1 --- a/lemon/floyd_warshall.h Fri Nov 04 13:53:22 2005 +0000
6.2 +++ b/lemon/floyd_warshall.h Fri Nov 04 14:48:10 2005 +0000
6.3 @@ -488,9 +488,9 @@
6.4 if (connected(source, target)) {
6.5 p.clear();
6.6 typename Path::Builder b(target);
6.7 - for(b.setStartNode(target); pred(source, target) != INVALID;
6.8 + for(b.setStartNode(target); predEdge(source, target) != INVALID;
6.9 target = predNode(target)) {
6.10 - b.pushFront(pred(source, target));
6.11 + b.pushFront(predEdge(source, target));
6.12 }
6.13 b.commit();
6.14 return true;
6.15 @@ -518,7 +518,7 @@
6.16 /// shortest path tree used in \ref predNode().
6.17 /// \pre \ref run() must be called before using this function.
6.18 /// \todo predEdge could be a better name.
6.19 - Edge pred(Node root, Node node) const {
6.20 + Edge predEdge(Node root, Node node) const {
6.21 return (*_pred)(root, node);
6.22 }
6.23
6.24 @@ -529,7 +529,7 @@
6.25 /// one node from a shortest path from the \c root to \c node. It is
6.26 /// INVALID if \c node is unreachable from the root or if \c node=root.
6.27 /// The shortest path tree used here is equal to the
6.28 - /// shortest path tree used in \ref pred().
6.29 + /// shortest path tree used in \ref predEdge().
6.30 /// \pre \ref run() must be called before using this function.
6.31 Node predNode(Node root, Node node) const {
6.32 return (*_pred)(root, node) == INVALID ?
7.1 --- a/lemon/johnson.h Fri Nov 04 13:53:22 2005 +0000
7.2 +++ b/lemon/johnson.h Fri Nov 04 14:48:10 2005 +0000
7.3 @@ -509,7 +509,7 @@
7.4 if (dijkstra.reached(jt)) {
7.5 _dist->set(it, jt, dijkstra.dist(jt) +
7.6 potential[jt] - potential[it]);
7.7 - _pred->set(it, jt, dijkstra.pred(jt));
7.8 + _pred->set(it, jt, dijkstra.predEdge(jt));
7.9 } else {
7.10 _dist->set(it, jt, OperationTraits::infinity());
7.11 _pred->set(it, jt, INVALID);
7.12 @@ -634,9 +634,9 @@
7.13 if (connected(source, target)) {
7.14 p.clear();
7.15 typename Path::Builder b(target);
7.16 - for(b.setStartNode(target); pred(source, target) != INVALID;
7.17 + for(b.setStartNode(target); predEdge(source, target) != INVALID;
7.18 target = predNode(target)) {
7.19 - b.pushFront(pred(source, target));
7.20 + b.pushFront(predEdge(source, target));
7.21 }
7.22 b.commit();
7.23 return true;
7.24 @@ -664,7 +664,7 @@
7.25 /// shortest path tree used in \ref predNode().
7.26 /// \pre \ref run() must be called before using this function.
7.27 /// \todo predEdge could be a better name.
7.28 - Edge pred(Node root, Node node) const {
7.29 + Edge predEdge(Node root, Node node) const {
7.30 return (*_pred)(root, node);
7.31 }
7.32
7.33 @@ -675,7 +675,7 @@
7.34 /// one node from a shortest path from the \c root to \c node. It is
7.35 /// INVALID if \c node is unreachable from the root or if \c node=root.
7.36 /// The shortest path tree used here is equal to the
7.37 - /// shortest path tree used in \ref pred().
7.38 + /// shortest path tree used in \ref predEdge().
7.39 /// \pre \ref run() must be called before using this function.
7.40 Node predNode(Node root, Node node) const {
7.41 return (*_pred)(root, node) == INVALID ?
8.1 --- a/lemon/min_cost_flow.h Fri Nov 04 13:53:22 2005 +0000
8.2 +++ b/lemon/min_cost_flow.h Fri Nov 04 14:48:10 2005 +0000
8.3 @@ -151,7 +151,7 @@
8.4 Node n=t;
8.5 ResGraphEdge e;
8.6 while (n!=s){
8.7 - e = dijkstra.pred(n);
8.8 + e = dijkstra.predEdge(n);
8.9 n = dijkstra.predNode(n);
8.10 res_graph.augment(e,1);
8.11 //Let's update the total length
9.1 --- a/lemon/topology.h Fri Nov 04 13:53:22 2005 +0000
9.2 +++ b/lemon/topology.h Fri Nov 04 14:48:10 2005 +0000
9.3 @@ -110,12 +110,16 @@
9.4 ///
9.5 /// Find the connected components of an undirected graph.
9.6 ///
9.7 + /// \image html connected_components.png
9.8 + /// \image latex connected_components.eps "Connected components" width=\textwidth
9.9 + ///
9.10 /// \param g The graph. In must be undirected.
9.11 /// \retval comp A writable node map. The values will be set from 0 to
9.12 /// the number of the connected components minus one. Each values of the map
9.13 /// will be set exactly once, the values of a certain component will be
9.14 /// set continuously.
9.15 /// \return The number of components
9.16 + ///
9.17 template <class UndirGraph, class NodeMap>
9.18 int connectedComponents(const UndirGraph &graph, NodeMap &compMap) {
9.19 checkConcept<concept::UndirGraph, UndirGraph>();
9.20 @@ -348,12 +352,16 @@
9.21 /// relation on the nodes of the graph. Two nodes are in relationship
9.22 /// when there are directed paths between them in both direction.
9.23 ///
9.24 + /// \image html strongly_connected_components.png
9.25 + /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
9.26 + ///
9.27 /// \param g The graph.
9.28 /// \retval comp A writable node map. The values will be set from 0 to
9.29 /// the number of the strongly connected components minus one. Each values
9.30 /// of the map will be set exactly once, the values of a certain component
9.31 /// will be set continuously.
9.32 /// \return The number of components
9.33 + ///
9.34 template <typename Graph, typename NodeMap>
9.35 int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) {
9.36 checkConcept<concept::StaticGraph, Graph>();
9.37 @@ -746,12 +754,16 @@
9.38 /// relation on the undirected edges. Two undirected edge are in relationship
9.39 /// when they are on same circle.
9.40 ///
9.41 + /// \image html node_biconnected_components.png
9.42 + /// \image latex node_biconnected_components.eps "Node biconnected components" width=\textwidth
9.43 + ///
9.44 /// \param graph The graph.
9.45 /// \retval comp A writable undir edge map. The values will be set from 0 to
9.46 /// the number of the biconnected components minus one. Each values
9.47 /// of the map will be set exactly once, the values of a certain component
9.48 /// will be set continuously.
9.49 /// \return The number of components.
9.50 + ///
9.51 template <typename UndirGraph, typename UndirEdgeMap>
9.52 int nodeBiconnectedComponents(const UndirGraph& graph,
9.53 UndirEdgeMap& compMap) {
9.54 @@ -1069,12 +1081,16 @@
9.55 /// relation on the nodes. Two nodes are in relationship when they are
9.56 /// connected at least two edge-disjoint paths.
9.57 ///
9.58 + /// \image html edge_biconnected_components.png
9.59 + /// \image latex edge_biconnected_components.eps "Edge biconnected components" width=\textwidth
9.60 + ///
9.61 /// \param graph The graph.
9.62 /// \retval comp A writable node map. The values will be set from 0 to
9.63 /// the number of the biconnected components minus one. Each values
9.64 /// of the map will be set exactly once, the values of a certain component
9.65 /// will be set continuously.
9.66 /// \return The number of components.
9.67 + ///
9.68 template <typename UndirGraph, typename NodeMap>
9.69 int edgeBiconnectedComponents(const UndirGraph& graph, NodeMap& compMap) {
9.70 checkConcept<concept::UndirGraph, UndirGraph>();
9.71 @@ -1322,7 +1338,7 @@
9.72 Node source = graph.source(edge);
9.73 Node target = graph.target(edge);
9.74 if (dfs.reached(target) &&
9.75 - dfs.pred(source) != graph.oppositeEdge(edge)) {
9.76 + dfs.predEdge(source) != graph.oppositeEdge(edge)) {
9.77 return false;
9.78 }
9.79 dfs.processNextEdge();
9.80 @@ -1353,7 +1369,7 @@
9.81 Node source = graph.source(edge);
9.82 Node target = graph.target(edge);
9.83 if (dfs.reached(target) &&
9.84 - dfs.pred(source) != graph.oppositeEdge(edge)) {
9.85 + dfs.predEdge(source) != graph.oppositeEdge(edge)) {
9.86 return false;
9.87 }
9.88 dfs.processNextEdge();
10.1 --- a/test/all_pairs_shortest_path_test.cc Fri Nov 04 13:53:22 2005 +0000
10.2 +++ b/test/all_pairs_shortest_path_test.cc Fri Nov 04 14:48:10 2005 +0000
10.3 @@ -88,15 +88,15 @@
10.4 if (it != jt) {
10.5 check(johnson.dist(it, jt) ==
10.6 johnson.dist(it, johnson.predNode(it, jt)) +
10.7 - length[johnson.pred(it, jt)],
10.8 + length[johnson.predEdge(it, jt)],
10.9 "Wrong edge in all pairs shortest path");
10.10 check(fibJohnson.dist(it, jt) ==
10.11 fibJohnson.dist(it, fibJohnson.predNode(it, jt)) +
10.12 - length[fibJohnson.pred(it, jt)],
10.13 + length[fibJohnson.predEdge(it, jt)],
10.14 "Wrong edge in all pairs shortest path");
10.15 check(floyd.dist(it, jt) ==
10.16 floyd.dist(it, floyd.predNode(it, jt)) +
10.17 - length[floyd.pred(it, jt)],
10.18 + length[floyd.predEdge(it, jt)],
10.19 "Wrong edge in all pairs shortest path");
10.20 }
10.21 }
11.1 --- a/test/bfs_test.cc Fri Nov 04 13:53:22 2005 +0000
11.2 +++ b/test/bfs_test.cc Fri Nov 04 14:48:10 2005 +0000
11.3 @@ -50,7 +50,7 @@
11.4 bfs_test.run(n);
11.5
11.6 l = bfs_test.dist(n);
11.7 - e = bfs_test.pred(n);
11.8 + e = bfs_test.predEdge(n);
11.9 n = bfs_test.predNode(n);
11.10 d = bfs_test.distMap();
11.11 p = bfs_test.predMap();
11.12 @@ -121,8 +121,8 @@
11.13
11.14 for(NodeIt v(G); v==INVALID; ++v) {
11.15 check(bfs_test.reached(v),"Each node should be reached.");
11.16 - if ( bfs_test.pred(v)!=INVALID ) {
11.17 - Edge e=bfs_test.pred(v);
11.18 + if ( bfs_test.predEdge(v)!=INVALID ) {
11.19 + Edge e=bfs_test.predEdge(v);
11.20 Node u=G.source(e);
11.21 check(u==bfs_test.predNode(v),"Wrong tree.");
11.22 check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
12.1 --- a/test/dfs_test.cc Fri Nov 04 13:53:22 2005 +0000
12.2 +++ b/test/dfs_test.cc Fri Nov 04 14:48:10 2005 +0000
12.3 @@ -50,7 +50,7 @@
12.4 dfs_test.run(n);
12.5
12.6 l = dfs_test.dist(n);
12.7 - e = dfs_test.pred(n);
12.8 + e = dfs_test.predEdge(n);
12.9 n = dfs_test.predNode(n);
12.10 d = dfs_test.distMap();
12.11 p = dfs_test.predMap();
12.12 @@ -111,8 +111,8 @@
12.13
12.14 for(NodeIt v(G); v!=INVALID; ++v) {
12.15 check(dfs_test.reached(v),"Each node should be reached.");
12.16 - if ( dfs_test.pred(v)!=INVALID ) {
12.17 - Edge e=dfs_test.pred(v);
12.18 + if ( dfs_test.predEdge(v)!=INVALID ) {
12.19 + Edge e=dfs_test.predEdge(v);
12.20 Node u=G.source(e);
12.21 check(u==dfs_test.predNode(v),"Wrong tree.");
12.22 check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
13.1 --- a/test/dijkstra_test.cc Fri Nov 04 13:53:22 2005 +0000
13.2 +++ b/test/dijkstra_test.cc Fri Nov 04 14:48:10 2005 +0000
13.3 @@ -54,7 +54,7 @@
13.4 dijkstra_test.run(n);
13.5
13.6 l = dijkstra_test.dist(n);
13.7 - e = dijkstra_test.pred(n);
13.8 + e = dijkstra_test.predEdge(n);
13.9 n = dijkstra_test.predNode(n);
13.10 d = dijkstra_test.distMap();
13.11 p = dijkstra_test.predMap();
13.12 @@ -135,8 +135,8 @@
13.13 ///\bug This works only for integer lengths
13.14 for(NodeIt v(G); v!=INVALID; ++v){
13.15 check(dijkstra_test.reached(v),"Each node should be reached.");
13.16 - if ( dijkstra_test.pred(v)!=INVALID ) {
13.17 - Edge e=dijkstra_test.pred(v);
13.18 + if ( dijkstra_test.predEdge(v)!=INVALID ) {
13.19 + Edge e=dijkstra_test.predEdge(v);
13.20 Node u=G.source(e);
13.21 check(u==dijkstra_test.predNode(v),"Wrong tree.");
13.22 check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
14.1 --- a/test/heap_test.h Fri Nov 04 13:53:22 2005 +0000
14.2 +++ b/test/heap_test.h Fri Nov 04 14:48:10 2005 +0000
14.3 @@ -93,8 +93,8 @@
14.4 }
14.5
14.6 for(NodeIt v(graph); v!=INVALID; ++v) {
14.7 - if ( dijkstra.reached(v) && dijkstra.pred(v) != INVALID ) {
14.8 - Edge e=dijkstra.pred(v);
14.9 + if ( dijkstra.reached(v) && dijkstra.predEdge(v) != INVALID ) {
14.10 + Edge e=dijkstra.predEdge(v);
14.11 Node u=graph.source(e);
14.12 check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],
14.13 "Error in a shortest path tree edge!");