Changeset 6:b63d1bc367f7 in lemon-0.x

Timestamp:

12/16/03 17:19:08 (21 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@19

Message:

!!!Tests!!!

Location:

src

Files:

• include/bfs.h (modified) (1 diff)
• include/graph.h (modified) (3 diffs)
• work/bfsdemo.cc (modified) (1 diff)
• work/bfsdemo2.cc (added)

src/include/bfs.h

@@ -241 +241 @@
 
   // bfs algorithm class
+
+  template<class G>  //the default traits
+  class default_bfs_T
+  {
+  public:
+    
+    typedef G Graph;
+    typedef typename G::OutEdgeIterator SearchEdgeIterator;
+    
+    typedef typename G::NodeMap<bool> visited_map_t;
+    typedef typename G::NodeMap<typename G::EdgeIterator> tree_map_t;
+    
+    typedef typename G::NodeMap<int> dist_map_t;   //node->int (W)
+    typedef typename G::NodeMap<int> priority_map_t; //node->int (W)
+};
+
   template<class T>
   class Bfs
   {
   public:
-    typedef typename T::Graph_t Graph;
+    typedef typename T::Graph Graph;
     typedef typename Graph::NodeIterator NodeIterator;
     typedef typename Graph::EdgeIterator EdgeIterator;

src/include/graph.h

@@ -5 +5 @@
 //inline void *operator new(size_t s, void *p) { return p; }
 #include <new>
+#include <vector>
 
 namespace NEGRO 
@@ -41 +42 @@
     class AllEdgeIterator;
     
-    class FirstAnythingTypeNode;
+    class FirstAnythingTypeNode; //Required by the unified First() function.
 
     friend class NodeIterator;
@@ -392 +393 @@
 
     Graph() : _FST(this) {}
+
+    // MAPS:
+    template<class T> class NodeMap
+    {
+      Graph<N,E> *G;
+      vector<T> map;
+
+    public:
+      typedef T value_type;
+      void Set(NodeIterator i, const T &t) {map[i.Index()]=t;}
+      T &Get(NodeIterator i) {return map[i.Index()];}
+      T &operator[](NodeIterator i) {return map[i.Index()];}
+
+      void update() { map.resize(G->OldGraph<N,E>::NodeMax());}
+
+      NodeMap(Graph<N,E> &Gr) : map(Gr.OldGraph<N,E>::NodeMax()) { G=&Gr ;}
+      
+    };
+
+    template<class T> class EdgeMap
+    {
+      Graph<N,E> *G;
+      vector<T> map;
+
+    public:
+      typedef T value_type;
+      void Set(NodeIterator i, const T &t) {map[i.Index()]=t;}
+      T &Get(NodeIterator i) {return map[i.Index()];}
+      T &operator[](NodeIterator i) {return map[i.Index()];}
+      
+      void update()
+        { map.resize(Gr.OldGraph<N,E>::edge_block_num*EDGE_BLOCK_SIZE);}
+      
+      EdgeMap(Graph<N,E> &Gr) 
+        :map(Gr.OldGraph<N,E>::edge_block_num*EDGE_BLOCK_SIZE)
+        { G=&Gr ;}
+      
+    };
+    
   };
   

src/work/bfsdemo.cc

@@ -83 +83 @@
 public:
 
-  typedef IGraph Graph_t;
+  typedef IGraph Graph;
   typedef IGraph::OutEdgeIterator SearchEdgeIterator;