1.1 --- a/src/work/marci/bipartite_matching_try_2.cc Fri Apr 30 16:46:19 2004 +0000
1.2 +++ b/src/work/marci/bipartite_matching_try_2.cc Fri Apr 30 17:10:01 2004 +0000
1.3 @@ -10,7 +10,6 @@
1.4 #include <time_measure.h>
1.5 #include <for_each_macros.h>
1.6 #include <bfs_iterator.h>
1.7 -#include <graph_wrapper.h>
1.8 #include <bipartite_graph_wrapper.h>
1.9 #include <maps.h>
1.10 #include <max_flow.h>
1.11 @@ -40,7 +39,9 @@
1.12 using namespace hugo;
1.13
1.14 int main() {
1.15 - typedef UndirListGraph Graph;
1.16 + //typedef UndirListGraph Graph;
1.17 + typedef BipartiteGraph<ListGraph> Graph;
1.18 +
1.19 typedef Graph::Node Node;
1.20 typedef Graph::NodeIt NodeIt;
1.21 typedef Graph::Edge Edge;
1.22 @@ -63,108 +64,30 @@
1.23 std::cin >> m;
1.24
1.25
1.26 - for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode());
1.27 - for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode());
1.28 + for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode(false));
1.29 + for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode(true));
1.30
1.31 random_init();
1.32 for(int i=0; i<m; ++i) {
1.33 g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
1.34 }
1.35
1.36 - Graph::NodeMap<int> ref_map(g, -1);
1.37 + std::cout << "Edges of the bipartite graph:" << std::endl;
1.38 + FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " ";
1.39 + std::cout << std::endl;
1.40
1.41 - IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
1.42 - for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false);
1.43 - for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true);
1.44 + typedef stGraphWrapper<Graph> stGW;
1.45 + stGW stgw(g);
1.46 + ConstMap<stGW::Edge, int> const1map(1);
1.47
1.48 -// Graph::Node u;
1.49 -// std::cout << "These nodes will be in S:\n";
1.50 -// //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen
1.51 -// //irni 1etlen FOR_EACH-csel.
1.52 -// for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u))
1.53 -// std::cout << u << " ";
1.54 -// std::cout << "\n";
1.55 -// std::cout << "These nodes will be in T:\n";
1.56 -// for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u))
1.57 -// std::cout << u << " ";
1.58 -// std::cout << "\n";
1.59
1.60 - typedef BipartiteGraphWrapper<Graph> BGW;
1.61 - BGW bgw(g, bipartite_map);
1.62 -
1.63 -// std::cout << "Nodes by NodeIt:\n";
1.64 -// FOR_EACH_LOC(BGW::NodeIt, n, bgw) {
1.65 -// std::cout << n << " ";
1.66 -// }
1.67 -// std::cout << "\n";
1.68 -// std::cout << "Nodes in S by ClassNodeIt:\n";
1.69 -// FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) {
1.70 -// std::cout << n << " ";
1.71 -// }
1.72 -// std::cout << "\n";
1.73 -// std::cout << "Nodes in T by ClassNodeIt:\n";
1.74 -// FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) {
1.75 -// std::cout << n << " ";
1.76 -// }
1.77 -// std::cout << "\n";
1.78 -// std::cout << "Edges of the bipartite graph:\n";
1.79 -// FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
1.80 -// std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
1.81 -// }
1.82 -
1.83 -// BGW::NodeMap<int> dbyj(bgw);
1.84 -// BGW::EdgeMap<int> dbyxcj(bgw);
1.85 -
1.86 - typedef stGraphWrapper<BGW> stGW;
1.87 - stGW stgw(bgw);
1.88 - ConstMap<stGW::Edge, int> const1map(1);
1.89 -// stGW::NodeMap<int> ize(stgw);
1.90 -
1.91 -// BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
1.92 -// Graph::NodeIt si;
1.93 -// Graph::Node s;
1.94 -// s=g.first(si);
1.95 -// bfs.pushAndSetReached(BGW::Node(s));
1.96 -// while (!bfs.finished()) { ++bfs; }
1.97 -
1.98 -// FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
1.99 -// std::cout << "out-edges of " << n << ":\n";
1.100 -// FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) {
1.101 -// std::cout << " " << e << "\n";
1.102 -// std::cout << " aNode: " << stgw.aNode(e) << "\n";
1.103 -// std::cout << " bNode: " << stgw.bNode(e) << "\n";
1.104 -// }
1.105 -// std::cout << "in-edges of " << n << ":\n";
1.106 -// FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) {
1.107 -// std::cout << " " << e << "\n";
1.108 -// std::cout << " aNode: " << stgw.aNode(e) << "\n";
1.109 -// std::cout << " bNode: " << stgw.bNode(e) << "\n";
1.110 -// }
1.111 -// }
1.112 -// std::cout << "Edges of the stGraphWrapper:\n";
1.113 -// FOR_EACH_LOC(stGW::EdgeIt, n, stgw) {
1.114 -// std::cout << " " << n << "\n";
1.115 -// }
1.116 -
1.117 -// stGW::NodeMap<bool> b(stgw);
1.118 -// FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
1.119 -// std::cout << n << ": " << b[n] <<"\n";
1.120 -// }
1.121 -
1.122 -// std::cout << "Bfs from s: \n";
1.123 -// BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
1.124 -// bfs_stgw.pushAndSetReached(stgw.S_NODE);
1.125 -// while (!bfs_stgw.finished()) {
1.126 -// std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n";
1.127 -// ++bfs_stgw;
1.128 -// }
1.129
1.130
1.131 Timer ts;
1.132 ts.reset();
1.133 - stGW::EdgeMap<int> max_flow(stgw);
1.134 + stGW::EdgeMap<int> flow(stgw);
1.135 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
1.136 - max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, max_flow);
1.137 + max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
1.138 // while (max_flow_test.augmentOnShortestPath()) { }
1.139 typedef ListGraph MutableGraph;
1.140 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
1.141 @@ -173,10 +96,10 @@
1.142 }
1.143 std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
1.144 std::cout << "elapsed time: " << ts << std::endl;
1.145 -// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
1.146 -// std::cout << e << ": " << max_flow[e] << "\n";
1.147 -// }
1.148 -// std::cout << "\n";
1.149 + FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
1.150 + if (flow[e]) std::cout << e << std::endl;
1.151 + }
1.152 + std::cout << std::endl;
1.153
1.154 ts.reset();
1.155 stGW::EdgeMap<int> pre_flow(stgw);