1.1 --- a/src/work/marci/bipartite_graph_wrapper.h Fri Apr 30 16:46:19 2004 +0000
1.2 +++ b/src/work/marci/bipartite_graph_wrapper.h Fri Apr 30 17:10:01 2004 +0000
1.3 @@ -31,9 +31,9 @@
1.4 SFalseTTrueMap;
1.5 SFalseTTrueMap* s_false_t_true_map;
1.6
1.7 - BipartiteGraphWrapper() : GraphWrapper<Graph>(0) { }
1.8 + BipartiteGraphWrapper() : GraphWrapper<Graph>() { }
1.9 void setSFalseTTrueMap(SFalseTTrueMap& _s_false_t_true_map) {
1.10 - s_false_t_true_map=_s_false_t_true_map;
1.11 + s_false_t_true_map=&_s_false_t_true_map;
1.12 }
1.13
1.14 public:
1.15 @@ -196,11 +196,11 @@
1.16 public:
1.17 typedef typename Parent::Node Node;
1.18 typedef typename Parent::Edge Edge;
1.19 - BipartiteGraph() : BipartiteGraphWrapper<Graph>(0),
1.20 + BipartiteGraph() : BipartiteGraphWrapper<Graph>(),
1.21 gr(), bipartite_map(gr),
1.22 s_false_t_true_map(bipartite_map) {
1.23 Parent::setGraph(gr);
1.24 - Parent::setSFalseTTrueMap(bipartite_map);
1.25 + Parent::setSFalseTTrueMap(s_false_t_true_map);
1.26 }
1.27
1.28 /// the \c bool parameter which can be \c S_Class or \c T_Class shows
2.1 --- a/src/work/marci/bipartite_matching_try_2.cc Fri Apr 30 16:46:19 2004 +0000
2.2 +++ b/src/work/marci/bipartite_matching_try_2.cc Fri Apr 30 17:10:01 2004 +0000
2.3 @@ -10,7 +10,6 @@
2.4 #include <time_measure.h>
2.5 #include <for_each_macros.h>
2.6 #include <bfs_iterator.h>
2.7 -#include <graph_wrapper.h>
2.8 #include <bipartite_graph_wrapper.h>
2.9 #include <maps.h>
2.10 #include <max_flow.h>
2.11 @@ -40,7 +39,9 @@
2.12 using namespace hugo;
2.13
2.14 int main() {
2.15 - typedef UndirListGraph Graph;
2.16 + //typedef UndirListGraph Graph;
2.17 + typedef BipartiteGraph<ListGraph> Graph;
2.18 +
2.19 typedef Graph::Node Node;
2.20 typedef Graph::NodeIt NodeIt;
2.21 typedef Graph::Edge Edge;
2.22 @@ -63,108 +64,30 @@
2.23 std::cin >> m;
2.24
2.25
2.26 - for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode());
2.27 - for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode());
2.28 + for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode(false));
2.29 + for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode(true));
2.30
2.31 random_init();
2.32 for(int i=0; i<m; ++i) {
2.33 g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
2.34 }
2.35
2.36 - Graph::NodeMap<int> ref_map(g, -1);
2.37 + std::cout << "Edges of the bipartite graph:" << std::endl;
2.38 + FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " ";
2.39 + std::cout << std::endl;
2.40
2.41 - IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
2.42 - for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false);
2.43 - for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true);
2.44 + typedef stGraphWrapper<Graph> stGW;
2.45 + stGW stgw(g);
2.46 + ConstMap<stGW::Edge, int> const1map(1);
2.47
2.48 -// Graph::Node u;
2.49 -// std::cout << "These nodes will be in S:\n";
2.50 -// //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen
2.51 -// //irni 1etlen FOR_EACH-csel.
2.52 -// for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u))
2.53 -// std::cout << u << " ";
2.54 -// std::cout << "\n";
2.55 -// std::cout << "These nodes will be in T:\n";
2.56 -// for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u))
2.57 -// std::cout << u << " ";
2.58 -// std::cout << "\n";
2.59
2.60 - typedef BipartiteGraphWrapper<Graph> BGW;
2.61 - BGW bgw(g, bipartite_map);
2.62 -
2.63 -// std::cout << "Nodes by NodeIt:\n";
2.64 -// FOR_EACH_LOC(BGW::NodeIt, n, bgw) {
2.65 -// std::cout << n << " ";
2.66 -// }
2.67 -// std::cout << "\n";
2.68 -// std::cout << "Nodes in S by ClassNodeIt:\n";
2.69 -// FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) {
2.70 -// std::cout << n << " ";
2.71 -// }
2.72 -// std::cout << "\n";
2.73 -// std::cout << "Nodes in T by ClassNodeIt:\n";
2.74 -// FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) {
2.75 -// std::cout << n << " ";
2.76 -// }
2.77 -// std::cout << "\n";
2.78 -// std::cout << "Edges of the bipartite graph:\n";
2.79 -// FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
2.80 -// std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
2.81 -// }
2.82 -
2.83 -// BGW::NodeMap<int> dbyj(bgw);
2.84 -// BGW::EdgeMap<int> dbyxcj(bgw);
2.85 -
2.86 - typedef stGraphWrapper<BGW> stGW;
2.87 - stGW stgw(bgw);
2.88 - ConstMap<stGW::Edge, int> const1map(1);
2.89 -// stGW::NodeMap<int> ize(stgw);
2.90 -
2.91 -// BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
2.92 -// Graph::NodeIt si;
2.93 -// Graph::Node s;
2.94 -// s=g.first(si);
2.95 -// bfs.pushAndSetReached(BGW::Node(s));
2.96 -// while (!bfs.finished()) { ++bfs; }
2.97 -
2.98 -// FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
2.99 -// std::cout << "out-edges of " << n << ":\n";
2.100 -// FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) {
2.101 -// std::cout << " " << e << "\n";
2.102 -// std::cout << " aNode: " << stgw.aNode(e) << "\n";
2.103 -// std::cout << " bNode: " << stgw.bNode(e) << "\n";
2.104 -// }
2.105 -// std::cout << "in-edges of " << n << ":\n";
2.106 -// FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) {
2.107 -// std::cout << " " << e << "\n";
2.108 -// std::cout << " aNode: " << stgw.aNode(e) << "\n";
2.109 -// std::cout << " bNode: " << stgw.bNode(e) << "\n";
2.110 -// }
2.111 -// }
2.112 -// std::cout << "Edges of the stGraphWrapper:\n";
2.113 -// FOR_EACH_LOC(stGW::EdgeIt, n, stgw) {
2.114 -// std::cout << " " << n << "\n";
2.115 -// }
2.116 -
2.117 -// stGW::NodeMap<bool> b(stgw);
2.118 -// FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
2.119 -// std::cout << n << ": " << b[n] <<"\n";
2.120 -// }
2.121 -
2.122 -// std::cout << "Bfs from s: \n";
2.123 -// BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
2.124 -// bfs_stgw.pushAndSetReached(stgw.S_NODE);
2.125 -// while (!bfs_stgw.finished()) {
2.126 -// std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n";
2.127 -// ++bfs_stgw;
2.128 -// }
2.129
2.130
2.131 Timer ts;
2.132 ts.reset();
2.133 - stGW::EdgeMap<int> max_flow(stgw);
2.134 + stGW::EdgeMap<int> flow(stgw);
2.135 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
2.136 - max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, max_flow);
2.137 + max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
2.138 // while (max_flow_test.augmentOnShortestPath()) { }
2.139 typedef ListGraph MutableGraph;
2.140 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
2.141 @@ -173,10 +96,10 @@
2.142 }
2.143 std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
2.144 std::cout << "elapsed time: " << ts << std::endl;
2.145 -// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
2.146 -// std::cout << e << ": " << max_flow[e] << "\n";
2.147 -// }
2.148 -// std::cout << "\n";
2.149 + FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
2.150 + if (flow[e]) std::cout << e << std::endl;
2.151 + }
2.152 + std::cout << std::endl;
2.153
2.154 ts.reset();
2.155 stGW::EdgeMap<int> pre_flow(stgw);
3.1 --- a/src/work/marci/graph_wrapper.h Fri Apr 30 16:46:19 2004 +0000
3.2 +++ b/src/work/marci/graph_wrapper.h Fri Apr 30 17:10:01 2004 +0000
3.3 @@ -11,7 +11,7 @@
3.4 ///\author Marton Makai
3.5
3.6 #include <invalid.h>
3.7 -#include <iter_map.h>
3.8 +//#include <iter_map.h>
3.9
3.10 namespace hugo {
3.11