Changeset 59:41c7f9c09a12 in lemon-0.x for src/work/list_graph.hh

Timestamp:

02/04/04 13:46:33 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

.

File:

• src/work/list_graph.hh (modified) (14 diffs)

src/work/list_graph.hh

@@ -1 @@
-#ifndef MARCI_LIST_GRAPH_HH
-#define MARCI_LIST_GRAPH_HH
+#ifndef LIST_GRAPH_HH
+#define LIST_GRAPH_HH
 
 #include <iostream>
 
 namespace marci {
-
-  template <typename It>
-  int number_of(It _it) { 
-    int i=0;
-    for( ; _it.valid(); ++_it) { ++i; } 
-    return i;
-  }
 
   template <typename It>
@@ -21 +14 @@
 
   class ListGraph {
+
     class node_item;
     class edge_item;
+
   public:
+
     class NodeIt;
     class EachNodeIt;
@@ -31 +27 @@
     class InEdgeIt;
     class SymEdgeIt;
-
-    template <typename T>
+    template <typename ValueType> class NodeMap;
+    template <typename ValueType> class EdgeMap;
+    
+  private:
+    
+    template <typename ValueType> friend class NodeMap;
+    template <typename ValueType> friend class EdgeMap;
+
+    template <typename ValueType>
     class NodeMap {
-      //typedef typename Graph::NodeIt NodeIt;
-      //typedef typename Graph::EachNodeIt EachNodeIt;
       const ListGraph& G; 
-      std::vector<T> container;
-    public:
-      NodeMap(const ListGraph& _G) : G(_G) {
-        int i=0;
-        for(EachNodeIt it=G.template first<EachNodeIt>(); it.valid(); ++it) ++i;
-        container.resize(i); 
-      }
-      NodeMap(const ListGraph& _G, const T a) : G(_G) {
-        for(EachNodeIt it=G.template first<EachNodeIt>(); it.valid(); ++it) { 
-          container.push_back(a); 
-        }
-      }
-      void set(const NodeIt nit, const T a) { container[G.id(nit)]=a; }
-      T get(const NodeIt nit) const { return container[G.id(nit)]; }
-    };
-
-    template <typename T>
+      std::vector<ValueType> container;
+    public:
+      NodeMap(const ListGraph& _G) : G(_G), container(_G.node_id) { }
+      NodeMap(const ListGraph& _G, const ValueType a) : 
+        G(_G), container(_G.node_id, a) { }
+      void set(const NodeIt nit, const ValueType a) { container[G.id(nit)]=a; }
+      ValueType get(const NodeIt nit) const { return container[G.id(nit)]; }
+    };
+
+    template <typename ValueType>
     class EdgeMap {
-      //typedef typename Graph::EdgeIt EdgeIt;
-      //typedef typename Graph::EachEdgeIt EachEdgeIt;
       const ListGraph& G; 
-      std::vector<T> container;
-    public:
-      EdgeMap(const ListGraph& _G) : G(_G) {
-        int i=0;
-        for(EachEdgeIt it=G.template first<EachEdgeIt>(); it.valid(); ++it) ++i;
-        container.resize(i); 
-      }
-      EdgeMap(const ListGraph& _G, const T a) : G(_G) {
-        for(EachEdgeIt it=G.template first<EachEdgeIt>(); it.valid(); ++it) { 
-          container.push_back(a); 
-        }
-      }
-      void set(const EdgeIt eit, const T a) { container[G.id(eit)]=a; }
-      T get(const EdgeIt eit) const { return container[G.id(eit)]; }
-    };
-
-    //typedef template<typename T> NodePropertyVector<ListGraph, T> NodeMap;
-    //template <typename T>
-    //typedef NodePropertyVector<ListGraph, T> NodeMap;
-    //template <typename T>
-    //typedef typename NodePropertyVector<ListGraph, T> NodeMap;
-    //template <typename T>
-    //typedef NodePropertyVector<typename ListGraph, T> NodeMap;
-    //template <typename T>
-    //typedef typename NodePropertyVector<typename ListGraph, T> NodeMap;
-    //template <typename T>
-    //typedef template NodePropertyVector<ListGraph, T> NodeMap;
-    //template <typename T>
-    //typedef template typename NodePropertyVector<ListGraph, T> NodeMap;
-    //template <typename T>
-    //typedef template NodePropertyVector<typename ListGraph, T> NodeMap;
-    //template <typename T>
-    //typedef template typename NodePropertyVector<typename ListGraph, T> NodeMap;
-    //template <typename T>
-    //typedef EdgePropertyVector<ListGraph, T> EdgeMap;
-
-  private:
+      std::vector<ValueType> container;
+    public:
+      EdgeMap(const ListGraph& _G) : G(_G), container(_G.edge_id) { }
+      EdgeMap(const ListGraph& _G, const ValueType a) : 
+        G(_G), container(_G.edge_id, a) { }
+      void set(const EdgeIt eit, const ValueType a) { container[G.id(eit)]=a; }
+      ValueType get(const EdgeIt eit) const { return container[G.id(eit)]; }
+    };
+
     int node_id;
     int edge_id;
@@ -114 +78 @@
       friend std::ostream& operator<<(std::ostream& os, const NodeIt& i);
       friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i);
-      ListGraph* G;
+      //ListGraph* G;
       int id;
       edge_item* _first_out_edge;
@@ -136 +100 @@
       friend class SymEdgeIt;
       friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i);
-      ListGraph* G;
+      //ListGraph* G;
       int id;
       node_item* _tail;
@@ -257 +221 @@
     /* functions to construct iterators from the graph, or from each other */
 
-    EachNodeIt firstNode() const { return EachNodeIt(_first_node); }
-    EachEdgeIt firstEdge() const { 
-      node_item* v=_first_node;
-      edge_item* edge=v->_first_out_edge;
-      while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
-      return EachEdgeIt(v, edge); 
-    }
+    //EachNodeIt firstNode() const { return EachNodeIt(*this); }
+    //EachEdgeIt firstEdge() const { return EachEdgeIt(*this); }
     
     //OutEdgeIt firstOutEdge(const NodeIt v) const { return OutEdgeIt(v); }
-    InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); }
-    SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); }
+    //InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); }
+    //SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); }
     NodeIt tail(const EdgeIt e) const { return e.tailNode(); }
     NodeIt head(const EdgeIt e) const { return e.headNode(); }
@@ -288 +247 @@
     /* for experimental purpose */
 
-    void getFirst(EachNodeIt& v) const { v=EachNodeIt(_first_node); }
-    void getFirst(EachEdgeIt& e) const { e=firstEdge(); }
+    void getFirst(EachNodeIt& v) const { v=EachNodeIt(*this); }
+    void getFirst(EachEdgeIt& e) const { e=EachEdgeIt(*this); }
     void getFirst(OutEdgeIt& e, const NodeIt& v) const { e=OutEdgeIt(v); }
     void getFirst(InEdgeIt& e, const NodeIt& v) const { e=InEdgeIt(v); }
@@ -387 +346 @@
     class EachNodeIt : public NodeIt {
       friend class ListGraph;
+    protected:
+      EachNodeIt(const ListGraph& G) : NodeIt(G._first_node) { }
     public:
       EachNodeIt() : NodeIt() { }
       EachNodeIt(node_item* v) : NodeIt(v) { }
-      EachNodeIt(const ListGraph& G) : NodeIt(G._first_node) { }
       EachNodeIt& operator++() { node=node->_next_node; return *this; }
     };
@@ -423 +383 @@
     class EachEdgeIt : public EdgeIt {
       friend class ListGraph;
-      node_item* v;
-    public:
-      EachEdgeIt() : EdgeIt(), v(0) { }
-      EachEdgeIt(node_item* _v, edge_item* _e) : EdgeIt(_e), v(_v) { }
+    protected:
       EachEdgeIt(const ListGraph& G) {
-        v=G._first_node;
-        edge=v->_first_out_edge;
+        node_item* v=G._first_node;
+        if (v) edge=v->_first_out_edge; else edge=0;
         while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
       }
+    public:
+      EachEdgeIt() : EdgeIt() { }
+      EachEdgeIt(edge_item* _e) : EdgeIt(_e) { }
       EachEdgeIt& operator++() { 
+        node_item* v=edge->_tail;
         edge=edge->_next_out; 
         while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
@@ -442 +403 @@
       friend class ListGraph;
       node_item* v;
+    protected:
+      OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_out_edge; }
     public:
       OutEdgeIt() : EdgeIt(), v(0) { }
-    protected:
-      OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_out_edge; }
-    public:
       OutEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_out_edge; }
       OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
@@ -458 +418 @@
       friend class ListGraph;
       node_item* v;
+    protected:
+      InEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_in_edge; }
     public:
       InEdgeIt() : EdgeIt(), v(0) { }
-    protected:
-      InEdgeIt(const NodeIt& _v) : v(_v.node) { 
-        edge=v->_first_in_edge; 
-      }
-    public:
       InEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_in_edge; }
       InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
@@ -477 +434 @@
       bool out_or_in; //1 iff out, 0 iff in
       node_item* v;
-    public:
-      SymEdgeIt() : EdgeIt(), v(0) { }
     protected:
       SymEdgeIt(const NodeIt& _v) : v(_v.node) { 
@@ -486 +441 @@
       }
     public:
+      SymEdgeIt() : EdgeIt(), v(0) { }
       SymEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { 
         out_or_in=1;
@@ -550 +506 @@
 } //namespace marci
 
-#endif //MARCI_LIST_GRAPH_HH
+#endif //LIST_GRAPH_HH