src/work/marci/merge_node_graph_wrapper_test.cc
author alpar
Sat, 08 Jan 2005 20:16:56 +0000
changeset 1062 8226427845bc
parent 1016 18d009b23e42
permissions -rw-r--r--
- Parallel edge support (without arrowheads)
- Texts on the nodes
     1 #include <iostream>
     2 #include <fstream>
     3 
     4 #include <lemon/list_graph.h>
     5 #include <lemon/smart_graph.h>
     6 #include <lemon/dimacs.h>
     7 #include <lemon/preflow.h>
     8 #include <lemon/full_graph.h>
     9 #include <merge_node_graph_wrapper.h>
    10 
    11 #include<lemon/concept_check.h>
    12 #include<lemon/concept/graph.h>
    13 
    14 using std::cout;
    15 using std::endl;
    16 
    17 using namespace lemon;
    18 using namespace lemon::concept;
    19 
    20 class Graph3 : ListGraph {
    21 public:
    22   class Node : public ListGraph::Node { };
    23   class Edge { };
    24 };
    25 
    26 template <typename Graph>
    27 void printGraph(const Graph& g) {
    28   cout << " nodes:" << endl;
    29   for (typename Graph::NodeIt n(g); n!=INVALID; ++n) { 
    30     cout << "  " << g.id(n) << ": out edges:" << endl;
    31     for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) 
    32       cout << "   " << g.id(g.source(e)) << "->" << g.id(g.target(e)) << endl;
    33   }
    34   cout << " edges:" << endl;
    35   for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) { 
    36     cout << "   " << g.id(e) << ": " 
    37 	 << g.id(g.source(e)) << "->" << g.id(g.target(e)) << endl;
    38   }  
    39 }
    40 
    41 int main() {
    42   {
    43     cout << "FIRST TEST" << endl;
    44     //typedef SmartGraph Graph1;
    45     typedef ListGraph Graph1;
    46     typedef ListGraph Graph2;
    47     typedef SmartGraph Graph3;
    48     
    49 //     {
    50 //       checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph2> >();   
    51 //       MergeEdgeGraphWrapper<Graph1, Graph2>::printNode(); 
    52 //       MergeEdgeGraphWrapper<Graph1, Graph2>::printEdge(); 
    53 //       checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph1> >();   
    54 //       MergeEdgeGraphWrapper<Graph1, Graph1>::printNode(); 
    55 //       MergeEdgeGraphWrapper<Graph1, Graph1>::printEdge(); 
    56 //       typedef ResGraphWrapper<Graph1, int, 
    57 // 	ConstMap<Graph1, int>, ConstMap<Graph1, int> > Graph4;
    58 //       checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph4> >();   
    59 //       MergeEdgeGraphWrapper<Graph1, Graph4>::printNode(); 
    60 //       MergeEdgeGraphWrapper<Graph1, Graph4>::printEdge();
    61 //       checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph4, Graph1> >();   
    62 //       MergeEdgeGraphWrapper<Graph4, Graph1>::printNode(); 
    63 //       MergeEdgeGraphWrapper<Graph4, Graph1>::printEdge();  
    64 //     }
    65   
    66     Graph1 g1;
    67     Graph2 g2;
    68     typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW;
    69     GW gw(g1, g2);
    70     Graph1::Node s1, t1;
    71     Graph2::Node s2, t2;
    72     Graph1::EdgeMap<int> cap1(g1);
    73     Graph2::EdgeMap<int> cap2(g2);
    74 
    75     std::ifstream f1("graph1.dim");
    76     std::ifstream f2("graph2.dim");
    77     readDimacs(f1, g1);
    78     readDimacs(f2, g2);
    79 
    80 //     GW::NodeMap<int> ize(gw, 8);
    81 //     for (GW::NodeIt n(gw); n!=INVALID; ++n) ize.set(n, 9);
    82 //     GW::EdgeMap<int> mize(gw, 8);
    83 //     for (GW::EdgeIt n(gw); n!=INVALID; ++n) mize.set(n, 7);
    84 
    85 //     std::ifstream f1("flow-1.dim");
    86 //     std::ifstream f2("flow2.dim");
    87 //     readDimacs(f1, g1, cap1, s1, t1);
    88 //     readDimacs(f2, g2, cap2, s2, t2);
    89     
    90 //     GW::EdgeMap<int> cap(gw);
    91 //     for (GW::EdgeIt e(gw); e!=INVALID; ++e) {
    92 //       if (gw.forward(e)) cap.set(e, cap1[e]);
    93 //       if (gw.backward(e)) cap.set(e, cap2[e]);
    94 //     }
    95 
    96 //     {
    97 //       GW::EdgeMap<int> flow(gw, 0);
    98 //       Preflow<GW, int> preflow(gw, GW::Node(s1, INVALID, false), 
    99 // 			       GW::Node(t1, INVALID, false), cap, flow);
   100 //       preflow.run();
   101 //       std::cout << "s1->t1: " << preflow.flowValue() << std::endl; 
   102 //     }
   103 //     {
   104 //       GW::EdgeMap<int> flow(gw, 0);
   105 //       Preflow<GW, int> preflow(gw, GW::Node(INVALID, s2, true), 
   106 // 			       GW::Node(INVALID, t2, true), cap, flow);
   107 //       preflow.run();
   108 //       std::cout << "s2->t2: " << preflow.flowValue() << std::endl; 
   109 //     }
   110 //     {
   111 //       GW::EdgeMap<int> flow(gw, 0);
   112 //       Preflow<GW, int> preflow(gw, GW::Node(s1, INVALID, false), 
   113 // 			       GW::Node(INVALID, t2, true), cap, flow);
   114 //       preflow.run();
   115 //       std::cout << "s1->t2: " << preflow.flowValue() << std::endl; 
   116 //     }
   117 //     {
   118 //       GW::EdgeMap<int> flow(gw, 0);
   119 //       Preflow<GW, int> preflow(gw, GW::Node(INVALID, s2, true), 
   120 // 			       GW::Node(s1, INVALID, false), cap, flow);
   121 //       preflow.run();
   122 //       std::cout << "s2->t1: " << preflow.flowValue() << std::endl; 
   123 //     }
   124      cout << "1st graph" << endl;
   125      printGraph(g1);
   126 
   127      cout << "2nd graph" << endl;
   128      printGraph(g2);
   129 
   130      cout << "merged graph" << endl;
   131      printGraph(gw);
   132      
   133 //      for (GW::NodeIt n(gw); n!=INVALID; ++n) 
   134 //        std::cout << ize[n] << std::endl;
   135 //      for (GW::EdgeIt n(gw); n!=INVALID; ++n) 
   136 //        std::cout << mize[n] << std::endl;
   137      
   138      typedef NewEdgeSetGraphWrapper2<GW, Graph3> GWW;
   139 //     {
   140 //       checkConcept<StaticGraph, GWW>();   
   141 //     }
   142 
   143      GWW gww(gw);
   144  
   145      cout << "new edges graph" << endl;
   146      printGraph(gww);
   147 
   148      GWW::NodeIt n(gww);
   149      GWW::Node n1=n; 
   150      ++n;
   151      GWW::Node n2=n; 
   152      gww.addEdge(n1, n2);
   153      //     gww.addNode();
   154      //     gww.addNode();
   155 
   156      cout << "new edges graph" << endl;
   157      printGraph(gww);
   158 
   159      typedef AugmentingGraphWrapper<GW, GWW> GWWW;
   160      //     {
   161      //       checkConcept<StaticGraph, GWWW>();   
   162      //     }
   163      GWWW gwww(gw, gww);
   164 
   165      cout << "fully merged graph" << endl;
   166      printGraph(gwww);
   167   }
   168 
   169 
   170   {
   171     cout << "SECOND TEST" << endl;
   172     typedef SmartGraph Graph1;
   173 //     {
   174 //       checkConcept<StaticGraph, Graph1>();
   175 //     }
   176 
   177     Graph1 g1;
   178 
   179     FullGraph pre_g2(2);
   180     ConstMap<FullGraph::Edge, bool> const_false_map(false);
   181     typedef EdgeSubGraphWrapper<FullGraph, ConstMap<FullGraph::Edge, bool> >
   182       Graph2;
   183 //     {
   184 //       checkConcept<StaticGraph, Graph2>();
   185 //     }
   186 
   187     Graph2 g2(pre_g2, const_false_map);
   188 
   189     typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW;
   190 //     {
   191 //       checkConcept<StaticGraph, GW>();   
   192 //     }
   193     GW gw(g1, g2);
   194     GW::Node sw;
   195     GW::Node tw;
   196     {
   197       Graph2::NodeIt k(g2);
   198       sw=GW::Node(INVALID, k, true);
   199       ++k;
   200       tw=GW::Node(INVALID, k, true);
   201     }
   202 
   203     std::ifstream f1("graph2.dim");
   204     readDimacs(f1, g1);
   205 
   206     cout << "1st graph" << endl;
   207     printGraph(g1);
   208 
   209     cout << "2nd graph" << endl;
   210     printGraph(g2);
   211 
   212     cout << "merged graph" << endl;
   213     printGraph(gw);
   214 
   215     typedef ListGraph Graph3;
   216     //typedef SmartGraph Graph3;
   217     Graph3 g3;
   218     GW::NodeMap<Graph3::Node> gwn(gw);
   219     Graph3::NodeMap<GW::Node> g3n(g3);
   220     for (GW::NodeIt n(gw); n!=INVALID; ++n) {
   221       Graph3::Node m=g3.addNode();
   222       gwn.set(n, m);
   223       g3n.set(m, n);
   224     }
   225 
   226     typedef NewEdgeSetGraphWrapper<GW, Graph3> GWW;
   227 //     {
   228 //       checkConcept<StaticGraph, GWW>();   
   229 //     }
   230 
   231     GWW gww(gw, g3, gwn, g3n);
   232 
   233     for (Graph1::NodeIt n(g1); n!=INVALID; ++n) {
   234       g3.addEdge(gwn[sw], gwn[GW::Node(n,INVALID,false)]);
   235     }
   236 
   237 //     for (Graph1::NodeIt n(g1); n!=INVALID; ++n) {
   238 //       gww.addEdge(sw, GW::Node(n,INVALID,false));
   239 //     }
   240 
   241     cout << "new edges" << endl;
   242     printGraph(g3);
   243 
   244     cout << "new edges in the new graph" << endl;
   245     printGraph(gww);
   246 
   247     typedef AugmentingGraphWrapper<GW, GWW> GWWW;
   248 //     {
   249 //       checkConcept<StaticGraph, GWWW>();   
   250 //     }
   251     GWWW gwww(gw, gww);
   252 
   253     cout << "new edges merged into the original graph" << endl;
   254     printGraph(gwww);
   255 
   256   }
   257 
   258 }