More documented file.
7 #include <sage_graph.h>
8 //#include <smart_graph.h>
10 #include <hugo/time_measure.h>
11 #include <hugo/for_each_macros.h>
13 #include <hugo/graph_wrapper.h>
14 #include <bipartite_graph_wrapper.h>
15 #include <hugo/maps.h>
19 * Inicializalja a veletlenszamgeneratort.
20 * Figyelem, ez nem jo igazi random szamokhoz,
21 * erre ne bizzad a titkaidat!
25 unsigned int seed = getpid();
33 * Egy veletlen int-et ad vissza 0 es m-1 kozott.
37 return int( double(m) * rand() / (RAND_MAX + 1.0) );
43 typedef UndirSageGraph Graph;
44 typedef Graph::Node Node;
45 typedef Graph::NodeIt NodeIt;
46 typedef Graph::Edge Edge;
47 typedef Graph::EdgeIt EdgeIt;
48 typedef Graph::OutEdgeIt OutEdgeIt;
52 std::vector<Graph::Node> s_nodes;
53 std::vector<Graph::Node> t_nodes;
56 std::cout << "number of nodes in the first color class=";
59 std::cout << "number of nodes in the second color class=";
62 std::cout << "number of edges=";
66 for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode());
67 for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode());
70 for(int i=0; i<m; ++i) {
71 g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
74 Graph::NodeMap<int> ref_map(g, -1);
76 IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
77 for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false);
78 for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true);
81 // std::cout << "These nodes will be in S:\n";
82 // //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen
83 // //irni 1etlen FOR_EACH-csel.
84 // for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u))
85 // std::cout << u << " ";
87 // std::cout << "These nodes will be in T:\n";
88 // for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u))
89 // std::cout << u << " ";
92 typedef BipartiteGraphWrapper<Graph> BGW;
93 BGW bgw(g, bipartite_map);
95 // std::cout << "Nodes by NodeIt:\n";
96 // FOR_EACH_LOC(BGW::NodeIt, n, bgw) {
97 // std::cout << n << " ";
100 // std::cout << "Nodes in S by ClassNodeIt:\n";
101 // FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) {
102 // std::cout << n << " ";
104 // std::cout << "\n";
105 // std::cout << "Nodes in T by ClassNodeIt:\n";
106 // FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) {
107 // std::cout << n << " ";
109 // std::cout << "\n";
110 // std::cout << "Edges of the bipartite graph:\n";
111 // FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
112 // std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
115 // BGW::NodeMap<int> dbyj(bgw);
116 // BGW::EdgeMap<int> dbyxcj(bgw);
118 typedef stGraphWrapper<BGW> stGW;
120 ConstMap<stGW::Edge, int> const1map(1);
121 // stGW::NodeMap<int> ize(stgw);
123 // BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
127 // bfs.pushAndSetReached(BGW::Node(s));
128 // while (!bfs.finished()) { ++bfs; }
130 // FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
131 // std::cout << "out-edges of " << n << ":\n";
132 // FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) {
133 // std::cout << " " << e << "\n";
134 // std::cout << " aNode: " << stgw.aNode(e) << "\n";
135 // std::cout << " bNode: " << stgw.bNode(e) << "\n";
137 // std::cout << "in-edges of " << n << ":\n";
138 // FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) {
139 // std::cout << " " << e << "\n";
140 // std::cout << " aNode: " << stgw.aNode(e) << "\n";
141 // std::cout << " bNode: " << stgw.bNode(e) << "\n";
144 // std::cout << "Edges of the stGraphWrapper:\n";
145 // FOR_EACH_LOC(stGW::EdgeIt, n, stgw) {
146 // std::cout << " " << n << "\n";
149 // stGW::NodeMap<bool> b(stgw);
150 // FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
151 // std::cout << n << ": " << b[n] <<"\n";
154 // std::cout << "Bfs from s: \n";
155 // BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
156 // bfs_stgw.pushAndSetReached(stgw.S_NODE);
157 // while (!bfs_stgw.finished()) {
158 // std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n";
165 stGW::EdgeMap<int> max_flow(stgw);
166 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
167 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, max_flow);
168 // while (max_flow_test.augmentOnShortestPath()) { }
169 typedef SageGraph MutableGraph;
170 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
171 while (max_flow_test.augmentOnBlockingFlow2()) {
172 std::cout << max_flow_test.flowValue() << std::endl;
174 std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
175 std::cout << "elapsed time: " << ts << std::endl;
176 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
177 // std::cout << e << ": " << max_flow[e] << "\n";
179 // std::cout << "\n";
182 stGW::EdgeMap<int> pre_flow(stgw);
183 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
184 pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow/*, true*/);
186 std::cout << "pre flow value: " << max_flow_test.flowValue() << std::endl;
187 std::cout << "elapsed time: " << ts << std::endl;
188 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
189 // std::cout << e << ": " << pre_flow[e] << "\n";
191 // std::cout << "\n";