1.1 --- a/src/work/marci/bipartite_graph_wrapper.h Thu Aug 19 11:34:48 2004 +0000
1.2 +++ b/src/work/marci/bipartite_graph_wrapper.h Mon Aug 23 11:06:00 2004 +0000
1.3 @@ -30,9 +30,10 @@
1.4 /// \author Marton Makai
1.5 template<typename Graph>
1.6 class BipartiteGraphWrapper : public GraphWrapper<Graph> {
1.7 - protected:
1.8 + public:
1.9 typedef IterableBoolMap< typename Graph::template NodeMap<int> >
1.10 SFalseTTrueMap;
1.11 + protected:
1.12 SFalseTTrueMap* s_false_t_true_map;
1.13
1.14 BipartiteGraphWrapper() : GraphWrapper<Graph>()/*,
1.15 @@ -46,6 +47,12 @@
1.16 //FIXME vhogy igy kellene, csak az en forditom nem eszi meg
1.17 static const bool S_CLASS;
1.18 static const bool T_CLASS;
1.19 +
1.20 + /// This method is to reach the iterable maps of the bipartite graph or
1.21 + /// bipartite graph wrapper.
1.22 + const SFalseTTrueMap& sFalseTTrueMap() const {
1.23 + return *s_false_t_true_map;
1.24 + }
1.25
1.26 //bool S_CLASS;
1.27 //bool T_CLASS;
1.28 @@ -211,13 +218,13 @@
1.29 /// does not work well.
1.30 template<typename Graph>
1.31 class BipartiteGraph : public BipartiteGraphWrapper<Graph> {
1.32 - typedef IterableBoolMap< typename Graph::template NodeMap<int> >
1.33 - SFalseTTrueMap;
1.34 +// typedef IterableBoolMap< typename Graph::template NodeMap<int> >
1.35 +// SFalseTTrueMap;
1.36 typedef BipartiteGraphWrapper<Graph> Parent;
1.37 protected:
1.38 Graph gr;
1.39 typename Graph::template NodeMap<int> bipartite_map;
1.40 - SFalseTTrueMap s_false_t_true_map;
1.41 + typename Parent::SFalseTTrueMap s_false_t_true_map;
1.42 public:
1.43 typedef typename Parent::Node Node;
1.44 typedef typename Parent::Edge Edge;
1.45 @@ -258,9 +265,20 @@
1.46 }
1.47 };
1.48
1.49 + template<typename Graph, typename sIterableMap, typename tIterableMap>
1.50 + class stGraphWrapper;
1.51
1.52 + /// Easier stuff for bipartite graphs.
1.53 template<typename Graph>
1.54 - class stGraphWrapper;
1.55 + class stBipartiteGraphWrapper : public
1.56 + stGraphWrapper<Graph, typename Graph::SFalseTTrueMap,
1.57 + typename Graph::SFalseTTrueMap> {
1.58 + public:
1.59 + typedef stGraphWrapper<Graph, typename Graph::SFalseTTrueMap,
1.60 + typename Graph::SFalseTTrueMap> Parent;
1.61 + stBipartiteGraphWrapper(Graph& _graph) :
1.62 + Parent(_graph, _graph.sFalseTTrueMap(), _graph.sFalseTTrueMap()) { }
1.63 + };
1.64
1.65 // template<typename Graph>
1.66 // std::ostream&
1.67 @@ -287,13 +305,16 @@
1.68 /// graph have to be oriented from S to T.
1.69 ///
1.70 /// \author Marton Makai
1.71 - template<typename Graph>
1.72 + template<typename Graph, typename sIterableMap, typename tIterableMap>
1.73 class stGraphWrapper : public GraphWrapper<Graph> {
1.74 + protected:
1.75 + const sIterableMap* s_iterable_map;
1.76 + const tIterableMap* t_iterable_map;
1.77 public:
1.78 class Node;
1.79 friend class Node;
1.80 //GN, int
1.81 -//0 normalis, 1 s, 2, true, ez az iteralasi sorrend,
1.82 +//0 normalis, 1 s, 2 t, ez az iteralasi sorrend,
1.83 //es a vege a false azaz (invalid, 3)
1.84 class NodeIt;
1.85 friend class NodeIt;
1.86 @@ -334,9 +355,15 @@
1.87 static const bool S_CLASS=false;
1.88 static const bool T_CLASS=true;
1.89
1.90 - stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) ,
1.91 - S_NODE(INVALID, 1),
1.92 - T_NODE(INVALID, 2) { }
1.93 + // \bug not too nice constructor.
1.94 + stGraphWrapper(Graph& _graph,
1.95 + const sIterableMap& _s_iterable_map,
1.96 + const tIterableMap& _t_iterable_map) :
1.97 + GraphWrapper<Graph>(_graph),
1.98 + s_iterable_map(&_s_iterable_map),
1.99 + t_iterable_map(&_t_iterable_map),
1.100 + S_NODE(INVALID, 1),
1.101 + T_NODE(INVALID, 2) { }
1.102
1.103
1.104 // std::ostream&
1.105 @@ -349,7 +376,7 @@
1.106 class Node : public Graph::Node {
1.107 protected:
1.108 friend class GraphWrapper<Graph>;
1.109 - friend class stGraphWrapper<Graph>;
1.110 + friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
1.111 template <typename T> friend class NodeMap;
1.112 friend class Edge;
1.113 friend class OutEdgeIt;
1.114 @@ -380,7 +407,7 @@
1.115
1.116 class NodeIt {
1.117 friend class GraphWrapper<Graph>;
1.118 - friend class stGraphWrapper<Graph>;
1.119 + friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
1.120 typename Graph::NodeIt n;
1.121 int spec;
1.122 public:
1.123 @@ -388,7 +415,8 @@
1.124 NodeIt(const typename Graph::NodeIt& _n, int _spec) :
1.125 n(_n), spec(_spec) { }
1.126 NodeIt(const Invalid& i) : n(i), spec(3) { }
1.127 - NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
1.128 + NodeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G)
1.129 + : n(*(_G.graph)), spec(0) {
1.130 if (!_G.graph->valid(n)) spec=1;
1.131 }
1.132 operator Node() const { return Node(n, spec); }
1.133 @@ -396,7 +424,7 @@
1.134
1.135 class Edge : public Graph::Edge {
1.136 friend class GraphWrapper<Graph>;
1.137 - friend class stGraphWrapper<Graph>;
1.138 + friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
1.139 template <typename T> friend class EdgeMap;
1.140 int spec;
1.141 typename Graph::Node n;
1.142 @@ -429,7 +457,7 @@
1.143
1.144 class OutEdgeIt {
1.145 friend class GraphWrapper<Graph>;
1.146 - friend class stGraphWrapper<Graph>;
1.147 + friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
1.148 typename Graph::OutEdgeIt e;
1.149 int spec;
1.150 typename Graph::ClassNodeIt n;
1.151 @@ -440,7 +468,8 @@
1.152 e(_e), spec(_spec), n(_n) {
1.153 }
1.154 OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1.155 - OutEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
1.156 + OutEdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G,
1.157 + const Node& _n) {
1.158 switch (_n.spec) {
1.159 case 0 :
1.160 if (_G.graph->inSClass(_n)) { //S, van normalis kiel
1.161 @@ -473,7 +502,7 @@
1.162
1.163 class InEdgeIt {
1.164 friend class GraphWrapper<Graph>;
1.165 - friend class stGraphWrapper<Graph>;
1.166 + friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
1.167 typename Graph::InEdgeIt e;
1.168 int spec;
1.169 typename Graph::ClassNodeIt n;
1.170 @@ -484,7 +513,8 @@
1.171 e(_e), spec(_spec), n(_n) {
1.172 }
1.173 InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1.174 - InEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
1.175 + InEdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G,
1.176 + const Node& _n) {
1.177 switch (_n.spec) {
1.178 case 0 :
1.179 if (_G.graph->inTClass(_n)) { //T, van normalis beel
1.180 @@ -517,7 +547,7 @@
1.181
1.182 class EdgeIt {
1.183 friend class GraphWrapper<Graph>;
1.184 - friend class stGraphWrapper<Graph>;
1.185 + friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
1.186 typename Graph::EdgeIt e;
1.187 int spec;
1.188 typename Graph::ClassNodeIt n;
1.189 @@ -527,7 +557,7 @@
1.190 const typename Graph::ClassNodeIt& _n) :
1.191 e(_e), spec(_spec), n(_n) { }
1.192 EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1.193 - EdgeIt(const stGraphWrapper<Graph>& _G) :
1.194 + EdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G) :
1.195 e(*(_G.graph)), spec(0), n(INVALID) {
1.196 if (!_G.graph->valid(e)) {
1.197 spec=1;
1.198 @@ -718,12 +748,14 @@
1.199 protected:
1.200 T s_value, t_value;
1.201 public:
1.202 - NodeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
1.203 - s_value(),
1.204 - t_value() { }
1.205 - NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
1.206 - s_value(a),
1.207 - t_value(a) { }
1.208 + NodeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G) :
1.209 + Parent(_G),
1.210 + s_value(),
1.211 + t_value() { }
1.212 + NodeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G, T a)
1.213 + : Parent(_G, a),
1.214 + s_value(a),
1.215 + t_value(a) { }
1.216 T operator[](const Node& n) const {
1.217 switch (n.spec) {
1.218 case 0:
1.219 @@ -753,7 +785,7 @@
1.220
1.221 /// This class is to wrap a node-map of \c Graph and two variables
1.222 /// storing values for \c S_NODE and \c T_NODE to a node-map of
1.223 - /// stGraphWrapper<Graph>.
1.224 + /// stGraphWrapper<Graph, sIterableMap, tIterableMap>.
1.225 template<typename NM> class NodeMapWrapper {
1.226 public:
1.227 typedef Node KeyType;
1.228 @@ -797,10 +829,12 @@
1.229 protected:
1.230 typename GraphWrapper<Graph>::template NodeMap<T> node_value;
1.231 public:
1.232 - EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
1.233 - node_value(_G) { }
1.234 - EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
1.235 - node_value(_G, a) { }
1.236 + EdgeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G)
1.237 + : Parent(_G),
1.238 + node_value(_G) { }
1.239 + EdgeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G, T a)
1.240 + : Parent(_G, a),
1.241 + node_value(_G, a) { }
1.242 T operator[](const Edge& e) const {
1.243 switch (e.spec) {
1.244 case 0:
1.245 @@ -829,7 +863,7 @@
1.246 };
1.247
1.248 /// This class is to wrap an edge-map and a node-map of \c Graph
1.249 - /// to an edge-map of stGraphWrapper<Graph>.
1.250 + /// to an edge-map of stGraphWrapper<Graph, sIterableMap, tIterableMap>.
1.251 template<typename EM, typename NM>
1.252 class EdgeMapWrapper {
1.253 public:
2.1 --- a/src/work/marci/bipartite_graph_wrapper_test.cc Thu Aug 19 11:34:48 2004 +0000
2.2 +++ b/src/work/marci/bipartite_graph_wrapper_test.cc Mon Aug 23 11:06:00 2004 +0000
2.3 @@ -89,7 +89,7 @@
2.4 BGW::NodeMap<int> dbyj(bgw);
2.5 BGW::EdgeMap<int> dbyxcj(bgw);
2.6
2.7 - typedef stGraphWrapper<BGW> stGW;
2.8 + typedef stBipartiteGraphWrapper<BGW> stGW;
2.9 stGW stgw(bgw);
2.10 ConstMap<stGW::Edge, int> const1map(1);
2.11 stGW::NodeMap<int> ize(stgw);
3.1 --- a/src/work/marci/bipartite_matching_try.cc Thu Aug 19 11:34:48 2004 +0000
3.2 +++ b/src/work/marci/bipartite_matching_try.cc Mon Aug 23 11:06:00 2004 +0000
3.3 @@ -116,7 +116,7 @@
3.4 // BGW::NodeMap<int> dbyj(bgw);
3.5 // BGW::EdgeMap<int> dbyxcj(bgw);
3.6
3.7 - typedef stGraphWrapper<BGW> stGW;
3.8 + typedef stBipartiteGraphWrapper<BGW> stGW;
3.9 stGW stgw(bgw);
3.10 ConstMap<stGW::Edge, int> const1map(1);
3.11 // stGW::NodeMap<int> ize(stgw);
4.1 --- a/src/work/marci/bipartite_matching_try_3.cc Thu Aug 19 11:34:48 2004 +0000
4.2 +++ b/src/work/marci/bipartite_matching_try_3.cc Mon Aug 23 11:06:00 2004 +0000
4.3 @@ -17,6 +17,9 @@
4.4
4.5 using namespace hugo;
4.6
4.7 +using std::cout;
4.8 +using std::endl;
4.9 +
4.10 int main() {
4.11 //typedef UndirListGraph Graph;
4.12 typedef BipartiteGraph<SageGraph> Graph;
4.13 @@ -30,53 +33,54 @@
4.14 Graph g;
4.15
4.16 int a;
4.17 - std::cout << "number of nodes in the first color class=";
4.18 + cout << "number of nodes in the first color class=";
4.19 std::cin >> a;
4.20 int b;
4.21 - std::cout << "number of nodes in the second color class=";
4.22 + cout << "number of nodes in the second color class=";
4.23 std::cin >> b;
4.24 int m;
4.25 - std::cout << "number of edges=";
4.26 + cout << "number of edges=";
4.27 std::cin >> m;
4.28
4.29 - std::cout << "Generatig a random bipartite graph..." << std::endl;
4.30 + cout << "Generatig a random bipartite graph..." << endl;
4.31 random_init();
4.32 randomBipartiteGraph(g, a, b, m);
4.33
4.34 -// std::cout << "Edges of the bipartite graph:" << std::endl;
4.35 -// FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " ";
4.36 -// std::cout << std::endl;
4.37 +// cout << "Edges of the bipartite graph:" << endl;
4.38 +// FOR_EACH_LOC(EdgeIt, e, g) cout << e << " ";
4.39 +// cout << endl;
4.40
4.41 -// std::cout << "Nodes:" << std::endl;
4.42 -// FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " ";
4.43 -// std::cout << std::endl;
4.44 -// std::cout << "Nodes in T:" << std::endl;
4.45 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
4.46 -// std::cout << std::endl;
4.47 -// std::cout << "Nodes in S:" << std::endl;
4.48 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
4.49 -// std::cout << std::endl;
4.50 +// cout << "Nodes:" << endl;
4.51 +// FOR_EACH_LOC(Graph::NodeIt, v, g) cout << v << " ";
4.52 +// cout << endl;
4.53 +// cout << "Nodes in T:" << endl;
4.54 +// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) cout << v << " ";
4.55 +// cout << endl;
4.56 +// cout << "Nodes in S:" << endl;
4.57 +// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) cout << v << " ";
4.58 +// cout << endl;
4.59
4.60 -// std::cout << "Erasing the first node..." << std::endl;
4.61 +// cout << "Erasing the first node..." << endl;
4.62 // NodeIt n;
4.63 // g.first(n);
4.64 // g.erase(n);
4.65 -// std::cout << "Nodes of the bipartite graph:" << std::endl;
4.66 -// FOR_EACH_GLOB(n, g) std::cout << n << " ";
4.67 -// std::cout << std::endl;
4.68 +// cout << "Nodes of the bipartite graph:" << endl;
4.69 +// FOR_EACH_GLOB(n, g) cout << n << " ";
4.70 +// cout << endl;
4.71
4.72 -// std::cout << "Nodes in T:" << std::endl;
4.73 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
4.74 -// std::cout << std::endl;
4.75 -// std::cout << "Nodes in S:" << std::endl;
4.76 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
4.77 -// std::cout << std::endl;
4.78 +// cout << "Nodes in T:" << endl;
4.79 +// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) cout << v << " ";
4.80 +// cout << endl;
4.81 +// cout << "Nodes in S:" << endl;
4.82 +// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) cout << v << " ";
4.83 +// cout << endl;
4.84
4.85 - typedef stGraphWrapper<Graph> stGW;
4.86 + typedef stBipartiteGraphWrapper<Graph> stGW;
4.87 stGW stgw(g);
4.88 ConstMap<stGW::Edge, int> const1map(1);
4.89
4.90 Timer ts;
4.91 + cout << "max bipartite matching with stGraphWrapper..." << endl;
4.92 ts.reset();
4.93 stGW::EdgeMap<int> flow(stgw);
4.94 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
4.95 @@ -86,14 +90,14 @@
4.96 // typedef ListGraph MutableGraph;
4.97 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
4.98 // while (max_flow_test.augmentOnBlockingFlow2()) {
4.99 -// std::cout << max_flow_test.flowValue() << std::endl;
4.100 +// cout << max_flow_test.flowValue() << endl;
4.101 // }
4.102 - std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
4.103 - std::cout << "elapsed time: " << ts << std::endl;
4.104 + cout << "matching value: " << max_flow_test.flowValue() << endl;
4.105 + cout << "elapsed time: " << ts << endl;
4.106 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
4.107 -// if (flow[e]) std::cout << e << std::endl;
4.108 +// if (flow[e]) cout << e << endl;
4.109 // }
4.110 - std::cout << std::endl;
4.111 + cout << endl;
4.112
4.113 typedef ConstMap<Graph::Edge, int> EdgeCap;
4.114 EdgeCap ge1(1);
4.115 @@ -104,12 +108,13 @@
4.116 typedef Graph::NodeMap<int> NodeFlow;
4.117 NodeFlow gnf(g); //0
4.118
4.119 - typedef stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
4.120 - typedef stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
4.121 + typedef stGW::EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
4.122 + typedef stGW::EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
4.123 CapMap cm(ge1, gn1);
4.124 FlowMap fm(gef, gnf);
4.125
4.126 //Timer ts;
4.127 + cout << "max bipartite matching with stGraphWrapper..." << endl;
4.128 ts.reset();
4.129 //stGW::EdgeMap<int> flow(stgw);
4.130 MaxFlow<stGW, int, CapMap, FlowMap>
4.131 @@ -119,15 +124,16 @@
4.132 // typedef ListGraph MutableGraph;
4.133 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
4.134 // while (max_flow_test.augmentOnBlockingFlow2()) {
4.135 -// std::cout << max_flow_test.flowValue() << std::endl;
4.136 +// cout << max_flow_test.flowValue() << endl;
4.137 // }
4.138 - std::cout << "max flow value: " << max_flow_test1.flowValue() << std::endl;
4.139 - std::cout << "elapsed time: " << ts << std::endl;
4.140 + cout << "matching value: " << max_flow_test1.flowValue() << endl;
4.141 + cout << "elapsed time: " << ts << endl;
4.142 // FOR_EACH_LOC(Graph::EdgeIt, e, g) {
4.143 -// if (gef[e]) std::cout << e << std::endl;
4.144 +// if (gef[e]) cout << e << endl;
4.145 // }
4.146 - std::cout << std::endl;
4.147 + cout << endl;
4.148
4.149 + cout << "max bipartite matching with stGraphWrapper..." << endl;
4.150 ts.reset();
4.151 FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0);
4.152 FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0);
4.153 @@ -136,27 +142,41 @@
4.154 matching_test(g, ge1, gn1, gef, gnf);
4.155 matching_test.run();
4.156
4.157 - std::cout << "max flow value: " << matching_test.matchingValue() << std::endl;
4.158 - std::cout << "elapsed time: " << ts << std::endl;
4.159 + cout << "matching value: " << matching_test.matchingValue() << endl;
4.160 + cout << "elapsed time: " << ts << endl;
4.161 // FOR_EACH_LOC(Graph::EdgeIt, e, g) {
4.162 -// if (gef[e]) std::cout << e << std::endl;
4.163 +// if (gef[e]) cout << e << endl;
4.164 // }
4.165 - std::cout << std::endl;
4.166 + cout << endl;
4.167
4.168 + cout << "max bipartite matching with MaxBipartiteMatching..." << endl;
4.169 ts.reset();
4.170 FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0);
4.171 //FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0);
4.172 - MaxBipartiteMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>,
4.173 - Graph::EdgeMap<int>, Graph::NodeMap<int> >
4.174 - matching_test_1(g, ge1, gn1, gef/*, gnf*/);
4.175 + typedef MaxBipartiteMatching<Graph, ConstMap<Graph::Edge, int>,
4.176 + ConstMap<Graph::Node, int>,
4.177 + Graph::EdgeMap<int>, Graph::NodeMap<int> > MaxBipartiteMatching;
4.178 + MaxBipartiteMatching matching_test_1(g, ge1, gn1, gef/*, gnf*/);
4.179 matching_test_1.run();
4.180
4.181 - std::cout << "max flow value: " << matching_test_1.matchingValue() << std::endl;
4.182 - std::cout << "elapsed time: " << ts << std::endl;
4.183 + cout << "matching value: " << matching_test_1.matchingValue() << endl;
4.184 + cout << "elapsed time: " << ts << endl;
4.185 // FOR_EACH_LOC(Graph::EdgeIt, e, g) {
4.186 -// if (gef[e]) std::cout << e << std::endl;
4.187 +// if (gef[e]) cout << e << endl;
4.188 // }
4.189 - std::cout << std::endl;
4.190 + cout << endl;
4.191 +
4.192 + cout << "testing optimality with MaxBipartiteMatching..." << endl;
4.193 + ts.reset();
4.194 + matching_test_1.run(MaxBipartiteMatching::GEN_MATCHING);
4.195 + cout << "matching value: " << matching_test_1.matchingValue() << endl;
4.196 + cout << "elapsed time: " << ts << endl;
4.197 +
4.198 + cout << "testing optimality with MaxBipartiteMatching..." << endl;
4.199 + ts.reset();
4.200 + matching_test_1.run(MaxBipartiteMatching::GEN_MATCHING_WITH_GOOD_NODE_FLOW);
4.201 + cout << "matching value: " << matching_test_1.matchingValue() << endl;
4.202 + cout << "elapsed time: " << ts << endl;
4.203
4.204 return 0;
4.205 }
5.1 --- a/src/work/marci/leda/bipartite_matching_leda_gen.cc Thu Aug 19 11:34:48 2004 +0000
5.2 +++ b/src/work/marci/leda/bipartite_matching_leda_gen.cc Mon Aug 23 11:06:00 2004 +0000
5.3 @@ -97,7 +97,7 @@
5.4
5.5
5.6 //st-wrapper
5.7 - typedef stGraphWrapper<BGW> stGW;
5.8 + typedef stBipartiteGraphWrapper<BGW> stGW;
5.9 stGW stgw(bgw);
5.10 ConstMap<stGW::Edge, int> const1map(1);
5.11 stGW::EdgeMap<int> flow(stgw);
6.1 --- a/src/work/marci/leda/comparison.cc Thu Aug 19 11:34:48 2004 +0000
6.2 +++ b/src/work/marci/leda/comparison.cc Mon Aug 23 11:06:00 2004 +0000
6.3 @@ -97,7 +97,7 @@
6.4
6.5
6.6 //st-wrapper
6.7 - typedef stGraphWrapper<BGW> stGW;
6.8 + typedef stBipartiteGraphWrapper<BGW> stGW;
6.9 stGW stgw(bgw);
6.10 ConstMap<stGW::Edge, int> const1map(1);
6.11 stGW::EdgeMap<int> flow(stgw);
7.1 --- a/src/work/marci/lp/lp_solver_wrapper.h Thu Aug 19 11:34:48 2004 +0000
7.2 +++ b/src/work/marci/lp/lp_solver_wrapper.h Mon Aug 23 11:06:00 2004 +0000
7.3 @@ -331,8 +331,8 @@
7.4 lpx_set_col_bnds(lp, col_iter_map[col_it], bound_type, lo, up);
7.5 }
7.6 ///.
7.7 - void setObjCoef(const ColIt& col_it, double obj_coef) {
7.8 - lpx_set_obj_coef(lp, col_iter_map[col_it], obj_coef);
7.9 + double getObjCoef(const ColIt& col_it) {
7.10 + return lpx_get_obj_coef(lp, col_iter_map[col_it]);
7.11 }
7.12 ///.
7.13 void setRowBounds(const RowIt& row_it, int bound_type,
8.1 --- a/src/work/marci/max_bipartite_matching.h Thu Aug 19 11:34:48 2004 +0000
8.2 +++ b/src/work/marci/max_bipartite_matching.h Mon Aug 23 11:06:00 2004 +0000
8.3 @@ -59,18 +59,25 @@
8.4 // NodeCap* node_cap;
8.5 // EdgeFlow* edge_flow;
8.6 // NodeFlow* node_flow;
8.7 - typedef stGraphWrapper<Graph> stGW;
8.8 + typedef stBipartiteGraphWrapper<Graph> stGW;
8.9 stGW stgw;
8.10 typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
8.11 CapMap cap;
8.12 NodeFlow* node_flow;
8.13 typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
8.14 FlowMap flow;
8.15 - MaxFlow<stGW, int, CapMap, FlowMap> mf;
8.16 + typedef MaxFlow<stGW, int, CapMap, FlowMap> MaxFlow;
8.17 + MaxFlow mf;
8.18 //graph* g;
8.19 //EdgeCap* edge_cap;
8.20 //EdgeFlow* edge_flow;
8.21 public:
8.22 + enum MatchingEnum{
8.23 + ZERO_MATCHING,
8.24 + GEN_MATCHING,
8.25 + GEN_MATCHING_WITH_GOOD_NODE_FLOW,
8.26 + NO_MATCHING
8.27 + };
8.28 /// For capacitated b-matchings, edge-caoacities and node-capacities
8.29 /// have to be given. After running \c run the matching is is given
8.30 /// back in the edge-map \c _edge_flow and \c _node_map can be used
8.31 @@ -98,9 +105,34 @@
8.32 /// The class have a nontrivial destructor.
8.33 ~MaxBipartiteMatching() { if (node_flow) delete node_flow; }
8.34 /// run computes the max matching.
8.35 - void run() { mf.run(); }
8.36 + void run(MatchingEnum me=ZERO_MATCHING) {
8.37 + switch (me) {
8.38 + case ZERO_MATCHING:
8.39 + mf.run(MaxFlow::ZERO_FLOW);
8.40 + break;
8.41 + case GEN_MATCHING:
8.42 + {
8.43 + typename stGW::OutEdgeIt e;
8.44 + for (stgw.first(e, stgw.S_NODE); stgw.valid(e); stgw.next(e))
8.45 + flow.set(e, cap[e]);
8.46 + }
8.47 + {
8.48 + typename stGW::InEdgeIt e;
8.49 + for (stgw.first(e, stgw.T_NODE); stgw.valid(e); stgw.next(e))
8.50 + flow.set(e, 0);
8.51 + }
8.52 + mf.run(MaxFlow::PRE_FLOW);
8.53 + break;
8.54 + case GEN_MATCHING_WITH_GOOD_NODE_FLOW:
8.55 + mf.run(MaxFlow::GEN_FLOW);
8.56 + break;
8.57 + case NO_MATCHING:
8.58 + mf.run(MaxFlow::NO_FLOW);
8.59 + break;
8.60 + }
8.61 + }
8.62 /// The matching value after running \c run.
8.63 - int matchingValue() { return mf.flowValue(); }
8.64 + int matchingValue() const { return mf.flowValue(); }
8.65 };
8.66
8.67 } //namespace hugo
9.1 --- a/src/work/marci/max_bipartite_matching_demo.cc Thu Aug 19 11:34:48 2004 +0000
9.2 +++ b/src/work/marci/max_bipartite_matching_demo.cc Mon Aug 23 11:06:00 2004 +0000
9.3 @@ -70,8 +70,7 @@
9.4 cin >> b;
9.5 int m;
9.6 cout << "number of edges=";
9.7 - cin >> m;
9.8 -
9.9 + cin >> m;
9.10
9.11 for(int i=0; i<a; ++i) {
9.12 s_nodes.push_back(G.addNode());