1.1 --- a/src/work/marci/leda/bipartite_matching_leda.cc Tue Apr 27 13:53:27 2004 +0000
1.2 +++ b/src/work/marci/leda/bipartite_matching_leda.cc Tue Apr 27 14:10:19 2004 +0000
1.3 @@ -7,6 +7,7 @@
1.4 #include <LEDA/graph.h>
1.5 #include <LEDA/mcb_matching.h>
1.6 #include <LEDA/list.h>
1.7 +#include <LEDA/graph_gen.h>
1.8
1.9 #include <leda_graph_wrapper.h>
1.10 #include <list_graph.h>
1.11 @@ -89,88 +90,15 @@
1.12 for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false);
1.13 for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true);
1.14
1.15 -// Graph::Node u;
1.16 -// std::cout << "These nodes will be in S:\n";
1.17 -// //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen
1.18 -// //irni 1etlen FOR_EACH-csel.
1.19 -// for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u))
1.20 -// std::cout << u << " ";
1.21 -// std::cout << "\n";
1.22 -// std::cout << "These nodes will be in T:\n";
1.23 -// for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u))
1.24 -// std::cout << u << " ";
1.25 -// std::cout << "\n";
1.26 -
1.27 typedef BipartiteGraphWrapper<Graph> BGW;
1.28 BGW bgw(g, bipartite_map);
1.29
1.30 -// std::cout << "Nodes by NodeIt:\n";
1.31 -// FOR_EACH_LOC(BGW::NodeIt, n, bgw) {
1.32 -// std::cout << n << " ";
1.33 -// }
1.34 -// std::cout << "\n";
1.35 -// std::cout << "Nodes in S by ClassNodeIt:\n";
1.36 -// FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) {
1.37 -// std::cout << n << " ";
1.38 -// }
1.39 -// std::cout << "\n";
1.40 -// std::cout << "Nodes in T by ClassNodeIt:\n";
1.41 -// FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) {
1.42 -// std::cout << n << " ";
1.43 -// }
1.44 -// std::cout << "\n";
1.45 -// std::cout << "Edges of the bipartite graph:\n";
1.46 -// FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
1.47 -// std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
1.48 -// }
1.49 -
1.50 BGW::NodeMap<int> dbyj(bgw);
1.51 BGW::EdgeMap<int> dbyxcj(bgw);
1.52
1.53 typedef stGraphWrapper<BGW> stGW;
1.54 stGW stgw(bgw);
1.55 ConstMap<stGW::Edge, int> const1map(1);
1.56 -// stGW::NodeMap<int> ize(stgw);
1.57 -
1.58 -// BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
1.59 -// Graph::NodeIt si;
1.60 -// Graph::Node s;
1.61 -// s=g.first(si);
1.62 -// bfs.pushAndSetReached(BGW::Node(s));
1.63 -// while (!bfs.finished()) { ++bfs; }
1.64 -
1.65 -// FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
1.66 -// std::cout << "out-edges of " << n << ":\n";
1.67 -// FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) {
1.68 -// std::cout << " " << e << "\n";
1.69 -// std::cout << " aNode: " << stgw.aNode(e) << "\n";
1.70 -// std::cout << " bNode: " << stgw.bNode(e) << "\n";
1.71 -// }
1.72 -// std::cout << "in-edges of " << n << ":\n";
1.73 -// FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) {
1.74 -// std::cout << " " << e << "\n";
1.75 -// std::cout << " aNode: " << stgw.aNode(e) << "\n";
1.76 -// std::cout << " bNode: " << stgw.bNode(e) << "\n";
1.77 -// }
1.78 -// }
1.79 -// std::cout << "Edges of the stGraphWrapper:\n";
1.80 -// FOR_EACH_LOC(stGW::EdgeIt, n, stgw) {
1.81 -// std::cout << " " << n << "\n";
1.82 -// }
1.83 -
1.84 -// stGW::NodeMap<bool> b(stgw);
1.85 -// FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
1.86 -// std::cout << n << ": " << b[n] <<"\n";
1.87 -// }
1.88 -
1.89 -// std::cout << "Bfs from s: \n";
1.90 -// BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
1.91 -// bfs_stgw.pushAndSetReached(stgw.S_NODE);
1.92 -// while (!bfs_stgw.finished()) {
1.93 -// std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n";
1.94 -// ++bfs_stgw;
1.95 -// }
1.96 -
1.97
1.98 Timer ts;
1.99 ts.reset();
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/marci/leda/bipartite_matching_leda_gen.cc Tue Apr 27 14:10:19 2004 +0000
2.3 @@ -0,0 +1,158 @@
2.4 +// -*- c++ -*-
2.5 +#include <iostream>
2.6 +#include <fstream>
2.7 +#include <vector>
2.8 +#include <cstdlib>
2.9 +
2.10 +#include <LEDA/graph.h>
2.11 +#include <LEDA/mcb_matching.h>
2.12 +#include <LEDA/list.h>
2.13 +#include <LEDA/graph_gen.h>
2.14 +
2.15 +#include <leda_graph_wrapper.h>
2.16 +#include <list_graph.h>
2.17 +//#include <smart_graph.h>
2.18 +//#include <dimacs.h>
2.19 +#include <time_measure.h>
2.20 +#include <for_each_macros.h>
2.21 +//#include <bfs_iterator.h>
2.22 +#include <graph_wrapper.h>
2.23 +#include <maps.h>
2.24 +#include <edmonds_karp.h>
2.25 +#include <preflow.h>
2.26 +
2.27 +/**
2.28 + * Inicializalja a veletlenszamgeneratort.
2.29 + * Figyelem, ez nem jo igazi random szamokhoz,
2.30 + * erre ne bizzad a titkaidat!
2.31 + */
2.32 +void random_init()
2.33 +{
2.34 + unsigned int seed = getpid();
2.35 + seed |= seed << 15;
2.36 + seed ^= time(0);
2.37 +
2.38 + srand(seed);
2.39 +}
2.40 +
2.41 +/**
2.42 + * Egy veletlen int-et ad vissza 0 es m-1 kozott.
2.43 + */
2.44 +int random(int m)
2.45 +{
2.46 + return int( double(m) * rand() / (RAND_MAX + 1.0) );
2.47 +}
2.48 +
2.49 +using namespace hugo;
2.50 +
2.51 +int main() {
2.52 + //for leda graph
2.53 + leda::graph lg;
2.54 + //lg.make_undirected();
2.55 + typedef LedaGraphWrapper<leda::graph> Graph;
2.56 + Graph g(lg);
2.57 +
2.58 + //for UndirListGraph
2.59 + //typedef UndirListGraph Graph;
2.60 + //Graph g;
2.61 +
2.62 + typedef Graph::Node Node;
2.63 + typedef Graph::NodeIt NodeIt;
2.64 + typedef Graph::Edge Edge;
2.65 + typedef Graph::EdgeIt EdgeIt;
2.66 + typedef Graph::OutEdgeIt OutEdgeIt;
2.67 +
2.68 + std::vector<Graph::Node> s_nodes;
2.69 + std::vector<Graph::Node> t_nodes;
2.70 +
2.71 + int a;
2.72 + std::cout << "number of nodes in the first color class=";
2.73 + std::cin >> a;
2.74 + int b;
2.75 + std::cout << "number of nodes in the second color class=";
2.76 + std::cin >> b;
2.77 + int m;
2.78 + std::cout << "number of edges=";
2.79 + std::cin >> m;
2.80 + int k;
2.81 + std::cout << "number of groups in LEDA random group graph=";
2.82 + std::cin >> k;
2.83 +
2.84 + leda_list<leda_node> lS;
2.85 + leda_list<leda_node> lT;
2.86 + random_bigraph(lg, a, b, m, lS, lT, k);
2.87 +
2.88 +// for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode());
2.89 +// for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode());
2.90 +
2.91 +// random_init();
2.92 +// for(int i=0; i<m; ++i) {
2.93 +// g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
2.94 +// }
2.95 +
2.96 + Graph::NodeMap<int> ref_map(g, -1);
2.97 +
2.98 + IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
2.99 +// for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false);
2.100 +// for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true);
2.101 + leda_node ln;
2.102 + forall(ln, lS) bipartite_map.insert(ln, false);
2.103 + forall(ln, lT) bipartite_map.insert(ln, true);
2.104 +
2.105 + typedef BipartiteGraphWrapper<Graph> BGW;
2.106 + BGW bgw(g, bipartite_map);
2.107 +
2.108 + // BGW::NodeMap<int> dbyj(bgw);
2.109 + // BGW::EdgeMap<int> dbyxcj(bgw);
2.110 +
2.111 + typedef stGraphWrapper<BGW> stGW;
2.112 + stGW stgw(bgw);
2.113 + ConstMap<stGW::Edge, int> const1map(1);
2.114 + stGW::EdgeMap<int> flow(stgw);
2.115 +
2.116 + Timer ts;
2.117 + FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
2.118 + ts.reset();
2.119 + // stGW::EdgeMap<int> pre_flow(stgw);
2.120 + Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
2.121 + pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow, true);
2.122 + pre_flow_test.run();
2.123 + std::cout << "HUGO pre flow value: " << pre_flow_test.flowValue() << std::endl;
2.124 + std::cout << "elapsed time: " << ts << std::endl;
2.125 +// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
2.126 +// std::cout << e << ": " << pre_flow[e] << "\n";
2.127 +// }
2.128 + std::cout << "\n";
2.129 +
2.130 + ts.reset();
2.131 + leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
2.132 + // stGW::EdgeMap<int> pre_flow(stgw);
2.133 + //Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
2.134 + // pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true);
2.135 + //pre_flow_test.run();
2.136 + std::cout << "LEDA matching value: " << ml.size() << std::endl;
2.137 + std::cout << "elapsed time: " << ts << std::endl;
2.138 +// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
2.139 +// std::cout << e << ": " << pre_flow[e] << "\n";
2.140 +// }
2.141 + std::cout << "\n";
2.142 +
2.143 + FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
2.144 + ts.reset();
2.145 + MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
2.146 + max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
2.147 +// while (max_flow_test.augmentOnShortestPath()) { }
2.148 + typedef ListGraph MutableGraph;
2.149 +// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
2.150 + while (max_flow_test.augmentOnBlockingFlow2()) {
2.151 + std::cout << max_flow_test.flowValue() << std::endl;
2.152 + }
2.153 + std::cout << "HUGO blocking flow value: " << max_flow_test.flowValue() << std::endl;
2.154 + std::cout << "elapsed time: " << ts << std::endl;
2.155 +// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
2.156 +// std::cout << e << ": " << max_flow[e] << "\n";
2.157 +// }
2.158 +// std::cout << "\n";
2.159 +
2.160 + return 0;
2.161 +}
3.1 --- a/src/work/marci/leda/leda_graph_wrapper.h Tue Apr 27 13:53:27 2004 +0000
3.2 +++ b/src/work/marci/leda/leda_graph_wrapper.h Tue Apr 27 14:10:19 2004 +0000
3.3 @@ -63,6 +63,7 @@
3.4 protected:
3.5 template <typename T> friend class NodeMap;
3.6 leda_node _n;
3.7 + public: //FIXME
3.8 Node(leda_node __n) : _n(__n) { }
3.9 public:
3.10 /// @warning The default constructor sets the iterator
3.11 @@ -95,6 +96,7 @@
3.12 protected:
3.13 template <typename T> friend class EdgeMap;
3.14 leda_edge _e;
3.15 + public: //FIXME
3.16 Edge(leda_edge __e) : _e(__e) { }
3.17 public:
3.18 /// @warning The default constructor sets the iterator
4.1 --- a/src/work/marci/leda/makefile Tue Apr 27 13:53:27 2004 +0000
4.2 +++ b/src/work/marci/leda/makefile Tue Apr 27 14:10:19 2004 +0000
4.3 @@ -4,7 +4,7 @@
4.4 INCLUDEDIRS ?= -I../../../include -I../.. -I../../{marci,jacint,alpar,klao,akos,athos} -I$(LEDAROOT)/incl -I.
4.5 LDFLAGS = -L$(LEDAROOT) -lG -lL -lm
4.6
4.7 -BINARIES = bipartite_matching_leda
4.8 +BINARIES = bipartite_matching_leda bipartite_matching_leda_gen
4.9
4.10 include ../../makefile
4.11