Changeset 312:54e07057eb47 in lemon-0.x
- Timestamp:
- 04/07/04 12:57:58 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@430
- Location:
- src/work/marci
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/marci/edmonds_karp.h
r311 r312 275 275 bool _augment=false; 276 276 277 typedef typename ResGW::NodeMap<bool> ReachedMap; 278 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); 277 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); 279 278 bfs.pushAndSetReached(s); 280 279 … … 340 339 ResGW res_graph(*g, *flow, *capacity); 341 340 342 typedef typename ResGW::NodeMap<bool> ReachedMap; 343 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); 341 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); 344 342 345 343 bfs.pushAndSetReached(s); … … 392 390 __augment=false; 393 391 //computing blocking flow with dfs 394 typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap; 395 DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap> dfs(F);392 393 DfsIterator5< MG, typename MG::NodeMap<bool> > dfs(F); 396 394 typename MG::NodeMap<typename MG::Edge> pred(F); 397 395 pred.set(sF, INVALID); … … 451 449 452 450 //bfs for distances on the residual graph 453 typedef typename ResGW::NodeMap<bool> ReachedMap; 454 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); 451 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); 455 452 bfs.pushAndSetReached(s); 456 453 typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's … … 500 497 __augment=false; 501 498 //computing blocking flow with dfs 502 typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap; 503 DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F); 499 DfsIterator5< MG, typename MG::NodeMap<bool> > dfs(F); 504 500 typename MG::NodeMap<typename MG::Edge> pred(F); 505 501 pred.set(sF, INVALID); … … 557 553 ResGW res_graph(*g, *flow, *capacity); 558 554 559 typedef typename ResGW::NodeMap<bool> ReachedMap; 560 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); 555 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); 561 556 562 557 bfs.pushAndSetReached(s); … … 598 593 __augment=false; 599 594 //computing blocking flow with dfs 600 typedef typename ErasingResGW::NodeMap<bool> BlockingReachedMap; 601 DfsIterator5< ErasingResGW, BlockingReachedMap > 595 DfsIterator5< ErasingResGW, typename ErasingResGW::NodeMap<bool> > 602 596 dfs(erasing_res_graph); 603 597 typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt> -
src/work/marci/graph_wrapper.h
r311 r312 7 7 namespace hugo { 8 8 9 template<typename Graph> 10 class TrivGraphWrapper { 11 protected: 12 Graph* graph; 13 14 public: 15 // typedef Graph BaseGraph; 16 typedef Graph ParentGraph; 17 18 // TrivGraphWrapper() : graph(0) { } 19 TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } 20 // void setGraph(Graph& _graph) { graph = &_graph; } 21 // Graph& getGraph() const { return *graph; } 22 23 typedef typename Graph::Node Node; 24 class NodeIt : public Graph::NodeIt { 25 public: 26 NodeIt() { } 27 NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } 28 // NodeIt(const typename BaseGraph::NodeIt& n) : Graph::NodeIt(n) { } 29 NodeIt(const Invalid& i) : Graph::NodeIt(i) { } 30 NodeIt(const TrivGraphWrapper<Graph>& _G) : 31 Graph::NodeIt(*(_G.graph)) { } 32 // operator typename BaseGraph::NodeIt() { 33 // return typename BaseGraph::NodeIt(this->Graph::NodeIt); 34 // } 35 }; 36 typedef typename Graph::Edge Edge; 37 class OutEdgeIt : public Graph::OutEdgeIt { 38 public: 39 OutEdgeIt() { } 40 OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } 41 OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } 42 OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) : 43 Graph::OutEdgeIt(*(_G.graph), n) { } 44 }; 45 class InEdgeIt : public Graph::InEdgeIt { 46 public: 47 InEdgeIt() { } 48 InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } 49 InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } 50 InEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) : 51 Graph::InEdgeIt(*(_G.graph), n) { } 52 }; 53 //typedef typename Graph::SymEdgeIt SymEdgeIt; 54 class EdgeIt : public Graph::EdgeIt { 55 public: 56 EdgeIt() { } 57 EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } 58 EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } 59 EdgeIt(const TrivGraphWrapper<Graph>& _G) : 60 Graph::EdgeIt(*(_G.graph)) { } 61 }; 62 63 NodeIt& first(NodeIt& i) const { 64 i=NodeIt(*this); 65 return i; 66 } 67 // template<typename I> I& first(I& i) const { 68 // i=I(*this); 9 // template<typename Graph> 10 // class TrivGraphWrapper { 11 // protected: 12 // Graph* graph; 13 14 // public: 15 // // typedef Graph BaseGraph; 16 // typedef Graph ParentGraph; 17 18 // // TrivGraphWrapper() : graph(0) { } 19 // TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } 20 // // void setGraph(Graph& _graph) { graph = &_graph; } 21 // // Graph& getGraph() const { return *graph; } 22 23 // typedef typename Graph::Node Node; 24 // class NodeIt : public Graph::NodeIt { 25 // public: 26 // NodeIt() { } 27 // NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } 28 // NodeIt(const Invalid& i) : Graph::NodeIt(i) { } 29 // NodeIt(const TrivGraphWrapper<Graph>& _G) : 30 // Graph::NodeIt(*(_G.graph)) { } 31 // }; 32 // typedef typename Graph::Edge Edge; 33 // class OutEdgeIt : public Graph::OutEdgeIt { 34 // public: 35 // OutEdgeIt() { } 36 // OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } 37 // OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } 38 // OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) : 39 // Graph::OutEdgeIt(*(_G.graph), n) { } 40 // }; 41 // class InEdgeIt : public Graph::InEdgeIt { 42 // public: 43 // InEdgeIt() { } 44 // InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } 45 // InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } 46 // InEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) : 47 // Graph::InEdgeIt(*(_G.graph), n) { } 48 // }; 49 // //typedef typename Graph::SymEdgeIt SymEdgeIt; 50 // class EdgeIt : public Graph::EdgeIt { 51 // public: 52 // EdgeIt() { } 53 // EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } 54 // EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } 55 // EdgeIt(const TrivGraphWrapper<Graph>& _G) : 56 // Graph::EdgeIt(*(_G.graph)) { } 57 // }; 58 59 // NodeIt& first(NodeIt& i) const { 60 // i=NodeIt(*this); 69 61 // return i; 70 62 // } 71 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 72 i=OutEdgeIt(*this, p); 73 return i; 74 } 75 InEdgeIt& first(InEdgeIt& i, const Node& p) const { 76 i=InEdgeIt(*this, p); 77 return i; 78 } 79 EdgeIt& first(EdgeIt& i) const { 80 i=EdgeIt(*this); 81 return i; 82 } 83 // template<typename I, typename P> I& first(I& i, const P& p) const { 84 // i=I(*this, p); 63 // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 64 // i=OutEdgeIt(*this, p); 85 65 // return i; 86 66 // } 87 88 // template<typename I> I getNext(const I& i) const { 89 // return graph->getNext(i); } 90 // template<typename I> I& next(I &i) const { graph->next(i); return i; } 91 NodeIt& next(NodeIt& i) const { graph->next(i); return i; } 92 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; } 93 InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; } 94 EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; } 95 96 template< typename It > It first() const { 97 It e; this->first(e); return e; } 98 99 template< typename It > It first(const Node& v) const { 100 It e; this->first(e, v); return e; } 101 102 Node head(const Edge& e) const { return graph->head(e); } 103 Node tail(const Edge& e) const { return graph->tail(e); } 104 105 template<typename I> bool valid(const I& i) const { 106 return graph->valid(i); } 107 108 //template<typename I> void setInvalid(const I &i); 109 //{ return graph->setInvalid(i); } 110 111 int nodeNum() const { return graph->nodeNum(); } 112 int edgeNum() const { return graph->edgeNum(); } 113 114 template<typename I> Node aNode(const I& e) const { 115 return graph->aNode(e); } 116 template<typename I> Node bNode(const I& e) const { 117 return graph->bNode(e); } 118 119 Node addNode() const { return graph->addNode(); } 120 Edge addEdge(const Node& tail, const Node& head) const { 121 return graph->addEdge(tail, head); } 122 123 template<typename I> void erase(const I& i) const { graph->erase(i); } 124 125 void clear() const { graph->clear(); } 126 127 template<typename T> class NodeMap : public Graph::NodeMap<T> { 128 public: 129 NodeMap(const TrivGraphWrapper<Graph>& _G) : 130 Graph::NodeMap<T>(*(_G.graph)) { } 131 NodeMap(const TrivGraphWrapper<Graph>& _G, T a) : 132 Graph::NodeMap<T>(*(_G.graph), a) { } 133 }; 134 135 template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 136 public: 137 EdgeMap(const TrivGraphWrapper<Graph>& _G) : 138 Graph::EdgeMap<T>(*(_G.graph)) { } 139 EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) : 140 Graph::EdgeMap<T>(*(_G.graph), a) { } 141 }; 142 143 // template<typename Map, typename T> class NodeMapWrapper { 144 // protected: 145 // Map* map; 146 // public: 147 // NodeMapWrapper(Map& _map) : map(&_map) { } 148 // void set(Node n, T a) { map->set(n, a); } 149 // T get(Node n) const { return map->get(n); } 150 // }; 151 152 // template<typename Map, typename T> class EdgeMapWrapper { 153 // protected: 154 // Map* map; 155 // public: 156 // EdgeMapWrapper(Map& _map) : map(&_map) { } 157 // void set(Edge n, T a) { map->set(n, a); } 158 // T get(Edge n) const { return map->get(n); } 159 // }; 160 }; 67 // InEdgeIt& first(InEdgeIt& i, const Node& p) const { 68 // i=InEdgeIt(*this, p); 69 // return i; 70 // } 71 // EdgeIt& first(EdgeIt& i) const { 72 // i=EdgeIt(*this); 73 // return i; 74 // } 75 // // template<typename I> I& first(I& i) const { 76 // // i=I(*this); 77 // // return i; 78 // // } 79 // // template<typename I, typename P> I& first(I& i, const P& p) const { 80 // // i=I(*this, p); 81 // // return i; 82 // // } 83 84 // // template<typename I> I getNext(const I& i) const { 85 // // return graph->getNext(i); } 86 87 // NodeIt& next(NodeIt& i) const { graph->next(i); return i; } 88 // OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; } 89 // InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; } 90 // EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; } 91 // // template<typename I> I& next(I &i) const { graph->next(i); return i; } 92 // template< typename It > It first() const { 93 // It e; this->first(e); return e; } 94 95 // template< typename It > It first(const Node& v) const { 96 // It e; this->first(e, v); return e; } 97 98 // Node head(const Edge& e) const { return graph->head(e); } 99 // Node tail(const Edge& e) const { return graph->tail(e); } 100 101 // template<typename I> bool valid(const I& i) const { 102 // return graph->valid(i); } 103 104 // //template<typename I> void setInvalid(const I &i); 105 // //{ return graph->setInvalid(i); } 106 107 // int nodeNum() const { return graph->nodeNum(); } 108 // int edgeNum() const { return graph->edgeNum(); } 109 110 // template<typename I> Node aNode(const I& e) const { 111 // return graph->aNode(e); } 112 // template<typename I> Node bNode(const I& e) const { 113 // return graph->bNode(e); } 114 115 // Node addNode() const { return graph->addNode(); } 116 // Edge addEdge(const Node& tail, const Node& head) const { 117 // return graph->addEdge(tail, head); } 118 119 // template<typename I> void erase(const I& i) const { graph->erase(i); } 120 121 // void clear() const { graph->clear(); } 122 123 // template<typename T> class NodeMap : public Graph::NodeMap<T> { 124 // public: 125 // NodeMap(const TrivGraphWrapper<Graph>& _G) : 126 // Graph::NodeMap<T>(*(_G.graph)) { } 127 // NodeMap(const TrivGraphWrapper<Graph>& _G, T a) : 128 // Graph::NodeMap<T>(*(_G.graph), a) { } 129 // }; 130 131 // template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 132 // public: 133 // EdgeMap(const TrivGraphWrapper<Graph>& _G) : 134 // Graph::EdgeMap<T>(*(_G.graph)) { } 135 // EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) : 136 // Graph::EdgeMap<T>(*(_G.graph), a) { } 137 // }; 138 139 // // template<typename Map, typename T> class NodeMapWrapper { 140 // // protected: 141 // // Map* map; 142 // // public: 143 // // NodeMapWrapper(Map& _map) : map(&_map) { } 144 // // void set(Node n, T a) { map->set(n, a); } 145 // // T get(Node n) const { return map->get(n); } 146 // // }; 147 148 // // template<typename Map, typename T> class EdgeMapWrapper { 149 // // protected: 150 // // Map* map; 151 // // public: 152 // // EdgeMapWrapper(Map& _map) : map(&_map) { } 153 // // void set(Edge n, T a) { map->set(n, a); } 154 // // T get(Edge n) const { return map->get(n); } 155 // // }; 156 // }; 161 157 162 158 … … 177 173 typedef typename Graph::Node Node; 178 174 class NodeIt : public Graph::NodeIt { 175 typedef typename Graph::NodeIt GraphNodeIt; 179 176 public: 180 177 NodeIt() { } … … 183 180 NodeIt(const GraphWrapper<Graph>& _G) : 184 181 Graph::NodeIt(*(_G.graph)) { } 182 // operator Node() const { 183 // std::cout << "ize" << std::endl; 184 // return Node(this->GraphNodeIt); 185 // } 185 186 }; 186 187 typedef typename Graph::Edge Edge; 187 188 class OutEdgeIt : public Graph::OutEdgeIt { 189 typedef typename Graph::OutEdgeIt GraphOutEdgeIt; 188 190 public: 189 191 OutEdgeIt() { } … … 192 194 OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) : 193 195 Graph::OutEdgeIt(*(_G.graph), n) { } 196 // operator Edge() const { 197 // std::cout << "ize" << std::endl; 198 // return Edge(this->GraphOutEdgeIt); 199 // } 194 200 }; 195 201 class InEdgeIt : public Graph::InEdgeIt { 202 typedef typename Graph::InEdgeIt GraphInEdgeIt; 196 203 public: 197 204 InEdgeIt() { } … … 200 207 InEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) : 201 208 Graph::InEdgeIt(*(_G.graph), n) { } 209 // operator Edge() const { 210 // std::cout << "ize" << std::endl; 211 // return Edge(this->InOutEdgeIt); 212 // } 202 213 }; 203 214 //typedef typename Graph::SymEdgeIt SymEdgeIt; 204 215 class EdgeIt : public Graph::EdgeIt { 216 typedef typename Graph::EdgeIt GraphEdgeIt; 205 217 public: 206 218 EdgeIt() { } … … 209 221 EdgeIt(const GraphWrapper<Graph>& _G) : 210 222 Graph::EdgeIt(*(_G.graph)) { } 223 // operator Edge() const { 224 // std::cout << "ize" << std::endl; 225 // return Edge(this->GraphEdgeIt); 226 // } 211 227 }; 212 228 213 229 NodeIt& first(NodeIt& i) const { 214 230 i=NodeIt(*this); 231 return i; 232 } 233 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 234 i=OutEdgeIt(*this, p); 235 return i; 236 } 237 InEdgeIt& first(InEdgeIt& i, const Node& p) const { 238 i=InEdgeIt(*this, p); 239 return i; 240 } 241 EdgeIt& first(EdgeIt& i) const { 242 i=EdgeIt(*this); 215 243 return i; 216 244 } … … 219 247 // return i; 220 248 // } 221 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {222 i=OutEdgeIt(*this, p);223 return i;224 }225 InEdgeIt& first(InEdgeIt& i, const Node& p) const {226 i=InEdgeIt(*this, p);227 return i;228 }229 EdgeIt& first(EdgeIt& i) const {230 i=EdgeIt(*this);231 return i;232 }233 249 // template<typename I, typename P> I& first(I& i, const P& p) const { 234 250 // i=I(*this, p); … … 238 254 // template<typename I> I getNext(const I& i) const { 239 255 // return gw.getNext(i); } 240 // template<typename I> I& next(I &i) const { graph->next(i); return i; } 256 241 257 NodeIt& next(NodeIt& i) const { graph->next(i); return i; } 242 258 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; } 243 259 InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; } 244 260 EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; } 245 261 // template<typename I> I& next(I &i) const { graph->next(i); return i; } 246 262 template< typename It > It first() const { 247 263 It e; this->first(e); return e; } … … 252 268 Node head(const Edge& e) const { return graph->head(e); } 253 269 Node tail(const Edge& e) const { return graph->tail(e); } 270 // Node tail(const OutEdgeIt& e) const { return graph->tail(Edge(e)); } 254 271 255 272 template<typename I> bool valid(const I& i) const { -
src/work/marci/iterator_bfs_demo.cc
r304 r312 89 89 90 90 { 91 typedef TrivGraphWrapper<const Graph> GW; 92 GW gw(G); 93 94 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); 91 EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name); 95 92 96 93 cout << "bfs and dfs iterator demo on the directed graph" << endl; 97 for(G W::NodeIt n(gw); gw.valid(n); gw.next(n)) {94 for(Graph::NodeIt n(G); G.valid(n); G.next(n)) { 98 95 cout << node_name[n] << ": "; 99 96 cout << "out edges: "; 100 for(G W::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))97 for(Graph::OutEdgeIt e(G, n); G.valid(e); G.next(e)) 101 98 cout << edge_name[e] << " "; 102 99 cout << "in edges: "; 103 for(G W::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))100 for(Graph::InEdgeIt e(G, n); G.valid(e); G.next(e)) 104 101 cout << edge_name[e] << " "; 105 102 cout << endl; … … 107 104 108 105 cout << "bfs from s ..." << endl; 109 BfsIterator5< G W, GW::NodeMap<bool> > bfs(gw);106 BfsIterator5< Graph, Graph::NodeMap<bool> > bfs(G); 110 107 bfs.pushAndSetReached(s); 111 108 while (!bfs.finished()) { 112 109 //cout << "edge: "; 113 if ( gw.valid(bfs)) {110 if (G.valid(bfs)) { 114 111 cout << edge_name[bfs] << /*endl*/", " << 115 node_name[ gw.aNode(bfs)] <<116 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 117 node_name[ gw.bNode(bfs)] <<112 node_name[G.aNode(bfs)] << 113 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 114 node_name[G.bNode(bfs)] << 118 115 (bfs.isBNodeNewlyReached() ? ": is newly reached." : 119 116 ": is not newly reached."); … … 140 137 141 138 cout << "dfs from s ..." << endl; 142 DfsIterator5< G W, GW::NodeMap<bool> > dfs(gw);139 DfsIterator5< Graph, Graph::NodeMap<bool> > dfs(G); 143 140 dfs.pushAndSetReached(s); 144 141 while (!dfs.finished()) { 145 142 ++dfs; 146 143 //cout << "edge: "; 147 if ( gw.valid(dfs)) {144 if (G.valid(dfs)) { 148 145 cout << edge_name[dfs] << /*endl*/", " << 149 node_name[ gw.aNode(dfs)] <<150 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 151 node_name[ gw.bNode(dfs)] <<146 node_name[G.aNode(dfs)] << 147 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 148 node_name[G.bNode(dfs)] << 152 149 (dfs.isBNodeNewlyReached() ? ": is newly reached." : 153 150 ": is not newly reached."); … … 165 162 166 163 { 167 typedef RevGraphWrapper<const TrivGraphWrapper<const Graph>> GW;164 typedef RevGraphWrapper<const Graph> GW; 168 165 GW gw(G); 169 166 … … 241 238 { 242 239 //typedef UndirGraphWrapper<const Graph> GW; 243 typedef UndirGraphWrapper<const TrivGraphWrapper<const Graph>> GW;240 typedef UndirGraphWrapper<const Graph> GW; 244 241 GW gw(G); 245 242
Note: See TracChangeset
for help on using the changeset viewer.