Changeset 298:315d826faa8f in lemon-0.x for src/work
- Timestamp:
- 04/05/04 16:19:02 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@416
- Location:
- src/work/marci/experiment
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/marci/experiment/bfs_iterator_1.h
r281 r298 631 631 632 632 633 template <typename Graph Wrapper, /*typename OutEdgeIt,*/634 typename ReachedMap/*=typename Graph Wrapper::NodeMap<bool>*/ >633 template <typename Graph, /*typename OutEdgeIt,*/ 634 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > 635 635 class BfsIterator5 { 636 typedef typename GraphWrapper::Node Node; 637 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; 638 const GraphWrapper* g; 636 protected: 637 typedef typename Graph::Node Node; 638 typedef typename Graph::OutEdgeIt OutEdgeIt; 639 const Graph* graph; 639 640 std::queue<Node> bfs_queue; 640 641 ReachedMap& reached; … … 643 644 bool own_reached_map; 644 645 public: 645 BfsIterator5(const Graph Wrapper& _g, ReachedMap& _reached) :646 g (&_g), reached(_reached),646 BfsIterator5(const Graph& _graph, ReachedMap& _reached) : 647 graph(&_graph), reached(_reached), 647 648 own_reached_map(false) { } 648 BfsIterator5(const Graph Wrapper& _g) :649 g (&_g), reached(*(new ReachedMap(*g/*, false*/))),649 BfsIterator5(const Graph& _graph) : 650 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 650 651 own_reached_map(true) { } 651 // BfsIterator5(const typename GraphWrapper::BaseGraph& _G,652 // ReachedMap& _reached) :653 // G(_G), reached(_reached),654 // own_reached_map(false) { }655 // BfsIterator5(const typename GraphWrapper::BaseGraph& _G) :656 // G(_G), reached(*(new ReachedMap(G /*, false*/))),657 // own_reached_map(true) { }658 652 ~BfsIterator5() { if (own_reached_map) delete &reached; } 659 653 void pushAndSetReached(Node s) { … … 661 655 if (bfs_queue.empty()) { 662 656 bfs_queue.push(s); 663 g ->first(actual_edge, s);664 if (g ->valid(actual_edge)) {665 Node w=g ->bNode(actual_edge);657 graph->first(actual_edge, s); 658 if (graph->valid(actual_edge)) { 659 Node w=graph->bNode(actual_edge); 666 660 if (!reached.get(w)) { 667 661 bfs_queue.push(w); … … 676 670 } 677 671 } 678 BfsIterator5<Graph Wrapper, /*OutEdgeIt,*/ ReachedMap>&672 BfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>& 679 673 operator++() { 680 if (g ->valid(actual_edge)) {681 g ->next(actual_edge);682 if (g ->valid(actual_edge)) {683 Node w=g ->bNode(actual_edge);674 if (graph->valid(actual_edge)) { 675 graph->next(actual_edge); 676 if (graph->valid(actual_edge)) { 677 Node w=graph->bNode(actual_edge); 684 678 if (!reached.get(w)) { 685 679 bfs_queue.push(w); … … 693 687 bfs_queue.pop(); 694 688 if (!bfs_queue.empty()) { 695 g ->first(actual_edge, bfs_queue.front());696 if (g ->valid(actual_edge)) {697 Node w=g ->bNode(actual_edge);689 graph->first(actual_edge, bfs_queue.front()); 690 if (graph->valid(actual_edge)) { 691 Node w=graph->bNode(actual_edge); 698 692 if (!reached.get(w)) { 699 693 bfs_queue.push(w); … … 711 705 operator OutEdgeIt () const { return actual_edge; } 712 706 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 713 bool isANodeExamined() const { return !(g ->valid(actual_edge)); }707 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } 714 708 Node aNode() const { return bfs_queue.front(); } 715 Node bNode() const { return g ->bNode(actual_edge); }709 Node bNode() const { return graph->bNode(actual_edge); } 716 710 const ReachedMap& getReachedMap() const { return reached; } 717 711 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } … … 774 768 // }; 775 769 776 template <typename Graph Wrapper, /*typename OutEdgeIt,*/777 typename ReachedMap/*=typename Graph Wrapper::NodeMap<bool>*/ >770 template <typename Graph, /*typename OutEdgeIt,*/ 771 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > 778 772 class DfsIterator5 { 779 typedef typename GraphWrapper::Node Node; 780 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; 781 const GraphWrapper* g; 773 protected: 774 typedef typename Graph::Node Node; 775 typedef typename Graph::OutEdgeIt OutEdgeIt; 776 const Graph* graph; 782 777 std::stack<OutEdgeIt> dfs_stack; 783 778 bool b_node_newly_reached; … … 787 782 bool own_reached_map; 788 783 public: 789 DfsIterator5(const Graph Wrapper& _g, ReachedMap& _reached) :790 g (&_g), reached(_reached),784 DfsIterator5(const Graph& _graph, ReachedMap& _reached) : 785 graph(&_graph), reached(_reached), 791 786 own_reached_map(false) { } 792 DfsIterator5(const Graph Wrapper& _g) :793 g (&_g), reached(*(new ReachedMap(*g/*, false*/))),787 DfsIterator5(const Graph& _graph) : 788 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 794 789 own_reached_map(true) { } 795 790 ~DfsIterator5() { if (own_reached_map) delete &reached; } … … 798 793 reached.set(s, true); 799 794 OutEdgeIt e; 800 g ->first(e, s);795 graph->first(e, s); 801 796 dfs_stack.push(e); 802 797 } 803 DfsIterator5<Graph Wrapper, /*OutEdgeIt,*/ ReachedMap>&798 DfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>& 804 799 operator++() { 805 800 actual_edge=dfs_stack.top(); 806 801 //actual_node=G.aNode(actual_edge); 807 if (g ->valid(actual_edge)/*.valid()*/) {808 Node w=g ->bNode(actual_edge);802 if (graph->valid(actual_edge)/*.valid()*/) { 803 Node w=graph->bNode(actual_edge); 809 804 actual_node=w; 810 805 if (!reached.get(w)) { 811 806 OutEdgeIt e; 812 g ->first(e, w);807 graph->first(e, w); 813 808 dfs_stack.push(e); 814 809 reached.set(w, true); 815 810 b_node_newly_reached=true; 816 811 } else { 817 actual_node=g ->aNode(actual_edge);818 g ->next(dfs_stack.top());812 actual_node=graph->aNode(actual_edge); 813 graph->next(dfs_stack.top()); 819 814 b_node_newly_reached=false; 820 815 } … … 828 823 operator OutEdgeIt () const { return actual_edge; } 829 824 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 830 bool isANodeExamined() const { return !(g ->valid(actual_edge)); }825 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } 831 826 Node aNode() const { return actual_node; /*FIXME*/} 832 827 Node bNode() const { return G.bNode(actual_edge); } -
src/work/marci/experiment/edmonds_karp_1.h
r281 r298 249 249 250 250 251 template <typename Graph Wrapper, typename Number, typename FlowMap, typename CapacityMap>251 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> 252 252 class MaxFlow { 253 253 protected: 254 typedef GraphWrapper GW; 255 typedef typename GW::Node Node; 256 typedef typename GW::Edge Edge; 257 typedef typename GW::EdgeIt EdgeIt; 258 typedef typename GW::OutEdgeIt OutEdgeIt; 259 typedef typename GW::InEdgeIt InEdgeIt; 260 //const Graph* G; 261 //GW gw; 262 const GW* g; 254 typedef typename Graph::Node Node; 255 typedef typename Graph::Edge Edge; 256 typedef typename Graph::EdgeIt EdgeIt; 257 typedef typename Graph::OutEdgeIt OutEdgeIt; 258 typedef typename Graph::InEdgeIt InEdgeIt; 259 const Graph* g; 263 260 Node s; 264 261 Node t; 265 262 FlowMap* flow; 266 263 const CapacityMap* capacity; 267 typedef ResGraphWrapper<const G W, Number, FlowMap, CapacityMap > ResGW;264 typedef ResGraphWrapper<const Graph, Number, FlowMap, CapacityMap > ResGW; 268 265 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; 269 266 typedef typename ResGW::Edge ResGWEdge; 270 267 public: 271 268 272 MaxFlow(const G W& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :269 MaxFlow(const Graph& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : 273 270 g(&_g), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { } 274 271 … … 646 643 return _augment; 647 644 } 648 649 // bool augmentOnBlockingFlow2() {650 // bool _augment=false;651 652 // //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;653 // typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;654 // typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;655 // typedef typename EAugGraph::Edge EAugEdge;656 657 // EAugGraph res_graph(*G, *flow, *capacity);658 659 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap;660 // BfsIterator5<661 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,662 // /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/663 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);664 665 // bfs.pushAndSetReached(s);666 667 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::668 // NodeMap<int>& dist=res_graph.dist;669 670 // while ( !bfs.finished() ) {671 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;672 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {673 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);674 // }675 // ++bfs;676 // } //computing distances from s in the residual graph677 678 // bool __augment=true;679 680 // while (__augment) {681 682 // __augment=false;683 // //computing blocking flow with dfs684 // typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;685 // DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >686 // dfs(res_graph);687 // typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);688 // pred.set(s, EAugEdge(INVALID));689 // //invalid iterators for sources690 691 // typename EAugGraph::NodeMap<Number> free(res_graph);692 693 // dfs.pushAndSetReached(s);694 // while (!dfs.finished()) {695 // ++dfs;696 // if (res_graph.valid(EAugOutEdgeIt(dfs))) {697 // if (dfs.isBNodeNewlyReached()) {698 699 // typename EAugGraph::Node v=res_graph.aNode(dfs);700 // typename EAugGraph::Node w=res_graph.bNode(dfs);701 702 // pred.set(w, EAugOutEdgeIt(dfs));703 // if (res_graph.valid(pred.get(v))) {704 // free.set(w, std::min(free.get(v), res_graph.free(dfs)));705 // } else {706 // free.set(w, res_graph.free(dfs));707 // }708 709 // if (w==t) {710 // __augment=true;711 // _augment=true;712 // break;713 // }714 // } else {715 // res_graph.erase(dfs);716 // }717 // }718 719 // }720 721 // if (__augment) {722 // typename EAugGraph::Node n=t;723 // Number augment_value=free.get(t);724 // while (res_graph.valid(pred.get(n))) {725 // EAugEdge e=pred.get(n);726 // res_graph.augment(e, augment_value);727 // n=res_graph.tail(e);728 // if (res_graph.free(e)==0)729 // res_graph.erase(e);730 // }731 // }732 733 // }734 735 // return _augment;736 // }737 645 738 646 void run() { -
src/work/marci/experiment/graph_wrapper_1.h
r281 r298 14 14 public: 15 15 typedef Graph BaseGraph; 16 17 // TrivGraphWrapper() : graph(0) { } 18 TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } 19 // void setGraph(Graph& _graph) { graph = &_graph; } 20 // Graph& getGraph() const { return *graph; } 16 21 17 22 typedef typename Graph::Node Node; … … 25 30 }; 26 31 typedef typename Graph::Edge Edge; 27 //typedef typename Graph::OutEdgeIt OutEdgeIt;28 32 class OutEdgeIt : public Graph::OutEdgeIt { 29 33 public: … … 34 38 Graph::OutEdgeIt(*(_G.graph), n) { } 35 39 }; 36 //typedef typename Graph::InEdgeIt InEdgeIt;37 40 class InEdgeIt : public Graph::InEdgeIt { 38 41 public: … … 44 47 }; 45 48 //typedef typename Graph::SymEdgeIt SymEdgeIt; 46 //typedef typename Graph::EdgeIt EdgeIt;47 49 class EdgeIt : public Graph::EdgeIt { 48 50 public: … … 54 56 }; 55 57 56 //TrivGraphWrapper() : graph(0) { }57 TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }58 59 // void setGraph(Graph& _graph) { graph = &_graph; }60 // Graph& getGraph() const { return (*graph); }61 62 58 NodeIt& first(NodeIt& i) const { 63 59 i=NodeIt(*this); … … 69 65 } 70 66 // template<typename I> I& first(I& i) const { 71 // //return graph->first(i);72 67 // i=I(*this); 73 68 // return i; … … 82 77 } 83 78 // template<typename I, typename P> I& first(I& i, const P& p) const { 84 // //return graph->first(i, p);85 79 // i=I(*this, p); 86 80 // return i; … … 92 86 93 87 template< typename It > It first() const { 94 It e; first(e); return e; }88 It e; this->first(e); return e; } 95 89 96 90 template< typename It > It first(const Node& v) const { 97 It e; first(e, v); return e; }91 It e; this->first(e, v); return e; } 98 92 99 93 Node head(const Edge& e) const { return graph->head(e); } 100 94 Node tail(const Edge& e) const { return graph->tail(e); } 101 95 102 template<typename I> bool valid(const I& i) const 103 {return graph->valid(i); }96 template<typename I> bool valid(const I& i) const { 97 return graph->valid(i); } 104 98 105 99 //template<typename I> void setInvalid(const I &i); … … 143 137 public: 144 138 NodeMapWrapper(Map& _map) : map(&_map) { } 145 //template<typename T>146 139 void set(Node n, T a) { map->set(n, a); } 147 //template<typename T>148 140 T get(Node n) const { return map->get(n); } 149 141 }; … … 154 146 public: 155 147 EdgeMapWrapper(Map& _map) : map(&_map) { } 156 //template<typename T>157 148 void set(Edge n, T a) { map->set(n, a); } 158 //template<typename T>159 149 T get(Edge n) const { return map->get(n); } 160 150 }; 161 151 }; 162 152 163 template<typename GraphWrapper> 164 class GraphWrapperSkeleton { 153 154 template<typename Graph> 155 class GraphWrapper { 165 156 protected: 166 Graph Wrapper gw;157 Graph* graph; 167 158 168 159 public: 169 //typedef typename GraphWrapper::BaseGraph BaseGraph; 170 171 // typedef typename GraphWrapper::Node Node; 172 // typedef typename GraphWrapper::NodeIt NodeIt; 173 174 // typedef typename GraphWrapper::Edge Edge; 175 // typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; 176 // typedef typename GraphWrapper::InEdgeIt InEdgeIt; 177 // //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt; 178 // typedef typename GraphWrapper::EdgeIt EdgeIt; 179 180 typedef typename GraphWrapper::Node Node; 181 class NodeIt : public GraphWrapper::NodeIt { 160 typedef Graph BaseGraph; 161 162 // GraphWrapper() : graph(0) { } 163 GraphWrapper(Graph& _graph) : graph(&_graph) { } 164 // void setGraph(Graph& _graph) { graph=&_graph; } 165 // Graph& getGraph() const { return *graph; } 166 167 typedef typename Graph::Node Node; 168 class NodeIt : public Graph::NodeIt { 182 169 public: 183 170 NodeIt() { } 184 NodeIt(const typename GraphWrapper::NodeIt& n) : 185 GraphWrapper::NodeIt(n) { } 186 NodeIt(const Invalid& i) : GraphWrapper::NodeIt(i) { } 187 NodeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) : 188 GraphWrapper::NodeIt(_G.gw) { } 189 }; 190 typedef typename GraphWrapper::Edge Edge; 191 //typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; 192 class OutEdgeIt : public GraphWrapper::OutEdgeIt { 171 NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } 172 NodeIt(const Invalid& i) : Graph::NodeIt(i) { } 173 NodeIt(const GraphWrapper<Graph>& _G) : 174 Graph::NodeIt(*(_G.graph)) { } 175 }; 176 typedef typename Graph::Edge Edge; 177 class OutEdgeIt : public Graph::OutEdgeIt { 193 178 public: 194 179 OutEdgeIt() { } 195 OutEdgeIt(const typename GraphWrapper::OutEdgeIt& e) : 196 GraphWrapper::OutEdgeIt(e) { } 197 OutEdgeIt(const Invalid& i) : GraphWrapper::OutEdgeIt(i) { } 198 OutEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) : 199 GraphWrapper::OutEdgeIt(_G.gw, n) { } 200 }; 201 //typedef typename GraphWrapper::InEdgeIt InEdgeIt; 202 class InEdgeIt : public GraphWrapper::InEdgeIt { 180 OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } 181 OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } 182 OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) : 183 Graph::OutEdgeIt(*(_G.graph), n) { } 184 }; 185 class InEdgeIt : public Graph::InEdgeIt { 203 186 public: 204 187 InEdgeIt() { } 205 InEdgeIt(const typename GraphWrapper::InEdgeIt& e) : 206 GraphWrapper::InEdgeIt(e) { } 207 InEdgeIt(const Invalid& i) : GraphWrapper::InEdgeIt(i) { } 208 InEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) : 209 GraphWrapper::InEdgeIt(_G.gw, n) { } 210 }; 211 //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt; 212 //typedef typename GraphWrapper::EdgeIt EdgeIt; 213 class EdgeIt : public GraphWrapper::EdgeIt { 188 InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } 189 InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } 190 InEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) : 191 Graph::InEdgeIt(*(_G.graph), n) { } 192 }; 193 //typedef typename Graph::SymEdgeIt SymEdgeIt; 194 class EdgeIt : public Graph::EdgeIt { 214 195 public: 215 196 EdgeIt() { } 216 EdgeIt(const typename GraphWrapper::EdgeIt& e) : 217 GraphWrapper::EdgeIt(e) { } 218 EdgeIt(const Invalid& i) : GraphWrapper::EdgeIt(i) { } 219 EdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) : 220 GraphWrapper::EdgeIt(_G.gw) { } 221 }; 222 223 224 //GraphWrapperSkeleton() : gw() { } 225 GraphWrapperSkeleton(GraphWrapper _gw) : gw(_gw) { } 226 227 //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); } 228 //BaseGraph& getGraph() const { return gw.getGraph(); } 229 230 template<typename I> I& first(I& i) const { 231 i=I(*this); 197 EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } 198 EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } 199 EdgeIt(const GraphWrapper<Graph>& _G) : 200 Graph::EdgeIt(*(_G.graph)) { } 201 }; 202 203 NodeIt& first(NodeIt& i) const { 204 i=NodeIt(*this); 232 205 return i; 233 206 } 234 template<typename I, typename P> I& first(I& i, const P& p) const { 235 i=I(*this, p); 236 return i; 237 } 238 239 // template<typename I> I getNext(const I& i) const { return gw.getNext(i); } 240 template<typename I> I& next(I &i) const { gw.next(i); return i; } 207 EdgeIt& first(EdgeIt& i) const { 208 i=EdgeIt(*this); 209 return i; 210 } 211 // template<typename I> I& first(I& i) const { 212 // i=I(*this); 213 // return i; 214 // } 215 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 216 i=OutEdgeIt(*this, p); 217 return i; 218 } 219 InEdgeIt& first(InEdgeIt& i, const Node& p) const { 220 i=InEdgeIt(*this, p); 221 return i; 222 } 223 // template<typename I, typename P> I& first(I& i, const P& p) const { 224 // i=I(*this, p); 225 // return i; 226 // } 227 228 // template<typename I> I getNext(const I& i) const { 229 // return gw.getNext(i); } 230 template<typename I> I& next(I &i) const { graph->next(i); return i; } 241 231 242 232 template< typename It > It first() const { … … 246 236 It e; this->first(e, v); return e; } 247 237 248 Node head(const Edge& e) const { return gw.head(e); } 249 Node tail(const Edge& e) const { return gw.tail(e); } 250 251 template<typename I> bool valid(const I& i) const { return gw.valid(i); } 238 Node head(const Edge& e) const { return graph->head(e); } 239 Node tail(const Edge& e) const { return graph->tail(e); } 240 241 template<typename I> bool valid(const I& i) const { 242 return graph->valid(i); } 252 243 253 244 //template<typename I> void setInvalid(const I &i); 254 245 //{ return graph->setInvalid(i); } 255 246 256 int nodeNum() const { return gw.nodeNum(); } 257 int edgeNum() const { return gw.edgeNum(); } 258 259 template<typename I> Node aNode(const I& e) const { return gw.aNode(e); } 260 template<typename I> Node bNode(const I& e) const { return gw.bNode(e); } 261 262 Node addNode() const { return gw.addNode(); } 247 int nodeNum() const { return graph->nodeNum(); } 248 int edgeNum() const { return graph->edgeNum(); } 249 250 template<typename I> Node aNode(const I& e) const { 251 return graph->aNode(e); } 252 template<typename I> Node bNode(const I& e) const { 253 return graph->bNode(e); } 254 255 Node addNode() const { return graph->addNode(); } 263 256 Edge addEdge(const Node& tail, const Node& head) const { 264 return gw.addEdge(tail, head); } 265 266 template<typename I> void erase(const I& i) const { gw.erase(i); } 267 268 void clear() const { gw.clear(); } 269 270 template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> { 271 public: 272 NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) : 273 GraphWrapper::NodeMap<T>(_G.gw) { } 274 NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) : 275 GraphWrapper::NodeMap<T>(_G.gw, a) { } 276 }; 277 278 template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> { 279 public: 280 EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) : 281 GraphWrapper::EdgeMap<T>(_G.gw) { } 282 EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) : 283 GraphWrapper::EdgeMap<T>(_G.gw, a) { } 284 }; 285 }; 286 287 template<typename GraphWrapper> 288 class GraphWrapperSkeleton1 { 289 protected: 290 GraphWrapper* g; 291 292 public: 293 //typedef typename GraphWrapper::BaseGraph BaseGraph; 294 295 // typedef typename GraphWrapper::Node Node; 296 // typedef typename GraphWrapper::NodeIt NodeIt; 297 298 // typedef typename GraphWrapper::Edge Edge; 299 // typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; 300 // typedef typename GraphWrapper::InEdgeIt InEdgeIt; 301 // //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt; 302 // typedef typename GraphWrapper::EdgeIt EdgeIt; 303 304 typedef typename GraphWrapper::Node Node; 305 class NodeIt : public GraphWrapper::NodeIt { 306 public: 307 NodeIt() { } 308 NodeIt(const typename GraphWrapper::NodeIt& n) : 309 GraphWrapper::NodeIt(n) { } 310 NodeIt(const Invalid& i) : GraphWrapper::NodeIt(i) { } 311 NodeIt(const GraphWrapperSkeleton1<GraphWrapper>& _G) : 312 GraphWrapper::NodeIt(*(_G.g)) { } 313 }; 314 typedef typename GraphWrapper::Edge Edge; 315 //typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; 316 class OutEdgeIt : public GraphWrapper::OutEdgeIt { 317 public: 318 OutEdgeIt() { } 319 OutEdgeIt(const typename GraphWrapper::OutEdgeIt& e) : 320 GraphWrapper::OutEdgeIt(e) { } 321 OutEdgeIt(const Invalid& i) : GraphWrapper::OutEdgeIt(i) { } 322 OutEdgeIt(const GraphWrapperSkeleton1<GraphWrapper>& _G, const Node& n) : 323 GraphWrapper::OutEdgeIt(*(_G.g), n) { } 324 }; 325 //typedef typename GraphWrapper::InEdgeIt InEdgeIt; 326 class InEdgeIt : public GraphWrapper::InEdgeIt { 327 public: 328 InEdgeIt() { } 329 InEdgeIt(const typename GraphWrapper::InEdgeIt& e) : 330 GraphWrapper::InEdgeIt(e) { } 331 InEdgeIt(const Invalid& i) : GraphWrapper::InEdgeIt(i) { } 332 InEdgeIt(const GraphWrapperSkeleton1<GraphWrapper>& _G, const Node& n) : 333 GraphWrapper::InEdgeIt(*(_G.g), n) { } 334 }; 335 //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt; 336 //typedef typename GraphWrapper::EdgeIt EdgeIt; 337 class EdgeIt : public GraphWrapper::EdgeIt { 338 public: 339 EdgeIt() { } 340 EdgeIt(const typename GraphWrapper::EdgeIt& e) : 341 GraphWrapper::EdgeIt(e) { } 342 EdgeIt(const Invalid& i) : GraphWrapper::EdgeIt(i) { } 343 EdgeIt(const GraphWrapperSkeleton1<GraphWrapper>& _G) : 344 GraphWrapper::EdgeIt(*(_G.g)) { } 345 }; 346 347 348 //GraphWrapperSkeleton() : gw() { } 349 GraphWrapperSkeleton1(GraphWrapper& _gw) : g(&_gw) { } 350 351 //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); } 352 //BaseGraph& getGraph() const { return gw.getGraph(); } 353 354 template<typename I> I& first(I& i) const { 355 i=I(*this); 356 return i; 357 } 358 template<typename I, typename P> I& first(I& i, const P& p) const { 359 i=I(*this, p); 360 return i; 361 } 362 363 // template<typename I> I getNext(const I& i) const { return gw.getNext(i); } 364 template<typename I> I& next(I &i) const { g->next(i); return i; } 365 366 template< typename It > It first() const { 367 It e; this->first(e); return e; } 368 369 template< typename It > It first(const Node& v) const { 370 It e; this->first(e, v); return e; } 371 372 Node head(const Edge& e) const { return g->head(e); } 373 Node tail(const Edge& e) const { return g->tail(e); } 374 375 template<typename I> bool valid(const I& i) const { return g->valid(i); } 376 377 //template<typename I> void setInvalid(const I &i); 378 //{ return graph->setInvalid(i); } 379 380 int nodeNum() const { return g->nodeNum(); } 381 int edgeNum() const { return g->edgeNum(); } 382 383 template<typename I> Node aNode(const I& e) const { return g->aNode(e); } 384 template<typename I> Node bNode(const I& e) const { return g->bNode(e); } 385 386 Node addNode() const { return g->addNode(); } 387 Edge addEdge(const Node& tail, const Node& head) const { 388 return g->addEdge(tail, head); } 389 390 template<typename I> void erase(const I& i) const { g->erase(i); } 391 392 void clear() const { g->clear(); } 393 394 template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> { 395 public: 396 NodeMap(const GraphWrapperSkeleton1<GraphWrapper>& _G) : 397 GraphWrapper::NodeMap<T>(*(_G.g)) { } 398 NodeMap(const GraphWrapperSkeleton1<GraphWrapper>& _G, T a) : 399 GraphWrapper::NodeMap<T>(*(_G.g), a) { } 400 }; 401 402 template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> { 403 public: 404 EdgeMap(const GraphWrapperSkeleton1<GraphWrapper>& _G) : 405 GraphWrapper::EdgeMap<T>(*(_G.g)) { } 406 EdgeMap(const GraphWrapperSkeleton1<GraphWrapper>& _G, T a) : 407 GraphWrapper::EdgeMap<T>(*(_G.g), a) { } 257 return graph->addEdge(tail, head); } 258 259 template<typename I> void erase(const I& i) const { graph->erase(i); } 260 261 void clear() const { graph->clear(); } 262 263 template<typename T> class NodeMap : public Graph::NodeMap<T> { 264 public: 265 NodeMap(const GraphWrapper<Graph>& _G) : 266 Graph::NodeMap<T>(*(_G.graph)) { } 267 NodeMap(const GraphWrapper<Graph>& _G, T a) : 268 Graph::NodeMap<T>(*(_G.graph), a) { } 269 }; 270 271 template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 272 public: 273 EdgeMap(const GraphWrapper<Graph>& _G) : 274 Graph::EdgeMap<T>(*(_G.graph)) { } 275 EdgeMap(const GraphWrapper<Graph>& _G, T a) : 276 Graph::EdgeMap<T>(*(_G.graph), a) { } 408 277 }; 409 278 }; … … 490 359 // }; 491 360 492 // template<typename /*Graph*/GraphWrapper 493 // /*=typename GraphWrapperSkeleton< TrivGraphWrapper<Graph>*/ > 494 // class RevGraphWrapper : 495 // public GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/ { 496 // protected: 497 // //Graph* graph; 498 499 // public: 500 // //typedef Graph BaseGraph; 501 502 // //typedef typename Graph::Node Node; 503 // //typedef typename Graph::NodeIt NodeIt; 504 505 // //typedef typename Graph::Edge Edge; 506 // typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::OutEdgeIt InEdgeIt; 507 // typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::InEdgeIt OutEdgeIt; 508 // //typedef typename Graph::SymEdgeIt SymEdgeIt; 509 // //typedef typename Graph::EdgeIt EdgeIt; 510 511 // //RevGraphWrapper() : graph(0) { } 512 // RevGraphWrapper(GraphWrapper _gw/*BaseGraph& _graph*/) : GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/(_gw/*TrivGraphWrapper<Graph>(_graph)*/) { } 513 514 // //void setGraph(Graph& _graph) { graph = &_graph; } 515 // //Graph& getGraph() const { return (*graph); } 516 517 // //template<typename I> I& first(I& i) const { return graph->first(i); } 518 // //template<typename I, typename P> I& first(I& i, const P& p) const { 519 // // return graph->first(i, p); } 520 521 // //template<typename I> I getNext(const I& i) const { 522 // // return graph->getNext(i); } 523 // //template<typename I> I& next(I &i) const { return graph->next(i); } 524 525 // //template< typename It > It first() const { 526 // // It e; first(e); return e; } 527 528 // //template< typename It > It first(const Node& v) const { 529 // // It e; first(e, v); return e; } 530 531 // //Node head(const Edge& e) const { return graph->tail(e); } 532 // //Node tail(const Edge& e) const { return graph->head(e); } 533 534 // //template<typename I> bool valid(const I& i) const 535 // // { return graph->valid(i); } 536 537 // //template<typename I> void setInvalid(const I &i); 538 // //{ return graph->setInvalid(i); } 539 540 // //template<typename I> Node aNode(const I& e) const { 541 // // return graph->aNode(e); } 542 // //template<typename I> Node bNode(const I& e) const { 543 // // return graph->bNode(e); } 544 545 // //Node addNode() const { return graph->addNode(); } 546 // //Edge addEdge(const Node& tail, const Node& head) const { 547 // // return graph->addEdge(tail, head); } 548 549 // //int nodeNum() const { return graph->nodeNum(); } 550 // //int edgeNum() const { return graph->edgeNum(); } 551 552 // //template<typename I> void erase(const I& i) const { graph->erase(i); } 553 554 // //void clear() const { graph->clear(); } 555 556 // template<typename T> class NodeMap : 557 // public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T> 558 // { 559 // public: 560 // NodeMap(const RevGraphWrapper<GraphWrapper>& _gw) : 561 // GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw) { } 562 // NodeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) : 563 // GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw, a) { } 564 // }; 565 566 // template<typename T> class EdgeMap : 567 // public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T> { 568 // public: 569 // EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw) : 570 // GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw) { } 571 // EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) : 572 // GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw, a) { } 573 // }; 574 // }; 575 576 template<typename GraphWrapper> 577 class RevGraphWrapper : public GraphWrapperSkeleton1<GraphWrapper> { 361 362 template<typename Graph> 363 class RevGraphWrapper : public GraphWrapper<Graph> { 578 364 public: 579 typedef typename GraphWrapper Skeleton1<GraphWrapper>::Node Node;580 typedef typename GraphWrapper Skeleton1<GraphWrapper>::Edge Edge;365 typedef typename GraphWrapper<Graph>::Node Node; 366 typedef typename GraphWrapper<Graph>::Edge Edge; 581 367 //FIXME 582 //If Graph Wrapper::OutEdgeIt is not defined368 //If Graph::OutEdgeIt is not defined 583 369 //and we do not want to use RevGraphWrapper::InEdgeIt, 584 370 //this won't work, because of typedef … … 587 373 //Unfortunately all the typedefs are instantiated in templates, 588 374 //unlike other stuff 589 typedef typename GraphWrapper Skeleton1<GraphWrapper>::OutEdgeIt InEdgeIt;590 typedef typename GraphWrapper Skeleton1<GraphWrapper>::InEdgeIt OutEdgeIt;591 592 RevGraphWrapper(GraphWrapper& _gw) : 593 GraphWrapperSkeleton1<GraphWrapper>(_gw) { }375 typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt; 376 typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt; 377 378 // RevGraphWrapper() : GraphWrapper<Graph>() { } 379 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 594 380 595 381 Node head(const Edge& e) const 596 { return GraphWrapper Skeleton1<GraphWrapper>::tail(e); }382 { return GraphWrapper<Graph>::tail(e); } 597 383 Node tail(const Edge& e) const 598 { return GraphWrapper Skeleton1<GraphWrapper>::head(e); }384 { return GraphWrapper<Graph>::head(e); } 599 385 }; 600 386 601 387 //Subgraph on the same node-set and partial edge-set 602 template<typename Graph Wrapper, typename EdgeFilterMap>603 class SubGraphWrapper : public GraphWrapper Skeleton1<GraphWrapper> {388 template<typename Graph, typename EdgeFilterMap> 389 class SubGraphWrapper : public GraphWrapper<Graph> { 604 390 protected: 605 391 EdgeFilterMap* filter_map; 606 392 public: 607 typedef typename GraphWrapperSkeleton1<GraphWrapper>::Node Node; 608 typedef typename GraphWrapperSkeleton1<GraphWrapper>::NodeIt NodeIt; 609 typedef typename GraphWrapperSkeleton1<GraphWrapper>::Edge Edge; 610 typedef typename GraphWrapperSkeleton1<GraphWrapper>::EdgeIt EdgeIt; 611 typedef typename GraphWrapperSkeleton1<GraphWrapper>::InEdgeIt InEdgeIt; 612 typedef typename GraphWrapperSkeleton1<GraphWrapper>::OutEdgeIt OutEdgeIt; 613 614 SubGraphWrapper(GraphWrapper& _gw, EdgeFilterMap& _filter_map) : 615 GraphWrapperSkeleton1<GraphWrapper>(_gw), filter_map(&_filter_map) { } 393 typedef typename GraphWrapper<Graph>::Node Node; 394 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; 395 typedef typename GraphWrapper<Graph>::Edge Edge; 396 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt; 397 typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt; 398 typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt; 399 400 // SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { } 401 SubGraphWrapper(Graph& _graph, EdgeFilterMap& _filter_map) : 402 GraphWrapper<Graph>(_graph), filter_map(&_filter_map) { } 616 403 617 404 template<typename I> I& first(I& i) const { 618 g ->first(i);619 while (g ->valid(i) && !filter_map->get(i)) { g->next(i); }405 graph->first(i); 406 while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } 620 407 return i; 621 408 } 622 409 template<typename I, typename P> I& first(I& i, const P& p) const { 623 g ->first(i, p);624 while (g ->valid(i) && !filter_map->get(i)) { g->next(i); }410 graph->first(i, p); 411 while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } 625 412 return i; 626 413 } … … 630 417 //} 631 418 template<typename I> I& next(I &i) const { 632 g ->next(i);633 while (g ->valid(i) && !filter_map->get(i)) { g->next(i); }419 graph->next(i); 420 while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } 634 421 return i; 635 422 } … … 802 589 803 590 804 template<typename Graph Wrapper>805 class UndirGraphWrapper : public GraphWrapper Skeleton1<GraphWrapper> {591 template<typename Graph> 592 class UndirGraphWrapper : public GraphWrapper<Graph> { 806 593 protected: 807 // GraphWrapper gw; 808 594 typedef typename Graph::Edge GraphEdge; 595 typedef typename Graph::OutEdgeIt GraphOutEdgeIt; 596 typedef typename Graph::InEdgeIt GraphInEdgeIt; 809 597 public: 810 //typedef GraphWrapper BaseGraph; 811 812 typedef typename GraphWrapperSkeleton1<GraphWrapper>::Node Node; 813 typedef typename GraphWrapperSkeleton1<GraphWrapper>::NodeIt NodeIt; 814 815 //private: 816 //FIXME ezeknek valojaban a GraphWrapper megfelelo dolgai kellene hogy 817 //legyenek, at kell irni 818 typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/ 819 GraphWrapper::Edge GraphEdge; 820 typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/ 821 GraphWrapper::OutEdgeIt GraphOutEdgeIt; 822 typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/ 823 GraphWrapper::InEdgeIt GraphInEdgeIt; 824 //public: 825 826 //UndirGraphWrapper() : graph(0) { } 827 UndirGraphWrapper(GraphWrapper& _gw) : 828 GraphWrapperSkeleton1<GraphWrapper>(_gw) { } 829 830 //UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { } 831 832 //void setGraph(Graph& _graph) { graph = &_graph; } 833 //Graph& getGraph() const { return (*graph); } 834 598 typedef typename GraphWrapper<Graph>::Node Node; 599 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; 600 601 // UndirGraphWrapper() : GraphWrapper<Graph>() { } 602 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 603 835 604 class Edge { 836 friend class UndirGraphWrapper<Graph Wrapper>;605 friend class UndirGraphWrapper<Graph>; 837 606 protected: 838 607 bool out_or_in; //true iff out … … 867 636 868 637 class OutEdgeIt : public Edge { 869 friend class UndirGraphWrapper<Graph Wrapper>;638 friend class UndirGraphWrapper<Graph>; 870 639 public: 871 640 OutEdgeIt() : Edge() { } 872 641 OutEdgeIt(const Invalid& i) : Edge(i) { } 873 OutEdgeIt(const UndirGraphWrapper<Graph Wrapper>& _G, const Node& n)642 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n) 874 643 : Edge() { 875 out_or_in=true; _G.g ->first(out, n);876 if (!(_G.g ->valid(out))) { out_or_in=false; _G.g->first(in, n); }644 out_or_in=true; _G.graph->first(out, n); 645 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); } 877 646 } 878 647 }; … … 881 650 882 651 class EdgeIt : public Edge { 883 friend class UndirGraphWrapper<Graph Wrapper>;652 friend class UndirGraphWrapper<Graph>; 884 653 protected: 885 654 NodeIt v; … … 887 656 EdgeIt() : Edge() { } 888 657 EdgeIt(const Invalid& i) : Edge(i) { } 889 EdgeIt(const UndirGraphWrapper<Graph Wrapper>& _G)658 EdgeIt(const UndirGraphWrapper<Graph>& _G) 890 659 : Edge() { 891 660 out_or_in=true; 892 661 //Node v; 893 662 _G.first(v); 894 if (_G.valid(v)) _G.g ->first(out); else out=INVALID;895 while (_G.valid(v) && !_G.g ->valid(out)) {896 _G.g ->next(v);897 if (_G.valid(v)) _G.g ->first(out);663 if (_G.valid(v)) _G.graph->first(out); else out=INVALID; 664 while (_G.valid(v) && !_G.graph->valid(out)) { 665 _G.graph->next(v); 666 if (_G.valid(v)) _G.graph->first(out); 898 667 } 899 668 } … … 901 670 902 671 OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { 903 e.out_or_in=true; g ->first(e.out, n);904 if (!(g ->valid(e.out))) { e.out_or_in=false; g->first(e.in, n); }672 e.out_or_in=true; graph->first(e.out, n); 673 if (!(graph->valid(e.out))) { e.out_or_in=false; graph->first(e.in, n); } 905 674 return e; 906 675 } … … 910 679 //NodeIt v; 911 680 first(e.v); 912 if (valid(e.v)) g ->first(e.out, e.v); else e.out=INVALID;913 while (valid(e.v) && !g ->valid(e.out)) {914 g ->next(e.v);915 if (valid(e.v)) g ->first(e.out, e.v);681 if (valid(e.v)) graph->first(e.out, e.v); else e.out=INVALID; 682 while (valid(e.v) && !graph->valid(e.out)) { 683 graph->next(e.v); 684 if (valid(e.v)) graph->first(e.out, e.v); 916 685 } 917 686 return e; 918 687 } 919 688 920 template<typename I> I& first(I& i) const { g ->first(i); return i; }689 template<typename I> I& first(I& i) const { graph->first(i); return i; } 921 690 template<typename I, typename P> I& first(I& i, const P& p) const { 922 g ->first(i, p); return i; }691 graph->first(i, p); return i; } 923 692 924 693 OutEdgeIt& next(OutEdgeIt& e) const { 925 694 if (e.out_or_in) { 926 Node n=g ->tail(e.out);927 g ->next(e.out);928 if (!g ->valid(e.out)) { e.out_or_in=false; g->first(e.in, n); }695 Node n=graph->tail(e.out); 696 graph->next(e.out); 697 if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); } 929 698 } else { 930 g ->next(e.in);699 graph->next(e.in); 931 700 } 932 701 return e; … … 935 704 EdgeIt& next(EdgeIt& e) const { 936 705 //NodeIt v=tail(e); 937 g ->next(e.out);938 while (valid(e.v) && !g ->valid(e.out)) {706 graph->next(e.out); 707 while (valid(e.v) && !graph->valid(e.out)) { 939 708 next(e.v); 940 if (valid(e.v)) g ->first(e.out, e.v);709 if (valid(e.v)) graph->first(e.out, e.v); 941 710 } 942 711 return e; 943 712 } 944 713 945 template<typename I> I& next(I &i) const { return g ->next(i); }714 template<typename I> I& next(I &i) const { return graph->next(i); } 946 715 // template<typename I> I getNext(const I& i) const { return gw.getNext(i); } 947 716 948 717 template< typename It > It first() const { 949 It e; first(e); return e; }718 It e; this->first(e); return e; } 950 719 951 720 template< typename It > It first(const Node& v) const { 952 It e; first(e, v); return e; }721 It e; this->first(e, v); return e; } 953 722 954 723 // Node head(const Edge& e) const { return gw.head(e); } … … 967 736 968 737 Node aNode(const OutEdgeIt& e) const { 969 if (e.out_or_in) return g ->tail(e); else return g->head(e); }738 if (e.out_or_in) return graph->tail(e); else return graph->head(e); } 970 739 Node bNode(const OutEdgeIt& e) const { 971 if (e.out_or_in) return g ->head(e); else return g->tail(e); }740 if (e.out_or_in) return graph->head(e); else return graph->tail(e); } 972 741 973 742 // Node addNode() const { return gw.addNode(); } … … 981 750 // void clear() const { gw.clear(); } 982 751 983 // template<typename T> class NodeMap : public Graph Wrapper::NodeMap<T> {752 // template<typename T> class NodeMap : public Graph::NodeMap<T> { 984 753 // public: 985 // NodeMap(const UndirGraphWrapper<Graph Wrapper>& _G) :986 // Graph Wrapper::NodeMap<T>(_G.gw) { }987 // NodeMap(const UndirGraphWrapper<Graph Wrapper>& _G, T a) :988 // Graph Wrapper::NodeMap<T>(_G.gw, a) { }754 // NodeMap(const UndirGraphWrapper<Graph>& _G) : 755 // Graph::NodeMap<T>(_G.gw) { } 756 // NodeMap(const UndirGraphWrapper<Graph>& _G, T a) : 757 // Graph::NodeMap<T>(_G.gw, a) { } 989 758 // }; 990 759 991 760 // template<typename T> class EdgeMap : 992 // public GraphWrapperSkeleton<Graph Wrapper>::EdgeMap<T> {761 // public GraphWrapperSkeleton<Graph>::EdgeMap<T> { 993 762 // public: 994 // EdgeMap(const UndirGraphWrapper<Graph Wrapper>& _G) :995 // GraphWrapperSkeleton<Graph Wrapper>::EdgeMap<T>(_G.gw) { }996 // EdgeMap(const UndirGraphWrapper<Graph Wrapper>& _G, T a) :997 // Graph Wrapper::EdgeMap<T>(_G.gw, a) { }763 // EdgeMap(const UndirGraphWrapper<Graph>& _G) : 764 // GraphWrapperSkeleton<Graph>::EdgeMap<T>(_G.gw) { } 765 // EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) : 766 // Graph::EdgeMap<T>(_G.gw, a) { } 998 767 // }; 999 768 }; … … 1072 841 1073 842 1074 template<typename Graph Wrapper, typename Number, typename FlowMap, typename CapacityMap>1075 class ResGraphWrapper : public GraphWrapper Skeleton1<GraphWrapper>{843 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> 844 class ResGraphWrapper : public GraphWrapper<Graph>{ 1076 845 public: 1077 //typedef Graph BaseGraph; 1078 //typedef TrivGraphWrapper<const Graph> GraphWrapper; 1079 typedef typename GraphWrapperSkeleton1<GraphWrapper>::Node Node; 1080 typedef typename GraphWrapperSkeleton1<GraphWrapper>::NodeIt NodeIt; 1081 private: 1082 typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/ 1083 GraphWrapper::OutEdgeIt OldOutEdgeIt; 1084 typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/ 1085 GraphWrapper::InEdgeIt OldInEdgeIt; 846 typedef typename GraphWrapper<Graph>::Node Node; 847 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; 1086 848 protected: 1087 //const Graph* graph;1088 //GraphWrapper gw;849 typedef typename Graph::OutEdgeIt OldOutEdgeIt; 850 typedef typename Graph::InEdgeIt OldInEdgeIt; 1089 851 FlowMap* flow; 1090 852 const CapacityMap* capacity; 1091 853 public: 1092 854 1093 ResGraphWrapper(Graph Wrapper& _gw, FlowMap& _flow,855 ResGraphWrapper(Graph& _graph, FlowMap& _flow, 1094 856 const CapacityMap& _capacity) : 1095 GraphWrapperSkeleton1<GraphWrapper>(_gw), 1096 flow(&_flow), capacity(&_capacity) { } 1097 1098 //void setGraph(const Graph& _graph) { graph = &_graph; } 1099 //const Graph& getGraph() const { return (*graph); } 857 GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { } 1100 858 1101 859 class Edge; … … 1105 863 1106 864 class Edge { 1107 friend class ResGraphWrapper<Graph Wrapper, Number, FlowMap, CapacityMap>;865 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 1108 866 protected: 1109 867 bool out_or_in; //true, iff out … … 1131 889 1132 890 class OutEdgeIt : public Edge { 1133 friend class ResGraphWrapper<Graph Wrapper, Number, FlowMap, CapacityMap>;891 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 1134 892 public: 1135 893 OutEdgeIt() { } … … 1138 896 OutEdgeIt(const Invalid& i) : Edge(i) { } 1139 897 protected: 1140 OutEdgeIt(const ResGraphWrapper<Graph Wrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {1141 resG.g ->first(out, v);1142 while( resG.g ->valid(out) && !(resG.resCap(out)>0) ) { resG.g->next(out); }1143 if (!resG.g ->valid(out)) {898 OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() { 899 resG.graph->first(out, v); 900 while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } 901 if (!resG.graph->valid(out)) { 1144 902 out_or_in=0; 1145 resG.g ->first(in, v);1146 while( resG.g ->valid(in) && !(resG.resCap(in)>0) ) { resG.g->next(in); }903 resG.graph->first(in, v); 904 while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } 1147 905 } 1148 906 } … … 1170 928 1171 929 class EdgeIt : public Edge { 1172 friend class ResGraphWrapper<Graph Wrapper, Number, FlowMap, CapacityMap>;930 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 1173 931 NodeIt v; 1174 932 public: … … 1176 934 //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } 1177 935 EdgeIt(const Invalid& i) : Edge(i) { } 1178 EdgeIt(const ResGraphWrapper<Graph Wrapper, Number, FlowMap, CapacityMap>& resG) : Edge() {1179 resG.g ->first(v);1180 if (resG.g ->valid(v)) resG.g->first(out, v); else out=INVALID;1181 while (resG.g ->valid(out) && !(resG.resCap(out)>0) ) { resG.g->next(out); }1182 while (resG.g ->valid(v) && !resG.g->valid(out)) {1183 resG.g ->next(v);1184 if (resG.g ->valid(v)) resG.g->first(out, v);1185 while (resG.g ->valid(out) && !(resG.resCap(out)>0) ) { resG.g->next(out); }936 EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() { 937 resG.graph->first(v); 938 if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID; 939 while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } 940 while (resG.graph->valid(v) && !resG.graph->valid(out)) { 941 resG.graph->next(v); 942 if (resG.graph->valid(v)) resG.graph->first(out, v); 943 while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } 1186 944 } 1187 if (!resG.g ->valid(out)) {945 if (!resG.graph->valid(out)) { 1188 946 out_or_in=0; 1189 resG.g ->first(v);1190 if (resG.g ->valid(v)) resG.g->first(in, v); else in=INVALID;1191 while (resG.g ->valid(in) && !(resG.resCap(in)>0) ) { resG.g->next(in); }1192 while (resG.g ->valid(v) && !resG.g->valid(in)) {1193 resG.g ->next(v);1194 if (resG.g ->valid(v)) resG.g->first(in, v);1195 while (resG.g ->valid(in) && !(resG.resCap(in)>0) ) { resG.g->next(in); }947 resG.graph->first(v); 948 if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID; 949 while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } 950 while (resG.graph->valid(v) && !resG.graph->valid(in)) { 951 resG.graph->next(v); 952 if (resG.graph->valid(v)) resG.graph->first(in, v); 953 while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } 1196 954 } 1197 955 } … … 1230 988 }; 1231 989 1232 NodeIt& first(NodeIt& v) const { g ->first(v); return v; }990 NodeIt& first(NodeIt& v) const { graph->first(v); return v; } 1233 991 OutEdgeIt& first(OutEdgeIt& e, Node v) const { 1234 992 e=OutEdgeIt(*this, v); … … 1240 998 } 1241 999 1242 NodeIt& next(NodeIt& n) const { return g ->next(n); }1000 NodeIt& next(NodeIt& n) const { return graph->next(n); } 1243 1001 1244 1002 OutEdgeIt& next(OutEdgeIt& e) const { 1245 1003 if (e.out_or_in) { 1246 Node v=g ->aNode(e.out);1247 g ->next(e.out);1248 while( g ->valid(e.out) && !(resCap(e.out)>0) ) { g->next(e.out); }1249 if (!g ->valid(e.out)) {1004 Node v=graph->aNode(e.out); 1005 graph->next(e.out); 1006 while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } 1007 if (!graph->valid(e.out)) { 1250 1008 e.out_or_in=0; 1251 g ->first(e.in, v);1252 while( g ->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }1009 graph->first(e.in, v); 1010 while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1253 1011 } 1254 1012 } else { 1255 g ->next(e.in);1256 while( g ->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }1013 graph->next(e.in); 1014 while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1257 1015 } 1258 1016 return e; … … 1261 1019 EdgeIt& next(EdgeIt& e) const { 1262 1020 if (e.out_or_in) { 1263 g ->next(e.out);1264 while (g ->valid(e.out) && !(resCap(e.out)>0) ) { g->next(e.out); }1265 while (g ->valid(e.v) && !g->valid(e.out)) {1266 g ->next(e.v);1267 if (g ->valid(e.v)) g->first(e.out, e.v);1268 while (g ->valid(e.out) && !(resCap(e.out)>0) ) { g->next(e.out); }1021 graph->next(e.out); 1022 while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } 1023 while (graph->valid(e.v) && !graph->valid(e.out)) { 1024 graph->next(e.v); 1025 if (graph->valid(e.v)) graph->first(e.out, e.v); 1026 while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } 1269 1027 } 1270 if (!g ->valid(e.out)) {1028 if (!graph->valid(e.out)) { 1271 1029 e.out_or_in=0; 1272 g ->first(e.v);1273 if (g ->valid(e.v)) g->first(e.in, e.v); else e.in=INVALID;1274 while (g ->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }1275 while (g ->valid(e.v) && !g->valid(e.in)) {1276 g ->next(e.v);1277 if (g ->valid(e.v)) g->first(e.in, e.v);1278 while (g ->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }1030 graph->first(e.v); 1031 if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID; 1032 while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1033 while (graph->valid(e.v) && !graph->valid(e.in)) { 1034 graph->next(e.v); 1035 if (graph->valid(e.v)) graph->first(e.in, e.v); 1036 while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1279 1037 } 1280 1038 } 1281 1039 } else { 1282 g ->next(e.in);1283 while (g ->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }1284 while (g ->valid(e.v) && !g->valid(e.in)) {1285 g ->next(e.v);1286 if (g ->valid(e.v)) g->first(e.in, e.v);1287 while (g ->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }1040 graph->next(e.in); 1041 while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1042 while (graph->valid(e.v) && !graph->valid(e.in)) { 1043 graph->next(e.v); 1044 if (graph->valid(e.v)) graph->first(e.in, e.v); 1045 while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1288 1046 } 1289 1047 } … … 1307 1065 1308 1066 Node tail(Edge e) const { 1309 return ((e.out_or_in) ? g ->aNode(e.out) : g->aNode(e.in)); }1067 return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } 1310 1068 Node head(Edge e) const { 1311 return ((e.out_or_in) ? g ->bNode(e.out) : g->bNode(e.in)); }1069 return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } 1312 1070 1313 1071 Node aNode(OutEdgeIt e) const { 1314 return ((e.out_or_in) ? g ->aNode(e.out) : g->aNode(e.in)); }1072 return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } 1315 1073 Node bNode(OutEdgeIt e) const { 1316 return ((e.out_or_in) ? g ->bNode(e.out) : g->bNode(e.in)); }1317 1318 int nodeNum() const { return g ->nodeNum(); }1074 return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } 1075 1076 int nodeNum() const { return graph->nodeNum(); } 1319 1077 //FIXME 1320 //int edgeNum() const { return g ->edgeNum(); }1321 1322 1323 int id(Node v) const { return g ->id(v); }1324 1325 bool valid(Node n) const { return g ->valid(n); }1078 //int edgeNum() const { return graph->edgeNum(); } 1079 1080 1081 int id(Node v) const { return graph->id(v); } 1082 1083 bool valid(Node n) const { return graph->valid(n); } 1326 1084 bool valid(Edge e) const { 1327 return e.out_or_in ? g ->valid(e.out) : g->valid(e.in); }1085 return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); } 1328 1086 1329 1087 void augment(const Edge& e, Number a) const { … … 1349 1107 } 1350 1108 1351 // template<typename T> class NodeMap : public Graph Wrapper::NodeMap<T> {1109 // template<typename T> class NodeMap : public Graph::NodeMap<T> { 1352 1110 // public: 1353 // NodeMap(const ResGraphWrapper<Graph Wrapper, Number, FlowMap, CapacityMap>& _G)1354 // : Graph Wrapper::NodeMap<T>(_G.gw) { }1355 // NodeMap(const ResGraphWrapper<Graph Wrapper, Number, FlowMap, CapacityMap>& _G,1356 // T a) : Graph Wrapper::NodeMap<T>(_G.gw, a) { }1111 // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) 1112 // : Graph::NodeMap<T>(_G.gw) { } 1113 // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, 1114 // T a) : Graph::NodeMap<T>(_G.gw, a) { } 1357 1115 // }; 1358 1116 … … 1369 1127 template <typename T> 1370 1128 class EdgeMap { 1371 typename Graph Wrapper::EdgeMap<T> forward_map, backward_map;1372 public: 1373 EdgeMap(const ResGraphWrapper<Graph Wrapper, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.gw), backward_map(_G.gw) { }1374 EdgeMap(const ResGraphWrapper<Graph Wrapper, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { }1129 typename Graph::EdgeMap<T> forward_map, backward_map; 1130 public: 1131 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } 1132 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } 1375 1133 void set(Edge e, T a) { 1376 1134 if (e.out_or_in) … … 1388 1146 }; 1389 1147 1390 // Subgraph on the same node-set and partial edge-set1391 template<typename Graph Wrapper, typename FirstOutEdgesMap>1392 class ErasingFirstGraphWrapper : public GraphWrapper Skeleton1<GraphWrapper> {1148 //ErasingFirstGraphWrapper for blocking flows 1149 template<typename Graph, typename FirstOutEdgesMap> 1150 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> { 1393 1151 protected: 1394 1152 FirstOutEdgesMap* first_out_edges; 1395 1153 public: 1396 typedef typename GraphWrapperSkeleton1<GraphWrapper>::Node Node; 1397 typedef typename GraphWrapperSkeleton1<GraphWrapper>::NodeIt NodeIt; 1398 typedef typename GraphWrapperSkeleton1<GraphWrapper>::Edge Edge; 1399 typedef typename GraphWrapperSkeleton1<GraphWrapper>::EdgeIt EdgeIt; 1400 typedef typename GraphWrapperSkeleton1<GraphWrapper>::InEdgeIt InEdgeIt; 1401 typedef typename GraphWrapperSkeleton1<GraphWrapper>::OutEdgeIt OutEdgeIt; 1402 1403 ErasingFirstGraphWrapper(GraphWrapper& _gw, FirstOutEdgesMap& _first_out_edges) : 1404 GraphWrapperSkeleton1<GraphWrapper>(_gw), first_out_edges(&_first_out_edges) { } 1154 typedef typename GraphWrapper<Graph>::Node Node; 1155 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; 1156 typedef typename GraphWrapper<Graph>::Edge Edge; 1157 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt; 1158 typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt; 1159 typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt; 1160 1161 ErasingFirstGraphWrapper(Graph& _graph, 1162 FirstOutEdgesMap& _first_out_edges) : 1163 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 1405 1164 1406 1165 template<typename I> I& first(I& i) const { 1407 g->first(i); 1408 //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); } 1166 graph->first(i); 1409 1167 return i; 1410 1168 } … … 1414 1172 } 1415 1173 template<typename I, typename P> I& first(I& i, const P& p) const { 1416 g->first(i, p); 1417 //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); } 1174 graph->first(i, p); 1418 1175 return i; 1419 1176 } … … 1423 1180 //} 1424 1181 template<typename I> I& next(I &i) const { 1425 g->next(i); 1426 //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); } 1182 graph->next(i); 1427 1183 return i; 1428 1184 } … … 1440 1196 } 1441 1197 }; 1442 1443 // template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>1444 // class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {1445 // protected:1446 // ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;1447 // //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;1448 // public:1449 // ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,1450 // const CapacityMap& _capacity) :1451 // ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),1452 // first_out_edges(*this) /*, dist(*this)*/ {1453 // for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {1454 // OutEdgeIt e;1455 // ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);1456 // first_out_edges.set(n, e);1457 // }1458 // }1459 1460 // //void setGraph(Graph& _graph) { graph = &_graph; }1461 // //Graph& getGraph() const { return (*graph); }1462 1463 // //TrivGraphWrapper() : graph(0) { }1464 // //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }1465 1466 // //typedef Graph BaseGraph;1467 1468 // //typedef typename Graph::Node Node;1469 // //typedef typename Graph::NodeIt NodeIt;1470 1471 // //typedef typename Graph::Edge Edge;1472 // //typedef typename Graph::OutEdgeIt OutEdgeIt;1473 // //typedef typename Graph::InEdgeIt InEdgeIt;1474 // //typedef typename Graph::SymEdgeIt SymEdgeIt;1475 // //typedef typename Graph::EdgeIt EdgeIt;1476 1477 // typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;1478 // typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;1479 1480 // typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;1481 // typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;1482 // //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;1483 // //typedef typename Graph::SymEdgeIt SymEdgeIt;1484 // //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;1485 1486 // NodeIt& first(NodeIt& n) const {1487 // return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);1488 // }1489 1490 // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {1491 // e=first_out_edges.get(n);1492 // return e;1493 // }1494 1495 // //ROSSZ template<typename I> I& first(I& i) const { return first(i); }1496 // //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {1497 // // return first(i, p); }1498 1499 // //template<typename I> I getNext(const I& i) const {1500 // // return gw.getNext(i); }1501 // //template<typename I> I& next(I &i) const { return gw.next(i); }1502 1503 // template< typename It > It first() const {1504 // It e; first(e); return e; }1505 1506 // template< typename It > It first(const Node& v) const {1507 // It e; first(e, v); return e; }1508 1509 // //Node head(const Edge& e) const { return gw.head(e); }1510 // //Node tail(const Edge& e) const { return gw.tail(e); }1511 1512 // //template<typename I> bool valid(const I& i) const1513 // // { return gw.valid(i); }1514 1515 // //int nodeNum() const { return gw.nodeNum(); }1516 // //int edgeNum() const { return gw.edgeNum(); }1517 1518 // //template<typename I> Node aNode(const I& e) const {1519 // // return gw.aNode(e); }1520 // //template<typename I> Node bNode(const I& e) const {1521 // // return gw.bNode(e); }1522 1523 // //Node addNode() const { return gw.addNode(); }1524 // //Edge addEdge(const Node& tail, const Node& head) const {1525 // // return gw.addEdge(tail, head); }1526 1527 // //void erase(const OutEdgeIt& e) {1528 // // first_out_edge(this->tail(e))=e;1529 // //}1530 // void erase(const Edge& e) {1531 // OutEdgeIt f(e);1532 // next(f);1533 // first_out_edges.set(this->tail(e), f);1534 // }1535 // //template<typename I> void erase(const I& i) const { gw.erase(i); }1536 1537 // //void clear() const { gw.clear(); }1538 1539 // template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {1540 // public:1541 // NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :1542 // ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }1543 // NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :1544 // ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }1545 // };1546 1547 // template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {1548 // public:1549 // EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :1550 // ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }1551 // EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :1552 // ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }1553 // };1554 // };1555 1556 // template<typename GraphWrapper>1557 // class FilterGraphWrapper {1558 // };1559 1560 // template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>1561 // class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {1562 1563 // //Graph* graph;1564 1565 // public:1566 // //typedef Graph BaseGraph;1567 1568 // typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;1569 // typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;1570 1571 // typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;1572 // typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;1573 // //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;1574 // //typedef typename Graph::SymEdgeIt SymEdgeIt;1575 // typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;1576 1577 // //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;1578 1579 // public:1580 // FilterGraphWrapper(const Graph& _G, FlowMap& _flow,1581 // const CapacityMap& _capacity) :1582 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, gw.nodeNum()) {1583 // }1584 1585 // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {1586 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);1587 // while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))1588 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);1589 // return e;1590 // }1591 1592 // NodeIt& next(NodeIt& e) const {1593 // return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);1594 // }1595 1596 // OutEdgeIt& next(OutEdgeIt& e) const {1597 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);1598 // while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e))))1599 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);1600 // return e;1601 // }1602 1603 // NodeIt& first(NodeIt& n) const {1604 // return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);1605 // }1606 1607 // void erase(const Edge& e) {1608 // OutEdgeIt f(e);1609 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);1610 // while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f))))1611 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);1612 // first_out_edges.set(this->tail(e), f);1613 // }1614 1615 // //TrivGraphWrapper() : graph(0) { }1616 // //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }1617 1618 // //void setGraph(Graph& _graph) { graph = &_graph; }1619 // //Graph& getGraph() const { return (*graph); }1620 1621 // //template<typename I> I& first(I& i) const { return gw.first(i); }1622 // //template<typename I, typename P> I& first(I& i, const P& p) const {1623 // // return gw.first(i, p); }1624 1625 // //template<typename I> I getNext(const I& i) const {1626 // // return gw.getNext(i); }1627 // //template<typename I> I& next(I &i) const { return gw.next(i); }1628 1629 // template< typename It > It first() const {1630 // It e; first(e); return e; }1631 1632 // template< typename It > It first(const Node& v) const {1633 // It e; first(e, v); return e; }1634 1635 // //Node head(const Edge& e) const { return gw.head(e); }1636 // //Node tail(const Edge& e) const { return gw.tail(e); }1637 1638 // //template<typename I> bool valid(const I& i) const1639 // // { return gw.valid(i); }1640 1641 // //template<typename I> void setInvalid(const I &i);1642 // //{ return gw.setInvalid(i); }1643 1644 // //int nodeNum() const { return gw.nodeNum(); }1645 // //int edgeNum() const { return gw.edgeNum(); }1646 1647 // //template<typename I> Node aNode(const I& e) const {1648 // // return gw.aNode(e); }1649 // //template<typename I> Node bNode(const I& e) const {1650 // // return gw.bNode(e); }1651 1652 // //Node addNode() const { return gw.addNode(); }1653 // //Edge addEdge(const Node& tail, const Node& head) const {1654 // // return gw.addEdge(tail, head); }1655 1656 // //template<typename I> void erase(const I& i) const { gw.erase(i); }1657 1658 // //void clear() const { gw.clear(); }1659 1660 // template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {1661 // public:1662 // NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :1663 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }1664 // NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :1665 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }1666 // };1667 1668 // template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {1669 // public:1670 // EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :1671 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }1672 // EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :1673 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }1674 // };1675 1676 // public:1677 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;1678 1679 // };1680 1681 1682 1198 1683 1199 // // FIXME: comparison should be made better!!!
Note: See TracChangeset
for help on using the changeset viewer.