Changeset 902:309d81806228 in lemon0.x for src
 Timestamp:
 09/22/04 14:25:50 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1210
 Location:
 src/work/marci
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/bipartite_graph_wrapper.h
r768 r902 72 72 class InEdgeIt; 73 73 friend class InEdgeIt; 74 class ClassNodeIt {74 class ClassNodeIt : public Node { 75 75 friend class BipartiteGraphWrapper<Graph>; 76 76 protected: 77 Node n;77 const BipartiteGraphWrapper<Graph>* gw; 78 78 public: 79 79 ClassNodeIt() { } 80 ClassNodeIt(const Invalid& i) : n(i) { } 81 ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) { 82 _G.s_false_t_true_map>first(n, _class); 80 ClassNodeIt(Invalid i) : Node(i) { } 81 ClassNodeIt(const BipartiteGraphWrapper<Graph>& _gw, bool _class) : 82 Node(), gw(&_gw) { 83 _gw.s_false_t_true_map>first(*this, _class); 83 84 } 84 85 //FIXME needed in new concept, important here 85 ClassNodeIt(const Node& _n) : n(_n) { } 86 operator Node() const { return n; } 86 ClassNodeIt(const BipartiteGraphWrapper<Graph>& _gw, const Node& n) : 87 Node(n), gw(&_gw) { } 88 ClassNodeIt& operator++() { 89 gw>s_false_t_true_map>next(*this); 90 return *this; 91 } 87 92 }; 88 93 // class SNodeIt { … … 106 111 // operator Node() const { return n; } 107 112 // }; 108 class OutEdgeIt {109 friend class BipartiteGraphWrapper<Graph>;110 protected:111 typename Graph::OutEdgeIt e;112 public:113 OutEdgeIt() { }114 OutEdgeIt(const Invalid& i) : e(i) { }115 OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {116 if (!(*(_G.s_false_t_true_map))[_n])117 e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));118 else119 e=INVALID;120 }121 operator Edge() const { return Edge(typename Graph::Edge(e)); }122 };123 class InEdgeIt {124 friend class BipartiteGraphWrapper<Graph>;125 protected:126 typename Graph::InEdgeIt e;127 public:128 InEdgeIt() { }129 InEdgeIt(const Invalid& i) : e(i) { }130 InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {131 if ((*(_G.s_false_t_true_map))[_n])132 e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));133 else134 e=INVALID;135 }136 operator Edge() const { return Edge(typename Graph::Edge(e)); }137 };113 // class OutEdgeIt { 114 // friend class BipartiteGraphWrapper<Graph>; 115 // protected: 116 // typename Graph::OutEdgeIt e; 117 // public: 118 // OutEdgeIt() { } 119 // OutEdgeIt(const Invalid& i) : e(i) { } 120 // OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) { 121 // if (!(*(_G.s_false_t_true_map))[_n]) 122 // e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n)); 123 // else 124 // e=INVALID; 125 // } 126 // operator Edge() const { return Edge(typename Graph::Edge(e)); } 127 // }; 128 // class InEdgeIt { 129 // friend class BipartiteGraphWrapper<Graph>; 130 // protected: 131 // typename Graph::InEdgeIt e; 132 // public: 133 // InEdgeIt() { } 134 // InEdgeIt(const Invalid& i) : e(i) { } 135 // InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) { 136 // if ((*(_G.s_false_t_true_map))[_n]) 137 // e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n)); 138 // else 139 // e=INVALID; 140 // } 141 // operator Edge() const { return Edge(typename Graph::Edge(e)); } 142 // }; 138 143 139 144 using GraphWrapper<Graph>::first; 140 145 ClassNodeIt& first(ClassNodeIt& n, bool _class) const { 141 n=ClassNodeIt(*this, _class) ; return n; } 146 n=ClassNodeIt(*this, _class); return n; 147 } 142 148 // SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; } 143 149 // TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; } 144 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {145 i=OutEdgeIt(*this, p); return i;146 }147 InEdgeIt& first(InEdgeIt& i, const Node& p) const {148 i=InEdgeIt(*this, p); return i;149 }150 151 using GraphWrapper<Graph>::next;152 ClassNodeIt& next(ClassNodeIt& n) const {153 this>s_false_t_true_map>next(n.n); return n;154 }150 // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 151 // i=OutEdgeIt(*this, p); return i; 152 // } 153 // InEdgeIt& first(InEdgeIt& i, const Node& p) const { 154 // i=InEdgeIt(*this, p); return i; 155 // } 156 157 // using GraphWrapper<Graph>::next; 158 // ClassNodeIt& next(ClassNodeIt& n) const { 159 // this>s_false_t_true_map>next(n.n); return n; 160 // } 155 161 // SNodeIt& next(SNodeIt& n) const { 156 162 // this>s_false_t_true_map>next(n); return n; … … 159 165 // this>s_false_t_true_map>next(n); return n; 160 166 // } 161 OutEdgeIt& next(OutEdgeIt& i) const { this>graph>next(i.e); return i; }162 InEdgeIt& next(InEdgeIt& i) const { this>graph>next(i.e); return i; }163 164 Node tail(const Edge& e) {165 if (!(*(this>s_false_t_true_map))[this>graph>tail(e)])166 return Node(this>graph>tail(e));167 else168 return Node(this>graph>head(e));169 }170 Node head(const Edge& e) {171 if (!(*(this>s_false_t_true_map))[this>graph>tail(e)])172 return Node(this>graph>head(e));173 else174 return Node(this>graph>tail(e));175 }176 177 Node aNode(const OutEdgeIt& e) const {178 return Node(this>graph>aNode(e.e));179 }180 Node aNode(const InEdgeIt& e) const {181 return Node(this>graph>aNode(e.e));182 }183 Node bNode(const OutEdgeIt& e) const {184 return Node(this>graph>bNode(e.e));185 }186 Node bNode(const InEdgeIt& e) const {187 return Node(this>graph>bNode(e.e));188 }167 // OutEdgeIt& next(OutEdgeIt& i) const { this>graph>next(i.e); return i; } 168 // InEdgeIt& next(InEdgeIt& i) const { this>graph>next(i.e); return i; } 169 170 // Node tail(const Edge& e) { 171 // if (!(*(this>s_false_t_true_map))[this>graph>tail(e)]) 172 // return Node(this>graph>tail(e)); 173 // else 174 // return Node(this>graph>head(e)); 175 // } 176 // Node head(const Edge& e) { 177 // if (!(*(this>s_false_t_true_map))[this>graph>tail(e)]) 178 // return Node(this>graph>head(e)); 179 // else 180 // return Node(this>graph>tail(e)); 181 // } 182 183 // Node aNode(const OutEdgeIt& e) const { 184 // return Node(this>graph>aNode(e.e)); 185 // } 186 // Node aNode(const InEdgeIt& e) const { 187 // return Node(this>graph>aNode(e.e)); 188 // } 189 // Node bNode(const OutEdgeIt& e) const { 190 // return Node(this>graph>bNode(e.e)); 191 // } 192 // Node bNode(const InEdgeIt& e) const { 193 // return Node(this>graph>bNode(e.e)); 194 // } 189 195 190 196 /// Returns true iff \c n is in S. 
src/work/marci/bipartite_graph_wrapper_test.cc
r768 r902 4 4 #include <vector> 5 5 6 #include <sage_graph.h>7 //#include <smart_graph.h>6 //#include <sage_graph.h> 7 #include <hugo/smart_graph.h> 8 8 //#include <dimacs.h> 9 9 #include <hugo/time_measure.h> 10 #include <for_each_macros.h>10 //#include <for_each_macros.h> 11 11 #include <bfs_dfs.h> 12 12 #include <hugo/graph_wrapper.h> 13 13 #include <bipartite_graph_wrapper.h> 14 14 #include <hugo/maps.h> 15 #include <hugo/ max_flow.h>15 #include <hugo/preflow.h> 16 16 #include <augmenting_flow.h> 17 18 using std::cout; 19 using std::endl; 17 20 18 21 using namespace hugo; 19 22 20 23 int main() { 21 typedef UndirSageGraph Graph; 24 //typedef UndirSageGraph Graph; 25 typedef SmartGraph Graph; 22 26 typedef Graph::Node Node; 23 27 typedef Graph::NodeIt NodeIt; … … 53 57 54 58 Graph::Node u; 55 std::cout << "These nodes will be in S:\n";59 cout << "These nodes will be in S:" << endl; 56 60 //FIXME azert kellene ++, es invalid vizsgalat ubol, hogy ezt le lehessen 57 61 //irni 1etlen FOR_EACHcsel. 58 for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u))59 std::cout << u<< " ";60 std::cout << "\n";61 std::cout << "These nodes will be in T:\n";62 for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u))63 std::cout << u<< " ";64 std::cout << "\n";62 for (bipartite_map.first(u, false); u!=INVALID; bipartite_map.next(u)) 63 cout << g.id(u) << " "; 64 cout << endl; 65 cout << "These nodes will be in T:" << endl; 66 for (bipartite_map.first(u, true); u!=INVALID; bipartite_map.next(u)) 67 cout << g.id(u) << " "; 68 cout << endl; 65 69 66 70 typedef BipartiteGraphWrapper<Graph> BGW; 67 71 BGW bgw(g, bipartite_map); 68 72 69 std::cout << "Nodes by NodeIt:\n"; 70 FOR_EACH_LOC(BGW::NodeIt, n, bgw) { 71 std::cout << n << " "; 72 } 73 std::cout << "\n"; 74 std::cout << "Nodes in S by ClassNodeIt:\n"; 75 FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) { 76 std::cout << n << " "; 77 } 78 std::cout << "\n"; 79 std::cout << "Nodes in T by ClassNodeIt:\n"; 80 FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) { 81 std::cout << n << " "; 82 } 83 std::cout << "\n"; 84 std::cout << "Edges of the bipartite graph:\n"; 85 FOR_EACH_LOC(BGW::EdgeIt, e, bgw) { 86 std::cout << bgw.tail(e) << ">" << bgw.head(e) << std::endl; 87 } 73 cout << "Nodes by NodeIt:" << endl; 74 for (BGW::NodeIt n(bgw); n!=INVALID; ++n) 75 cout << g.id(n) << " "; 76 cout << endl; 77 78 cout << "Nodes in S by ClassNodeIt:" << endl; 79 for (BGW::ClassNodeIt n(bgw, bgw.S_CLASS); n!=INVALID; ++n) 80 cout << g.id(n) << " "; 81 cout << endl; 82 83 cout << "Nodes in T by ClassNodeIt:" << endl; 84 for (BGW::ClassNodeIt n(bgw, bgw.T_CLASS); n!=INVALID; ++n) 85 cout << g.id(n) << " "; 86 cout << endl; 87 88 cout << "Edges of the bipartite graph:" << endl; 89 for (BGW::EdgeIt e(bgw); e!=INVALID; ++e) 90 cout << g.id(bgw.tail(e)) << ">" << g.id(bgw.head(e)) << endl; 88 91 89 92 BGW::NodeMap<int> dbyj(bgw); 90 93 BGW::EdgeMap<int> dbyxcj(bgw); 91 94 92 typedef stBipartiteGraphWrapper<BGW> stGW;93 stGW stgw(bgw);94 ConstMap<stGW::Edge, int> const1map(1);95 stGW::NodeMap<int> ize(stgw);96 stGW::EdgeMap<int> flow(stgw);95 // typedef stBipartiteGraphWrapper<BGW> stGW; 96 // stGW stgw(bgw); 97 // ConstMap<stGW::Edge, int> const1map(1); 98 // stGW::NodeMap<int> ize(stgw); 99 // stGW::EdgeMap<int> flow(stgw); 97 100 98 BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);99 Graph::NodeIt si;100 Graph::Node s;101 s=g.first(si);102 bfs.pushAndSetReached(BGW::Node(s));103 while (!bfs.finished()) { ++bfs; }101 // BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw); 102 // Graph::NodeIt si; 103 // Graph::Node s; 104 // s=g.first(si); 105 // bfs.pushAndSetReached(BGW::Node(s)); 106 // while (!bfs.finished()) { ++bfs; } 104 107 105 FOR_EACH_LOC(stGW::NodeIt, n, stgw) {106 std::cout << "outedges of " << n << ":\n";107 FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) {108 std::cout << " " << e << "\n";109 std::cout << " aNode: " << stgw.aNode(e) << "\n";110 std::cout << " bNode: " << stgw.bNode(e) << "\n";111 }112 std::cout << "inedges of " << n << ":\n";113 FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) {114 std::cout << " " << e << "\n";115 std::cout << " aNode: " << stgw.aNode(e) << "\n";116 std::cout << " bNode: " << stgw.bNode(e) << "\n";117 }118 }119 std::cout << "Edges of the stGraphWrapper:\n";120 FOR_EACH_LOC(stGW::EdgeIt, n, stgw) {121 std::cout << " " << n << "\n";122 }108 // FOR_EACH_LOC(stGW::NodeIt, n, stgw) { 109 // cout << "outedges of " << n << ":" << endl; 110 // FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) { 111 // cout << " " << e << endl; 112 // cout << " aNode: " << stgw.aNode(e) << endl; 113 // cout << " bNode: " << stgw.bNode(e) << endl; 114 // } 115 // cout << "inedges of " << n << ":" << endl; 116 // FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) { 117 // cout << " " << e << endl; 118 // cout << " aNode: " << stgw.aNode(e) << endl; 119 // cout << " bNode: " << stgw.bNode(e) << endl; 120 // } 121 // } 122 // cout << "Edges of the stGraphWrapper:" << endl; 123 // FOR_EACH_LOC(stGW::EdgeIt, n, stgw) { 124 // cout << " " << n << endl; 125 // } 123 126 124 stGW::NodeMap<bool> b(stgw);125 FOR_EACH_LOC(stGW::NodeIt, n, stgw) {126 std::cout << n << ": " << b[n] <<"\n";127 }127 // stGW::NodeMap<bool> b(stgw); 128 // FOR_EACH_LOC(stGW::NodeIt, n, stgw) { 129 // cout << n << ": " << b[n] << endl; 130 // } 128 131 129 std::cout << "Bfs from s: \n";130 BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);131 bfs_stgw.pushAndSetReached(stgw.S_NODE);132 while (!bfs_stgw.finished()) {133 std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n";134 ++bfs_stgw;135 }132 // cout << "Bfs from s:" << endl; 133 // BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw); 134 // bfs_stgw.pushAndSetReached(stgw.S_NODE); 135 // while (!bfs_stgw.finished()) { 136 // cout << " " << stGW::OutEdgeIt(bfs_stgw) << endl; 137 // ++bfs_stgw; 138 // } 136 139 137 AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >138 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);139 while (max_flow_test.augmentOnShortestPath()) { }140 // AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 141 // max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow); 142 // while (max_flow_test.augmentOnShortestPath()) { } 140 143 141 std::cout << max_flow_test.flowValue() << std::endl;144 // cout << max_flow_test.flowValue() << std::endl; 142 145 143 146 return 0;
Note: See TracChangeset
for help on using the changeset viewer.