1.1 --- a/src/work/Doxyfile Tue May 11 17:02:32 2004 +0000
1.2 +++ b/src/work/Doxyfile Tue May 11 17:37:34 2004 +0000
1.3 @@ -400,7 +400,8 @@
1.4 jacint/max_matching.h \
1.5 marci/bfs_dfs.h \
1.6 marci/bfs_dfs_misc.h \
1.7 - jacint/graph_gen.h
1.8 + jacint/graph_gen.h \
1.9 + marci/max_bipartite_matching.h
1.10
1.11 # If the value of the INPUT tag contains directories, you can use the
1.12 # FILE_PATTERNS tag to specify one or more wildcard pattern (like *.cpp
2.1 --- a/src/work/marci/bipartite_matching_try_2.cc Tue May 11 17:02:32 2004 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,128 +0,0 @@
2.4 -// -*- c++ -*-
2.5 -#include <iostream>
2.6 -#include <fstream>
2.7 -#include <vector>
2.8 -#include <cstdlib>
2.9 -
2.10 -#include <list_graph.h>
2.11 -//#include <smart_graph.h>
2.12 -//#include <dimacs.h>
2.13 -#include <hugo/time_measure.h>
2.14 -#include <for_each_macros.h>
2.15 -#include <bfs_dfs.h>
2.16 -#include <bipartite_graph_wrapper.h>
2.17 -#include <hugo/maps.h>
2.18 -#include <max_flow.h>
2.19 -
2.20 -/**
2.21 - * Inicializalja a veletlenszamgeneratort.
2.22 - * Figyelem, ez nem jo igazi random szamokhoz,
2.23 - * erre ne bizzad a titkaidat!
2.24 - */
2.25 -void random_init()
2.26 -{
2.27 - unsigned int seed = getpid();
2.28 - seed |= seed << 15;
2.29 - seed ^= time(0);
2.30 -
2.31 - srand(seed);
2.32 -}
2.33 -
2.34 -/**
2.35 - * Egy veletlen int-et ad vissza 0 es m-1 kozott.
2.36 - */
2.37 -int random(int m)
2.38 -{
2.39 - return int( double(m) * rand() / (RAND_MAX + 1.0) );
2.40 -}
2.41 -
2.42 -using namespace hugo;
2.43 -
2.44 -int main() {
2.45 - //typedef UndirListGraph Graph;
2.46 - typedef BipartiteGraph<ListGraph> Graph;
2.47 -
2.48 - typedef Graph::Node Node;
2.49 - typedef Graph::NodeIt NodeIt;
2.50 - typedef Graph::Edge Edge;
2.51 - typedef Graph::EdgeIt EdgeIt;
2.52 - typedef Graph::OutEdgeIt OutEdgeIt;
2.53 -
2.54 - Graph g;
2.55 -
2.56 - std::vector<Graph::Node> s_nodes;
2.57 - std::vector<Graph::Node> t_nodes;
2.58 -
2.59 - int a;
2.60 - std::cout << "number of nodes in the first color class=";
2.61 - std::cin >> a;
2.62 - int b;
2.63 - std::cout << "number of nodes in the second color class=";
2.64 - std::cin >> b;
2.65 - int m;
2.66 - std::cout << "number of edges=";
2.67 - std::cin >> m;
2.68 -
2.69 - std::cout << "Generatig a random bipartite graph..." << std::endl;
2.70 - for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode(false));
2.71 - for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode(true));
2.72 -
2.73 - random_init();
2.74 - for(int i=0; i<m; ++i) {
2.75 - g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
2.76 - }
2.77 -
2.78 -// std::cout << "Edges of the bipartite graph:" << std::endl;
2.79 -// FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " ";
2.80 -// std::cout << std::endl;
2.81 -
2.82 -// std::cout << "Nodes:" << std::endl;
2.83 -// FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " ";
2.84 -// std::cout << std::endl;
2.85 -// std::cout << "Nodes in T:" << std::endl;
2.86 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
2.87 -// std::cout << std::endl;
2.88 -// std::cout << "Nodes in S:" << std::endl;
2.89 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
2.90 -// std::cout << std::endl;
2.91 -
2.92 -// std::cout << "Erasing the first node..." << std::endl;
2.93 -// NodeIt n;
2.94 -// g.first(n);
2.95 -// g.erase(n);
2.96 -// std::cout << "Nodes of the bipartite graph:" << std::endl;
2.97 -// FOR_EACH_GLOB(n, g) std::cout << n << " ";
2.98 -// std::cout << std::endl;
2.99 -
2.100 -// std::cout << "Nodes in T:" << std::endl;
2.101 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
2.102 -// std::cout << std::endl;
2.103 -// std::cout << "Nodes in S:" << std::endl;
2.104 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
2.105 -// std::cout << std::endl;
2.106 -
2.107 - typedef stGraphWrapper<Graph> stGW;
2.108 - stGW stgw(g);
2.109 - ConstMap<stGW::Edge, int> const1map(1);
2.110 -
2.111 - Timer ts;
2.112 - ts.reset();
2.113 - stGW::EdgeMap<int> flow(stgw);
2.114 - MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
2.115 - max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
2.116 - max_flow_test.run();
2.117 -// while (max_flow_test.augmentOnShortestPath()) { }
2.118 -// typedef ListGraph MutableGraph;
2.119 -// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
2.120 -// while (max_flow_test.augmentOnBlockingFlow2()) {
2.121 -// std::cout << max_flow_test.flowValue() << std::endl;
2.122 -// }
2.123 - std::cout << "max flow value: " << max_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 -// if (flow[e]) std::cout << e << std::endl;
2.127 -// }
2.128 -// std::cout << std::endl;
2.129 -
2.130 - return 0;
2.131 -}
3.1 --- a/src/work/marci/bipartite_matching_try_3.cc Tue May 11 17:02:32 2004 +0000
3.2 +++ b/src/work/marci/bipartite_matching_try_3.cc Tue May 11 17:37:34 2004 +0000
3.3 @@ -131,7 +131,7 @@
3.4 ts.reset();
3.5 FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0);
3.6 FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0);
3.7 - MaxMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>,
3.8 + MaxBipartiteMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>,
3.9 Graph::EdgeMap<int>, Graph::NodeMap<int> >
3.10 matching_test(g, ge1, gn1, gef, gnf);
3.11 matching_test.run();
3.12 @@ -146,7 +146,7 @@
3.13 ts.reset();
3.14 FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0);
3.15 //FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0);
3.16 - MaxMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>,
3.17 + MaxBipartiteMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>,
3.18 Graph::EdgeMap<int>, Graph::NodeMap<int> >
3.19 matching_test_1(g, ge1, gn1, gef/*, gnf*/);
3.20 matching_test_1.run();
4.1 --- a/src/work/marci/makefile Tue May 11 17:02:32 2004 +0000
4.2 +++ b/src/work/marci/makefile Tue May 11 17:37:34 2004 +0000
4.3 @@ -4,7 +4,7 @@
4.4 INCLUDEDIRS ?= -I../.. -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
4.5
4.6 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
4.7 -BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_2 bipartite_matching_try_3 top_sort_test
4.8 +BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_3 top_sort_test
4.9 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
4.10
4.11 include ../makefile
5.1 --- a/src/work/marci/max_bipartite_matching.h Tue May 11 17:02:32 2004 +0000
5.2 +++ b/src/work/marci/max_bipartite_matching.h Tue May 11 17:37:34 2004 +0000
5.3 @@ -33,15 +33,17 @@
5.4 // }
5.5 // };
5.6
5.7 - /// A bipartite matching class.
5.8 + /// \brief A bipartite matching class.
5.9 + ///
5.10 /// This class reduces the matching problem to a flow problem and
5.11 /// a preflow is used on a wrapper. Such a generic approach means that
5.12 /// matchings, b-matchings an capacitated b-matchings can be handled in
5.13 /// a similar way. Due to the efficiency of the preflow algorithm, an
5.14 /// efficient matching framework is obtained.
5.15 + /// \ingroup galgs
5.16 template <typename Graph, typename EdgeCap, typename NodeCap,
5.17 typename EdgeFlow, typename NodeFlow>
5.18 - class MaxMatching {
5.19 + class MaxBipartiteMatching {
5.20 protected:
5.21 // EdgeCap* edge_cap;
5.22 // NodeCap* node_cap;
5.23 @@ -65,7 +67,7 @@
5.24 /// to obtain saturation information about nodes.
5.25 ///\bug Note that the values in _edge_flow and _node_flow have
5.26 /// to form a flow.
5.27 - MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
5.28 + MaxBipartiteMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
5.29 EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
5.30 stgw(_g),
5.31 cap(_edge_cap, _node_cap),
5.32 @@ -76,7 +78,7 @@
5.33 /// this constructor is more comfortable.
5.34 ///\bug Note that the values in _edge_flow and _node_flow have
5.35 /// to form a flow.
5.36 - MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
5.37 + MaxBipartiteMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
5.38 EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) :
5.39 stgw(_g),
5.40 cap(_edge_cap, _node_cap),
5.41 @@ -84,7 +86,7 @@
5.42 flow(_edge_flow, *node_flow),
5.43 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
5.44 /// The class have a nontrivial destructor.
5.45 - ~MaxMatching() { if (node_flow) delete node_flow; }
5.46 + ~MaxBipartiteMatching() { if (node_flow) delete node_flow; }
5.47 /// run computes the max matching.
5.48 void run() { mf.run(); }
5.49 /// The matching value after running \c run.