Changeset 1009:8cb323dbae93 in lemon-0.x for src/work/marci

Timestamp:

11/19/04 18:22:29 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

RoadMap? to STGraphWrapper

Location:

src/work/marci

Files:

• merge_node_graph_wrapper.h (modified) (6 diffs)
• merge_node_graph_wrapper_test.cc (modified) (6 diffs)

src/work/marci/merge_node_graph_wrapper.h

@@ -39 +39 @@
   };
 
+  /*! A base class for merging the node-set of two node-disjoint graphs 
+    into the node-set of one graph.
+   */
   template <typename _Graph1, typename _Graph2, typename Enable=void>
   class MergeNodeGraphWrapperBase : 
     public P1<_Graph1>, public P2<_Graph2> {
   public:
-    void print() const { std::cout << "generic" << std::endl; }
+    void printNode() const { std::cout << "generic" << std::endl; }
     typedef _Graph1 Graph1;
     typedef _Graph2 Graph2;
@@ -140 +143 @@
           ParentMap2::set(n, value);
       }
-      using ParentMap1::operator[];
-      using ParentMap2::operator[];
+//       using ParentMap1::operator[];
+//       using ParentMap2::operator[];
     };
 
@@ -153 +156 @@
     public P1<_Graph1>, public P2<_Graph2> {
   public :
-    void print() const { std::cout << "same" << std::endl; }
+    void printNode() const { std::cout << "same" << std::endl; }
     typedef _Graph1 Graph1;
     typedef _Graph2 Graph2;
@@ -176 +179 @@
     public P1<_Graph1>, public P2<_Graph2> {
   public :
-    void print() const { std::cout << "2. nagyobb" << std::endl; }
+    void printNode() const { std::cout << "2. nagyobb" << std::endl; }
     typedef _Graph1 Graph1;
     typedef _Graph2 Graph2;
@@ -199 +202 @@
     public P1<_Graph1>, public P2<_Graph2> {
   public :
-    void print() const { std::cout << "1. nagyobb" << std::endl; }
+    void printNode() const { std::cout << "1. nagyobb" << std::endl; }
     typedef _Graph1 Graph1;
     typedef _Graph2 Graph2;
@@ -216 +219 @@
 
 
+  template <typename _Graph1, typename _Graph2>
+  class MergeNodeGraphWrapper : public 
+  IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2> > {
+  public:
+    typedef _Graph1 Graph1;
+    typedef _Graph2 Graph2;
+    typedef IterableGraphExtender<
+      MergeNodeGraphWrapperBase<_Graph1, _Graph2> > Parent;
+  protected:
+    MergeNodeGraphWrapper() { }
+  public:
+    MergeNodeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) { 
+      Parent::Parent1::setGraph(_graph1);
+      Parent::Parent2::setGraph(_graph2);
+    }
+  };
+
+
+  /*! A base class for merging the node-sets and edge-sets of 
+    two node-disjoint graphs 
+    into one graph.
+   */
   template <typename _Graph1, typename _Graph2, typename Enable=void>
-  class MergeNodeGraphWrapper : public 
-  IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2, Enable> > {
+  class MergeEdgeGraphWrapperBase : 
+    public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
+  public:
+    void printEdge() const { std::cout << "generic" << std::endl; }
+    typedef _Graph1 Graph1;
+    typedef _Graph2 Graph2;
+    typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
+    typedef typename Parent::Parent1 Parent1;
+    typedef typename Parent::Parent2 Parent2;
+//     typedef P1<_Graph1> Parent1;
+//     typedef P2<_Graph2> Parent2;
+    typedef typename Parent1::Edge Graph1Edge;
+    typedef typename Parent2::Edge Graph2Edge;
+  protected:
+    MergeEdgeGraphWrapperBase() { }
+  public:
+    template <typename _Value> class EdgeMap;
+
+    typedef typename Parent::Node Node;
+
+    class Edge : public Graph1Edge, public Graph2Edge {
+      friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>;
+      template <typename Value> friend class EdgeMap;
+    protected:
+      bool backward; //true, iff backward
+    public:
+      Edge() { }
+      /// \todo =false is needed, or causes problems?
+      /// If \c _backward is false, then we get an edge corresponding to the 
+      /// original one, otherwise its oppositely directed pair is obtained.
+      Edge(const Graph1Edge& n1, 
+           const Graph2Edge& n2, bool _backward) : 
+        Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
+      Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
+      bool operator==(const Edge& v) const { 
+        return (this->backward==v.backward && 
+                static_cast<Graph1Edge>(*this)==
+                static_cast<Graph1Edge>(v) && 
+                static_cast<Graph2Edge>(*this)==
+                static_cast<Graph2Edge>(v));
+      } 
+      bool operator!=(const Edge& v) const { 
+        return (this->backward!=v.backward || 
+                static_cast<Graph1Edge>(*this)!=
+                static_cast<Graph1Edge>(v) || 
+                static_cast<Graph2Edge>(*this)!=
+                static_cast<Graph2Edge>(v));
+      }
+    };
+
+    using Parent::first;
+    void first(Edge& i) const {
+      Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
+      i.backward=false;
+      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+        Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
+        i.backward=true;
+      }
+    }
+    void firstIn(Edge& i, const Node& n) const {
+      Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
+      i.backward=false;
+      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+        Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
+        i.backward=true;
+      }
+    }
+    void firstOut(Edge& i, const Node& n) const {
+      Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
+      i.backward=false;
+      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+        Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
+        i.backward=true;
+      }
+    }
+
+    using Parent::next;
+    void next(Edge& i) const {
+      if (!(i.backward)) {
+        Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
+        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+          Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
+          i.backward=true;
+        }
+      } else {
+        Parent2::graph->next(*static_cast<Graph2Edge*>(&i));
+      }
+    }
+    void nextIn(Edge& i) const {
+      if (!(i.backward)) {
+        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
+        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+          Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
+          i.backward=true;
+        }
+      } else {
+        Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
+      }
+    }
+    void nextOut(Edge& i) const {
+      if (!(i.backward)) {
+        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
+        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+          Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
+          i.backward=true;
+        }
+      } else {
+        Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
+      }
+    }
+
+    Node source(const Edge& i) const {
+      if (!(i.backward)) {
+        return 
+          Node(Parent1::graph->source(i), INVALID, false);
+      } else {
+        return 
+          Node(INVALID, Parent2::graph->source(i), true);
+      }
+    }
+
+    Node target(const Edge& i) const {
+      if (!(i.backward)) {
+        return 
+          Node(Parent1::graph->target(i), INVALID, false);
+      } else {
+        return 
+          Node(INVALID, Parent2::graph->target(i), true);
+      }
+    }
+
+    using Parent::id;
+    int id(const Edge& n) const { 
+      if (!n.backward) 
+        return this->Parent1::graph->id(n);
+      else
+        return this->Parent2::graph->id(n);
+    }
+
+    template <typename _Value> 
+    class EdgeMap : public Parent1::template EdgeMap<_Value>, 
+                    public Parent2::template EdgeMap<_Value> { 
+      typedef typename Parent1::template EdgeMap<_Value> ParentMap1;
+      typedef typename Parent2::template EdgeMap<_Value> ParentMap2;
+    public:
+      typedef _Value Value;
+      typedef Edge Key;
+      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) : 
+        ParentMap1(gw), ParentMap2(gw) { }
+      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw, 
+              const _Value& value) : 
+        ParentMap1(gw, value), ParentMap2(gw, value) { }
+      _Value operator[](const Edge& n) const {
+        if (!n.backward) 
+          return ParentMap1::operator[](n);
+        else 
+          return ParentMap2::operator[](n);
+      }
+      void set(const Edge& n, const _Value& value) {
+        if (!n.backward) 
+          ParentMap1::set(n, value);
+        else 
+          ParentMap2::set(n, value);
+      }
+//       using ParentMap1::operator[];
+//       using ParentMap2::operator[];
+    };
+
+  };
+
+
+  template <typename _Graph1, typename _Graph2>
+  class MergeEdgeGraphWrapper : public 
+  IterableGraphExtender<MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > {
   public:
     typedef _Graph1 Graph1;
     typedef _Graph2 Graph2;
     typedef IterableGraphExtender<
-      MergeNodeGraphWrapperBase<_Graph1, _Graph2, Enable> > Parent;
-  protected:
-    MergeNodeGraphWrapper() { }
-  public:
-    MergeNodeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) { 
+      MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > Parent;
+  protected:
+    MergeEdgeGraphWrapper() { }
+  public:
+    MergeEdgeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) { 
       Parent::Parent1::setGraph(_graph1);
       Parent::Parent2::setGraph(_graph2);

src/work/marci/merge_node_graph_wrapper_test.cc

@@ -1 +1 @@
 #include <iostream>
+#include <fstream>
 
 #include <lemon/list_graph.h>
 #include <lemon/smart_graph.h>
+#include <lemon/dimacs.h>
 #include <merge_node_graph_wrapper.h>
 
@@ -24 +26 @@
   typedef ListGraph Graph2;
   
-//   {
-//     checkConcept<StaticGraph, NewEdgeSetGraphWrapper<Graph1, Graph2> >(); 
-//   }
   {
+    checkConcept<StaticGraph, NewEdgeSetGraphWrapper<Graph1, Graph2> >(); 
+  }
+  {
+    checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph2> >(); 
+  }
+  
   Graph1 g;
   Graph2 h;
-  typedef MergeNodeGraphWrapper<Graph1, Graph2> GW;
+  typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW;
   GW gw(g, h);
-  Graph1::Node n1=g.addNode();
-  Graph1::Node n2=g.addNode();
-  Graph1::Node n3=g.addNode();
-  Graph2::Node n4=h.addNode();
-  Graph2::Node n5=h.addNode();
+
+  std::ifstream f1("graph1.dim");
+  std::ifstream f2("graph2.dim");
+  readDimacs(f1, g);
+  readDimacs(f2, h);
+  {
+
+//   Graph1::Node n1=g.addNode();
+//   Graph1::Node n2=g.addNode();
+//   Graph1::Node n3=g.addNode();
+//   Graph2::Node n4=h.addNode();
+//   Graph2::Node n5=h.addNode();
+//   Graph2::Node n6=h.addNode();
+//   Graph1::Edge e1=g.addEdge(n1, n2);
+//   Graph1::Edge e2=g.addEdge(n1, n3);
+//   Graph2::Edge e3=h.addEdge(n4, n5);
+//   Graph2::Edge e4=h.addEdge(n4, n5);
   //GW::NodeIt n(gw)
+  cout << "1st graph" << endl;
+  cout << " nodes:" << endl;
+  for (Graph1::NodeIt n(g); n!=INVALID; ++n) { 
+    cout << "  " << g.id(n) << endl;
+  }
+  cout << " edges:" << endl;
+  for (Graph1::EdgeIt n(g); n!=INVALID; ++n) { 
+    cout << "  " << g.id(n) << ": " 
+         << g.id(g.source(n)) << "->" << g.id(g.target(n)) << endl;
+  }
+  cout << "2nd graph" << endl;
+  cout << " nodes:" << endl;
+  for (Graph2::NodeIt n(h); n!=INVALID; ++n) { 
+    cout << "  " << h.id(n) << endl;
+  }
+  cout << " edges:" << endl;
+  for (Graph2::EdgeIt n(h); n!=INVALID; ++n) { 
+    cout << "  " << h.id(n) << ": " 
+         << h.id(h.source(n)) << "->" << h.id(h.target(n)) << endl;
+  }
+  cout << "merged graph" << endl;
+  cout << " nodes:" << endl;
   for (GW::NodeIt n(gw); n!=INVALID; ++n) { 
-    cout << gw.id(n) << endl;
+    cout << "  "<< gw.id(n) << endl;
+  }
+  cout << " edges:" << endl;
+  for (GW::EdgeIt n(gw); n!=INVALID; ++n) { 
+    cout << "  " << gw.id(n) << ": " 
+         << gw.id(gw.source(n)) << "->" << gw.id(gw.target(n)) << endl;
   }
 
@@ -49 +93 @@
   }
   for (Graph1::NodeIt n(g); n!=INVALID; ++n) { 
-    cout << nm[n] << endl;
+    cout << nm[GW::Node(n,INVALID,false)] << endl;
   }
   for (Graph2::NodeIt n(h); n!=INVALID; ++n) { 
-    cout << nm[n] << endl;
+    cout << nm[GW::Node(INVALID,n,true)] << endl;
   }
 
-  gw.print();
+  gw.printNode();
 
   {
@@ -65 +109 @@
     typedef MergeNodeGraphWrapper<Graph1, Graph2> GW;
     GW gw(g, h);    
-    gw.print();
+    gw.printNode();
   }
   {
@@ -75 +119 @@
     typedef MergeNodeGraphWrapper<Graph1, Graph2> GW;
     GW gw(g, h);    
-    gw.print();
+    gw.printNode();
   }
   {
@@ -85 +129 @@
     typedef MergeNodeGraphWrapper<Graph1, Graph2> GW;
     GW gw(g, h);    
-    gw.print();
+    gw.printNode();
   }
   }