1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/work/marci/bipartite_matching_leda.cc	Mon Apr 26 10:35:36 2004 +0000
     1.3 @@ -0,0 +1,219 @@
     1.4 +// -*- c++ -*-
     1.5 +#include <iostream>
     1.6 +#include <fstream>
     1.7 +#include <vector>
     1.8 +#include <cstdlib>
     1.9 +
    1.10 +#include <LEDA/graph.h>
    1.11 +#include <LEDA/mcb_matching.h>
    1.12 +#include <LEDA/list.h>
    1.13 +
    1.14 +#include <leda_graph_wrapper.h>
    1.15 +#include <list_graph.h>
    1.16 +//#include <smart_graph.h>
    1.17 +//#include <dimacs.h>
    1.18 +#include <time_measure.h>
    1.19 +#include <for_each_macros.h>
    1.20 +#include <bfs_iterator.h>
    1.21 +#include <graph_wrapper.h>
    1.22 +#include <maps.h>
    1.23 +#include <edmonds_karp.h>
    1.24 +#include <preflow.h>
    1.25 +
    1.26 +/**
    1.27 + * Inicializalja a veletlenszamgeneratort.
    1.28 + * Figyelem, ez nem jo igazi random szamokhoz,
    1.29 + * erre ne bizzad a titkaidat!
    1.30 + */
    1.31 +void random_init()
    1.32 +{
    1.33 +	unsigned int seed = getpid();
    1.34 +	seed |= seed << 15;
    1.35 +	seed ^= time(0);
    1.36 +
    1.37 +	srand(seed);
    1.38 +}
    1.39 +
    1.40 +/**
    1.41 + * Egy veletlen int-et ad vissza 0 es m-1 kozott.
    1.42 + */
    1.43 +int random(int m)
    1.44 +{
    1.45 +  return int( double(m) * rand() / (RAND_MAX + 1.0) );
    1.46 +}
    1.47 +
    1.48 +using namespace hugo;
    1.49 +
    1.50 +int main() {
    1.51 +  //for leda graph
    1.52 +  leda::graph lg;
    1.53 +  lg.make_undirected();
    1.54 +  typedef LedaGraphWrapper<leda::graph> Graph;
    1.55 +  Graph g(lg);
    1.56 +
    1.57 +  //for UndirListGraph
    1.58 +  //typedef UndirListGraph Graph; 
    1.59 +  //Graph g;
    1.60 +
    1.61 +  typedef Graph::Node Node;
    1.62 +  typedef Graph::NodeIt NodeIt;
    1.63 +  typedef Graph::Edge Edge;
    1.64 +  typedef Graph::EdgeIt EdgeIt;
    1.65 +  typedef Graph::OutEdgeIt OutEdgeIt;
    1.66 +
    1.67 +  std::vector<Graph::Node> s_nodes;
    1.68 +  std::vector<Graph::Node> t_nodes;
    1.69 +
    1.70 +  int a;
    1.71 +  std::cout << "number of nodes in the first color class=";
    1.72 +  std::cin >> a; 
    1.73 +  int b;
    1.74 +  std::cout << "number of nodes in the second color class=";
    1.75 +  std::cin >> b; 
    1.76 +  int m;
    1.77 +  std::cout << "number of edges=";
    1.78 +  std::cin >> m; 
    1.79 +  
    1.80 +
    1.81 +  for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode());
    1.82 +  for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode());
    1.83 +
    1.84 +  random_init();
    1.85 +  for(int i=0; i<m; ++i) {
    1.86 +    g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
    1.87 +  }
    1.88 +
    1.89 +  Graph::NodeMap<int> ref_map(g, -1);
    1.90 +
    1.91 +  IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
    1.92 +  for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false);
    1.93 +  for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true);
    1.94 +
    1.95 +//   Graph::Node u;
    1.96 +//   std::cout << "These nodes will be in S:\n";
    1.97 +//   //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen 
    1.98 +//   //irni 1etlen FOR_EACH-csel.
    1.99 +//   for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u)) 
   1.100 +//     std::cout << u << " ";
   1.101 +//   std::cout << "\n";
   1.102 +//   std::cout << "These nodes will be in T:\n";
   1.103 +//   for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u)) 
   1.104 +//     std::cout << u << " ";
   1.105 +//   std::cout << "\n";
   1.106 +
   1.107 +  typedef BipartiteGraphWrapper<Graph> BGW;
   1.108 +  BGW bgw(g, bipartite_map);
   1.109 +
   1.110 +//   std::cout << "Nodes by NodeIt:\n";
   1.111 +//   FOR_EACH_LOC(BGW::NodeIt, n, bgw) {
   1.112 +//     std::cout << n << " ";
   1.113 +//   }
   1.114 +//   std::cout << "\n";
   1.115 +//   std::cout << "Nodes in S by ClassNodeIt:\n";
   1.116 +//   FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) {
   1.117 +//     std::cout << n << " ";
   1.118 +//   }
   1.119 +//   std::cout << "\n";
   1.120 +//   std::cout << "Nodes in T by ClassNodeIt:\n";
   1.121 +//   FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) {
   1.122 +//     std::cout << n << " ";
   1.123 +//   }
   1.124 +//   std::cout << "\n";
   1.125 +//   std::cout << "Edges of the bipartite graph:\n";
   1.126 +//   FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
   1.127 +//     std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
   1.128 +//   }
   1.129 +
   1.130 +  BGW::NodeMap<int> dbyj(bgw);
   1.131 +  BGW::EdgeMap<int> dbyxcj(bgw);
   1.132 +
   1.133 +  typedef stGraphWrapper<BGW> stGW;
   1.134 +  stGW stgw(bgw);
   1.135 +  ConstMap<stGW::Edge, int> const1map(1);
   1.136 +//  stGW::NodeMap<int> ize(stgw);
   1.137 +
   1.138 +//   BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
   1.139 +//   Graph::NodeIt si;
   1.140 +//   Graph::Node s; 
   1.141 +//   s=g.first(si);
   1.142 +//   bfs.pushAndSetReached(BGW::Node(s));
   1.143 +//   while (!bfs.finished()) { ++bfs; }
   1.144 +
   1.145 +//   FOR_EACH_LOC(stGW::NodeIt, n, stgw) { 
   1.146 +//     std::cout << "out-edges of " << n << ":\n"; 
   1.147 +//     FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) { 
   1.148 +//       std::cout << " " << e << "\n";
   1.149 +//       std::cout << " aNode: " << stgw.aNode(e) << "\n";
   1.150 +//       std::cout << " bNode: " << stgw.bNode(e) << "\n";      
   1.151 +//     }
   1.152 +//     std::cout << "in-edges of " << n << ":\n"; 
   1.153 +//     FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) { 
   1.154 +//       std::cout << " " << e << "\n";
   1.155 +//       std::cout << " aNode: " << stgw.aNode(e) << "\n";
   1.156 +//       std::cout << " bNode: " << stgw.bNode(e) << "\n";     
   1.157 +//     }
   1.158 +//   }
   1.159 +//   std::cout << "Edges of the stGraphWrapper:\n"; 
   1.160 +//   FOR_EACH_LOC(stGW::EdgeIt, n, stgw) { 
   1.161 +//     std::cout << " " << n << "\n";
   1.162 +//   }
   1.163 +
   1.164 +//   stGW::NodeMap<bool> b(stgw);
   1.165 +//   FOR_EACH_LOC(stGW::NodeIt, n, stgw) { 
   1.166 +//     std::cout << n << ": " << b[n] <<"\n";
   1.167 +//   }
   1.168 +
   1.169 +//   std::cout << "Bfs from s: \n";
   1.170 +//   BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
   1.171 +//   bfs_stgw.pushAndSetReached(stgw.S_NODE);
   1.172 +//   while (!bfs_stgw.finished()) { 
   1.173 +//     std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n";
   1.174 +//     ++bfs_stgw; 
   1.175 +//   }
   1.176 +
   1.177 +
   1.178 +  Timer ts;
   1.179 +  ts.reset();
   1.180 +  stGW::EdgeMap<int> max_flow(stgw);
   1.181 +  MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
   1.182 +    max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, max_flow);
   1.183 +//  while (max_flow_test.augmentOnShortestPath()) { }
   1.184 +  typedef ListGraph MutableGraph;
   1.185 +//  while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
   1.186 +  while (max_flow_test.augmentOnBlockingFlow2()) {
   1.187 +   std::cout << max_flow_test.flowValue() << std::endl;
   1.188 +  }
   1.189 +  std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
   1.190 +  std::cout << "elapsed time: " << ts << std::endl;
   1.191 +//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 
   1.192 +//     std::cout << e << ": " << max_flow[e] << "\n"; 
   1.193 +//   }
   1.194 +//   std::cout << "\n";
   1.195 +
   1.196 +  ts.reset();
   1.197 +  stGW::EdgeMap<int> pre_flow(stgw);
   1.198 +  Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
   1.199 +    pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true);
   1.200 +  pre_flow_test.run();
   1.201 +  std::cout << "pre flow value: " << max_flow_test.flowValue() << std::endl;
   1.202 +  std::cout << "elapsed time: " << ts << std::endl;
   1.203 +//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 
   1.204 +//     std::cout << e << ": " << pre_flow[e] << "\n"; 
   1.205 +//   }
   1.206 +//   std::cout << "\n";
   1.207 +
   1.208 +  ts.reset();  
   1.209 +  MAX_CARD_BIPARTITE_MATCHING(lg);
   1.210 +  //  stGW::EdgeMap<int> pre_flow(stgw);
   1.211 +  //Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
   1.212 +  //  pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true);
   1.213 +  //pre_flow_test.run();
   1.214 +  //std::cout << "pre flow value: " << max_flow_test.flowValue() << std::endl;
   1.215 +  std::cout << "elapsed time: " << ts << std::endl;
   1.216 +//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 
   1.217 +//     std::cout << e << ": " << pre_flow[e] << "\n"; 
   1.218 +//   }
   1.219 +//   std::cout << "\n";
   1.220 +
   1.221 +  return 0;
   1.222 +}

     2.1 --- a/src/work/marci/makefile	Mon Apr 26 09:55:31 2004 +0000
     2.2 +++ b/src/work/marci/makefile	Mon Apr 26 10:35:36 2004 +0000
     2.3 @@ -1,12 +1,13 @@
     2.4  CXX2 = g++-2.95
     2.5  #CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
     2.6 +CXX3=$(CXX)
     2.7  #CXX=$(CXX3)
     2.8  #CC=$(CXX)
     2.9  #LEDAROOT ?= /ledasrc/LEDA-4.1
    2.10  BOOSTROOT ?= /home/marci/boost
    2.11  INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
    2.12 -LEDAINCLUDE ?= -I$(LEDAROOT)/incl
    2.13 -CXXFLAGS = -g -O3 -W -Wall $(INCLUDEDIRS) -ansi -pedantic -ftemplate-depth-30
    2.14 +#LEDAINCLUDE ?= -I$(LEDAROOT)/incl
    2.15 +#CXXFLAGS = -g -O3 -W -Wall $(INCLUDEDIRS) -ansi -pedantic -ftemplate-depth-30
    2.16  
    2.17  LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
    2.18  BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try
    2.19 @@ -30,11 +31,17 @@
    2.20  leda_graph_demo: leda_graph_demo.o
    2.21  	$(CXX3) -Wall -O -L$(LEDAROOT) -o leda_graph_demo leda_graph_demo.o -lG -lL -lm
    2.22  
    2.23 +bipartite_matching_leda.o:
    2.24 +	$(CXX3) $(CXXFLAGS) -I$(LEDAROOT)/incl -c bipartite_matching_leda.cc
    2.25 +
    2.26 +bipartite_matching_leda: bipartite_matching_leda.o
    2.27 +	$(CXX3) $(CXXFLAGS) -L$(LEDAROOT) -o bipartite_matching_leda bipartite_matching_leda.o -lG -lL -lm
    2.28 +
    2.29  max_bipartite_matching_demo.o:
    2.30 -	$(CXX3) -Wall -O -I.. -I../alpar -I$(LEDAROOT)/incl -I. -c max_bipartite_matching_demo.cc
    2.31 +	$(CXX3) $(CXXFLAGS) -I$(LEDAROOT)/incl -c max_bipartite_matching_demo.cc
    2.32  
    2.33  max_bipartite_matching_demo: max_bipartite_matching_demo.o
    2.34 -	$(CXX3) -Wall -O -L$(LEDAROOT) -o max_bipartite_matching_demo max_bipartite_matching_demo.o -lG -lL -lm
    2.35 +	$(CXX3) $(CXXFLAGS) -L$(LEDAROOT) -o max_bipartite_matching_demo max_bipartite_matching_demo.o -lG -lL -lm
    2.36  
    2.37  leda_bfs_dfs.o:
    2.38  	$(CXX3) -Wall -O -I.. -I../alpar -I$(LEDAROOT)/incl -I. -c leda_bfs_dfs.cc