1.1 --- a/src/work/marci/bipartite_graph_wrapper_test.cc Wed Sep 22 10:47:59 2004 +0000
1.2 +++ b/src/work/marci/bipartite_graph_wrapper_test.cc Wed Sep 22 12:25:50 2004 +0000
1.3 @@ -3,22 +3,26 @@
1.4 #include <fstream>
1.5 #include <vector>
1.6
1.7 -#include <sage_graph.h>
1.8 -//#include <smart_graph.h>
1.9 +//#include <sage_graph.h>
1.10 +#include <hugo/smart_graph.h>
1.11 //#include <dimacs.h>
1.12 #include <hugo/time_measure.h>
1.13 -#include <for_each_macros.h>
1.14 +//#include <for_each_macros.h>
1.15 #include <bfs_dfs.h>
1.16 #include <hugo/graph_wrapper.h>
1.17 #include <bipartite_graph_wrapper.h>
1.18 #include <hugo/maps.h>
1.19 -#include <hugo/max_flow.h>
1.20 +#include <hugo/preflow.h>
1.21 #include <augmenting_flow.h>
1.22
1.23 +using std::cout;
1.24 +using std::endl;
1.25 +
1.26 using namespace hugo;
1.27
1.28 int main() {
1.29 - typedef UndirSageGraph Graph;
1.30 + //typedef UndirSageGraph Graph;
1.31 + typedef SmartGraph Graph;
1.32 typedef Graph::Node Node;
1.33 typedef Graph::NodeIt NodeIt;
1.34 typedef Graph::Edge Edge;
1.35 @@ -52,93 +56,92 @@
1.36 for (int i=3; i<6; ++i) bipartite_map.insert(nodes[i], true);
1.37
1.38 Graph::Node u;
1.39 - std::cout << "These nodes will be in S:\n";
1.40 + cout << "These nodes will be in S:" << endl;
1.41 //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen
1.42 //irni 1etlen FOR_EACH-csel.
1.43 - for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u))
1.44 - std::cout << u << " ";
1.45 - std::cout << "\n";
1.46 - std::cout << "These nodes will be in T:\n";
1.47 - for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u))
1.48 - std::cout << u << " ";
1.49 - std::cout << "\n";
1.50 + for (bipartite_map.first(u, false); u!=INVALID; bipartite_map.next(u))
1.51 + cout << g.id(u) << " ";
1.52 + cout << endl;
1.53 + cout << "These nodes will be in T:" << endl;
1.54 + for (bipartite_map.first(u, true); u!=INVALID; bipartite_map.next(u))
1.55 + cout << g.id(u) << " ";
1.56 + cout << endl;
1.57
1.58 typedef BipartiteGraphWrapper<Graph> BGW;
1.59 BGW bgw(g, bipartite_map);
1.60
1.61 - std::cout << "Nodes by NodeIt:\n";
1.62 - FOR_EACH_LOC(BGW::NodeIt, n, bgw) {
1.63 - std::cout << n << " ";
1.64 - }
1.65 - std::cout << "\n";
1.66 - std::cout << "Nodes in S by ClassNodeIt:\n";
1.67 - FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) {
1.68 - std::cout << n << " ";
1.69 - }
1.70 - std::cout << "\n";
1.71 - std::cout << "Nodes in T by ClassNodeIt:\n";
1.72 - FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) {
1.73 - std::cout << n << " ";
1.74 - }
1.75 - std::cout << "\n";
1.76 - std::cout << "Edges of the bipartite graph:\n";
1.77 - FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
1.78 - std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
1.79 - }
1.80 + cout << "Nodes by NodeIt:" << endl;
1.81 + for (BGW::NodeIt n(bgw); n!=INVALID; ++n)
1.82 + cout << g.id(n) << " ";
1.83 + cout << endl;
1.84 +
1.85 + cout << "Nodes in S by ClassNodeIt:" << endl;
1.86 + for (BGW::ClassNodeIt n(bgw, bgw.S_CLASS); n!=INVALID; ++n)
1.87 + cout << g.id(n) << " ";
1.88 + cout << endl;
1.89 +
1.90 + cout << "Nodes in T by ClassNodeIt:" << endl;
1.91 + for (BGW::ClassNodeIt n(bgw, bgw.T_CLASS); n!=INVALID; ++n)
1.92 + cout << g.id(n) << " ";
1.93 + cout << endl;
1.94 +
1.95 + cout << "Edges of the bipartite graph:" << endl;
1.96 + for (BGW::EdgeIt e(bgw); e!=INVALID; ++e)
1.97 + cout << g.id(bgw.tail(e)) << "->" << g.id(bgw.head(e)) << endl;
1.98
1.99 BGW::NodeMap<int> dbyj(bgw);
1.100 BGW::EdgeMap<int> dbyxcj(bgw);
1.101
1.102 - typedef stBipartiteGraphWrapper<BGW> stGW;
1.103 - stGW stgw(bgw);
1.104 - ConstMap<stGW::Edge, int> const1map(1);
1.105 - stGW::NodeMap<int> ize(stgw);
1.106 - stGW::EdgeMap<int> flow(stgw);
1.107 +// typedef stBipartiteGraphWrapper<BGW> stGW;
1.108 +// stGW stgw(bgw);
1.109 +// ConstMap<stGW::Edge, int> const1map(1);
1.110 +// stGW::NodeMap<int> ize(stgw);
1.111 +// stGW::EdgeMap<int> flow(stgw);
1.112
1.113 - BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
1.114 - Graph::NodeIt si;
1.115 - Graph::Node s;
1.116 - s=g.first(si);
1.117 - bfs.pushAndSetReached(BGW::Node(s));
1.118 - while (!bfs.finished()) { ++bfs; }
1.119 +// BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
1.120 +// Graph::NodeIt si;
1.121 +// Graph::Node s;
1.122 +// s=g.first(si);
1.123 +// bfs.pushAndSetReached(BGW::Node(s));
1.124 +// while (!bfs.finished()) { ++bfs; }
1.125
1.126 - FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
1.127 - std::cout << "out-edges of " << n << ":\n";
1.128 - FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) {
1.129 - std::cout << " " << e << "\n";
1.130 - std::cout << " aNode: " << stgw.aNode(e) << "\n";
1.131 - std::cout << " bNode: " << stgw.bNode(e) << "\n";
1.132 - }
1.133 - std::cout << "in-edges of " << n << ":\n";
1.134 - FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) {
1.135 - std::cout << " " << e << "\n";
1.136 - std::cout << " aNode: " << stgw.aNode(e) << "\n";
1.137 - std::cout << " bNode: " << stgw.bNode(e) << "\n";
1.138 - }
1.139 - }
1.140 - std::cout << "Edges of the stGraphWrapper:\n";
1.141 - FOR_EACH_LOC(stGW::EdgeIt, n, stgw) {
1.142 - std::cout << " " << n << "\n";
1.143 - }
1.144 +// FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
1.145 +// cout << "out-edges of " << n << ":" << endl;
1.146 +// FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) {
1.147 +// cout << " " << e << endl;
1.148 +// cout << " aNode: " << stgw.aNode(e) << endl;
1.149 +// cout << " bNode: " << stgw.bNode(e) << endl;
1.150 +// }
1.151 +// cout << "in-edges of " << n << ":" << endl;
1.152 +// FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) {
1.153 +// cout << " " << e << endl;
1.154 +// cout << " aNode: " << stgw.aNode(e) << endl;
1.155 +// cout << " bNode: " << stgw.bNode(e) << endl;
1.156 +// }
1.157 +// }
1.158 +// cout << "Edges of the stGraphWrapper:" << endl;
1.159 +// FOR_EACH_LOC(stGW::EdgeIt, n, stgw) {
1.160 +// cout << " " << n << endl;
1.161 +// }
1.162
1.163 - stGW::NodeMap<bool> b(stgw);
1.164 - FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
1.165 - std::cout << n << ": " << b[n] <<"\n";
1.166 - }
1.167 +// stGW::NodeMap<bool> b(stgw);
1.168 +// FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
1.169 +// cout << n << ": " << b[n] << endl;
1.170 +// }
1.171
1.172 - std::cout << "Bfs from s: \n";
1.173 - BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
1.174 - bfs_stgw.pushAndSetReached(stgw.S_NODE);
1.175 - while (!bfs_stgw.finished()) {
1.176 - std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n";
1.177 - ++bfs_stgw;
1.178 - }
1.179 +// cout << "Bfs from s:" << endl;
1.180 +// BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
1.181 +// bfs_stgw.pushAndSetReached(stgw.S_NODE);
1.182 +// while (!bfs_stgw.finished()) {
1.183 +// cout << " " << stGW::OutEdgeIt(bfs_stgw) << endl;
1.184 +// ++bfs_stgw;
1.185 +// }
1.186
1.187 - AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
1.188 - max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
1.189 - while (max_flow_test.augmentOnShortestPath()) { }
1.190 +// AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
1.191 +// max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
1.192 +// while (max_flow_test.augmentOnShortestPath()) { }
1.193
1.194 - std::cout << max_flow_test.flowValue() << std::endl;
1.195 +// cout << max_flow_test.flowValue() << std::endl;
1.196
1.197 return 0;
1.198 }