# HG changeset patch # User deba # Date 1131115690 0 # Node ID 49045f2d28d42a2198f9460151c985a512ab6859 # Parent 3915867b6975357bd7a900a433db75884502c39a pred => predEdge rename diff -r 3915867b6975 -r 49045f2d28d4 demo/grid_graph_demo.cc --- a/demo/grid_graph_demo.cc Fri Nov 04 13:53:22 2005 +0000 +++ b/demo/grid_graph_demo.cc Fri Nov 04 14:48:10 2005 +0000 @@ -45,7 +45,7 @@ for (GridGraph::Node node = stop; node != start; node = bfs.predNode(node)) { - path[bfs.pred(node)] = true; + path[bfs.predEdge(node)] = true; } graphToEps(filtered, "grid_graph.eps").scaleToA4(). diff -r 3915867b6975 -r 49045f2d28d4 lemon/belmann_ford.h --- a/lemon/belmann_ford.h Fri Nov 04 13:53:22 2005 +0000 +++ b/lemon/belmann_ford.h Fri Nov 04 14:48:10 2005 +0000 @@ -503,8 +503,8 @@ if(reached(t)) { p.clear(); typename Path::Builder b(p); - for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t)) - b.pushFront(pred(t)); + for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t)) + b.pushFront(predEdge(t)); b.commit(); return true; } @@ -529,7 +529,7 @@ /// \pre \ref run() must be called before using /// this function. /// \todo predEdge could be a better name. - Edge pred(Node v) const { return (*_pred)[v]; } + Edge predEdge(Node v) const { return (*_pred)[v]; } /// \brief Returns the 'previous node' of the shortest path tree. /// @@ -537,7 +537,7 @@ /// tree, i.e. it returns the last but one node from a shortest path from /// the root to \c /v. It is INVALID if \c v is unreachable from the root /// or if \c v=s. The shortest path tree used here is equal to the - /// shortest path tree used in \ref pred(). \pre \ref run() must be + /// shortest path tree used in \ref predEdge(). \pre \ref run() must be /// called before using this function. Node predNode(Node v) const { return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]); diff -r 3915867b6975 -r 49045f2d28d4 lemon/bfs.h --- a/lemon/bfs.h Fri Nov 04 13:53:22 2005 +0000 +++ b/lemon/bfs.h Fri Nov 04 14:48:10 2005 +0000 @@ -620,8 +620,8 @@ if(reached(t)) { p.clear(); typename P::Builder b(p); - for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t)) - b.pushFront(pred(t)); + for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t)) + b.pushFront(predEdge(t)); b.commit(); return true; } @@ -648,7 +648,7 @@ ///\pre Either \ref run() or \ref start() must be called before using ///this function. ///\todo predEdge could be a better name. - Edge pred(Node v) const { return (*_pred)[v];} + Edge predEdge(Node v) const { return (*_pred)[v];} ///Returns the 'previous node' of the shortest path tree. @@ -659,7 +659,7 @@ ///It is INVALID if \c v is unreachable from the root(s) or ///if \c v itself a root. ///The shortest path tree used here is equal to the shortest path - ///tree used in \ref pred(). + ///tree used in \ref predEdge(). ///\pre Either \ref run() or \ref start() must be called before ///using this function. Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: diff -r 3915867b6975 -r 49045f2d28d4 lemon/dfs.h --- a/lemon/dfs.h Fri Nov 04 13:53:22 2005 +0000 +++ b/lemon/dfs.h Fri Nov 04 14:48:10 2005 +0000 @@ -642,8 +642,8 @@ if(reached(t)) { p.clear(); typename P::Builder b(p); - for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t)) - b.pushFront(pred(t)); + for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t)) + b.pushFront(predEdge(t)); b.commit(); return true; } @@ -670,7 +670,7 @@ ///\pre Either \ref run() or \ref start() must be called before using ///this function. ///\todo predEdge could be a better name. - Edge pred(Node v) const { return (*_pred)[v];} + Edge predEdge(Node v) const { return (*_pred)[v];} ///Returns the 'previous node' of the %DFS tree. @@ -681,7 +681,7 @@ ///It is INVALID if \c v is unreachable from the root(s) or ///if \c v itself a root. ///The %DFS tree used here is equal to the %DFS - ///tree used in \ref pred(). + ///tree used in \ref predEdge(). ///\pre Either \ref run() or \ref start() must be called before ///using this function. Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: diff -r 3915867b6975 -r 49045f2d28d4 lemon/dijkstra.h --- a/lemon/dijkstra.h Fri Nov 04 13:53:22 2005 +0000 +++ b/lemon/dijkstra.h Fri Nov 04 14:48:10 2005 +0000 @@ -733,8 +733,8 @@ if(reached(t)) { p.clear(); typename P::Builder b(p); - for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t)) - b.pushFront(pred(t)); + for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t)) + b.pushFront(predEdge(t)); b.commit(); return true; } @@ -759,7 +759,7 @@ ///\ref predNode(). \pre \ref run() must be called before using ///this function. ///\todo predEdge could be a better name. - Edge pred(Node v) const { return (*_pred)[v]; } + Edge predEdge(Node v) const { return (*_pred)[v]; } ///Returns the 'previous node' of the shortest path tree. @@ -767,7 +767,7 @@ ///i.e. it returns the last but one node from a shortest path from the ///root to \c /v. It is INVALID if \c v is unreachable from the root or if ///\c v=s. The shortest path tree used here is equal to the shortest path - ///tree used in \ref pred(). \pre \ref run() must be called before + ///tree used in \ref predEdge(). \pre \ref run() must be called before ///using this function. Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: G->source((*_pred)[v]); } diff -r 3915867b6975 -r 49045f2d28d4 lemon/floyd_warshall.h --- a/lemon/floyd_warshall.h Fri Nov 04 13:53:22 2005 +0000 +++ b/lemon/floyd_warshall.h Fri Nov 04 14:48:10 2005 +0000 @@ -488,9 +488,9 @@ if (connected(source, target)) { p.clear(); typename Path::Builder b(target); - for(b.setStartNode(target); pred(source, target) != INVALID; + for(b.setStartNode(target); predEdge(source, target) != INVALID; target = predNode(target)) { - b.pushFront(pred(source, target)); + b.pushFront(predEdge(source, target)); } b.commit(); return true; @@ -518,7 +518,7 @@ /// shortest path tree used in \ref predNode(). /// \pre \ref run() must be called before using this function. /// \todo predEdge could be a better name. - Edge pred(Node root, Node node) const { + Edge predEdge(Node root, Node node) const { return (*_pred)(root, node); } @@ -529,7 +529,7 @@ /// one node from a shortest path from the \c root to \c node. It is /// INVALID if \c node is unreachable from the root or if \c node=root. /// The shortest path tree used here is equal to the - /// shortest path tree used in \ref pred(). + /// shortest path tree used in \ref predEdge(). /// \pre \ref run() must be called before using this function. Node predNode(Node root, Node node) const { return (*_pred)(root, node) == INVALID ? diff -r 3915867b6975 -r 49045f2d28d4 lemon/johnson.h --- a/lemon/johnson.h Fri Nov 04 13:53:22 2005 +0000 +++ b/lemon/johnson.h Fri Nov 04 14:48:10 2005 +0000 @@ -509,7 +509,7 @@ if (dijkstra.reached(jt)) { _dist->set(it, jt, dijkstra.dist(jt) + potential[jt] - potential[it]); - _pred->set(it, jt, dijkstra.pred(jt)); + _pred->set(it, jt, dijkstra.predEdge(jt)); } else { _dist->set(it, jt, OperationTraits::infinity()); _pred->set(it, jt, INVALID); @@ -634,9 +634,9 @@ if (connected(source, target)) { p.clear(); typename Path::Builder b(target); - for(b.setStartNode(target); pred(source, target) != INVALID; + for(b.setStartNode(target); predEdge(source, target) != INVALID; target = predNode(target)) { - b.pushFront(pred(source, target)); + b.pushFront(predEdge(source, target)); } b.commit(); return true; @@ -664,7 +664,7 @@ /// shortest path tree used in \ref predNode(). /// \pre \ref run() must be called before using this function. /// \todo predEdge could be a better name. - Edge pred(Node root, Node node) const { + Edge predEdge(Node root, Node node) const { return (*_pred)(root, node); } @@ -675,7 +675,7 @@ /// one node from a shortest path from the \c root to \c node. It is /// INVALID if \c node is unreachable from the root or if \c node=root. /// The shortest path tree used here is equal to the - /// shortest path tree used in \ref pred(). + /// shortest path tree used in \ref predEdge(). /// \pre \ref run() must be called before using this function. Node predNode(Node root, Node node) const { return (*_pred)(root, node) == INVALID ? diff -r 3915867b6975 -r 49045f2d28d4 lemon/min_cost_flow.h --- a/lemon/min_cost_flow.h Fri Nov 04 13:53:22 2005 +0000 +++ b/lemon/min_cost_flow.h Fri Nov 04 14:48:10 2005 +0000 @@ -151,7 +151,7 @@ Node n=t; ResGraphEdge e; while (n!=s){ - e = dijkstra.pred(n); + e = dijkstra.predEdge(n); n = dijkstra.predNode(n); res_graph.augment(e,1); //Let's update the total length diff -r 3915867b6975 -r 49045f2d28d4 lemon/topology.h --- a/lemon/topology.h Fri Nov 04 13:53:22 2005 +0000 +++ b/lemon/topology.h Fri Nov 04 14:48:10 2005 +0000 @@ -110,12 +110,16 @@ /// /// Find the connected components of an undirected graph. /// + /// \image html connected_components.png + /// \image latex connected_components.eps "Connected components" width=\textwidth + /// /// \param g The graph. In must be undirected. /// \retval comp A writable node map. The values will be set from 0 to /// the number of the connected components minus one. Each values of the map /// will be set exactly once, the values of a certain component will be /// set continuously. /// \return The number of components + /// template int connectedComponents(const UndirGraph &graph, NodeMap &compMap) { checkConcept(); @@ -348,12 +352,16 @@ /// relation on the nodes of the graph. Two nodes are in relationship /// when there are directed paths between them in both direction. /// + /// \image html strongly_connected_components.png + /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth + /// /// \param g The graph. /// \retval comp A writable node map. The values will be set from 0 to /// the number of the strongly connected components minus one. Each values /// of the map will be set exactly once, the values of a certain component /// will be set continuously. /// \return The number of components + /// template int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) { checkConcept(); @@ -746,12 +754,16 @@ /// relation on the undirected edges. Two undirected edge are in relationship /// when they are on same circle. /// + /// \image html node_biconnected_components.png + /// \image latex node_biconnected_components.eps "Node biconnected components" width=\textwidth + /// /// \param graph The graph. /// \retval comp A writable undir edge map. The values will be set from 0 to /// the number of the biconnected components minus one. Each values /// of the map will be set exactly once, the values of a certain component /// will be set continuously. /// \return The number of components. + /// template int nodeBiconnectedComponents(const UndirGraph& graph, UndirEdgeMap& compMap) { @@ -1069,12 +1081,16 @@ /// relation on the nodes. Two nodes are in relationship when they are /// connected at least two edge-disjoint paths. /// + /// \image html edge_biconnected_components.png + /// \image latex edge_biconnected_components.eps "Edge biconnected components" width=\textwidth + /// /// \param graph The graph. /// \retval comp A writable node map. The values will be set from 0 to /// the number of the biconnected components minus one. Each values /// of the map will be set exactly once, the values of a certain component /// will be set continuously. /// \return The number of components. + /// template int edgeBiconnectedComponents(const UndirGraph& graph, NodeMap& compMap) { checkConcept(); @@ -1322,7 +1338,7 @@ Node source = graph.source(edge); Node target = graph.target(edge); if (dfs.reached(target) && - dfs.pred(source) != graph.oppositeEdge(edge)) { + dfs.predEdge(source) != graph.oppositeEdge(edge)) { return false; } dfs.processNextEdge(); @@ -1353,7 +1369,7 @@ Node source = graph.source(edge); Node target = graph.target(edge); if (dfs.reached(target) && - dfs.pred(source) != graph.oppositeEdge(edge)) { + dfs.predEdge(source) != graph.oppositeEdge(edge)) { return false; } dfs.processNextEdge(); diff -r 3915867b6975 -r 49045f2d28d4 test/all_pairs_shortest_path_test.cc --- a/test/all_pairs_shortest_path_test.cc Fri Nov 04 13:53:22 2005 +0000 +++ b/test/all_pairs_shortest_path_test.cc Fri Nov 04 14:48:10 2005 +0000 @@ -88,15 +88,15 @@ if (it != jt) { check(johnson.dist(it, jt) == johnson.dist(it, johnson.predNode(it, jt)) + - length[johnson.pred(it, jt)], + length[johnson.predEdge(it, jt)], "Wrong edge in all pairs shortest path"); check(fibJohnson.dist(it, jt) == fibJohnson.dist(it, fibJohnson.predNode(it, jt)) + - length[fibJohnson.pred(it, jt)], + length[fibJohnson.predEdge(it, jt)], "Wrong edge in all pairs shortest path"); check(floyd.dist(it, jt) == floyd.dist(it, floyd.predNode(it, jt)) + - length[floyd.pred(it, jt)], + length[floyd.predEdge(it, jt)], "Wrong edge in all pairs shortest path"); } } diff -r 3915867b6975 -r 49045f2d28d4 test/bfs_test.cc --- a/test/bfs_test.cc Fri Nov 04 13:53:22 2005 +0000 +++ b/test/bfs_test.cc Fri Nov 04 14:48:10 2005 +0000 @@ -50,7 +50,7 @@ bfs_test.run(n); l = bfs_test.dist(n); - e = bfs_test.pred(n); + e = bfs_test.predEdge(n); n = bfs_test.predNode(n); d = bfs_test.distMap(); p = bfs_test.predMap(); @@ -121,8 +121,8 @@ for(NodeIt v(G); v==INVALID; ++v) { check(bfs_test.reached(v),"Each node should be reached."); - if ( bfs_test.pred(v)!=INVALID ) { - Edge e=bfs_test.pred(v); + if ( bfs_test.predEdge(v)!=INVALID ) { + Edge e=bfs_test.predEdge(v); Node u=G.source(e); check(u==bfs_test.predNode(v),"Wrong tree."); check(bfs_test.dist(v) - bfs_test.dist(u) == 1, diff -r 3915867b6975 -r 49045f2d28d4 test/dfs_test.cc --- a/test/dfs_test.cc Fri Nov 04 13:53:22 2005 +0000 +++ b/test/dfs_test.cc Fri Nov 04 14:48:10 2005 +0000 @@ -50,7 +50,7 @@ dfs_test.run(n); l = dfs_test.dist(n); - e = dfs_test.pred(n); + e = dfs_test.predEdge(n); n = dfs_test.predNode(n); d = dfs_test.distMap(); p = dfs_test.predMap(); @@ -111,8 +111,8 @@ for(NodeIt v(G); v!=INVALID; ++v) { check(dfs_test.reached(v),"Each node should be reached."); - if ( dfs_test.pred(v)!=INVALID ) { - Edge e=dfs_test.pred(v); + if ( dfs_test.predEdge(v)!=INVALID ) { + Edge e=dfs_test.predEdge(v); Node u=G.source(e); check(u==dfs_test.predNode(v),"Wrong tree."); check(dfs_test.dist(v) - dfs_test.dist(u) == 1, diff -r 3915867b6975 -r 49045f2d28d4 test/dijkstra_test.cc --- a/test/dijkstra_test.cc Fri Nov 04 13:53:22 2005 +0000 +++ b/test/dijkstra_test.cc Fri Nov 04 14:48:10 2005 +0000 @@ -54,7 +54,7 @@ dijkstra_test.run(n); l = dijkstra_test.dist(n); - e = dijkstra_test.pred(n); + e = dijkstra_test.predEdge(n); n = dijkstra_test.predNode(n); d = dijkstra_test.distMap(); p = dijkstra_test.predMap(); @@ -135,8 +135,8 @@ ///\bug This works only for integer lengths for(NodeIt v(G); v!=INVALID; ++v){ check(dijkstra_test.reached(v),"Each node should be reached."); - if ( dijkstra_test.pred(v)!=INVALID ) { - Edge e=dijkstra_test.pred(v); + if ( dijkstra_test.predEdge(v)!=INVALID ) { + Edge e=dijkstra_test.predEdge(v); Node u=G.source(e); check(u==dijkstra_test.predNode(v),"Wrong tree."); check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e], diff -r 3915867b6975 -r 49045f2d28d4 test/heap_test.h --- a/test/heap_test.h Fri Nov 04 13:53:22 2005 +0000 +++ b/test/heap_test.h Fri Nov 04 14:48:10 2005 +0000 @@ -93,8 +93,8 @@ } for(NodeIt v(graph); v!=INVALID; ++v) { - if ( dijkstra.reached(v) && dijkstra.pred(v) != INVALID ) { - Edge e=dijkstra.pred(v); + if ( dijkstra.reached(v) && dijkstra.predEdge(v) != INVALID ) { + Edge e=dijkstra.predEdge(v); Node u=graph.source(e); check( dijkstra.dist(v) - dijkstra .dist(u) == length[e], "Error in a shortest path tree edge!");