Changeset 774:4297098d9677 in lemon-0.x for src/hugo/graph_wrapper.h
- Timestamp:
- 08/30/04 14:01:47 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1066
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/hugo/graph_wrapper.h
r739 r774 13 13 #include <hugo/invalid.h> 14 14 #include <hugo/maps.h> 15 //#include <iter_map.h>15 #include <iostream> 16 16 17 17 namespace hugo { … … 97 97 98 98 GraphWrapper(Graph& _graph) : graph(&_graph) { } 99 GraphWrapper(const GraphWrapper<Graph>& gw) : graph(gw.graph) { } 99 100 // Graph& getGraph() const { return *graph; } 100 101 101 // typedef typename Graph::Node Node; 102 class Node : public Graph::Node { 102 typedef typename Graph::Node Node; 103 // class Node : public Graph::Node { 104 // friend class GraphWrapper<Graph>; 105 // public: 106 // Node() { } 107 // Node(const typename Graph::Node& _n) : Graph::Node(_n) { } 108 // // /// \bug construction throughrthr multiple levels should be 109 // // /// handled better 110 // // Node(const typename ParentGraph::ParentGraph::Node& _n) : 111 // // Graph::Node(_n) { } 112 // Node(const Invalid& i) : Graph::Node(i) { } 113 // }; 114 class NodeIt : public Node { 115 const GraphWrapper<Graph>* gw; 103 116 friend class GraphWrapper<Graph>; 104 public:105 Node() { }106 Node(const typename Graph::Node& _n) : Graph::Node(_n) { }107 // /// \bug construction throughrthr multiple levels should be108 // /// handled better109 // Node(const typename ParentGraph::ParentGraph::Node& _n) :110 // Graph::Node(_n) { }111 Node(const Invalid& i) : Graph::Node(i) { }112 };113 class NodeIt {114 friend class GraphWrapper<Graph>;115 typename Graph::NodeIt n;116 117 public: 117 118 NodeIt() { } 118 NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } 119 NodeIt(const Invalid& i) : n(i) { } 120 NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { } 121 operator Node() const { return Node(typename Graph::Node(n)); } 122 }; 123 // typedef typename Graph::Edge Edge; 124 class Edge : public Graph::Edge { 119 // NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { } 120 NodeIt(Invalid i) : Node(i) { } 121 NodeIt(const GraphWrapper<Graph>& _gw) : 122 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { } 123 NodeIt(const GraphWrapper<Graph>& _gw, const Node& n) : 124 Node(n), gw(&_gw) { } 125 NodeIt& operator++() { 126 *(static_cast<Node*>(this))= 127 ++(typename Graph::NodeIt(*(gw->graph), *this)); 128 return *this; 129 } 130 }; 131 typedef typename Graph::Edge Edge; 132 // class Edge : public Graph::Edge { 133 // friend class GraphWrapper<Graph>; 134 // public: 135 // Edge() { } 136 // Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { } 137 // Edge(const Invalid& i) : Graph::Edge(i) { } 138 // }; 139 class OutEdgeIt : public Edge { 140 const GraphWrapper<Graph>* gw; 125 141 friend class GraphWrapper<Graph>; 126 public: 127 Edge() { } 128 Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { } 129 Edge(const Invalid& i) : Graph::Edge(i) { } 130 }; 131 class OutEdgeIt { 142 public: 143 OutEdgeIt() { } 144 //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { } 145 OutEdgeIt(Invalid i) : Edge(i) { } 146 OutEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) : 147 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { } 148 OutEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : 149 Edge(e), gw(&_gw) { } 150 OutEdgeIt& operator++() { 151 *(static_cast<Edge*>(this))= 152 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); 153 return *this; 154 } 155 }; 156 class InEdgeIt : public Edge { 157 const GraphWrapper<Graph>* gw; 132 158 friend class GraphWrapper<Graph>; 133 typename Graph::OutEdgeIt e; 134 public: 135 OutEdgeIt() { } 136 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } 137 OutEdgeIt(const Invalid& i) : e(i) { } 138 OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 139 e(*(_G.graph), typename Graph::Node(_n)) { } 140 operator Edge() const { return Edge(typename Graph::Edge(e)); } 141 }; 142 class InEdgeIt { 159 public: 160 InEdgeIt() { } 161 //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { } 162 InEdgeIt(Invalid i) : Edge(i) { } 163 InEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) : 164 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { } 165 InEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : 166 Edge(e), gw(&_gw) { } 167 InEdgeIt& operator++() { 168 *(static_cast<Edge*>(this))= 169 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); 170 return *this; 171 } 172 }; 173 //typedef typename Graph::SymEdgeIt SymEdgeIt; 174 class EdgeIt : public Edge { 175 const GraphWrapper<Graph>* gw; 143 176 friend class GraphWrapper<Graph>; 144 typename Graph::InEdgeIt e; 145 public: 146 InEdgeIt() { } 147 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } 148 InEdgeIt(const Invalid& i) : e(i) { } 149 InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 150 e(*(_G.graph), typename Graph::Node(_n)) { } 151 operator Edge() const { return Edge(typename Graph::Edge(e)); } 152 }; 153 //typedef typename Graph::SymEdgeIt SymEdgeIt; 154 class EdgeIt { 155 friend class GraphWrapper<Graph>; 156 typename Graph::EdgeIt e; 157 public: 177 public: 158 178 EdgeIt() { } 159 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } 160 EdgeIt(const Invalid& i) : e(i) { } 161 EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { } 162 operator Edge() const { return Edge(typename Graph::Edge(e)); } 179 //EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { } 180 EdgeIt(Invalid i) : Edge(i) { } 181 EdgeIt(const GraphWrapper<Graph>& _gw) : 182 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { } 183 EdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : 184 Edge(w), gw(&_gw) { } 185 EdgeIt& operator++() { 186 *(static_cast<Edge*>(this))= 187 ++(typename Graph::EdgeIt(*(gw->graph), *this)); 188 return *this; 189 } 163 190 }; 164 191 … … 176 203 } 177 204 178 NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }179 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }180 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }181 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }205 // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } 206 // OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } 207 // InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } 208 // EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } 182 209 183 210 Node tail(const Edge& e) const { … … 186 213 return Node(graph->head(static_cast<typename Graph::Edge>(e))); } 187 214 188 bool valid(const Node& n) const {189 return graph->valid(static_cast<typename Graph::Node>(n)); }190 bool valid(const Edge& e) const {191 return graph->valid(static_cast<typename Graph::Edge>(e)); }215 // bool valid(const Node& n) const { 216 // return graph->valid(static_cast<typename Graph::Node>(n)); } 217 // bool valid(const Edge& e) const { 218 // return graph->valid(static_cast<typename Graph::Edge>(e)); } 192 219 193 220 int nodeNum() const { return graph->nodeNum(); } 194 221 int edgeNum() const { return graph->edgeNum(); } 195 222 196 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }197 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }198 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }199 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }223 // Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } 224 // Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } 225 // Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } 226 // Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } 200 227 201 228 Node addNode() const { return Node(graph->addNode()); } … … 219 246 typedef typename Graph::template NodeMap<T> Parent; 220 247 public: 221 NodeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }222 NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }248 NodeMap(const GraphWrapper<Graph>& gw) : Parent(*(gw.graph)) { } 249 NodeMap(const GraphWrapper<Graph>& gw, T a) : Parent(*(gw.graph), a) { } 223 250 }; 224 251 … … 226 253 typedef typename Graph::template EdgeMap<T> Parent; 227 254 public: 228 EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }229 EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }255 EdgeMap(const GraphWrapper<Graph>& gw) : Parent(*(gw.graph)) { } 256 EdgeMap(const GraphWrapper<Graph>& gw, T a) : Parent(*(gw.graph), a) { } 230 257 }; 231 258 }; … … 247 274 public: 248 275 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 276 RevGraphWrapper(const RevGraphWrapper<Graph>& gw) : Parent(gw) { } 249 277 250 278 typedef typename GraphWrapper<Graph>::Node Node; … … 257 285 //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt; 258 286 259 class OutEdgeIt { 287 class OutEdgeIt : public Edge { 288 const RevGraphWrapper<Graph>* gw; 260 289 friend class GraphWrapper<Graph>; 261 friend class RevGraphWrapper<Graph>; 262 typename Graph::InEdgeIt e; 263 public: 290 public: 264 291 OutEdgeIt() { } 265 OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } 266 OutEdgeIt(const Invalid& i) : e(i) { } 267 OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 268 e(*(_G.graph), typename Graph::Node(_n)) { } 269 operator Edge() const { return Edge(typename Graph::Edge(e)); } 270 }; 271 class InEdgeIt { 292 //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { } 293 OutEdgeIt(Invalid i) : Edge(i) { } 294 OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) : 295 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { } 296 OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) : 297 Edge(e), gw(&_gw) { } 298 OutEdgeIt& operator++() { 299 *(static_cast<Edge*>(this))= 300 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); 301 return *this; 302 } 303 }; 304 class InEdgeIt : public Edge { 305 const RevGraphWrapper<Graph>* gw; 272 306 friend class GraphWrapper<Graph>; 273 friend class RevGraphWrapper<Graph>; 274 typename Graph::OutEdgeIt e; 275 public: 307 public: 276 308 InEdgeIt() { } 277 InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } 278 InEdgeIt(const Invalid& i) : e(i) { } 279 InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 280 e(*(_G.graph), typename Graph::Node(_n)) { } 281 operator Edge() const { return Edge(typename Graph::Edge(e)); } 309 //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { } 310 InEdgeIt(Invalid i) : Edge(i) { } 311 InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) : 312 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { } 313 InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) : 314 Edge(e), gw(&_gw) { } 315 InEdgeIt& operator++() { 316 *(static_cast<Edge*>(this))= 317 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); 318 return *this; 319 } 282 320 }; 283 321 … … 290 328 } 291 329 292 using GraphWrapper<Graph>::next;293 OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }294 InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }295 296 Node aNode(const OutEdgeIt& e) const {297 return Node(this->graph->aNode(e.e)); }298 Node aNode(const InEdgeIt& e) const {299 return Node(this->graph->aNode(e.e)); }300 Node bNode(const OutEdgeIt& e) const {301 return Node(this->graph->bNode(e.e)); }302 Node bNode(const InEdgeIt& e) const {303 return Node(this->graph->bNode(e.e)); }330 // using GraphWrapper<Graph>::next; 331 // OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } 332 // InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } 333 334 // Node aNode(const OutEdgeIt& e) const { 335 // return Node(this->graph->aNode(e.e)); } 336 // Node aNode(const InEdgeIt& e) const { 337 // return Node(this->graph->aNode(e.e)); } 338 // Node bNode(const OutEdgeIt& e) const { 339 // return Node(this->graph->bNode(e.e)); } 340 // Node bNode(const InEdgeIt& e) const { 341 // return Node(this->graph->bNode(e.e)); } 304 342 305 343 Node tail(const Edge& e) const { … … 309 347 310 348 }; 311 312 313 349 314 350 /// A graph wrapper for hiding nodes and edges from a graph. … … 627 663 typedef GraphWrapper<Graph> Parent; 628 664 protected: 629 //const CapacityMap* capacity;630 //FlowMap* flow;631 632 665 ForwardFilterMap* forward_filter; 633 666 BackwardFilterMap* backward_filter; … … 648 681 GraphWrapper<Graph>(_graph), 649 682 forward_filter(&_forward_filter), backward_filter(&_backward_filter) { } 683 SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph, 684 ForwardFilterMap, BackwardFilterMap>& gw) : 685 Parent(gw), 686 forward_filter(gw.forward_filter), 687 backward_filter(gw.backward_filter) { } 650 688 651 689 class Edge; … … 658 696 659 697 typedef typename GraphWrapper<Graph>::Node Node; 660 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; 661 698 //typedef typename GraphWrapper<Graph>::NodeIt NodeIt; 699 700 typedef typename Graph::Edge GraphEdge; 662 701 class Edge : public Graph::Edge { 663 702 friend class SubBidirGraphWrapper<Graph, … … 672 711 Edge() { } 673 712 ///\bug =false kell-e? zsoltnak kell az addEdge miatt 674 Edge(const typename Graph::Edge& _e, bool _backward=false) :675 Graph::Edge( _e), backward(_backward) { }676 Edge( const Invalid&i) : Graph::Edge(i), backward(true) { }713 Edge(const typename Graph::Edge& e, bool _backward/*=false*/) : 714 Graph::Edge(e), backward(_backward) { } 715 Edge(Invalid i) : Graph::Edge(i), backward(true) { } 677 716 //the unique invalid iterator 678 friend bool operator==(const Edge& u, const Edge& v) { 679 return (v.backward==u.backward && 680 static_cast<typename Graph::Edge>(u)== 717 // friend bool operator==(const Edge& u, const Edge& v) { 718 // return (u.backward==v.backward && 719 // static_cast<typename Graph::Edge>(u)== 720 // static_cast<typename Graph::Edge>(v)); 721 // } 722 // friend bool operator!=(const Edge& u, const Edge& v) { 723 // return (u.backward!=v.backward || 724 // static_cast<typename Graph::Edge>(u)!= 725 // static_cast<typename Graph::Edge>(v)); 726 // } 727 bool operator==(const Edge& v) const { 728 return (this->backward==v.backward && 729 static_cast<typename Graph::Edge>(*this)== 681 730 static_cast<typename Graph::Edge>(v)); 682 731 } 683 friend bool operator!=(const Edge& u, const Edge& v){684 return ( v.backward!=u.backward ||685 static_cast<typename Graph::Edge>( u)!=732 bool operator!=(const Edge& v) const { 733 return (this->backward!=v.backward || 734 static_cast<typename Graph::Edge>(*this)!= 686 735 static_cast<typename Graph::Edge>(v)); 687 } 688 }; 689 690 class OutEdgeIt {736 } 737 }; 738 739 class OutEdgeIt : public Edge { 691 740 friend class SubBidirGraphWrapper<Graph, 692 741 ForwardFilterMap, BackwardFilterMap>; 693 742 protected: 694 typename Graph::OutEdgeIt out; 695 typename Graph::InEdgeIt in; 696 bool backward; 743 const SubBidirGraphWrapper<Graph, 744 ForwardFilterMap, BackwardFilterMap>* gw; 697 745 public: 698 746 OutEdgeIt() { } 699 //FIXME 700 // OutEdgeIt(const Edge& e) : Edge(e) { } 701 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } 747 OutEdgeIt(Invalid i) : Edge(i) { } 702 748 //the unique invalid iterator 703 749 OutEdgeIt(const SubBidirGraphWrapper<Graph, 704 ForwardFilterMap, BackwardFilterMap>& _G, Node v) { 705 backward=false; 706 _G.graph->first(out, v); 707 while(_G.graph->valid(out) && !(*_G.forward_filter)[*this]) { _G.graph->next(out); } 708 if (!_G.graph->valid(out)) { 709 backward=true; 710 _G.graph->first(in, v); 711 while(_G.graph->valid(in) && !(*_G.backward_filter)[*this]) { _G.graph->next(in); } 750 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : 751 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) { 752 while (*static_cast<GraphEdge*>(this)!=INVALID && 753 !(*(gw->forward_filter))[*this]) 754 *(static_cast<GraphEdge*>(this))= 755 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); 756 if (*static_cast<GraphEdge*>(this)==INVALID) 757 *static_cast<Edge*>(this)= 758 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true); 759 while (*static_cast<GraphEdge*>(this)!=INVALID && 760 !(*(gw->backward_filter))[*this]) 761 *(static_cast<GraphEdge*>(this))= 762 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); 763 } 764 OutEdgeIt(const SubBidirGraphWrapper<Graph, 765 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 766 Edge(e), gw(&_gw) { } 767 OutEdgeIt& operator++() { 768 if (!this->backward) { 769 Node n=gw->tail(*this); 770 *(static_cast<GraphEdge*>(this))= 771 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); 772 while (*static_cast<GraphEdge*>(this)!=INVALID && 773 !(*(gw->forward_filter))[*this]) 774 *(static_cast<GraphEdge*>(this))= 775 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); 776 if (*static_cast<GraphEdge*>(this)==INVALID) 777 *static_cast<Edge*>(this)= 778 Edge(typename Graph::InEdgeIt(*(gw->graph), n), true); 779 while (*static_cast<GraphEdge*>(this)!=INVALID && 780 !(*(gw->backward_filter))[*this]) 781 *(static_cast<GraphEdge*>(this))= 782 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); 783 } else { 784 *(static_cast<GraphEdge*>(this))= 785 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); 786 while (*static_cast<GraphEdge*>(this)!=INVALID && 787 !(*(gw->backward_filter))[*this]) 788 *(static_cast<GraphEdge*>(this))= 789 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); 712 790 } 713 } 714 operator Edge() const { 715 // Edge e; 716 // e.forward=this->forward; 717 // if (this->forward) e=out; else e=in; 718 // return e; 719 if (this->backward) 720 return Edge(in, this->backward); 721 else 722 return Edge(out, this->backward); 723 } 724 }; 725 726 class InEdgeIt { 791 return *this; 792 } 793 }; 794 795 class InEdgeIt : public Edge { 727 796 friend class SubBidirGraphWrapper<Graph, 728 797 ForwardFilterMap, BackwardFilterMap>; 729 798 protected: 730 typename Graph::OutEdgeIt out; 731 typename Graph::InEdgeIt in; 732 bool backward; 799 const SubBidirGraphWrapper<Graph, 800 ForwardFilterMap, BackwardFilterMap>* gw; 733 801 public: 734 802 InEdgeIt() { } 735 //FIXME 736 // OutEdgeIt(const Edge& e) : Edge(e) { } 737 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } 803 InEdgeIt(Invalid i) : Edge(i) { } 738 804 //the unique invalid iterator 739 805 InEdgeIt(const SubBidirGraphWrapper<Graph, 740 ForwardFilterMap, BackwardFilterMap>& _G, Node v) { 741 backward=false; 742 _G.graph->first(in, v); 743 while(_G.graph->valid(in) && !(*_G.forward_filter)[*this]) { _G.graph->next(in); } 744 if (!_G.graph->valid(in)) { 745 backward=true; 746 _G.graph->first(out, v); 747 while(_G.graph->valid(out) && !(*_G.backward_filter)[*this]) { _G.graph->next(out); } 806 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : 807 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) { 808 while (*static_cast<GraphEdge*>(this)!=INVALID && 809 !(*(gw->forward_filter))[*this]) 810 *(static_cast<GraphEdge*>(this))= 811 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); 812 if (*static_cast<GraphEdge*>(this)==INVALID) 813 *static_cast<Edge*>(this)= 814 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true); 815 while (*static_cast<GraphEdge*>(this)!=INVALID && 816 !(*(gw->backward_filter))[*this]) 817 *(static_cast<GraphEdge*>(this))= 818 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); 819 } 820 InEdgeIt(const SubBidirGraphWrapper<Graph, 821 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 822 Edge(e), gw(&_gw) { } 823 InEdgeIt& operator++() { 824 if (!this->backward) { 825 Node n=gw->head(*this); 826 *(static_cast<GraphEdge*>(this))= 827 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); 828 while (*static_cast<GraphEdge*>(this)!=INVALID && 829 !(*(gw->forward_filter))[*this]) 830 *(static_cast<GraphEdge*>(this))= 831 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); 832 if (*static_cast<GraphEdge*>(this)==INVALID) 833 *static_cast<Edge*>(this)= 834 Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true); 835 while (*static_cast<GraphEdge*>(this)!=INVALID && 836 !(*(gw->backward_filter))[*this]) 837 *(static_cast<GraphEdge*>(this))= 838 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); 839 } else { 840 *(static_cast<GraphEdge*>(this))= 841 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); 842 while (*static_cast<GraphEdge*>(this)!=INVALID && 843 !(*(gw->backward_filter))[*this]) 844 *(static_cast<GraphEdge*>(this))= 845 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); 748 846 } 749 } 750 operator Edge() const { 751 // Edge e; 752 // e.forward=this->forward; 753 // if (this->forward) e=out; else e=in; 754 // return e; 755 if (this->backward) 756 return Edge(out, this->backward); 757 else 758 return Edge(in, this->backward); 759 } 760 }; 761 762 class EdgeIt { 847 return *this; 848 } 849 }; 850 851 class EdgeIt : public Edge { 763 852 friend class SubBidirGraphWrapper<Graph, 764 853 ForwardFilterMap, BackwardFilterMap>; 765 854 protected: 766 typename Graph::EdgeIt e;767 bool backward;855 const SubBidirGraphWrapper<Graph, 856 ForwardFilterMap, BackwardFilterMap>* gw; 768 857 public: 769 858 EdgeIt() { } 770 EdgeIt(const Invalid& i) : e(i), backward(true) { } 859 EdgeIt(Invalid i) : Edge(i) { } 860 //the unique invalid iterator 771 861 EdgeIt(const SubBidirGraphWrapper<Graph, 772 ForwardFilterMap, BackwardFilterMap>& _G) { 773 backward=false; 774 _G.graph->first(e); 775 while (_G.graph->valid(e) && !(*_G.forward_filter)[*this]) _G.graph->next(e); 776 if (!_G.graph->valid(e)) { 777 backward=true; 778 _G.graph->first(e); 779 while (_G.graph->valid(e) && !(*_G.backward_filter)[*this]) _G.graph->next(e); 862 ForwardFilterMap, BackwardFilterMap>& _gw) : 863 Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) { 864 while (*static_cast<GraphEdge*>(this)!=INVALID && 865 !(*(gw->forward_filter))[*this]) 866 *(static_cast<GraphEdge*>(this))= 867 ++(typename Graph::EdgeIt(*(gw->graph), *this)); 868 if (*static_cast<GraphEdge*>(this)==INVALID) 869 *static_cast<Edge*>(this)= 870 Edge(typename Graph::EdgeIt(*(_gw.graph)), true); 871 while (*static_cast<GraphEdge*>(this)!=INVALID && 872 !(*(gw->backward_filter))[*this]) 873 *(static_cast<GraphEdge*>(this))= 874 ++(typename Graph::EdgeIt(*(gw->graph), *this)); 875 } 876 EdgeIt(const SubBidirGraphWrapper<Graph, 877 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 878 Edge(e), gw(&_gw) { } 879 EdgeIt& operator++() { 880 if (!this->backward) { 881 *(static_cast<GraphEdge*>(this))= 882 ++(typename Graph::EdgeIt(*(gw->graph), *this)); 883 while (*static_cast<GraphEdge*>(this)!=INVALID && 884 !(*(gw->forward_filter))[*this]) 885 *(static_cast<GraphEdge*>(this))= 886 ++(typename Graph::EdgeIt(*(gw->graph), *this)); 887 if (*static_cast<GraphEdge*>(this)==INVALID) 888 *static_cast<Edge*>(this)= 889 Edge(typename Graph::EdgeIt(*(gw->graph)), true); 890 while (*static_cast<GraphEdge*>(this)!=INVALID && 891 !(*(gw->backward_filter))[*this]) 892 *(static_cast<GraphEdge*>(this))= 893 ++(typename Graph::EdgeIt(*(gw->graph), *this)); 894 } else { 895 *(static_cast<GraphEdge*>(this))= 896 ++(typename Graph::EdgeIt(*(gw->graph), *this)); 897 while (*static_cast<GraphEdge*>(this)!=INVALID && 898 !(*(gw->backward_filter))[*this]) 899 *(static_cast<GraphEdge*>(this))= 900 ++(typename Graph::EdgeIt(*(gw->graph), *this)); 780 901 } 781 } 782 operator Edge() const { 783 return Edge(e, this->backward); 902 return *this; 784 903 } 785 904 }; … … 800 919 } 801 920 802 using GraphWrapper<Graph>::next;803 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }804 OutEdgeIt& next(OutEdgeIt& e) const {805 if (!e.backward) {806 Node v=this->graph->aNode(e.out);807 this->graph->next(e.out);808 while(this->graph->valid(e.out) && !(*forward_filter)[e]) {809 this->graph->next(e.out); }810 if (!this->graph->valid(e.out)) {811 e.backward=true;812 this->graph->first(e.in, v);813 while(this->graph->valid(e.in) && !(*backward_filter)[e]) {814 this->graph->next(e.in); }815 }816 } else {817 this->graph->next(e.in);818 while(this->graph->valid(e.in) && !(*backward_filter)[e]) {819 this->graph->next(e.in); }820 }821 return e;822 }823 // FIXME Not tested824 InEdgeIt& next(InEdgeIt& e) const {825 if (!e.backward) {826 Node v=this->graph->aNode(e.in);827 this->graph->next(e.in);828 while(this->graph->valid(e.in) && !(*forward_filter)[e]) {829 this->graph->next(e.in); }830 if (!this->graph->valid(e.in)) {831 e.backward=true;832 this->graph->first(e.out, v);833 while(this->graph->valid(e.out) && !(*backward_filter)[e]) {834 this->graph->next(e.out); }835 }836 } else {837 this->graph->next(e.out);838 while(this->graph->valid(e.out) && !(*backward_filter)[e]) {839 this->graph->next(e.out); }840 }841 return e;842 }843 EdgeIt& next(EdgeIt& e) const {844 if (!e.backward) {845 this->graph->next(e.e);846 while(this->graph->valid(e.e) && !(*forward_filter)[e]) {847 this->graph->next(e.e); }848 if (!this->graph->valid(e.e)) {849 e.backward=true;850 this->graph->first(e.e);851 while(this->graph->valid(e.e) && !(*backward_filter)[e]) {852 this->graph->next(e.e); }853 }854 } else {855 this->graph->next(e.e);856 while(this->graph->valid(e.e) && !(*backward_filter)[e]) {857 this->graph->next(e.e); }858 }859 return e;860 }921 // using GraphWrapper<Graph>::next; 922 // // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; } 923 // OutEdgeIt& next(OutEdgeIt& e) const { 924 // if (!e.backward) { 925 // Node v=this->graph->aNode(e.out); 926 // this->graph->next(e.out); 927 // while(this->graph->valid(e.out) && !(*forward_filter)[e]) { 928 // this->graph->next(e.out); } 929 // if (!this->graph->valid(e.out)) { 930 // e.backward=true; 931 // this->graph->first(e.in, v); 932 // while(this->graph->valid(e.in) && !(*backward_filter)[e]) { 933 // this->graph->next(e.in); } 934 // } 935 // } else { 936 // this->graph->next(e.in); 937 // while(this->graph->valid(e.in) && !(*backward_filter)[e]) { 938 // this->graph->next(e.in); } 939 // } 940 // return e; 941 // } 942 // // FIXME Not tested 943 // InEdgeIt& next(InEdgeIt& e) const { 944 // if (!e.backward) { 945 // Node v=this->graph->aNode(e.in); 946 // this->graph->next(e.in); 947 // while(this->graph->valid(e.in) && !(*forward_filter)[e]) { 948 // this->graph->next(e.in); } 949 // if (!this->graph->valid(e.in)) { 950 // e.backward=true; 951 // this->graph->first(e.out, v); 952 // while(this->graph->valid(e.out) && !(*backward_filter)[e]) { 953 // this->graph->next(e.out); } 954 // } 955 // } else { 956 // this->graph->next(e.out); 957 // while(this->graph->valid(e.out) && !(*backward_filter)[e]) { 958 // this->graph->next(e.out); } 959 // } 960 // return e; 961 // } 962 // EdgeIt& next(EdgeIt& e) const { 963 // if (!e.backward) { 964 // this->graph->next(e.e); 965 // while(this->graph->valid(e.e) && !(*forward_filter)[e]) { 966 // this->graph->next(e.e); } 967 // if (!this->graph->valid(e.e)) { 968 // e.backward=true; 969 // this->graph->first(e.e); 970 // while(this->graph->valid(e.e) && !(*backward_filter)[e]) { 971 // this->graph->next(e.e); } 972 // } 973 // } else { 974 // this->graph->next(e.e); 975 // while(this->graph->valid(e.e) && !(*backward_filter)[e]) { 976 // this->graph->next(e.e); } 977 // } 978 // return e; 979 // } 861 980 862 981 Node tail(Edge e) const { … … 865 984 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); } 866 985 867 Node aNode(OutEdgeIt e) const {868 return ((!e.backward) ? this->graph->aNode(e.out) :869 this->graph->aNode(e.in)); }870 Node bNode(OutEdgeIt e) const {871 return ((!e.backward) ? this->graph->bNode(e.out) :872 this->graph->bNode(e.in)); }873 874 Node aNode(InEdgeIt e) const {875 return ((!e.backward) ? this->graph->aNode(e.in) :876 this->graph->aNode(e.out)); }877 Node bNode(InEdgeIt e) const {878 return ((!e.backward) ? this->graph->bNode(e.in) :879 this->graph->bNode(e.out)); }986 // Node aNode(OutEdgeIt e) const { 987 // return ((!e.backward) ? this->graph->aNode(e.out) : 988 // this->graph->aNode(e.in)); } 989 // Node bNode(OutEdgeIt e) const { 990 // return ((!e.backward) ? this->graph->bNode(e.out) : 991 // this->graph->bNode(e.in)); } 992 993 // Node aNode(InEdgeIt e) const { 994 // return ((!e.backward) ? this->graph->aNode(e.in) : 995 // this->graph->aNode(e.out)); } 996 // Node bNode(InEdgeIt e) const { 997 // return ((!e.backward) ? this->graph->bNode(e.in) : 998 // this->graph->bNode(e.out)); } 880 999 881 1000 /// Gives back the opposite edge. … … 894 1013 // int id(Node v) const { return graph->id(v); } 895 1014 896 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }897 bool valid(Edge e) const {898 return this->graph->valid(e);899 //return e.forward ? graph->valid(e.out) : graph->valid(e.in);900 }1015 // bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); } 1016 // bool valid(Edge e) const { 1017 // return this->graph->valid(e); 1018 // //return e.forward ? graph->valid(e.out) : graph->valid(e.in); 1019 // } 901 1020 902 1021 bool forward(const Edge& e) const { return !e.backward; } … … 940 1059 typedef Edge KeyType; 941 1060 EdgeMap(const SubBidirGraphWrapper<Graph, 942 ForwardFilterMap, BackwardFilterMap>& _G) :943 forward_map(*( _G.graph)), backward_map(*(_G.graph)) { }1061 ForwardFilterMap, BackwardFilterMap>& g) : 1062 forward_map(*(g.graph)), backward_map(*(g.graph)) { } 944 1063 EdgeMap(const SubBidirGraphWrapper<Graph, 945 ForwardFilterMap, BackwardFilterMap>& _G, T a) :946 forward_map(*( _G.graph), a), backward_map(*(_G.graph), a) { }1064 ForwardFilterMap, BackwardFilterMap>& g, T a) : 1065 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { } 947 1066 void set(Edge e, T a) { 948 1067 if (!e.backward)
Note: See TracChangeset
for help on using the changeset viewer.