Changeset 1283:fc20371677b9 in lemon-0.x for src/lemon

Timestamp:

03/31/05 15:31:39 (19 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/lemon

Files:

• bfs.h (modified) (1 diff)
• dfs.h (modified) (1 diff)
• dijkstra.h (modified) (2 diffs)

src/lemon/bfs.h

@@ -654 +654 @@
     ///@{
 
+    ///Copies the shortest path to \c t into \c p
+    
+    ///This function copies the shortest path to \c t into \c p.
+    ///If it \c \t is a source itself or unreachable, then it does not
+    ///alter \c p.
+    ///\todo Is it the right way to handle unreachable nodes?
+    ///\return Returns \c true if a path to \c t was actually copied to \c p,
+    ///\c false otherwise.
+    ///\sa DirPath
+    template<class P>
+    bool getPath(P &p,Node t) 
+    {
+      if(reached(t)) {
+        p.clear();
+        typename P::Builder b(p);
+        for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
+          b.pushFront(pred(t));
+        b.commit();
+        return true;
+      }
+      return false;
+    }
+
     ///The distance of a node from the root(s).
 

src/lemon/dfs.h

@@ -661 +661 @@
     ///@{
 
+    ///Copies the path to \c t on the DFS tree into \c p
+    
+    ///This function copies the path on the DFS tree to \c t into \c p.
+    ///If it \c \t is a source itself or unreachable, then it does not
+    ///alter \c p.
+    ///\todo Is it the right way to handle unreachable nodes?
+    ///\return Returns \c true if a path to \c t was actually copied to \c p,
+    ///\c false otherwise.
+    ///\sa DirPath
+    template<class P>
+    bool getPath(P &p,Node t) 
+    {
+      if(reached(t)) {
+        p.clear();
+        typename P::Builder b(p);
+        for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
+          b.pushFront(pred(t));
+        b.commit();
+        return true;
+      }
+      return false;
+    }
+
     ///The distance of a node from the root(s).
 

src/lemon/dijkstra.h

@@ -21 +21 @@
 ///\file
 ///\brief Dijkstra algorithm.
+///
+///\todo getPath() should be implemented! (also for BFS and DFS)
 
 #include <lemon/list_graph.h>
@@ -656 +658 @@
     ///@{
 
+    ///Copies the shortest path to \c t into \c p
+    
+    ///This function copies the shortest path to \c t into \c p.
+    ///If it \c \t is a source itself or unreachable, then it does not
+    ///alter \c p.
+    ///\todo Is it the right way to handle unreachable nodes?
+    ///\return Returns \c true if a path to \c t was actually copied to \c p,
+    ///\c false otherwise.
+    ///\sa DirPath
+    template<class P>
+    bool getPath(P &p,Node t) 
+    {
+      if(reached(t)) {
+        p.clear();
+        typename P::Builder b(p);
+        for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
+          b.pushFront(pred(t));
+        b.commit();
+        return true;
+      }
+      return false;
+    }
+          
     ///The distance of a node from the root.