src/work/marci/leda/bipartite_matching_comparison.cc
author marci
Wed, 26 Jan 2005 15:54:06 +0000
changeset 1097 c91e765266d7
parent 921 818510fa3d99
permissions -rw-r--r--
A proposal or test implementation for linear expression`
marci@617
     1
// -*- c++ -*-
marci@617
     2
#include <iostream>
marci@617
     3
#include <fstream>
marci@617
     4
#include <vector>
marci@617
     5
#include <cstdlib>
marci@617
     6
marci@617
     7
#include <LEDA/graph.h>
marci@617
     8
#include <LEDA/mcb_matching.h>
marci@617
     9
#include <LEDA/list.h>
marci@617
    10
#include <LEDA/graph_gen.h>
marci@617
    11
marci@617
    12
#include <leda_graph_wrapper.h>
marci@648
    13
#include <sage_graph.h>
marci@617
    14
//#include <smart_graph.h>
marci@617
    15
//#include <dimacs.h>
alpar@921
    16
#include <lemon/time_measure.h>
marci@769
    17
#include <for_each_macros.h>
alpar@921
    18
#include <lemon/graph_wrapper.h>
marci@617
    19
#include <bipartite_graph_wrapper.h>
alpar@921
    20
#include <lemon/maps.h>
alpar@921
    21
#include <lemon/max_flow.h>
marci@617
    22
marci@770
    23
using std::cin;
marci@769
    24
using std::cout;
marci@769
    25
using std::endl;
marci@617
    26
alpar@921
    27
using namespace lemon;
marci@617
    28
marci@617
    29
int main() {
marci@617
    30
  //for leda graph
marci@617
    31
  leda::graph lg;
marci@617
    32
  //lg.make_undirected();
marci@617
    33
  typedef LedaGraphWrapper<leda::graph> Graph;
marci@617
    34
  Graph g(lg);
marci@617
    35
marci@648
    36
  //for UndirSageGraph
marci@648
    37
  //typedef UndirSageGraph Graph; 
marci@617
    38
  //Graph g;
marci@617
    39
marci@617
    40
  typedef Graph::Node Node;
marci@617
    41
  typedef Graph::NodeIt NodeIt;
marci@617
    42
  typedef Graph::Edge Edge;
marci@617
    43
  typedef Graph::EdgeIt EdgeIt;
marci@617
    44
  typedef Graph::OutEdgeIt OutEdgeIt;
marci@617
    45
marci@617
    46
  std::vector<Graph::Node> s_nodes;
marci@617
    47
  std::vector<Graph::Node> t_nodes;
marci@617
    48
marci@617
    49
  int a;
marci@769
    50
  cout << "number of nodes in the first color class=";
marci@770
    51
  cin >> a; 
marci@617
    52
  int b;
marci@769
    53
  cout << "number of nodes in the second color class=";
marci@770
    54
  cin >> b; 
marci@617
    55
  int m;
marci@769
    56
  cout << "number of edges=";
marci@770
    57
  cin >> m; 
marci@617
    58
  int k;
marci@769
    59
  cout << "A bipartite graph is a random group graph if the color classes \nA and B are partitiones to A_0, A_1, ..., A_{k-1} and B_0, B_1, ..., B_{k-1} \nas equally as possible \nand the edges from A_i goes to A_{i-1 mod k} and A_{i+1 mod k}.\n";
marci@769
    60
  cout << "number of groups in LEDA random group graph=";
marci@770
    61
  cin >> k; 
marci@769
    62
  cout << endl;
marci@617
    63
  
marci@617
    64
  leda_list<leda_node> lS;
marci@617
    65
  leda_list<leda_node> lT;
marci@617
    66
  random_bigraph(lg, a, b, m, lS, lT, k);
marci@617
    67
marci@617
    68
  Graph::NodeMap<int> ref_map(g, -1);
marci@617
    69
  IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
marci@617
    70
marci@617
    71
  //generating leda random group graph
marci@617
    72
  leda_node ln;
marci@617
    73
  forall(ln, lS) bipartite_map.insert(ln, false);
marci@617
    74
  forall(ln, lT) bipartite_map.insert(ln, true);
marci@617
    75
marci@617
    76
  //making bipartite graph
marci@617
    77
  typedef BipartiteGraphWrapper<Graph> BGW;
marci@617
    78
  BGW bgw(g, bipartite_map);
marci@617
    79
marci@617
    80
marci@617
    81
  //st-wrapper
marci@768
    82
  typedef stBipartiteGraphWrapper<BGW> stGW;
marci@617
    83
  stGW stgw(bgw);
marci@617
    84
  ConstMap<stGW::Edge, int> const1map(1);
marci@617
    85
  stGW::EdgeMap<int> flow(stgw);
marci@617
    86
marci@617
    87
  Timer ts;
marci@617
    88
marci@617
    89
  ts.reset();
marci@617
    90
  FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
marci@617
    91
  MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
marci@617
    92
    max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
marci@617
    93
  max_flow_test.run();
alpar@921
    94
  cout << "LEMON max matching algorithm based on preflow." << endl 
marci@617
    95
	    << "Size of matching: " 
marci@769
    96
	    << max_flow_test.flowValue() << endl;
marci@769
    97
  cout << "elapsed time: " << ts << endl << endl;
marci@617
    98
marci@617
    99
  ts.reset();  
marci@617
   100
  leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
marci@769
   101
  cout << "LEDA max matching algorithm." << endl 
marci@617
   102
	    << "Size of matching: " 
marci@769
   103
	    << ml.size() << endl;
marci@769
   104
  cout << "elapsed time: " << ts << endl << endl;
marci@617
   105
marci@617
   106
//   ts.reset();
marci@617
   107
//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
marci@648
   108
//   typedef SageGraph MutableGraph;
marci@617
   109
//   while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { }
alpar@921
   110
//   cout << "LEMON max matching algorithm based on blocking flow augmentation." 
marci@769
   111
// 	    << endl << "Matching size: " 
marci@769
   112
// 	    << max_flow_test.flowValue() << endl;
marci@769
   113
//   cout << "elapsed time: " << ts << endl << endl;
marci@617
   114
marci@617
   115
  {
marci@648
   116
  SageGraph hg;
marci@648
   117
  SageGraph::Node s=hg.addNode();  
marci@648
   118
  SageGraph::Node t=hg.addNode();
marci@648
   119
  BGW::NodeMap<SageGraph::Node> b_s_nodes(bgw);  
marci@648
   120
  BGW::NodeMap<SageGraph::Node> b_t_nodes(bgw);
marci@617
   121
  
marci@617
   122
  FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, BGW::S_CLASS) {
marci@617
   123
    b_s_nodes.set(n, hg.addNode());
marci@617
   124
    hg.addEdge(s, b_s_nodes[n]);
marci@617
   125
  }
marci@617
   126
  FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, BGW::T_CLASS) {
marci@617
   127
    b_t_nodes.set(n, hg.addNode());
marci@617
   128
    hg.addEdge(b_t_nodes[n], t);
marci@617
   129
  }
marci@617
   130
marci@617
   131
  FOR_EACH_LOC(BGW::EdgeIt, e, bgw) 
alpar@986
   132
    hg.addEdge(b_s_nodes[bgw.source(e)], b_t_nodes[bgw.target(e)]);
marci@617
   133
marci@648
   134
  ConstMap<SageGraph::Edge, int> cm(1);
marci@648
   135
  SageGraph::EdgeMap<int> flow(hg); //0
marci@617
   136
  
marci@617
   137
  Timer ts;
marci@617
   138
marci@617
   139
  ts.reset();
marci@648
   140
  MaxFlow<SageGraph, int, ConstMap<SageGraph::Edge, int>, 
marci@648
   141
    SageGraph::EdgeMap<int> > 
marci@617
   142
    max_flow_test(hg, s, t, cm, flow);
marci@617
   143
  max_flow_test.run();
alpar@921
   144
  cout << "LEMON max matching algorithm on SageGraph by copying the graph, based on preflow." 
marci@769
   145
	    << endl 
marci@617
   146
	    << "Size of matching: " 
marci@769
   147
	    << max_flow_test.flowValue() << endl;
marci@769
   148
  cout << "elapsed time: " << ts << endl << endl;
marci@617
   149
  }
marci@617
   150
marci@617
   151
  return 0;
marci@617
   152
}