1.1 --- a/src/work/marci/bipartite_graph_wrapper.h Wed Sep 22 10:47:59 2004 +0000
1.2 +++ b/src/work/marci/bipartite_graph_wrapper.h Wed Sep 22 12:25:50 2004 +0000
1.3 @@ -71,19 +71,24 @@
1.4 friend class OutEdgeIt;
1.5 class InEdgeIt;
1.6 friend class InEdgeIt;
1.7 - class ClassNodeIt {
1.8 + class ClassNodeIt : public Node {
1.9 friend class BipartiteGraphWrapper<Graph>;
1.10 protected:
1.11 - Node n;
1.12 + const BipartiteGraphWrapper<Graph>* gw;
1.13 public:
1.14 ClassNodeIt() { }
1.15 - ClassNodeIt(const Invalid& i) : n(i) { }
1.16 - ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) {
1.17 - _G.s_false_t_true_map->first(n, _class);
1.18 + ClassNodeIt(Invalid i) : Node(i) { }
1.19 + ClassNodeIt(const BipartiteGraphWrapper<Graph>& _gw, bool _class) :
1.20 + Node(), gw(&_gw) {
1.21 + _gw.s_false_t_true_map->first(*this, _class);
1.22 }
1.23 //FIXME needed in new concept, important here
1.24 - ClassNodeIt(const Node& _n) : n(_n) { }
1.25 - operator Node() const { return n; }
1.26 + ClassNodeIt(const BipartiteGraphWrapper<Graph>& _gw, const Node& n) :
1.27 + Node(n), gw(&_gw) { }
1.28 + ClassNodeIt& operator++() {
1.29 + gw->s_false_t_true_map->next(*this);
1.30 + return *this;
1.31 + }
1.32 };
1.33 // class SNodeIt {
1.34 // Node n;
1.35 @@ -105,87 +110,88 @@
1.36 // }
1.37 // operator Node() const { return n; }
1.38 // };
1.39 - class OutEdgeIt {
1.40 - friend class BipartiteGraphWrapper<Graph>;
1.41 - protected:
1.42 - typename Graph::OutEdgeIt e;
1.43 - public:
1.44 - OutEdgeIt() { }
1.45 - OutEdgeIt(const Invalid& i) : e(i) { }
1.46 - OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
1.47 - if (!(*(_G.s_false_t_true_map))[_n])
1.48 - e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
1.49 - else
1.50 - e=INVALID;
1.51 - }
1.52 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.53 - };
1.54 - class InEdgeIt {
1.55 - friend class BipartiteGraphWrapper<Graph>;
1.56 - protected:
1.57 - typename Graph::InEdgeIt e;
1.58 - public:
1.59 - InEdgeIt() { }
1.60 - InEdgeIt(const Invalid& i) : e(i) { }
1.61 - InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
1.62 - if ((*(_G.s_false_t_true_map))[_n])
1.63 - e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
1.64 - else
1.65 - e=INVALID;
1.66 - }
1.67 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.68 - };
1.69 +// class OutEdgeIt {
1.70 +// friend class BipartiteGraphWrapper<Graph>;
1.71 +// protected:
1.72 +// typename Graph::OutEdgeIt e;
1.73 +// public:
1.74 +// OutEdgeIt() { }
1.75 +// OutEdgeIt(const Invalid& i) : e(i) { }
1.76 +// OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
1.77 +// if (!(*(_G.s_false_t_true_map))[_n])
1.78 +// e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
1.79 +// else
1.80 +// e=INVALID;
1.81 +// }
1.82 +// operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.83 +// };
1.84 +// class InEdgeIt {
1.85 +// friend class BipartiteGraphWrapper<Graph>;
1.86 +// protected:
1.87 +// typename Graph::InEdgeIt e;
1.88 +// public:
1.89 +// InEdgeIt() { }
1.90 +// InEdgeIt(const Invalid& i) : e(i) { }
1.91 +// InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
1.92 +// if ((*(_G.s_false_t_true_map))[_n])
1.93 +// e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
1.94 +// else
1.95 +// e=INVALID;
1.96 +// }
1.97 +// operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.98 +// };
1.99
1.100 using GraphWrapper<Graph>::first;
1.101 ClassNodeIt& first(ClassNodeIt& n, bool _class) const {
1.102 - n=ClassNodeIt(*this, _class) ; return n; }
1.103 + n=ClassNodeIt(*this, _class); return n;
1.104 + }
1.105 // SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
1.106 // TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
1.107 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.108 - i=OutEdgeIt(*this, p); return i;
1.109 - }
1.110 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.111 - i=InEdgeIt(*this, p); return i;
1.112 - }
1.113 +// OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.114 +// i=OutEdgeIt(*this, p); return i;
1.115 +// }
1.116 +// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.117 +// i=InEdgeIt(*this, p); return i;
1.118 +// }
1.119
1.120 - using GraphWrapper<Graph>::next;
1.121 - ClassNodeIt& next(ClassNodeIt& n) const {
1.122 - this->s_false_t_true_map->next(n.n); return n;
1.123 - }
1.124 +// using GraphWrapper<Graph>::next;
1.125 +// ClassNodeIt& next(ClassNodeIt& n) const {
1.126 +// this->s_false_t_true_map->next(n.n); return n;
1.127 +// }
1.128 // SNodeIt& next(SNodeIt& n) const {
1.129 // this->s_false_t_true_map->next(n); return n;
1.130 // }
1.131 // TNodeIt& next(TNodeIt& n) const {
1.132 // this->s_false_t_true_map->next(n); return n;
1.133 // }
1.134 - OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1.135 - InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1.136 +// OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1.137 +// InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1.138
1.139 - Node tail(const Edge& e) {
1.140 - if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
1.141 - return Node(this->graph->tail(e));
1.142 - else
1.143 - return Node(this->graph->head(e));
1.144 - }
1.145 - Node head(const Edge& e) {
1.146 - if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
1.147 - return Node(this->graph->head(e));
1.148 - else
1.149 - return Node(this->graph->tail(e));
1.150 - }
1.151 +// Node tail(const Edge& e) {
1.152 +// if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
1.153 +// return Node(this->graph->tail(e));
1.154 +// else
1.155 +// return Node(this->graph->head(e));
1.156 +// }
1.157 +// Node head(const Edge& e) {
1.158 +// if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
1.159 +// return Node(this->graph->head(e));
1.160 +// else
1.161 +// return Node(this->graph->tail(e));
1.162 +// }
1.163
1.164 - Node aNode(const OutEdgeIt& e) const {
1.165 - return Node(this->graph->aNode(e.e));
1.166 - }
1.167 - Node aNode(const InEdgeIt& e) const {
1.168 - return Node(this->graph->aNode(e.e));
1.169 - }
1.170 - Node bNode(const OutEdgeIt& e) const {
1.171 - return Node(this->graph->bNode(e.e));
1.172 - }
1.173 - Node bNode(const InEdgeIt& e) const {
1.174 - return Node(this->graph->bNode(e.e));
1.175 - }
1.176 +// Node aNode(const OutEdgeIt& e) const {
1.177 +// return Node(this->graph->aNode(e.e));
1.178 +// }
1.179 +// Node aNode(const InEdgeIt& e) const {
1.180 +// return Node(this->graph->aNode(e.e));
1.181 +// }
1.182 +// Node bNode(const OutEdgeIt& e) const {
1.183 +// return Node(this->graph->bNode(e.e));
1.184 +// }
1.185 +// Node bNode(const InEdgeIt& e) const {
1.186 +// return Node(this->graph->bNode(e.e));
1.187 +// }
1.188
1.189 /// Returns true iff \c n is in S.
1.190 bool inSClass(const Node& n) const {
2.1 --- a/src/work/marci/bipartite_graph_wrapper_test.cc Wed Sep 22 10:47:59 2004 +0000
2.2 +++ b/src/work/marci/bipartite_graph_wrapper_test.cc Wed Sep 22 12:25:50 2004 +0000
2.3 @@ -3,22 +3,26 @@
2.4 #include <fstream>
2.5 #include <vector>
2.6
2.7 -#include <sage_graph.h>
2.8 -//#include <smart_graph.h>
2.9 +//#include <sage_graph.h>
2.10 +#include <hugo/smart_graph.h>
2.11 //#include <dimacs.h>
2.12 #include <hugo/time_measure.h>
2.13 -#include <for_each_macros.h>
2.14 +//#include <for_each_macros.h>
2.15 #include <bfs_dfs.h>
2.16 #include <hugo/graph_wrapper.h>
2.17 #include <bipartite_graph_wrapper.h>
2.18 #include <hugo/maps.h>
2.19 -#include <hugo/max_flow.h>
2.20 +#include <hugo/preflow.h>
2.21 #include <augmenting_flow.h>
2.22
2.23 +using std::cout;
2.24 +using std::endl;
2.25 +
2.26 using namespace hugo;
2.27
2.28 int main() {
2.29 - typedef UndirSageGraph Graph;
2.30 + //typedef UndirSageGraph Graph;
2.31 + typedef SmartGraph Graph;
2.32 typedef Graph::Node Node;
2.33 typedef Graph::NodeIt NodeIt;
2.34 typedef Graph::Edge Edge;
2.35 @@ -52,93 +56,92 @@
2.36 for (int i=3; i<6; ++i) bipartite_map.insert(nodes[i], true);
2.37
2.38 Graph::Node u;
2.39 - std::cout << "These nodes will be in S:\n";
2.40 + cout << "These nodes will be in S:" << endl;
2.41 //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen
2.42 //irni 1etlen FOR_EACH-csel.
2.43 - for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u))
2.44 - std::cout << u << " ";
2.45 - std::cout << "\n";
2.46 - std::cout << "These nodes will be in T:\n";
2.47 - for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u))
2.48 - std::cout << u << " ";
2.49 - std::cout << "\n";
2.50 + for (bipartite_map.first(u, false); u!=INVALID; bipartite_map.next(u))
2.51 + cout << g.id(u) << " ";
2.52 + cout << endl;
2.53 + cout << "These nodes will be in T:" << endl;
2.54 + for (bipartite_map.first(u, true); u!=INVALID; bipartite_map.next(u))
2.55 + cout << g.id(u) << " ";
2.56 + cout << endl;
2.57
2.58 typedef BipartiteGraphWrapper<Graph> BGW;
2.59 BGW bgw(g, bipartite_map);
2.60
2.61 - std::cout << "Nodes by NodeIt:\n";
2.62 - FOR_EACH_LOC(BGW::NodeIt, n, bgw) {
2.63 - std::cout << n << " ";
2.64 - }
2.65 - std::cout << "\n";
2.66 - std::cout << "Nodes in S by ClassNodeIt:\n";
2.67 - FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) {
2.68 - std::cout << n << " ";
2.69 - }
2.70 - std::cout << "\n";
2.71 - std::cout << "Nodes in T by ClassNodeIt:\n";
2.72 - FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) {
2.73 - std::cout << n << " ";
2.74 - }
2.75 - std::cout << "\n";
2.76 - std::cout << "Edges of the bipartite graph:\n";
2.77 - FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
2.78 - std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
2.79 - }
2.80 + cout << "Nodes by NodeIt:" << endl;
2.81 + for (BGW::NodeIt n(bgw); n!=INVALID; ++n)
2.82 + cout << g.id(n) << " ";
2.83 + cout << endl;
2.84 +
2.85 + cout << "Nodes in S by ClassNodeIt:" << endl;
2.86 + for (BGW::ClassNodeIt n(bgw, bgw.S_CLASS); n!=INVALID; ++n)
2.87 + cout << g.id(n) << " ";
2.88 + cout << endl;
2.89 +
2.90 + cout << "Nodes in T by ClassNodeIt:" << endl;
2.91 + for (BGW::ClassNodeIt n(bgw, bgw.T_CLASS); n!=INVALID; ++n)
2.92 + cout << g.id(n) << " ";
2.93 + cout << endl;
2.94 +
2.95 + cout << "Edges of the bipartite graph:" << endl;
2.96 + for (BGW::EdgeIt e(bgw); e!=INVALID; ++e)
2.97 + cout << g.id(bgw.tail(e)) << "->" << g.id(bgw.head(e)) << endl;
2.98
2.99 BGW::NodeMap<int> dbyj(bgw);
2.100 BGW::EdgeMap<int> dbyxcj(bgw);
2.101
2.102 - typedef stBipartiteGraphWrapper<BGW> stGW;
2.103 - stGW stgw(bgw);
2.104 - ConstMap<stGW::Edge, int> const1map(1);
2.105 - stGW::NodeMap<int> ize(stgw);
2.106 - stGW::EdgeMap<int> flow(stgw);
2.107 +// typedef stBipartiteGraphWrapper<BGW> stGW;
2.108 +// stGW stgw(bgw);
2.109 +// ConstMap<stGW::Edge, int> const1map(1);
2.110 +// stGW::NodeMap<int> ize(stgw);
2.111 +// stGW::EdgeMap<int> flow(stgw);
2.112
2.113 - BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
2.114 - Graph::NodeIt si;
2.115 - Graph::Node s;
2.116 - s=g.first(si);
2.117 - bfs.pushAndSetReached(BGW::Node(s));
2.118 - while (!bfs.finished()) { ++bfs; }
2.119 +// BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
2.120 +// Graph::NodeIt si;
2.121 +// Graph::Node s;
2.122 +// s=g.first(si);
2.123 +// bfs.pushAndSetReached(BGW::Node(s));
2.124 +// while (!bfs.finished()) { ++bfs; }
2.125
2.126 - FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
2.127 - std::cout << "out-edges of " << n << ":\n";
2.128 - FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) {
2.129 - std::cout << " " << e << "\n";
2.130 - std::cout << " aNode: " << stgw.aNode(e) << "\n";
2.131 - std::cout << " bNode: " << stgw.bNode(e) << "\n";
2.132 - }
2.133 - std::cout << "in-edges of " << n << ":\n";
2.134 - FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) {
2.135 - std::cout << " " << e << "\n";
2.136 - std::cout << " aNode: " << stgw.aNode(e) << "\n";
2.137 - std::cout << " bNode: " << stgw.bNode(e) << "\n";
2.138 - }
2.139 - }
2.140 - std::cout << "Edges of the stGraphWrapper:\n";
2.141 - FOR_EACH_LOC(stGW::EdgeIt, n, stgw) {
2.142 - std::cout << " " << n << "\n";
2.143 - }
2.144 +// FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
2.145 +// cout << "out-edges of " << n << ":" << endl;
2.146 +// FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) {
2.147 +// cout << " " << e << endl;
2.148 +// cout << " aNode: " << stgw.aNode(e) << endl;
2.149 +// cout << " bNode: " << stgw.bNode(e) << endl;
2.150 +// }
2.151 +// cout << "in-edges of " << n << ":" << endl;
2.152 +// FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) {
2.153 +// cout << " " << e << endl;
2.154 +// cout << " aNode: " << stgw.aNode(e) << endl;
2.155 +// cout << " bNode: " << stgw.bNode(e) << endl;
2.156 +// }
2.157 +// }
2.158 +// cout << "Edges of the stGraphWrapper:" << endl;
2.159 +// FOR_EACH_LOC(stGW::EdgeIt, n, stgw) {
2.160 +// cout << " " << n << endl;
2.161 +// }
2.162
2.163 - stGW::NodeMap<bool> b(stgw);
2.164 - FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
2.165 - std::cout << n << ": " << b[n] <<"\n";
2.166 - }
2.167 +// stGW::NodeMap<bool> b(stgw);
2.168 +// FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
2.169 +// cout << n << ": " << b[n] << endl;
2.170 +// }
2.171
2.172 - std::cout << "Bfs from s: \n";
2.173 - BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
2.174 - bfs_stgw.pushAndSetReached(stgw.S_NODE);
2.175 - while (!bfs_stgw.finished()) {
2.176 - std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n";
2.177 - ++bfs_stgw;
2.178 - }
2.179 +// cout << "Bfs from s:" << endl;
2.180 +// BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
2.181 +// bfs_stgw.pushAndSetReached(stgw.S_NODE);
2.182 +// while (!bfs_stgw.finished()) {
2.183 +// cout << " " << stGW::OutEdgeIt(bfs_stgw) << endl;
2.184 +// ++bfs_stgw;
2.185 +// }
2.186
2.187 - AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
2.188 - max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
2.189 - while (max_flow_test.augmentOnShortestPath()) { }
2.190 +// AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
2.191 +// max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
2.192 +// while (max_flow_test.augmentOnShortestPath()) { }
2.193
2.194 - std::cout << max_flow_test.flowValue() << std::endl;
2.195 +// cout << max_flow_test.flowValue() << std::endl;
2.196
2.197 return 0;
2.198 }