COIN-OR::LEMON - Graph Library

Changeset 1283:fc20371677b9 in lemon-0.x


Ignore:
Timestamp:
03/31/05 15:31:39 (15 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1715
Message:

getPath() added to Bfs/Dfs/Dijkstra?.

Location:
src
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/bfs.h

    r1270 r1283  
    654654    ///@{
    655655
     656    ///Copies the shortest path to \c t into \c p
     657   
     658    ///This function copies the shortest path to \c t into \c p.
     659    ///If it \c \t is a source itself or unreachable, then it does not
     660    ///alter \c p.
     661    ///\todo Is it the right way to handle unreachable nodes?
     662    ///\return Returns \c true if a path to \c t was actually copied to \c p,
     663    ///\c false otherwise.
     664    ///\sa DirPath
     665    template<class P>
     666    bool getPath(P &p,Node t)
     667    {
     668      if(reached(t)) {
     669        p.clear();
     670        typename P::Builder b(p);
     671        for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
     672          b.pushFront(pred(t));
     673        b.commit();
     674        return true;
     675      }
     676      return false;
     677    }
     678
    656679    ///The distance of a node from the root(s).
    657680
  • src/lemon/dfs.h

    r1236 r1283  
    661661    ///@{
    662662
     663    ///Copies the path to \c t on the DFS tree into \c p
     664   
     665    ///This function copies the path on the DFS tree to \c t into \c p.
     666    ///If it \c \t is a source itself or unreachable, then it does not
     667    ///alter \c p.
     668    ///\todo Is it the right way to handle unreachable nodes?
     669    ///\return Returns \c true if a path to \c t was actually copied to \c p,
     670    ///\c false otherwise.
     671    ///\sa DirPath
     672    template<class P>
     673    bool getPath(P &p,Node t)
     674    {
     675      if(reached(t)) {
     676        p.clear();
     677        typename P::Builder b(p);
     678        for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
     679          b.pushFront(pred(t));
     680        b.commit();
     681        return true;
     682      }
     683      return false;
     684    }
     685
    663686    ///The distance of a node from the root(s).
    664687
  • src/lemon/dijkstra.h

    r1236 r1283  
    2121///\file
    2222///\brief Dijkstra algorithm.
     23///
     24///\todo getPath() should be implemented! (also for BFS and DFS)
    2325
    2426#include <lemon/list_graph.h>
     
    656658    ///@{
    657659
     660    ///Copies the shortest path to \c t into \c p
     661   
     662    ///This function copies the shortest path to \c t into \c p.
     663    ///If it \c \t is a source itself or unreachable, then it does not
     664    ///alter \c p.
     665    ///\todo Is it the right way to handle unreachable nodes?
     666    ///\return Returns \c true if a path to \c t was actually copied to \c p,
     667    ///\c false otherwise.
     668    ///\sa DirPath
     669    template<class P>
     670    bool getPath(P &p,Node t)
     671    {
     672      if(reached(t)) {
     673        p.clear();
     674        typename P::Builder b(p);
     675        for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
     676          b.pushFront(pred(t));
     677        b.commit();
     678        return true;
     679      }
     680      return false;
     681    }
     682         
    658683    ///The distance of a node from the root.
    659684
  • src/test/bfs_test.cc

    r1220 r1283  
    1818#include <lemon/smart_graph.h>
    1919#include <lemon/bfs.h>
     20#include <lemon/path.h>
    2021#include<lemon/concept/graph.h>
    2122
     
    5758  b  = bfs_test.reached(n);
    5859
     60  DirPath<Graph> pp(G);
     61  bfs_test.getPath(pp,n);
    5962}
    6063
     
    104107  check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
    105108
     109  DirPath<Graph> p(G);
     110  check(bfs_test.getPath(p,t),"getPath() failed to set the path.");
     111  check(p.length()==3,"getPath() found a wrong path.");
     112 
    106113
    107114  for(EdgeIt e(G); e==INVALID; ++e) {
  • src/test/dfs_test.cc

    r1233 r1283  
    1818#include <lemon/smart_graph.h>
    1919#include <lemon/dfs.h>
     20#include <lemon/path.h>
    2021#include <lemon/concept/graph.h>
    2122
     
    5758  b  = dfs_test.reached(n);
    5859
     60  DirPath<Graph> pp(G);
     61  dfs_test.getPath(pp,n);
    5962}
    6063
     
    103106  dfs_test.run(s); 
    104107 
     108  DirPath<Graph> p(G);
     109  check(dfs_test.getPath(p,t),"getPath() failed to set the path.");
     110  check(p.length()==dfs_test.dist(t),"getPath() found a wrong path.");
     111 
    105112  for(NodeIt v(G); v!=INVALID; ++v) {
    106113    check(dfs_test.reached(v),"Each node should be reached.");
  • src/test/dijkstra_test.cc

    r1220 r1283  
    1818#include <lemon/smart_graph.h>
    1919#include <lemon/dijkstra.h>
     20#include <lemon/path.h>
    2021#include <lemon/maps.h>
    2122#include <lemon/concept/graph.h>
     
    6061  //  pn = dijkstra_test.predNodeMap();
    6162  b  = dijkstra_test.reached(n);
    62  
     63
     64  DirPath<Graph> pp(G);
     65  dijkstra_test.getPath(pp,n);
    6366}
    6467
     
    115118
    116119
     120  DirPath<Graph> p(G);
     121  check(dijkstra_test.getPath(p,t),"getPath() failed to set the path.");
     122  check(p.length()==4,"getPath() found a wrong path.");
     123 
     124
    117125  for(EdgeIt e(G); e!=INVALID; ++e) {
    118126    Node u=G.source(e);
Note: See TracChangeset for help on using the changeset viewer.