1.1 --- a/src/work/marci/bipartite_graph_wrapper_test.cc Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,147 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#include <iostream>
1.6 -#include <fstream>
1.7 -#include <vector>
1.8 -
1.9 -//#include <sage_graph.h>
1.10 -#include <lemon/smart_graph.h>
1.11 -//#include <dimacs.h>
1.12 -#include <lemon/time_measure.h>
1.13 -//#include <for_each_macros.h>
1.14 -#include <bfs_dfs.h>
1.15 -#include <lemon/graph_wrapper.h>
1.16 -#include <bipartite_graph_wrapper.h>
1.17 -#include <lemon/maps.h>
1.18 -#include <lemon/preflow.h>
1.19 -#include <augmenting_flow.h>
1.20 -
1.21 -using std::cout;
1.22 -using std::endl;
1.23 -
1.24 -using namespace lemon;
1.25 -
1.26 -int main() {
1.27 - //typedef UndirSageGraph Graph;
1.28 - typedef SmartGraph Graph;
1.29 - typedef Graph::Node Node;
1.30 - typedef Graph::NodeIt NodeIt;
1.31 - typedef Graph::Edge Edge;
1.32 - typedef Graph::EdgeIt EdgeIt;
1.33 - typedef Graph::OutEdgeIt OutEdgeIt;
1.34 -
1.35 - Graph g;
1.36 -// std::vector<Graph::Node> s_nodes;
1.37 -// std::vector<Graph::Node> t_nodes;
1.38 -// for (int i=0; i<3; ++i) s_nodes.push_back(g.addNode());
1.39 -// for (int i=0; i<3; ++i) t_nodes.push_back(g.addNode());
1.40 -// g.addEdge(s_nodes[0], t_nodes[2]);
1.41 -// g.addEdge(t_nodes[1], s_nodes[2]);
1.42 -// g.addEdge(s_nodes[0], t_nodes[1]);
1.43 -
1.44 -// Graph::NodeMap<int> ref_map(g, -1);
1.45 -// IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
1.46 -// for (int i=0; i<3; ++i) bipartite_map.insert(s_nodes[i], false);
1.47 -// for (int i=0; i<3; ++i) bipartite_map.insert(t_nodes[i], true);
1.48 -
1.49 - std::vector<Graph::Node> nodes;
1.50 - for (int i=0; i<3; ++i) nodes.push_back(g.addNode());
1.51 - for (int i=3; i<6; ++i) nodes.push_back(g.addNode());
1.52 - g.addEdge(nodes[0], nodes[3+2]);
1.53 - g.addEdge(nodes[3+1], nodes[2]);
1.54 - g.addEdge(nodes[0], nodes[3+1]);
1.55 -
1.56 - Graph::NodeMap<int> ref_map(g, -1);
1.57 - IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
1.58 - for (int i=0; i<3; ++i) bipartite_map.insert(nodes[i], false);
1.59 - for (int i=3; i<6; ++i) bipartite_map.insert(nodes[i], true);
1.60 -
1.61 - Graph::Node u;
1.62 - cout << "These nodes will be in S:" << endl;
1.63 - //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen
1.64 - //irni 1etlen FOR_EACH-csel.
1.65 - for (bipartite_map.first(u, false); u!=INVALID; bipartite_map.next(u))
1.66 - cout << g.id(u) << " ";
1.67 - cout << endl;
1.68 - cout << "These nodes will be in T:" << endl;
1.69 - for (bipartite_map.first(u, true); u!=INVALID; bipartite_map.next(u))
1.70 - cout << g.id(u) << " ";
1.71 - cout << endl;
1.72 -
1.73 - typedef BipartiteGraphWrapper<Graph> BGW;
1.74 - BGW bgw(g, bipartite_map);
1.75 -
1.76 - cout << "Nodes by NodeIt:" << endl;
1.77 - for (BGW::NodeIt n(bgw); n!=INVALID; ++n)
1.78 - cout << g.id(n) << " ";
1.79 - cout << endl;
1.80 -
1.81 - cout << "Nodes in S by ClassNodeIt:" << endl;
1.82 - for (BGW::ClassNodeIt n(bgw, bgw.S_CLASS); n!=INVALID; ++n)
1.83 - cout << g.id(n) << " ";
1.84 - cout << endl;
1.85 -
1.86 - cout << "Nodes in T by ClassNodeIt:" << endl;
1.87 - for (BGW::ClassNodeIt n(bgw, bgw.T_CLASS); n!=INVALID; ++n)
1.88 - cout << g.id(n) << " ";
1.89 - cout << endl;
1.90 -
1.91 - cout << "Edges of the bipartite graph:" << endl;
1.92 - for (BGW::EdgeIt e(bgw); e!=INVALID; ++e)
1.93 - cout << g.id(bgw.source(e)) << "->" << g.id(bgw.target(e)) << endl;
1.94 -
1.95 - BGW::NodeMap<int> dbyj(bgw);
1.96 - BGW::EdgeMap<int> dbyxcj(bgw);
1.97 -
1.98 -// typedef stBipartiteGraphWrapper<BGW> stGW;
1.99 -// stGW stgw(bgw);
1.100 -// ConstMap<stGW::Edge, int> const1map(1);
1.101 -// stGW::NodeMap<int> ize(stgw);
1.102 -// stGW::EdgeMap<int> flow(stgw);
1.103 -
1.104 -// BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
1.105 -// Graph::NodeIt si;
1.106 -// Graph::Node s;
1.107 -// s=g.first(si);
1.108 -// bfs.pushAndSetReached(BGW::Node(s));
1.109 -// while (!bfs.finished()) { ++bfs; }
1.110 -
1.111 -// FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
1.112 -// cout << "out-edges of " << n << ":" << endl;
1.113 -// FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) {
1.114 -// cout << " " << e << endl;
1.115 -// cout << " aNode: " << stgw.aNode(e) << endl;
1.116 -// cout << " bNode: " << stgw.bNode(e) << endl;
1.117 -// }
1.118 -// cout << "in-edges of " << n << ":" << endl;
1.119 -// FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) {
1.120 -// cout << " " << e << endl;
1.121 -// cout << " aNode: " << stgw.aNode(e) << endl;
1.122 -// cout << " bNode: " << stgw.bNode(e) << endl;
1.123 -// }
1.124 -// }
1.125 -// cout << "Edges of the stGraphWrapper:" << endl;
1.126 -// FOR_EACH_LOC(stGW::EdgeIt, n, stgw) {
1.127 -// cout << " " << n << endl;
1.128 -// }
1.129 -
1.130 -// stGW::NodeMap<bool> b(stgw);
1.131 -// FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
1.132 -// cout << n << ": " << b[n] << endl;
1.133 -// }
1.134 -
1.135 -// cout << "Bfs from s:" << endl;
1.136 -// BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
1.137 -// bfs_stgw.pushAndSetReached(stgw.S_NODE);
1.138 -// while (!bfs_stgw.finished()) {
1.139 -// cout << " " << stGW::OutEdgeIt(bfs_stgw) << endl;
1.140 -// ++bfs_stgw;
1.141 -// }
1.142 -
1.143 -// AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
1.144 -// max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
1.145 -// while (max_flow_test.augmentOnShortestPath()) { }
1.146 -
1.147 -// cout << max_flow_test.flowValue() << std::endl;
1.148 -
1.149 - return 0;
1.150 -}