Changeset 108:0351b00fd283 in lemon-0.x for src/work

Timestamp:

02/20/04 23:01:02 (21 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

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

Message:

Dynamic Maps added.

Location:

src/work/alpar

Files:

• f_ed_ka.h (modified) (2 diffs)
• f_ed_ka_demo.cc (modified) (3 diffs)
• smart_graph.h (modified) (8 diffs)

src/work/alpar/f_ed_ka.h

@@ -12 +12 @@
 //#include <bfs_iterator.hh>
 
-namespace marci {
+namespace hugo {
   template <typename Graph, typename FlowMap, typename CapacityMap>
   typename FlowMap::ValueType maxFlow(Graph &G,
@@ -115 +115 @@
   }
   
-} // namespace marci
+} // namespace hugo
 
 #endif //EDMONDS_KARP_HH

src/work/alpar/f_ed_ka_demo.cc

@@ -9 +9 @@
 #include "../marci/time_measure.h"
 
-using namespace marci;
+using namespace hugo;
 
 // Use a DIMACS max flow file as stdin.
@@ -15 +15 @@
 
 int main(int, char **) {
-  //  typedef SmartGraph Graph;
-  typedef ListGraph Graph;
+  typedef SmartGraph Graph;
+  //typedef ListGraph Graph;
 
   typedef Graph::NodeIt NodeIt;
@@ -24 +24 @@
   Graph G;
   NodeIt s, t;
-  Graph::EdgeMap<int> cap(G);
+  Graph::DynEdgeMap<int> cap(G);
   readDimacsMaxFlow(std::cin, G, s, t, cap);
 
   std::cout << "edmonds karp demo..." << std::endl;
-  Graph::EdgeMap<int> flow(G); //0 flow
+  Graph::DynEdgeMap<int> flow(G); //0 flow
   
   int ret;

src/work/alpar/smart_graph.h

@@ -28 +28 @@
     std::vector<EdgeT> edges;
     
+    template <typename Key> class DynMapBase
+    {
+    protected:
+      SmartGraph* G; 
+    public:
+      virtual void add(const Key k) = NULL;
+      virtual void erase(const Key k) = NULL;
+      DynMapBase(SmartGraph &_G) : G(&_G) {}
+      virtual ~DynMapBase() {}
+      friend class SmartGraph;
+    };
 
   public:
+    template <typename T> class DynEdgeMap;
+    template <typename T> class DynEdgeMap;
 
     class NodeIt;
+    class EdgeIt;
+
+  protected:
+    std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
+    std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
+    
+  public:
+
     class EachNodeIt;
-    class EdgeIt;
     class EachEdgeIt;
     class OutEdgeIt;
@@ -55 +75 @@
     SmartGraph() : nodes(), edges() { }
     
-    ~SmartGraph() {}
+    ~SmartGraph()
+    {
+      for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
+          i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
+      for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
+          i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
+    }
 
     int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
     int edgeNum() const { return edges.size(); }  //FIXME: What is this?
 
+    int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?
+    int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
+
+    
     NodeIt tail(EdgeIt e) const { return edges[e.n].tail; }
     NodeIt head(EdgeIt e) const { return edges[e.n].head; }
@@ -115 +145 @@
       NodeIt n; n.n=nodes.size();
       nodes.push_back(NodeT()); //FIXME: Hmmm...
+
+      for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
+          i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
+
       return n;
     }
+    
     EdgeIt addEdge(NodeIt u, NodeIt v) {
       EdgeIt e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
@@ -123 +158 @@
       edges[e.n].next_in=nodes[v.n].first_in;
       nodes[u.n].first_out=nodes[v.n].first_in=e.n;
+
+      for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
+          i!=dyn_edge_maps.end(); ++i) (**i).add(e.n);
+
       return e;
     }
@@ -131 +170 @@
       friend class SmartGraph;
       template <typename T> friend class NodeMap;
+      template <typename T> friend class DynNodeMap;
       
       friend class EdgeIt;
@@ -157 +197 @@
       friend class SmartGraph;
       template <typename T> friend class EdgeMap;
+      template <typename T> friend class DynEdgeMap;
       
       friend class NodeIt;
@@ -201 +242 @@
       typedef T ValueType;
       typedef NodeIt KeyType;
-      NodeMap(const SmartGraph& _G) : G(_G), container(G.nodeNum()) { }
+      NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
       NodeMap(const SmartGraph& _G, T a) : 
-        G(_G), container(G.nodeNum(), a) { }
+        G(_G), container(G.maxNodeId(), a) { }
       void set(NodeIt n, T a) { container[n.n]=a; }
       T get(NodeIt n) const { return container[n.n]; }
       T& operator[](NodeIt n) { return container[n.n]; }
       const T& operator[](NodeIt n) const { return container[n.n]; }
-      void update() { container.resize(G.nodeNum()); }
-      void update(T a) { container.resize(G.nodeNum(), a); }
+      void update() { container.resize(G.maxNodeId()); }
+      void update(T a) { container.resize(G.maxNodeId(), a); }
     };
 
@@ -219 +260 @@
       typedef T ValueType;
       typedef EdgeIt KeyType;
-      EdgeMap(const SmartGraph& _G) : G(_G), container(G.edgeNum()) { }
+      EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
       EdgeMap(const SmartGraph& _G, T a) : 
-        G(_G), container(G.edgeNum(), a) { }
+        G(_G), container(G.maxEdgeId(), a) { }
       void set(EdgeIt e, T a) { container[e.n]=a; }
       T get(EdgeIt e) const { return container[e.n]; }
       T& operator[](EdgeIt e) { return container[e.n]; } 
       const T& operator[](EdgeIt e) const { return container[e.n]; } 
-      void update() { container.resize(G.edgeNum()); }
-      void update(T a) { container.resize(G.edgeNum(), a); }
-    };
-
-
-
-
+      void update() { container.resize(G.maxEdgeId()); }
+      void update(T a) { container.resize(G.maxEdgeId(), a); }
+    };
+
+    template <typename T> class DynNodeMap : public DynMapBase<NodeIt>
+    {
+      std::vector<T> container;
+
+    public:
+      typedef T ValueType;
+      typedef NodeIt KeyType;
+
+      DynNodeMap(SmartGraph &_G) :
+        DynMapBase<NodeIt>(_G), container(_G.maxNodeId())
+      {
+        //FIXME: What if there are empty Id's?
+        G->dyn_node_maps.push_back(this);
+      }
+      ~DynNodeMap()
+      {
+        if(G) {
+          std::vector<DynMapBase<NodeIt>* >::iterator i;
+          for(i=G->dyn_node_maps.begin();
+              i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
+          if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
+        }
+      }
+
+      void add(const NodeIt k) 
+      {
+        if(k.n>=container.size()) container.resize(k.n+1);
+      }
+      void erase(const NodeIt k)
+      {
+        //FIXME: Please implement me.
+      }
+      
+      void set(NodeIt n, T a) { container[n.n]=a; }
+      T get(NodeIt n) const { return container[n.n]; }
+      T& operator[](NodeIt n) { return container[n.n]; }
+      const T& operator[](NodeIt n) const { return container[n.n]; }
+
+      void update() {}    //Useless for DynMaps
+      void update(T a) {}  //Useless for DynMaps
+    };
+    
+    template <typename T> class DynEdgeMap : public DynMapBase<EdgeIt>
+    {
+      std::vector<T> container;
+
+    public:
+      typedef T ValueType;
+      typedef EdgeIt KeyType;
+
+      DynEdgeMap(SmartGraph &_G) :
+        DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())
+      {
+        //FIXME: What if there are empty Id's?
+        //FIXME: Can I do that? :
+        G->dyn_edge_maps.push_back(this);
+      }
+      ~DynEdgeMap()
+      {
+        if(G) {
+          std::vector<DynMapBase<EdgeIt>* >::iterator i;
+          for(i=G->dyn_edge_maps.begin();
+              i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
+          if(*i==this) G->dyn_edge_maps.erase(i); //FIXME: Way too slow...
+        }
+      }
+
+      void add(const EdgeIt k) 
+      {
+        if(k.n>=int(container.size())) container.resize(k.n+1);
+      }
+      void erase(const EdgeIt k)
+      {
+        //FIXME: Please implement me.
+      }
+      
+      void set(EdgeIt n, T a) { container[n.n]=a; }
+      T get(EdgeIt n) const { return container[n.n]; }
+      T& operator[](EdgeIt n) { return container[n.n]; }
+      const T& operator[](EdgeIt n) const { return container[n.n]; }
+
+      void update() {}    //Useless for DynMaps
+      void update(T a) {}  //Useless for DynMaps
+    };
+        
   };
 } //namespace hugo