src/work/marci/bipartite_matching_try_3.cc
changeset 768 a5e9303a5511
parent 762 511200bdb71f
equal deleted inserted replaced
9:c15e4f798a62 10:593072769517
    15 #include <graph_gen.h>
    15 #include <graph_gen.h>
    16 #include <max_bipartite_matching.h>
    16 #include <max_bipartite_matching.h>
    17 
    17 
    18 using namespace hugo;
    18 using namespace hugo;
    19 
    19 
       
    20 using std::cout;
       
    21 using std::endl;
       
    22 
    20 int main() {
    23 int main() {
    21   //typedef UndirListGraph Graph; 
    24   //typedef UndirListGraph Graph; 
    22   typedef BipartiteGraph<SageGraph> Graph;
    25   typedef BipartiteGraph<SageGraph> Graph;
    23   
    26   
    24   typedef Graph::Node Node;
    27   typedef Graph::Node Node;
    28   typedef Graph::OutEdgeIt OutEdgeIt;
    31   typedef Graph::OutEdgeIt OutEdgeIt;
    29 
    32 
    30   Graph g;
    33   Graph g;
    31 
    34 
    32   int a;
    35   int a;
    33   std::cout << "number of nodes in the first color class=";
    36   cout << "number of nodes in the first color class=";
    34   std::cin >> a; 
    37   std::cin >> a; 
    35   int b;
    38   int b;
    36   std::cout << "number of nodes in the second color class=";
    39   cout << "number of nodes in the second color class=";
    37   std::cin >> b; 
    40   std::cin >> b; 
    38   int m;
    41   int m;
    39   std::cout << "number of edges=";
    42   cout << "number of edges=";
    40   std::cin >> m; 
    43   std::cin >> m; 
    41   
    44   
    42   std::cout << "Generatig a random bipartite graph..." << std::endl;
    45   cout << "Generatig a random bipartite graph..." << endl;
    43   random_init();
    46   random_init();
    44   randomBipartiteGraph(g, a, b, m);
    47   randomBipartiteGraph(g, a, b, m);
    45 
    48 
    46 //   std::cout << "Edges of the bipartite graph:" << std::endl;
    49 //   cout << "Edges of the bipartite graph:" << endl;
    47 //   FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " ";
    50 //   FOR_EACH_LOC(EdgeIt, e, g) cout << e << " ";
    48 //   std::cout << std::endl;
    51 //   cout << endl;
    49 
    52 
    50 //   std::cout << "Nodes:" << std::endl;
    53 //   cout << "Nodes:" << endl;
    51 //   FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " ";
    54 //   FOR_EACH_LOC(Graph::NodeIt, v, g) cout << v << " ";
    52 //   std::cout << std::endl;
    55 //   cout << endl;
    53 //   std::cout << "Nodes in T:" << std::endl;
    56 //   cout << "Nodes in T:" << endl;
    54 //   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
    57 //   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) cout << v << " ";
    55 //   std::cout << std::endl;
    58 //   cout << endl;
    56 //   std::cout << "Nodes in S:" << std::endl;
    59 //   cout << "Nodes in S:" << endl;
    57 //   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
    60 //   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) cout << v << " ";
    58 //   std::cout << std::endl;
    61 //   cout << endl;
    59 
    62 
    60 //   std::cout << "Erasing the first node..." << std::endl;
    63 //   cout << "Erasing the first node..." << endl;
    61 //   NodeIt n;
    64 //   NodeIt n;
    62 //   g.first(n);
    65 //   g.first(n);
    63 //   g.erase(n);
    66 //   g.erase(n);
    64 //   std::cout << "Nodes of the bipartite graph:" << std::endl;
    67 //   cout << "Nodes of the bipartite graph:" << endl;
    65 //   FOR_EACH_GLOB(n, g) std::cout << n << " ";
    68 //   FOR_EACH_GLOB(n, g) cout << n << " ";
    66 //   std::cout << std::endl;
    69 //   cout << endl;
    67 
    70 
    68 //   std::cout << "Nodes in T:" << std::endl;
    71 //   cout << "Nodes in T:" << endl;
    69 //   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
    72 //   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) cout << v << " ";
    70 //   std::cout << std::endl;
    73 //   cout << endl;
    71 //   std::cout << "Nodes in S:" << std::endl;
    74 //   cout << "Nodes in S:" << endl;
    72 //   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
    75 //   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) cout << v << " ";
    73 //   std::cout << std::endl;
    76 //   cout << endl;
    74 
    77 
    75   typedef stGraphWrapper<Graph> stGW;
    78   typedef stBipartiteGraphWrapper<Graph> stGW;
    76   stGW stgw(g);
    79   stGW stgw(g);
    77   ConstMap<stGW::Edge, int> const1map(1);
    80   ConstMap<stGW::Edge, int> const1map(1);
    78 
    81 
    79   Timer ts;
    82   Timer ts;
       
    83   cout << "max bipartite matching with stGraphWrapper..." << endl;
    80   ts.reset();
    84   ts.reset();
    81   stGW::EdgeMap<int> flow(stgw);
    85   stGW::EdgeMap<int> flow(stgw);
    82   MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
    86   MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
    83     max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
    87     max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
    84   max_flow_test.run();
    88   max_flow_test.run();
    85 //  while (max_flow_test.augmentOnShortestPath()) { }
    89 //  while (max_flow_test.augmentOnShortestPath()) { }
    86 //  typedef ListGraph MutableGraph;
    90 //  typedef ListGraph MutableGraph;
    87 //  while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
    91 //  while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
    88 //  while (max_flow_test.augmentOnBlockingFlow2()) {
    92 //  while (max_flow_test.augmentOnBlockingFlow2()) {
    89 //   std::cout << max_flow_test.flowValue() << std::endl;
    93 //   cout << max_flow_test.flowValue() << endl;
    90 //  }
    94 //  }
    91   std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
    95   cout << "matching value: " << max_flow_test.flowValue() << endl;
    92   std::cout << "elapsed time: " << ts << std::endl;
    96   cout << "elapsed time: " << ts << endl;
    93 //   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 
    97 //   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 
    94 //     if (flow[e]) std::cout << e << std::endl; 
    98 //     if (flow[e]) cout << e << endl; 
    95 //   }
    99 //   }
    96   std::cout << std::endl;
   100   cout << endl;
    97 
   101 
    98   typedef ConstMap<Graph::Edge, int> EdgeCap; 
   102   typedef ConstMap<Graph::Edge, int> EdgeCap; 
    99   EdgeCap ge1(1);
   103   EdgeCap ge1(1);
   100   typedef ConstMap<Graph::Node, int> NodeCap;
   104   typedef ConstMap<Graph::Node, int> NodeCap;
   101   NodeCap gn1(1);
   105   NodeCap gn1(1);
   102   typedef Graph::EdgeMap<int> EdgeFlow;
   106   typedef Graph::EdgeMap<int> EdgeFlow;
   103   EdgeFlow gef(g); //0
   107   EdgeFlow gef(g); //0
   104   typedef Graph::NodeMap<int> NodeFlow; 
   108   typedef Graph::NodeMap<int> NodeFlow; 
   105   NodeFlow gnf(g); //0 
   109   NodeFlow gnf(g); //0 
   106 
   110 
   107   typedef stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> CapMap; 
   111   typedef stGW::EdgeMapWrapper<EdgeCap, NodeCap> CapMap; 
   108   typedef stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap; 
   112   typedef stGW::EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap; 
   109   CapMap cm(ge1, gn1);
   113   CapMap cm(ge1, gn1);
   110   FlowMap fm(gef, gnf);
   114   FlowMap fm(gef, gnf);
   111 
   115 
   112   //Timer ts;
   116   //Timer ts;
       
   117   cout << "max bipartite matching with stGraphWrapper..." << endl;
   113   ts.reset();
   118   ts.reset();
   114   //stGW::EdgeMap<int> flow(stgw);
   119   //stGW::EdgeMap<int> flow(stgw);
   115   MaxFlow<stGW, int, CapMap, FlowMap> 
   120   MaxFlow<stGW, int, CapMap, FlowMap> 
   116     max_flow_test1(stgw, stgw.S_NODE, stgw.T_NODE, cm, fm);
   121     max_flow_test1(stgw, stgw.S_NODE, stgw.T_NODE, cm, fm);
   117   max_flow_test1.run();
   122   max_flow_test1.run();
   118 //  while (max_flow_test.augmentOnShortestPath()) { }
   123 //  while (max_flow_test.augmentOnShortestPath()) { }
   119 //  typedef ListGraph MutableGraph;
   124 //  typedef ListGraph MutableGraph;
   120 //  while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
   125 //  while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
   121 //  while (max_flow_test.augmentOnBlockingFlow2()) {
   126 //  while (max_flow_test.augmentOnBlockingFlow2()) {
   122 //   std::cout << max_flow_test.flowValue() << std::endl;
   127 //   cout << max_flow_test.flowValue() << endl;
   123 //  }
   128 //  }
   124   std::cout << "max flow value: " << max_flow_test1.flowValue() << std::endl;
   129   cout << "matching value: " << max_flow_test1.flowValue() << endl;
   125   std::cout << "elapsed time: " << ts << std::endl;
   130   cout << "elapsed time: " << ts << endl;
   126 //   FOR_EACH_LOC(Graph::EdgeIt, e, g) { 
   131 //   FOR_EACH_LOC(Graph::EdgeIt, e, g) { 
   127 //     if (gef[e]) std::cout << e << std::endl; 
   132 //     if (gef[e]) cout << e << endl; 
   128 //   }
   133 //   }
   129   std::cout << std::endl;
   134   cout << endl;
   130 
   135 
       
   136   cout << "max bipartite matching with stGraphWrapper..." << endl;
   131   ts.reset();
   137   ts.reset();
   132   FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0); 
   138   FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0); 
   133   FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0); 
   139   FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0); 
   134   MaxBipartiteMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>, 
   140   MaxBipartiteMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>, 
   135     Graph::EdgeMap<int>, Graph::NodeMap<int> > 
   141     Graph::EdgeMap<int>, Graph::NodeMap<int> > 
   136     matching_test(g, ge1, gn1, gef, gnf);
   142     matching_test(g, ge1, gn1, gef, gnf);
   137   matching_test.run();
   143   matching_test.run();
   138 
   144 
   139   std::cout << "max flow value: " << matching_test.matchingValue() << std::endl;
   145   cout << "matching value: " << matching_test.matchingValue() << endl;
   140   std::cout << "elapsed time: " << ts << std::endl;
   146   cout << "elapsed time: " << ts << endl;
   141 //   FOR_EACH_LOC(Graph::EdgeIt, e, g) { 
   147 //   FOR_EACH_LOC(Graph::EdgeIt, e, g) { 
   142 //     if (gef[e]) std::cout << e << std::endl; 
   148 //     if (gef[e]) cout << e << endl; 
   143 //   }
   149 //   }
   144   std::cout << std::endl;
   150   cout << endl;
   145 
   151 
       
   152   cout << "max bipartite matching with MaxBipartiteMatching..." << endl;
   146   ts.reset();
   153   ts.reset();
   147   FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0); 
   154   FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0); 
   148   //FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0); 
   155   //FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0); 
   149   MaxBipartiteMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>, 
   156   typedef MaxBipartiteMatching<Graph, ConstMap<Graph::Edge, int>, 
   150     Graph::EdgeMap<int>, Graph::NodeMap<int> > 
   157     ConstMap<Graph::Node, int>, 
   151     matching_test_1(g, ge1, gn1, gef/*, gnf*/);
   158     Graph::EdgeMap<int>, Graph::NodeMap<int> > MaxBipartiteMatching;
       
   159   MaxBipartiteMatching matching_test_1(g, ge1, gn1, gef/*, gnf*/);
   152   matching_test_1.run();
   160   matching_test_1.run();
   153 
   161 
   154   std::cout << "max flow value: " << matching_test_1.matchingValue() << std::endl;
   162   cout << "matching value: " << matching_test_1.matchingValue() << endl;
   155   std::cout << "elapsed time: " << ts << std::endl;
   163   cout << "elapsed time: " << ts << endl;
   156 //   FOR_EACH_LOC(Graph::EdgeIt, e, g) { 
   164 //   FOR_EACH_LOC(Graph::EdgeIt, e, g) { 
   157 //     if (gef[e]) std::cout << e << std::endl; 
   165 //     if (gef[e]) cout << e << endl; 
   158 //   }
   166 //   }
   159   std::cout << std::endl;
   167   cout << endl;
       
   168 
       
   169   cout << "testing optimality with MaxBipartiteMatching..." << endl;
       
   170   ts.reset();
       
   171   matching_test_1.run(MaxBipartiteMatching::GEN_MATCHING);
       
   172   cout << "matching value: " << matching_test_1.matchingValue() << endl;
       
   173   cout << "elapsed time: " << ts << endl;
       
   174 
       
   175   cout << "testing optimality with MaxBipartiteMatching..." << endl;
       
   176   ts.reset();
       
   177   matching_test_1.run(MaxBipartiteMatching::GEN_MATCHING_WITH_GOOD_NODE_FLOW);
       
   178   cout << "matching value: " << matching_test_1.matchingValue() << endl;
       
   179   cout << "elapsed time: " << ts << endl;
   160 
   180 
   161   return 0;
   181   return 0;
   162 }
   182 }