COIN-OR::LEMON - Graph Library

Changeset 1763:49045f2d28d4 in lemon-0.x


Ignore:
Timestamp:
11/04/05 15:48:10 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2295
Message:

pred => predEdge rename

Files:
14 edited

Legend:

Unmodified
Added
Removed
  • demo/grid_graph_demo.cc

    r1693 r1763  
    4646  for (GridGraph::Node node = stop;
    4747       node != start; node = bfs.predNode(node)) {
    48     path[bfs.pred(node)] = true;
     48    path[bfs.predEdge(node)] = true;
    4949  }
    5050 
  • lemon/belmann_ford.h

    r1754 r1763  
    504504        p.clear();
    505505        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));
    508508        b.commit();
    509509        return true;
     
    530530    /// this function.
    531531    /// \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]; }
    533533
    534534    /// \brief Returns the 'previous node' of the shortest path tree.
     
    538538    /// the root to \c /v. It is INVALID if \c v is unreachable from the root
    539539    /// 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 be
     540    /// shortest path tree used in \ref predEdge().  \pre \ref run() must be
    541541    /// called before using this function.
    542542    Node predNode(Node v) const {
  • lemon/bfs.h

    r1761 r1763  
    621621        p.clear();
    622622        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));
    625625        b.commit();
    626626        return true;
     
    649649    ///this function.
    650650    ///\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];}
    652652
    653653    ///Returns the 'previous node' of the shortest path tree.
     
    660660    ///if \c v itself a root.
    661661    ///The shortest path tree used here is equal to the shortest path
    662     ///tree used in \ref pred().
     662    ///tree used in \ref predEdge().
    663663    ///\pre Either \ref run() or \ref start() must be called before
    664664    ///using this function.
  • lemon/dfs.h

    r1761 r1763  
    643643        p.clear();
    644644        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));
    647647        b.commit();
    648648        return true;
     
    671671    ///this function.
    672672    ///\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];}
    674674
    675675    ///Returns the 'previous node' of the %DFS tree.
     
    682682    ///if \c v itself a root.
    683683    ///The %DFS tree used here is equal to the %DFS
    684     ///tree used in \ref pred().
     684    ///tree used in \ref predEdge().
    685685    ///\pre Either \ref run() or \ref start() must be called before
    686686    ///using this function.
  • lemon/dijkstra.h

    r1761 r1763  
    734734        p.clear();
    735735        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));
    738738        b.commit();
    739739        return true;
     
    760760    ///this function.
    761761    ///\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]; }
    763763
    764764    ///Returns the 'previous node' of the shortest path tree.
     
    768768    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
    769769    ///\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 before
     770    ///tree used in \ref predEdge().  \pre \ref run() must be called before
    771771    ///using this function.
    772772    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
  • lemon/floyd_warshall.h

    r1757 r1763  
    489489        p.clear();
    490490        typename Path::Builder b(target);
    491         for(b.setStartNode(target); pred(source, target) != INVALID;
     491        for(b.setStartNode(target); predEdge(source, target) != INVALID;
    492492            target = predNode(target)) {
    493           b.pushFront(pred(source, target));
     493          b.pushFront(predEdge(source, target));
    494494        }
    495495        b.commit();
     
    519519    /// \pre \ref run() must be called before using this function.
    520520    /// \todo predEdge could be a better name.
    521     Edge pred(Node root, Node node) const {
     521    Edge predEdge(Node root, Node node) const {
    522522      return (*_pred)(root, node);
    523523    }
     
    530530    /// INVALID if \c node is unreachable from the root or if \c node=root.
    531531    /// 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(). 
    533533    /// \pre \ref run() must be called before using this function.
    534534    Node predNode(Node root, Node node) const {
  • lemon/johnson.h

    r1757 r1763  
    510510            _dist->set(it, jt, dijkstra.dist(jt) +
    511511                       potential[jt] - potential[it]);
    512             _pred->set(it, jt, dijkstra.pred(jt));
     512            _pred->set(it, jt, dijkstra.predEdge(jt));
    513513          } else {
    514514            _dist->set(it, jt, OperationTraits::infinity());
     
    635635        p.clear();
    636636        typename Path::Builder b(target);
    637         for(b.setStartNode(target); pred(source, target) != INVALID;
     637        for(b.setStartNode(target); predEdge(source, target) != INVALID;
    638638            target = predNode(target)) {
    639           b.pushFront(pred(source, target));
     639          b.pushFront(predEdge(source, target));
    640640        }
    641641        b.commit();
     
    665665    /// \pre \ref run() must be called before using this function.
    666666    /// \todo predEdge could be a better name.
    667     Edge pred(Node root, Node node) const {
     667    Edge predEdge(Node root, Node node) const {
    668668      return (*_pred)(root, node);
    669669    }
     
    676676    /// INVALID if \c node is unreachable from the root or if \c node=root.
    677677    /// 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(). 
    679679    /// \pre \ref run() must be called before using this function.
    680680    Node predNode(Node root, Node node) const {
  • lemon/min_cost_flow.h

    r1527 r1763  
    152152        ResGraphEdge e;
    153153        while (n!=s){
    154           e = dijkstra.pred(n);
     154          e = dijkstra.predEdge(n);
    155155          n = dijkstra.predNode(n);
    156156          res_graph.augment(e,1);
  • lemon/topology.h

    r1750 r1763  
    111111  /// Find the connected components of an undirected graph.
    112112  ///
     113  /// \image html connected_components.png
     114  /// \image latex connected_components.eps "Connected components" width=\textwidth
     115  ///
    113116  /// \param g The graph. In must be undirected.
    114117  /// \retval comp A writable node map. The values will be set from 0 to
     
    117120  /// set continuously.
    118121  /// \return The number of components
     122  ///
    119123  template <class UndirGraph, class NodeMap>
    120124  int connectedComponents(const UndirGraph &graph, NodeMap &compMap) {
     
    349353  /// when there are directed paths between them in both direction.
    350354  ///
     355  /// \image html strongly_connected_components.png
     356  /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
     357  ///
    351358  /// \param g The graph.
    352359  /// \retval comp A writable node map. The values will be set from 0 to
     
    355362  /// will be set continuously.
    356363  /// \return The number of components
     364  ///
    357365  template <typename Graph, typename NodeMap>
    358366  int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) {
     
    747755  /// when they are on same circle.
    748756  ///
     757  /// \image html node_biconnected_components.png
     758  /// \image latex node_biconnected_components.eps "Node biconnected components" width=\textwidth
     759  ///
    749760  /// \param graph The graph.
    750761  /// \retval comp A writable undir edge map. The values will be set from 0 to
     
    753764  /// will be set continuously.
    754765  /// \return The number of components.
     766  ///
    755767  template <typename UndirGraph, typename UndirEdgeMap>
    756768  int nodeBiconnectedComponents(const UndirGraph& graph,
     
    10701082  /// connected at least two edge-disjoint paths.
    10711083  ///
     1084  /// \image html edge_biconnected_components.png
     1085  /// \image latex edge_biconnected_components.eps "Edge biconnected components" width=\textwidth
     1086  ///
    10721087  /// \param graph The graph.
    10731088  /// \retval comp A writable node map. The values will be set from 0 to
     
    10761091  /// will be set continuously.
    10771092  /// \return The number of components.
     1093  ///
    10781094  template <typename UndirGraph, typename NodeMap>
    10791095  int edgeBiconnectedComponents(const UndirGraph& graph, NodeMap& compMap) {
     
    13231339          Node target = graph.target(edge);
    13241340          if (dfs.reached(target) &&
    1325               dfs.pred(source) != graph.oppositeEdge(edge)) {
     1341              dfs.predEdge(source) != graph.oppositeEdge(edge)) {
    13261342            return false;
    13271343          }
     
    13541370      Node target = graph.target(edge);
    13551371      if (dfs.reached(target) &&
    1356           dfs.pred(source) != graph.oppositeEdge(edge)) {
     1372          dfs.predEdge(source) != graph.oppositeEdge(edge)) {
    13571373        return false;
    13581374      }
  • test/all_pairs_shortest_path_test.cc

    r1745 r1763  
    8989          check(johnson.dist(it, jt) ==
    9090                johnson.dist(it, johnson.predNode(it, jt)) +
    91                 length[johnson.pred(it, jt)],
     91                length[johnson.predEdge(it, jt)],
    9292                "Wrong edge in all pairs shortest path");
    9393          check(fibJohnson.dist(it, jt) ==
    9494                fibJohnson.dist(it, fibJohnson.predNode(it, jt)) +
    95                 length[fibJohnson.pred(it, jt)],
     95                length[fibJohnson.predEdge(it, jt)],
    9696                "Wrong edge in all pairs shortest path");
    9797          check(floyd.dist(it, jt) ==
    9898                floyd.dist(it, floyd.predNode(it, jt)) +
    99                 length[floyd.pred(it, jt)],
     99                length[floyd.predEdge(it, jt)],
    100100                "Wrong edge in all pairs shortest path");
    101101        }
  • test/bfs_test.cc

    r1435 r1763  
    5151 
    5252  l  = bfs_test.dist(n);
    53   e  = bfs_test.pred(n);
     53  e  = bfs_test.predEdge(n);
    5454  n  = bfs_test.predNode(n);
    5555  d  = bfs_test.distMap();
     
    122122  for(NodeIt v(G); v==INVALID; ++v) {
    123123    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);
    126126      Node u=G.source(e);
    127127      check(u==bfs_test.predNode(v),"Wrong tree.");
  • test/dfs_test.cc

    r1435 r1763  
    5151 
    5252  l  = dfs_test.dist(n);
    53   e  = dfs_test.pred(n);
     53  e  = dfs_test.predEdge(n);
    5454  n  = dfs_test.predNode(n);
    5555  d  = dfs_test.distMap();
     
    112112  for(NodeIt v(G); v!=INVALID; ++v) {
    113113    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);
    116116      Node u=G.source(e);
    117117      check(u==dfs_test.predNode(v),"Wrong tree.");
  • test/dijkstra_test.cc

    r1435 r1763  
    5555
    5656  l  = dijkstra_test.dist(n);
    57   e  = dijkstra_test.pred(n);
     57  e  = dijkstra_test.predEdge(n);
    5858  n  = dijkstra_test.predNode(n);
    5959  d  = dijkstra_test.distMap();
     
    136136  for(NodeIt v(G); v!=INVALID; ++v){
    137137    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);
    140140      Node u=G.source(e);
    141141      check(u==dijkstra_test.predNode(v),"Wrong tree.");
  • test/heap_test.h

    r1745 r1763  
    9494
    9595  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);
    9898      Node u=graph.source(e);
    9999      check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],
Note: See TracChangeset for help on using the changeset viewer.