1.1 --- a/src/work/jacint/max_flow.h Mon May 03 09:44:00 2004 +0000
1.2 +++ b/src/work/jacint/max_flow.h Mon May 03 10:04:27 2004 +0000
1.3 @@ -88,6 +88,20 @@
1.4 //In preflow, it shows levels of nodes.
1.5 //typename Graph::template NodeMap<int> level;
1.6 typename Graph::template NodeMap<Num> excess;
1.7 +// protected:
1.8 +// MaxFlow() { }
1.9 +// void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
1.10 +// FlowMap& _flow)
1.11 +// {
1.12 +// g=&_G;
1.13 +// s=_s;
1.14 +// t=_t;
1.15 +// capacity=&_capacity;
1.16 +// flow=&_flow;
1.17 +// n=_G.nodeNum;
1.18 +// level.set (_G); //kellene vmi ilyesmi fv
1.19 +// excess(_G,0); //itt is
1.20 +// }
1.21
1.22 public:
1.23
2.1 --- a/src/work/marci/bipartite_graph_wrapper.h Mon May 03 09:44:00 2004 +0000
2.2 +++ b/src/work/marci/bipartite_graph_wrapper.h Mon May 03 10:04:27 2004 +0000
2.3 @@ -310,7 +310,7 @@
2.4 //(invalid, 2, vmi)
2.5 //invalid, 3, invalid)
2.6 template <typename T> class NodeMap;
2.7 - template <typename T, typename Parent> class EdgeMap;
2.8 + template <typename T> class EdgeMap;
2.9
2.10 // template <typename T> friend class NodeMap;
2.11 // template <typename T> friend class EdgeMap;
2.12 @@ -385,7 +385,7 @@
2.13 class Edge : public Graph::Edge {
2.14 friend class GraphWrapper<Graph>;
2.15 friend class stGraphWrapper<Graph>;
2.16 - template <typename T, typename Parent> friend class EdgeMap;
2.17 + template <typename T> friend class EdgeMap;
2.18 int spec;
2.19 typename Graph::Node n;
2.20 public:
2.21 @@ -412,6 +412,7 @@
2.22 // operator<<(std::ostream& os, const typename stGraphWrapper<G>::Edge& i);
2.23 friend std::ostream& operator<< (std::ostream& os, const Edge& i);
2.24 int getSpec() const { return spec; }
2.25 + typename Graph::Node getNode() const { return n; }
2.26 };
2.27
2.28 class OutEdgeIt {
2.29 @@ -702,6 +703,7 @@
2.30
2.31 template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> {
2.32 typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
2.33 + protected:
2.34 T s_value, t_value;
2.35 public:
2.36 NodeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
2.37 @@ -714,14 +716,11 @@
2.38 switch (n.spec) {
2.39 case 0:
2.40 return Parent::operator[](n);
2.41 - break;
2.42 case 1:
2.43 return s_value;
2.44 - break;
2.45 case 2:
2.46 default:
2.47 return t_value;
2.48 - break;
2.49 }
2.50 }
2.51 void set(const Node& n, T t) {
2.52 @@ -740,11 +739,50 @@
2.53 }
2.54 };
2.55
2.56 - template<typename T,
2.57 - typename Parent=
2.58 - typename GraphWrapper<Graph>::template EdgeMap<T> >
2.59 - class EdgeMap : public Parent {
2.60 - //typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
2.61 + /// This class is to wrap a node-map of \c Graph and two variables
2.62 + /// storing values for \c S_NODE and \c T_NODE to a node-map of
2.63 + /// stGraphWrapper<Graph>.
2.64 + template<typename NM> class NodeMapWrapper {
2.65 + public:
2.66 + typedef Node KeyType;
2.67 + typedef typename NM::ValueType ValueType;
2.68 + protected:
2.69 + NM* nm;
2.70 + ValueType* s_value, t_value;
2.71 + public:
2.72 + NodeMapWrapper(NM& _nm, ValueType& _s_value, ValueType& _t_value) :
2.73 + nm(&_nm), s_value(&_s_value), t_value(&_t_value) { }
2.74 + ValueType operator[](const Node& n) const {
2.75 + switch (n.getSpec()) {
2.76 + case 0:
2.77 + return (*nm)[n];
2.78 + case 1:
2.79 + return *s_value;
2.80 + case 2:
2.81 + default:
2.82 + return *t_value;
2.83 + }
2.84 + }
2.85 + void set(const Node& n, ValueType t) {
2.86 + switch (n.getSpec()) {
2.87 + case 0:
2.88 + nm->set(n, t);
2.89 + break;
2.90 + case 1:
2.91 + *s_value=t;
2.92 + break;
2.93 + case 2:
2.94 + default:
2.95 + *t_value=t;
2.96 + break;
2.97 + }
2.98 + }
2.99 + };
2.100 +
2.101 + template<typename T>
2.102 + class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> {
2.103 + typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
2.104 + protected:
2.105 typename GraphWrapper<Graph>::template NodeMap<T> node_value;
2.106 public:
2.107 EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
2.108 @@ -755,14 +793,11 @@
2.109 switch (e.spec) {
2.110 case 0:
2.111 return Parent::operator[](e);
2.112 - break;
2.113 case 1:
2.114 return node_value[e.n];
2.115 - break;
2.116 case 2:
2.117 default:
2.118 return node_value[e.n];
2.119 - break;
2.120 }
2.121 }
2.122 void set(const Edge& e, T t) {
2.123 @@ -781,43 +816,45 @@
2.124 }
2.125 };
2.126
2.127 -// template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> {
2.128 -// typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
2.129 -// typename GraphWrapper<Graph>::template NodeMap<T> node_value;
2.130 -// public:
2.131 -// EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
2.132 -// node_value(_G) { }
2.133 -// EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
2.134 -// node_value(_G, a) { }
2.135 -// T operator[](const Edge& e) const {
2.136 -// switch (e.spec) {
2.137 -// case 0:
2.138 -// return Parent::operator[](e);
2.139 -// break;
2.140 -// case 1:
2.141 -// return node_value[e.n];
2.142 -// break;
2.143 -// case 2:
2.144 -// default:
2.145 -// return node_value[e.n];
2.146 -// break;
2.147 -// }
2.148 -// }
2.149 -// void set(const Edge& e, T t) {
2.150 -// switch (e.spec) {
2.151 -// case 0:
2.152 -// GraphWrapper<Graph>::template EdgeMap<T>::set(e, t);
2.153 -// break;
2.154 -// case 1:
2.155 -// node_value.set(e.n, t);
2.156 -// break;
2.157 -// case 2:
2.158 -// default:
2.159 -// node_value.set(e.n, t);
2.160 -// break;
2.161 -// }
2.162 -// }
2.163 -// };
2.164 + /// This class is to wrap an edge-map and a node-map of \c Graph
2.165 + /// to an edge-map of stGraphWrapper<Graph>.
2.166 + template<typename EM, typename NM>
2.167 + class EdgeMapWrapper {
2.168 + public:
2.169 + typedef Edge KeyType;
2.170 + typedef typename EM::ValueType ValueType;
2.171 + protected:
2.172 + EM* em;
2.173 + NM* nm;
2.174 + public:
2.175 + EdgeMapWrapper(EM& _em, NM& _nm) : em(&_em), nm(&_nm) { }
2.176 + ValueType operator[](const Edge& e) const {
2.177 + switch (e.getSpec()) {
2.178 + case 0:
2.179 + return (*em)[e];
2.180 + case 1:
2.181 + return (*nm)[e.getNode()];
2.182 + case 2:
2.183 + default:
2.184 + return (*nm)[e.getNode()];
2.185 + }
2.186 + }
2.187 + void set(const Edge& e, ValueType t) {
2.188 + switch (e.getSpec()) {
2.189 + case 0:
2.190 + em->set(e, t);
2.191 + break;
2.192 + case 1:
2.193 + nm->set(e.getNode(), t);
2.194 + break;
2.195 + case 2:
2.196 + default:
2.197 + nm->set(e.getNode(), t);
2.198 + break;
2.199 + }
2.200 + }
2.201 + };
2.202 +
2.203
2.204 // template<typename G>
2.205 friend std::ostream&
2.206 @@ -840,5 +877,5 @@
2.207 } //namespace hugo
2.208
2.209
2.210 -#endif //HUGO_GRAPH_WRAPPER_H
2.211 +#endif //HUGO_BIPARTITE_GRAPH_WRAPPER_H
2.212
3.1 --- a/src/work/marci/bipartite_matching_try_2.cc Mon May 03 09:44:00 2004 +0000
3.2 +++ b/src/work/marci/bipartite_matching_try_2.cc Mon May 03 10:04:27 2004 +0000
3.3 @@ -72,34 +72,34 @@
3.4 g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
3.5 }
3.6
3.7 - std::cout << "Edges of the bipartite graph:" << std::endl;
3.8 - FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " ";
3.9 - std::cout << std::endl;
3.10 +// std::cout << "Edges of the bipartite graph:" << std::endl;
3.11 +// FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " ";
3.12 +// std::cout << std::endl;
3.13
3.14 - std::cout << "Nodes:" << std::endl;
3.15 - FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " ";
3.16 - std::cout << std::endl;
3.17 - std::cout << "Nodes in T:" << std::endl;
3.18 - FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
3.19 - std::cout << std::endl;
3.20 - std::cout << "Nodes in S:" << std::endl;
3.21 - FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
3.22 - std::cout << std::endl;
3.23 +// std::cout << "Nodes:" << std::endl;
3.24 +// FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " ";
3.25 +// std::cout << std::endl;
3.26 +// std::cout << "Nodes in T:" << std::endl;
3.27 +// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
3.28 +// std::cout << std::endl;
3.29 +// std::cout << "Nodes in S:" << std::endl;
3.30 +// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
3.31 +// std::cout << std::endl;
3.32
3.33 - std::cout << "Erasing the first node..." << std::endl;
3.34 - NodeIt n;
3.35 - g.first(n);
3.36 - g.erase(n);
3.37 - std::cout << "Nodes of the bipartite graph:" << std::endl;
3.38 - FOR_EACH_GLOB(n, g) std::cout << n << " ";
3.39 - std::cout << std::endl;
3.40 +// std::cout << "Erasing the first node..." << std::endl;
3.41 +// NodeIt n;
3.42 +// g.first(n);
3.43 +// g.erase(n);
3.44 +// std::cout << "Nodes of the bipartite graph:" << std::endl;
3.45 +// FOR_EACH_GLOB(n, g) std::cout << n << " ";
3.46 +// std::cout << std::endl;
3.47
3.48 - std::cout << "Nodes in T:" << std::endl;
3.49 - FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
3.50 - std::cout << std::endl;
3.51 - std::cout << "Nodes in S:" << std::endl;
3.52 - FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
3.53 - std::cout << std::endl;
3.54 +// std::cout << "Nodes in T:" << std::endl;
3.55 +// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
3.56 +// std::cout << std::endl;
3.57 +// std::cout << "Nodes in S:" << std::endl;
3.58 +// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
3.59 +// std::cout << std::endl;
3.60
3.61 typedef stGraphWrapper<Graph> stGW;
3.62 stGW stgw(g);
3.63 @@ -119,10 +119,10 @@
3.64 // }
3.65 std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
3.66 std::cout << "elapsed time: " << ts << std::endl;
3.67 - FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
3.68 - if (flow[e]) std::cout << e << std::endl;
3.69 - }
3.70 - std::cout << std::endl;
3.71 +// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
3.72 +// if (flow[e]) std::cout << e << std::endl;
3.73 +// }
3.74 +// std::cout << std::endl;
3.75
3.76 return 0;
3.77 }
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/work/marci/bipartite_matching_try_3.cc Mon May 03 10:04:27 2004 +0000
4.3 @@ -0,0 +1,233 @@
4.4 +// -*- c++ -*-
4.5 +#include <iostream>
4.6 +#include <fstream>
4.7 +#include <vector>
4.8 +#include <cstdlib>
4.9 +
4.10 +#include <list_graph.h>
4.11 +//#include <smart_graph.h>
4.12 +//#include <dimacs.h>
4.13 +#include <time_measure.h>
4.14 +#include <for_each_macros.h>
4.15 +#include <bfs_iterator.h>
4.16 +#include <bipartite_graph_wrapper.h>
4.17 +#include <maps.h>
4.18 +#include <max_flow.h>
4.19 +
4.20 +using namespace hugo;
4.21 +
4.22 +// template <typename Graph, typename EdgeCap, typename NodeCap,
4.23 +// typename EdgeFlow, typename NodeFlow>
4.24 +// class MaxMatching : public MaxFlow<stGraphWrapper<Graph>,
4.25 +// stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > {
4.26 +// typedef MaxFlow<stGraphWrapper<Graph>,
4.27 +// stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>,
4.28 +// stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> >
4.29 +// Parent;
4.30 +// protected:
4.31 +// stGraphWrapper<Graph> gw;
4.32 +// stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> cap;
4.33 +// stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> flow;
4.34 +// //graph* g;
4.35 +// //EdgeCap* edge_cap;
4.36 +// //EdgeFlow* edge_flow;
4.37 +// public:
4.38 +// MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
4.39 +// EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
4.40 +// MaxFlow(), gw(_g),
4.41 +// cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow) {
4.42 +// Parent::set(gw, cap, flow);
4.43 +// }
4.44 +// };
4.45 +
4.46 +template <typename Graph, typename EdgeCap, typename NodeCap,
4.47 + typename EdgeFlow, typename NodeFlow>
4.48 +class MaxMatching {
4.49 +// : public MaxFlow<stGraphWrapper<Graph>,
4.50 +// stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > {
4.51 +// typedef MaxFlow<stGraphWrapper<Graph>,
4.52 +// stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>,
4.53 +// stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> >
4.54 +// Parent;
4.55 +protected:
4.56 +// EdgeCap* edge_cap;
4.57 +// NodeCap* node_cap;
4.58 +// EdgeFlow* edge_flow;
4.59 +// NodeFlow* node_flow;
4.60 + typedef stGraphWrapper<Graph> stGW;
4.61 + stGW stgw;
4.62 + typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
4.63 + CapMap cap;
4.64 + typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
4.65 + FlowMap flow;
4.66 + MaxFlow<stGW, int, CapMap, FlowMap> mf;
4.67 + //graph* g;
4.68 + //EdgeCap* edge_cap;
4.69 + //EdgeFlow* edge_flow;
4.70 +public:
4.71 + MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
4.72 + EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
4.73 + stgw(_g),
4.74 + cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow),
4.75 + mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
4.76 + void run() { mf.run(); }
4.77 + int matchingValue() { return mf.flowValue(); }
4.78 +};
4.79 +
4.80 +/**
4.81 + * Inicializalja a veletlenszamgeneratort.
4.82 + * Figyelem, ez nem jo igazi random szamokhoz,
4.83 + * erre ne bizzad a titkaidat!
4.84 + */
4.85 +void random_init()
4.86 +{
4.87 + unsigned int seed = getpid();
4.88 + seed |= seed << 15;
4.89 + seed ^= time(0);
4.90 +
4.91 + srand(seed);
4.92 +}
4.93 +
4.94 +/**
4.95 + * Egy veletlen int-et ad vissza 0 es m-1 kozott.
4.96 + */
4.97 +int random(int m)
4.98 +{
4.99 + return int( double(m) * rand() / (RAND_MAX + 1.0) );
4.100 +}
4.101 +
4.102 +int main() {
4.103 + //typedef UndirListGraph Graph;
4.104 + typedef BipartiteGraph<ListGraph> Graph;
4.105 +
4.106 + typedef Graph::Node Node;
4.107 + typedef Graph::NodeIt NodeIt;
4.108 + typedef Graph::Edge Edge;
4.109 + typedef Graph::EdgeIt EdgeIt;
4.110 + typedef Graph::OutEdgeIt OutEdgeIt;
4.111 +
4.112 + Graph g;
4.113 +
4.114 + std::vector<Graph::Node> s_nodes;
4.115 + std::vector<Graph::Node> t_nodes;
4.116 +
4.117 + int a;
4.118 + std::cout << "number of nodes in the first color class=";
4.119 + std::cin >> a;
4.120 + int b;
4.121 + std::cout << "number of nodes in the second color class=";
4.122 + std::cin >> b;
4.123 + int m;
4.124 + std::cout << "number of edges=";
4.125 + std::cin >> m;
4.126 +
4.127 + std::cout << "Generatig a random bipartite graph..." << std::endl;
4.128 + for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode(false));
4.129 + for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode(true));
4.130 +
4.131 + random_init();
4.132 + for(int i=0; i<m; ++i) {
4.133 + g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
4.134 + }
4.135 +
4.136 + std::cout << "Edges of the bipartite graph:" << std::endl;
4.137 + FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " ";
4.138 + std::cout << std::endl;
4.139 +
4.140 + std::cout << "Nodes:" << std::endl;
4.141 + FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " ";
4.142 + std::cout << std::endl;
4.143 + std::cout << "Nodes in T:" << std::endl;
4.144 + FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
4.145 + std::cout << std::endl;
4.146 + std::cout << "Nodes in S:" << std::endl;
4.147 + FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
4.148 + std::cout << std::endl;
4.149 +
4.150 + std::cout << "Erasing the first node..." << std::endl;
4.151 + NodeIt n;
4.152 + g.first(n);
4.153 + g.erase(n);
4.154 + std::cout << "Nodes of the bipartite graph:" << std::endl;
4.155 + FOR_EACH_GLOB(n, g) std::cout << n << " ";
4.156 + std::cout << std::endl;
4.157 +
4.158 + std::cout << "Nodes in T:" << std::endl;
4.159 + FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
4.160 + std::cout << std::endl;
4.161 + std::cout << "Nodes in S:" << std::endl;
4.162 + FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
4.163 + std::cout << std::endl;
4.164 +
4.165 + typedef stGraphWrapper<Graph> stGW;
4.166 + stGW stgw(g);
4.167 + ConstMap<stGW::Edge, int> const1map(1);
4.168 +
4.169 + Timer ts;
4.170 + ts.reset();
4.171 + stGW::EdgeMap<int> flow(stgw);
4.172 + MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
4.173 + max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
4.174 + max_flow_test.run();
4.175 +// while (max_flow_test.augmentOnShortestPath()) { }
4.176 +// typedef ListGraph MutableGraph;
4.177 +// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
4.178 +// while (max_flow_test.augmentOnBlockingFlow2()) {
4.179 +// std::cout << max_flow_test.flowValue() << std::endl;
4.180 +// }
4.181 + std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
4.182 + std::cout << "elapsed time: " << ts << std::endl;
4.183 + FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
4.184 + if (flow[e]) std::cout << e << std::endl;
4.185 + }
4.186 + std::cout << std::endl;
4.187 +
4.188 + typedef ConstMap<Graph::Edge, int> EdgeCap;
4.189 + EdgeCap ge1(1);
4.190 + typedef ConstMap<Graph::Node, int> NodeCap;
4.191 + NodeCap gn1(1);
4.192 + typedef Graph::EdgeMap<int> EdgeFlow;
4.193 + EdgeFlow gef(g); //0
4.194 + typedef Graph::NodeMap<int> NodeFlow;
4.195 + NodeFlow gnf(g); //0
4.196 +
4.197 + typedef stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
4.198 + typedef stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
4.199 + CapMap cm(ge1, gn1);
4.200 + FlowMap fm(gef, gnf);
4.201 +
4.202 + //Timer ts;
4.203 + ts.reset();
4.204 + //stGW::EdgeMap<int> flow(stgw);
4.205 + MaxFlow<stGW, int, CapMap, FlowMap>
4.206 + max_flow_test1(stgw, stgw.S_NODE, stgw.T_NODE, cm, fm);
4.207 + max_flow_test1.run();
4.208 +// while (max_flow_test.augmentOnShortestPath()) { }
4.209 +// typedef ListGraph MutableGraph;
4.210 +// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
4.211 +// while (max_flow_test.augmentOnBlockingFlow2()) {
4.212 +// std::cout << max_flow_test.flowValue() << std::endl;
4.213 +// }
4.214 + std::cout << "max flow value: " << max_flow_test1.flowValue() << std::endl;
4.215 + std::cout << "elapsed time: " << ts << std::endl;
4.216 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
4.217 +// if (gef[e]) std::cout << e << std::endl;
4.218 +// }
4.219 + std::cout << std::endl;
4.220 +
4.221 + ts.reset();
4.222 + FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0);
4.223 + FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0);
4.224 + MaxMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>,
4.225 + Graph::EdgeMap<int>, Graph::NodeMap<int> >
4.226 + matching_test(g, ge1, gn1, gef, gnf);
4.227 + matching_test.run();
4.228 +
4.229 + std::cout << "max flow value: " << matching_test.matchingValue() << std::endl;
4.230 + std::cout << "elapsed time: " << ts << std::endl;
4.231 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
4.232 +// if (gef[e]) std::cout << e << std::endl;
4.233 +// }
4.234 + std::cout << std::endl;
4.235 + return 0;
4.236 +}
5.1 --- a/src/work/marci/makefile Mon May 03 09:44:00 2004 +0000
5.2 +++ b/src/work/marci/makefile Mon May 03 10:04:27 2004 +0000
5.3 @@ -4,7 +4,7 @@
5.4 INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
5.5
5.6 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
5.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
5.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_2 bipartite_matching_try_3
5.9 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
5.10
5.11 include ../makefile