Changeset 1763:49045f2d28d4 in lemon-0.x
- Timestamp:
- 11/04/05 15:48:10 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2295
- Files:
-
- 14 edited
Legend:
- Unmodified
- Added
- Removed
-
demo/grid_graph_demo.cc
r1693 r1763 46 46 for (GridGraph::Node node = stop; 47 47 node != start; node = bfs.predNode(node)) { 48 path[bfs.pred (node)] = true;48 path[bfs.predEdge(node)] = true; 49 49 } 50 50 -
lemon/belmann_ford.h
r1754 r1763 504 504 p.clear(); 505 505 typename Path::Builder b(p); 506 for(b.setStartNode(t);pred (t)!=INVALID;t=predNode(t))507 b.pushFront(pred (t));506 for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t)) 507 b.pushFront(predEdge(t)); 508 508 b.commit(); 509 509 return true; … … 530 530 /// this function. 531 531 /// \todo predEdge could be a better name. 532 Edge pred (Node v) const { return (*_pred)[v]; }532 Edge predEdge(Node v) const { return (*_pred)[v]; } 533 533 534 534 /// \brief Returns the 'previous node' of the shortest path tree. … … 538 538 /// the root to \c /v. It is INVALID if \c v is unreachable from the root 539 539 /// or if \c v=s. The shortest path tree used here is equal to the 540 /// shortest path tree used in \ref pred (). \pre \ref run() must be540 /// shortest path tree used in \ref predEdge(). \pre \ref run() must be 541 541 /// called before using this function. 542 542 Node predNode(Node v) const { -
lemon/bfs.h
r1761 r1763 621 621 p.clear(); 622 622 typename P::Builder b(p); 623 for(b.setStartNode(t);pred (t)!=INVALID;t=predNode(t))624 b.pushFront(pred (t));623 for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t)) 624 b.pushFront(predEdge(t)); 625 625 b.commit(); 626 626 return true; … … 649 649 ///this function. 650 650 ///\todo predEdge could be a better name. 651 Edge pred (Node v) const { return (*_pred)[v];}651 Edge predEdge(Node v) const { return (*_pred)[v];} 652 652 653 653 ///Returns the 'previous node' of the shortest path tree. … … 660 660 ///if \c v itself a root. 661 661 ///The shortest path tree used here is equal to the shortest path 662 ///tree used in \ref pred ().662 ///tree used in \ref predEdge(). 663 663 ///\pre Either \ref run() or \ref start() must be called before 664 664 ///using this function. -
lemon/dfs.h
r1761 r1763 643 643 p.clear(); 644 644 typename P::Builder b(p); 645 for(b.setStartNode(t);pred (t)!=INVALID;t=predNode(t))646 b.pushFront(pred (t));645 for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t)) 646 b.pushFront(predEdge(t)); 647 647 b.commit(); 648 648 return true; … … 671 671 ///this function. 672 672 ///\todo predEdge could be a better name. 673 Edge pred (Node v) const { return (*_pred)[v];}673 Edge predEdge(Node v) const { return (*_pred)[v];} 674 674 675 675 ///Returns the 'previous node' of the %DFS tree. … … 682 682 ///if \c v itself a root. 683 683 ///The %DFS tree used here is equal to the %DFS 684 ///tree used in \ref pred ().684 ///tree used in \ref predEdge(). 685 685 ///\pre Either \ref run() or \ref start() must be called before 686 686 ///using this function. -
lemon/dijkstra.h
r1761 r1763 734 734 p.clear(); 735 735 typename P::Builder b(p); 736 for(b.setStartNode(t);pred (t)!=INVALID;t=predNode(t))737 b.pushFront(pred (t));736 for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t)) 737 b.pushFront(predEdge(t)); 738 738 b.commit(); 739 739 return true; … … 760 760 ///this function. 761 761 ///\todo predEdge could be a better name. 762 Edge pred (Node v) const { return (*_pred)[v]; }762 Edge predEdge(Node v) const { return (*_pred)[v]; } 763 763 764 764 ///Returns the 'previous node' of the shortest path tree. … … 768 768 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if 769 769 ///\c v=s. The shortest path tree used here is equal to the shortest path 770 ///tree used in \ref pred (). \pre \ref run() must be called before770 ///tree used in \ref predEdge(). \pre \ref run() must be called before 771 771 ///using this function. 772 772 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: -
lemon/floyd_warshall.h
r1757 r1763 489 489 p.clear(); 490 490 typename Path::Builder b(target); 491 for(b.setStartNode(target); pred (source, target) != INVALID;491 for(b.setStartNode(target); predEdge(source, target) != INVALID; 492 492 target = predNode(target)) { 493 b.pushFront(pred (source, target));493 b.pushFront(predEdge(source, target)); 494 494 } 495 495 b.commit(); … … 519 519 /// \pre \ref run() must be called before using this function. 520 520 /// \todo predEdge could be a better name. 521 Edge pred (Node root, Node node) const {521 Edge predEdge(Node root, Node node) const { 522 522 return (*_pred)(root, node); 523 523 } … … 530 530 /// INVALID if \c node is unreachable from the root or if \c node=root. 531 531 /// The shortest path tree used here is equal to the 532 /// shortest path tree used in \ref pred ().532 /// shortest path tree used in \ref predEdge(). 533 533 /// \pre \ref run() must be called before using this function. 534 534 Node predNode(Node root, Node node) const { -
lemon/johnson.h
r1757 r1763 510 510 _dist->set(it, jt, dijkstra.dist(jt) + 511 511 potential[jt] - potential[it]); 512 _pred->set(it, jt, dijkstra.pred (jt));512 _pred->set(it, jt, dijkstra.predEdge(jt)); 513 513 } else { 514 514 _dist->set(it, jt, OperationTraits::infinity()); … … 635 635 p.clear(); 636 636 typename Path::Builder b(target); 637 for(b.setStartNode(target); pred (source, target) != INVALID;637 for(b.setStartNode(target); predEdge(source, target) != INVALID; 638 638 target = predNode(target)) { 639 b.pushFront(pred (source, target));639 b.pushFront(predEdge(source, target)); 640 640 } 641 641 b.commit(); … … 665 665 /// \pre \ref run() must be called before using this function. 666 666 /// \todo predEdge could be a better name. 667 Edge pred (Node root, Node node) const {667 Edge predEdge(Node root, Node node) const { 668 668 return (*_pred)(root, node); 669 669 } … … 676 676 /// INVALID if \c node is unreachable from the root or if \c node=root. 677 677 /// The shortest path tree used here is equal to the 678 /// shortest path tree used in \ref pred ().678 /// shortest path tree used in \ref predEdge(). 679 679 /// \pre \ref run() must be called before using this function. 680 680 Node predNode(Node root, Node node) const { -
lemon/min_cost_flow.h
r1527 r1763 152 152 ResGraphEdge e; 153 153 while (n!=s){ 154 e = dijkstra.pred (n);154 e = dijkstra.predEdge(n); 155 155 n = dijkstra.predNode(n); 156 156 res_graph.augment(e,1); -
lemon/topology.h
r1750 r1763 111 111 /// Find the connected components of an undirected graph. 112 112 /// 113 /// \image html connected_components.png 114 /// \image latex connected_components.eps "Connected components" width=\textwidth 115 /// 113 116 /// \param g The graph. In must be undirected. 114 117 /// \retval comp A writable node map. The values will be set from 0 to … … 117 120 /// set continuously. 118 121 /// \return The number of components 122 /// 119 123 template <class UndirGraph, class NodeMap> 120 124 int connectedComponents(const UndirGraph &graph, NodeMap &compMap) { … … 349 353 /// when there are directed paths between them in both direction. 350 354 /// 355 /// \image html strongly_connected_components.png 356 /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth 357 /// 351 358 /// \param g The graph. 352 359 /// \retval comp A writable node map. The values will be set from 0 to … … 355 362 /// will be set continuously. 356 363 /// \return The number of components 364 /// 357 365 template <typename Graph, typename NodeMap> 358 366 int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) { … … 747 755 /// when they are on same circle. 748 756 /// 757 /// \image html node_biconnected_components.png 758 /// \image latex node_biconnected_components.eps "Node biconnected components" width=\textwidth 759 /// 749 760 /// \param graph The graph. 750 761 /// \retval comp A writable undir edge map. The values will be set from 0 to … … 753 764 /// will be set continuously. 754 765 /// \return The number of components. 766 /// 755 767 template <typename UndirGraph, typename UndirEdgeMap> 756 768 int nodeBiconnectedComponents(const UndirGraph& graph, … … 1070 1082 /// connected at least two edge-disjoint paths. 1071 1083 /// 1084 /// \image html edge_biconnected_components.png 1085 /// \image latex edge_biconnected_components.eps "Edge biconnected components" width=\textwidth 1086 /// 1072 1087 /// \param graph The graph. 1073 1088 /// \retval comp A writable node map. The values will be set from 0 to … … 1076 1091 /// will be set continuously. 1077 1092 /// \return The number of components. 1093 /// 1078 1094 template <typename UndirGraph, typename NodeMap> 1079 1095 int edgeBiconnectedComponents(const UndirGraph& graph, NodeMap& compMap) { … … 1323 1339 Node target = graph.target(edge); 1324 1340 if (dfs.reached(target) && 1325 dfs.pred (source) != graph.oppositeEdge(edge)) {1341 dfs.predEdge(source) != graph.oppositeEdge(edge)) { 1326 1342 return false; 1327 1343 } … … 1354 1370 Node target = graph.target(edge); 1355 1371 if (dfs.reached(target) && 1356 dfs.pred (source) != graph.oppositeEdge(edge)) {1372 dfs.predEdge(source) != graph.oppositeEdge(edge)) { 1357 1373 return false; 1358 1374 } -
test/all_pairs_shortest_path_test.cc
r1745 r1763 89 89 check(johnson.dist(it, jt) == 90 90 johnson.dist(it, johnson.predNode(it, jt)) + 91 length[johnson.pred (it, jt)],91 length[johnson.predEdge(it, jt)], 92 92 "Wrong edge in all pairs shortest path"); 93 93 check(fibJohnson.dist(it, jt) == 94 94 fibJohnson.dist(it, fibJohnson.predNode(it, jt)) + 95 length[fibJohnson.pred (it, jt)],95 length[fibJohnson.predEdge(it, jt)], 96 96 "Wrong edge in all pairs shortest path"); 97 97 check(floyd.dist(it, jt) == 98 98 floyd.dist(it, floyd.predNode(it, jt)) + 99 length[floyd.pred (it, jt)],99 length[floyd.predEdge(it, jt)], 100 100 "Wrong edge in all pairs shortest path"); 101 101 } -
test/bfs_test.cc
r1435 r1763 51 51 52 52 l = bfs_test.dist(n); 53 e = bfs_test.pred (n);53 e = bfs_test.predEdge(n); 54 54 n = bfs_test.predNode(n); 55 55 d = bfs_test.distMap(); … … 122 122 for(NodeIt v(G); v==INVALID; ++v) { 123 123 check(bfs_test.reached(v),"Each node should be reached."); 124 if ( bfs_test.pred (v)!=INVALID ) {125 Edge e=bfs_test.pred (v);124 if ( bfs_test.predEdge(v)!=INVALID ) { 125 Edge e=bfs_test.predEdge(v); 126 126 Node u=G.source(e); 127 127 check(u==bfs_test.predNode(v),"Wrong tree."); -
test/dfs_test.cc
r1435 r1763 51 51 52 52 l = dfs_test.dist(n); 53 e = dfs_test.pred (n);53 e = dfs_test.predEdge(n); 54 54 n = dfs_test.predNode(n); 55 55 d = dfs_test.distMap(); … … 112 112 for(NodeIt v(G); v!=INVALID; ++v) { 113 113 check(dfs_test.reached(v),"Each node should be reached."); 114 if ( dfs_test.pred (v)!=INVALID ) {115 Edge e=dfs_test.pred (v);114 if ( dfs_test.predEdge(v)!=INVALID ) { 115 Edge e=dfs_test.predEdge(v); 116 116 Node u=G.source(e); 117 117 check(u==dfs_test.predNode(v),"Wrong tree."); -
test/dijkstra_test.cc
r1435 r1763 55 55 56 56 l = dijkstra_test.dist(n); 57 e = dijkstra_test.pred (n);57 e = dijkstra_test.predEdge(n); 58 58 n = dijkstra_test.predNode(n); 59 59 d = dijkstra_test.distMap(); … … 136 136 for(NodeIt v(G); v!=INVALID; ++v){ 137 137 check(dijkstra_test.reached(v),"Each node should be reached."); 138 if ( dijkstra_test.pred (v)!=INVALID ) {139 Edge e=dijkstra_test.pred (v);138 if ( dijkstra_test.predEdge(v)!=INVALID ) { 139 Edge e=dijkstra_test.predEdge(v); 140 140 Node u=G.source(e); 141 141 check(u==dijkstra_test.predNode(v),"Wrong tree."); -
test/heap_test.h
r1745 r1763 94 94 95 95 for(NodeIt v(graph); v!=INVALID; ++v) { 96 if ( dijkstra.reached(v) && dijkstra.pred (v) != INVALID ) {97 Edge e=dijkstra.pred (v);96 if ( dijkstra.reached(v) && dijkstra.predEdge(v) != INVALID ) { 97 Edge e=dijkstra.predEdge(v); 98 98 Node u=graph.source(e); 99 99 check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],
Note: See TracChangeset
for help on using the changeset viewer.