00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_SUB_GRAPH_H
00020 #define LEMON_SUB_GRAPH_H
00021
00022 #include <lemon/graph_adaptor.h>
00023
00024 namespace lemon {
00025
00029 template <typename _Graph>
00030 class SubGraphBase : public GraphAdaptorBase<const _Graph> {
00031 public:
00032 typedef _Graph Graph;
00033 typedef SubGraphBase<_Graph> SubGraph;
00034 typedef GraphAdaptorBase<const _Graph> Parent;
00035 typedef Parent Base;
00036
00037 typedef typename Parent::Node Node;
00038 typedef typename Parent::Edge Edge;
00039
00040
00041 protected:
00042
00043 class NodesImpl;
00044 class EdgesImpl;
00045
00046 SubGraphBase() {}
00047
00048 void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) {
00049 Parent::setGraph(_graph);
00050 nodes = &_nodes;
00051 edges = &_edges;
00052 firstNode = INVALID;
00053
00054 Node node;
00055 Parent::first(node);
00056 while (node != INVALID) {
00057 (*nodes)[node].prev = node;
00058 (*nodes)[node].firstIn = INVALID;
00059 (*nodes)[node].firstOut = INVALID;
00060 Parent::next(node);
00061 }
00062
00063 Edge edge;
00064 Parent::first(edge);
00065 while (edge != INVALID) {
00066 (*edges)[edge].prevOut = edge;
00067 Parent::next(edge);
00068 }
00069 }
00070
00071 public:
00072
00073 void first(Node& node) const {
00074 node = firstNode;
00075 }
00076 void next(Node& node) const {
00077 node = (*nodes)[node].next;
00078 }
00079
00080 void first(Edge& edge) const {
00081 Node node = firstNode;
00082 while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
00083 node = (*nodes)[node].next;
00084 }
00085 if (node == INVALID) {
00086 edge = INVALID;
00087 } else {
00088 edge = (*nodes)[node].firstOut;
00089 }
00090 }
00091 void next(Edge& edge) const {
00092 if ((*edges)[edge].nextOut != INVALID) {
00093 edge = (*edges)[edge].nextOut;
00094 } else {
00095 Node node = (*nodes)[source(edge)].next;
00096 while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
00097 node = (*nodes)[node].next;
00098 }
00099 if (node == INVALID) {
00100 edge = INVALID;
00101 } else {
00102 edge = (*nodes)[node].firstOut;
00103 }
00104 }
00105 }
00106
00107 void firstOut(Edge& edge, const Node& node) const {
00108 edge = (*nodes)[node].firstOut;
00109 }
00110 void nextOut(Edge& edge) const {
00111 edge = (*edges)[edge].nextOut;
00112 }
00113
00114 void firstIn(Edge& edge, const Node& node) const {
00115 edge = (*nodes)[node].firstIn;
00116 }
00117 void nextIn(Edge& edge) const {
00118 edge = (*edges)[edge].nextIn;
00119 }
00120
00124 bool hidden(const Node& node) const {
00125 return (*nodes)[node].prev == node;
00126 }
00127
00133 void hide(const Node& node) {
00134 if (hidden(node)) return;
00135 Edge edge;
00136 firstOut(edge, node);
00137 while (edge != INVALID) {
00138 hide(edge);
00139 firstOut(edge, node);
00140 }
00141
00142 firstOut(edge, node);
00143 while (edge != INVALID) {
00144 hide(edge);
00145 firstOut(edge, node);
00146 }
00147 if ((*nodes)[node].prev != INVALID) {
00148 (*nodes)[(*nodes)[node].prev].next = (*nodes)[node].next;
00149 } else {
00150 firstNode = (*nodes)[node].next;
00151 }
00152 if ((*nodes)[node].next != INVALID) {
00153 (*nodes)[(*nodes)[node].next].prev = (*nodes)[node].prev;
00154 }
00155 (*nodes)[node].prev = node;
00156 (*nodes)[node].firstIn = INVALID;
00157 (*nodes)[node].firstOut = INVALID;
00158 }
00159
00164 void unHide(const Node& node) {
00165 if (!hidden(node)) return;
00166 (*nodes)[node].next = firstNode;
00167 (*nodes)[node].prev = INVALID;
00168 if ((*nodes)[node].next != INVALID) {
00169 (*nodes)[(*nodes)[node].next].prev = node;
00170 }
00171 firstNode = node;
00172 }
00173
00177 bool hidden(const Edge& edge) const {
00178 return (*edges)[edge].prevOut == edge;
00179 }
00180
00185 void hide(const Edge& edge) {
00186 if (hidden(edge)) return;
00187 if ((*edges)[edge].prevOut == edge) return;
00188 if ((*edges)[edge].prevOut != INVALID) {
00189 (*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut;
00190 } else {
00191 (*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut;
00192 }
00193 if ((*edges)[edge].nextOut != INVALID) {
00194 (*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut;
00195 }
00196
00197 if ((*edges)[edge].prevIn != INVALID) {
00198 (*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn;
00199 } else {
00200 (*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn;
00201 }
00202 if ((*edges)[edge].nextIn != INVALID) {
00203 (*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn;
00204 }
00205 (*edges)[edge].next = edge;
00206 }
00207
00213 void unHide(const Edge& edge) {
00214 if (!hidden(edge)) return;
00215
00216 Node node;
00217
00218 node = Parent::source(edge);
00219 unHide(node);
00220 (*edges)[edge].nextOut = (*nodes)[node].firstOut;
00221 (*edges)[edge].prevOut = INVALID;
00222 if ((*edges)[edge].nextOut != INVALID) {
00223 (*edges)[(*edges)[edge].nextOut].prevOut = edge;
00224 }
00225 (*nodes)[node].firstOut = edge;
00226
00227 node = Parent::target(edge);
00228 unHide(node);
00229 (*edges)[edge].nextIn = (*nodes)[node].firstIn;
00230 (*edges)[edge].prevIn = INVALID;
00231 if ((*edges)[edge].nextIn != INVALID) {
00232 (*edges)[(*edges)[edge].nextIn].prevIn = edge;
00233 }
00234 (*nodes)[node].firstIn = edge;
00235 }
00236
00237 typedef False NodeNumTag;
00238 typedef False EdgeNumTag;
00239
00240 protected:
00241 struct NodeT {
00242 Node prev, next;
00243 Edge firstIn, firstOut;
00244 };
00245 class NodesImpl : public Graph::template NodeMap<NodeT> {
00246 friend class SubGraphBase;
00247 public:
00248 typedef typename Graph::template NodeMap<NodeT> Parent;
00249
00250 NodesImpl(SubGraph& _adaptor, const Graph& _graph)
00251 : Parent(_graph), adaptor(_adaptor) {}
00252
00253 virtual ~NodesImpl() {}
00254
00255 virtual void build() {
00256 Parent::build();
00257 Node node;
00258 adaptor.Base::first(node);
00259 while (node != INVALID) {
00260 Parent::operator[](node).prev = node;
00261 Parent::operator[](node).firstIn = INVALID;
00262 Parent::operator[](node).firstOut = INVALID;
00263 adaptor.Base::next(node);
00264 }
00265 }
00266
00267 virtual void clear() {
00268 adaptor.firstNode = INVALID;
00269 Parent::clear();
00270 }
00271
00272 virtual void add(const Node& node) {
00273 Parent::add(node);
00274 Parent::operator[](node).prev = node;
00275 Parent::operator[](node).firstIn = INVALID;
00276 Parent::operator[](node).firstOut = INVALID;
00277 }
00278 virtual void add(const std::vector<Node>& nodes) {
00279 Parent::add(nodes);
00280 for (int i = 0; i < (int)nodes.size(); ++i) {
00281 Parent::operator[](nodes[i]).prev = nodes[i];
00282 Parent::operator[](nodes[i]).firstIn = INVALID;
00283 Parent::operator[](nodes[i]).firstOut = INVALID;
00284 }
00285 }
00286
00287 virtual void erase(const Node& node) {
00288 adaptor.hide(node);
00289 Parent::erase(node);
00290 }
00291
00292 virtual void erase(const std::vector<Node>& nodes) {
00293 for (int i = 0; i < (int)nodes.size(); ++i) {
00294 adaptor.hide(nodes[i]);
00295 }
00296 Parent::erase(nodes);
00297 }
00298
00299 private:
00300 SubGraph& adaptor;
00301 };
00302
00303 struct EdgeT {
00304 Edge prevOut, nextOut;
00305 Edge prevIn, nextIn;
00306 };
00307 class EdgesImpl : public Graph::template EdgeMap<EdgeT> {
00308 friend class SubGraphBase;
00309 public:
00310 typedef typename Graph::template EdgeMap<EdgeT> Parent;
00311
00312 EdgesImpl(SubGraph& _adaptor, const Graph& _graph)
00313 : Parent(_graph), adaptor(_adaptor) {}
00314
00315 virtual ~EdgesImpl() {}
00316
00317 virtual void build() {
00318 Parent::build();
00319 Edge edge;
00320 adaptor.Base::first(edge);
00321 while (edge != INVALID) {
00322 Parent::operator[](edge).prevOut = edge;
00323 adaptor.Base::next(edge);
00324 }
00325 }
00326
00327 virtual void clear() {
00328 Node node;
00329 adaptor.first(node);
00330 while (node != INVALID) {
00331 (*adaptor.nodes).firstIn = INVALID;
00332 (*adaptor.nodes).firstOut = INVALID;
00333 adaptor.next(node);
00334 }
00335 Parent::clear();
00336 }
00337
00338 virtual void add(const Edge& edge) {
00339 Parent::add(edge);
00340 Parent::operator[](edge).prevOut = edge;
00341 }
00342
00343 virtual void add(const std::vector<Edge>& edges) {
00344 Parent::add(edges);
00345 for (int i = 0; i < (int)edges.size(); ++i) {
00346 Parent::operator[](edges[i]).prevOut = edges[i];
00347 }
00348 }
00349
00350 virtual void erase(const Edge& edge) {
00351 adaptor.hide(edge);
00352 Parent::erase(edge);
00353 }
00354
00355 virtual void erase(const std::vector<Edge>& edges) {
00356 for (int i = 0; i < (int)edges.size(); ++i) {
00357 adaptor.hide(edges[i]);
00358 }
00359 Parent::erase(edge);
00360 }
00361
00362 private:
00363 SubGraph& adaptor;
00364 };
00365
00366 NodesImpl* nodes;
00367 EdgesImpl* edges;
00368 Node firstNode;
00369 };
00370
00386 template <typename Graph>
00387 class SubGraph
00388 : public IterableGraphExtender< SubGraphBase<Graph> > {
00389 public:
00390 typedef IterableGraphExtender< SubGraphBase<Graph> > Parent;
00391 public:
00396 SubGraph(const Graph& _graph)
00397 : Parent(), nodes(*this, _graph), edges(*this, _graph) {
00398 Parent::construct(_graph, nodes, edges);
00399 }
00400 private:
00401 typename Parent::NodesImpl nodes;
00402 typename Parent::EdgesImpl edges;
00403 };
00404
00408 template <typename _Graph>
00409 class EdgeSubGraphBase : public GraphAdaptorBase<const _Graph> {
00410 public:
00411 typedef _Graph Graph;
00412 typedef EdgeSubGraphBase<_Graph> SubGraph;
00413 typedef GraphAdaptorBase<const _Graph> Parent;
00414 typedef Parent Base;
00415
00416 typedef typename Parent::Node Node;
00417 typedef typename Parent::Edge Edge;
00418
00419
00420 protected:
00421
00422 class NodesImpl;
00423 class EdgesImpl;
00424
00425 EdgeSubGraphBase() {}
00426
00427 void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) {
00428 Parent::setGraph(_graph);
00429 nodes = &_nodes;
00430 edges = &_edges;
00431
00432 Node node;
00433 Parent::first(node);
00434 while (node != INVALID) {
00435 (*nodes)[node].firstIn = INVALID;
00436 (*nodes)[node].firstOut = INVALID;
00437 Parent::next(node);
00438 }
00439
00440 Edge edge;
00441 Parent::first(edge);
00442 while (edge != INVALID) {
00443 (*edges)[edge].prevOut = edge;
00444 Parent::next(edge);
00445 }
00446 }
00447
00448 public:
00449
00450 void first(Node& node) const {
00451 Parent::first(node);
00452 }
00453 void next(Node& node) const {
00454 Parent::next(node);
00455 }
00456
00457 void first(Edge& edge) const {
00458 Node node;
00459 Parent::first(node);
00460 while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
00461 Parent::next(node);
00462 }
00463 if (node == INVALID) {
00464 edge = INVALID;
00465 } else {
00466 edge = (*nodes)[node].firstOut;
00467 }
00468 }
00469 void next(Edge& edge) const {
00470 if ((*edges)[edge].nextOut != INVALID) {
00471 edge = (*edges)[edge].nextOut;
00472 } else {
00473 Node node = source(edge);
00474 Parent::next(node);
00475 while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
00476 Parent::next(node);
00477 }
00478 if (node == INVALID) {
00479 edge = INVALID;
00480 } else {
00481 edge = (*nodes)[node].firstOut;
00482 }
00483 }
00484 }
00485
00486 void firstOut(Edge& edge, const Node& node) const {
00487 edge = (*nodes)[node].firstOut;
00488 }
00489 void nextOut(Edge& edge) const {
00490 edge = (*edges)[edge].nextOut;
00491 }
00492
00493 void firstIn(Edge& edge, const Node& node) const {
00494 edge = (*nodes)[node].firstIn;
00495 }
00496 void nextIn(Edge& edge) const {
00497 edge = (*edges)[edge].nextIn;
00498 }
00499
00503 bool hidden(const Edge& edge) const {
00504 return (*edges)[edge].prevOut == edge;
00505 }
00506
00511 void hide(const Edge& edge) {
00512 if (hidden(edge)) return;
00513 if ((*edges)[edge].prevOut != INVALID) {
00514 (*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut;
00515 } else {
00516 (*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut;
00517 }
00518 if ((*edges)[edge].nextOut != INVALID) {
00519 (*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut;
00520 }
00521
00522 if ((*edges)[edge].prevIn != INVALID) {
00523 (*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn;
00524 } else {
00525 (*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn;
00526 }
00527 if ((*edges)[edge].nextIn != INVALID) {
00528 (*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn;
00529 }
00530 (*edges)[edge].prevOut = edge;
00531 }
00532
00537 void unHide(const Edge& edge) {
00538 if (!hidden(edge)) return;
00539 Node node;
00540
00541 node = Parent::source(edge);
00542 (*edges)[edge].nextOut = (*nodes)[node].firstOut;
00543 (*edges)[edge].prevOut = INVALID;
00544 if ((*edges)[edge].nextOut != INVALID) {
00545 (*edges)[(*edges)[edge].nextOut].prevOut = edge;
00546 }
00547 (*nodes)[node].firstOut = edge;
00548
00549 node = Parent::target(edge);
00550 (*edges)[edge].nextIn = (*nodes)[node].firstIn;
00551 (*edges)[edge].prevIn = INVALID;
00552 if ((*edges)[edge].nextIn != INVALID) {
00553 (*edges)[(*edges)[edge].nextIn].prevIn = edge;
00554 }
00555 (*nodes)[node].firstIn = edge;
00556 }
00557
00558 protected:
00559 struct NodeT {
00560 Edge firstIn, firstOut;
00561 };
00562 class NodesImpl : public Graph::template NodeMap<NodeT> {
00563 friend class EdgeSubGraphBase;
00564 public:
00565 typedef typename Graph::template NodeMap<NodeT> Parent;
00566
00567 NodesImpl(SubGraph& _adaptor, const Graph& _graph)
00568 : Parent(_graph), adaptor(_adaptor) {}
00569
00570 virtual ~NodesImpl() {}
00571
00572 virtual void build() {
00573 Parent::build();
00574 Node node;
00575 adaptor.Base::first(node);
00576 while (node != INVALID) {
00577 Parent::operator[](node).firstIn = INVALID;
00578 Parent::operator[](node).firstOut = INVALID;
00579 adaptor.Base::next(node);
00580 }
00581 }
00582
00583 virtual void add(const Node& node) {
00584 Parent::add(node);
00585 Parent::operator[](node).firstIn = INVALID;
00586 Parent::operator[](node).firstOut = INVALID;
00587 }
00588
00589 private:
00590 SubGraph& adaptor;
00591 };
00592
00593 struct EdgeT {
00594 Edge prevOut, nextOut;
00595 Edge prevIn, nextIn;
00596 };
00597 class EdgesImpl : public Graph::template EdgeMap<EdgeT> {
00598 friend class EdgeSubGraphBase;
00599 public:
00600 typedef typename Graph::template EdgeMap<EdgeT> Parent;
00601
00602 EdgesImpl(SubGraph& _adaptor, const Graph& _graph)
00603 : Parent(_graph), adaptor(_adaptor) {}
00604
00605 virtual ~EdgesImpl() {}
00606
00607 virtual void build() {
00608 Parent::build();
00609 Edge edge;
00610 adaptor.Base::first(edge);
00611 while (edge != INVALID) {
00612 Parent::operator[](edge).prevOut = edge;
00613 adaptor.Base::next(edge);
00614 }
00615 }
00616
00617 virtual void clear() {
00618 Node node;
00619 adaptor.Base::first(node);
00620 while (node != INVALID) {
00621 (*adaptor.nodes)[node].firstIn = INVALID;
00622 (*adaptor.nodes)[node].firstOut = INVALID;
00623 adaptor.Base::next(node);
00624 }
00625 Parent::clear();
00626 }
00627
00628 virtual void add(const Edge& edge) {
00629 Parent::add(edge);
00630 Parent::operator[](edge).prevOut = edge;
00631 }
00632
00633 virtual void add(const std::vector<Edge>& edges) {
00634 Parent::add(edges);
00635 for (int i = 0; i < (int)edges.size(); ++i) {
00636 Parent::operator[](edges[i]).prevOut = edges[i];
00637 }
00638 }
00639
00640 virtual void erase(const Edge& edge) {
00641 adaptor.hide(edge);
00642 Parent::erase(edge);
00643 }
00644
00645 virtual void erase(const std::vector<Edge>& edges) {
00646 for (int i = 0; i < (int)edges.size(); ++i) {
00647 adaptor.hide(edges[i]);
00648 }
00649 Parent::erase(edge);
00650 }
00651
00652 private:
00653 SubGraph& adaptor;
00654 };
00655
00656 NodesImpl* nodes;
00657 EdgesImpl* edges;
00658 };
00659
00675 template <typename Graph>
00676 class EdgeSubGraph
00677 : public IterableGraphExtender< EdgeSubGraphBase<Graph> > {
00678 public:
00679 typedef IterableGraphExtender< EdgeSubGraphBase<Graph> > Parent;
00680 public:
00685 EdgeSubGraph(const Graph& _graph)
00686 : Parent(), nodes(*this, _graph), edges(*this, _graph) {
00687 Parent::construct(_graph, nodes, edges);
00688 }
00689 private:
00690 typename Parent::NodesImpl nodes;
00691 typename Parent::EdgesImpl edges;
00692 };
00693
00694
00695
00696
00697
00698
00699
00700
00701
00702
00703
00704
00705
00706
00707
00708
00709
00710
00711
00712
00713
00714
00715
00716
00717
00718
00719
00720
00721
00722
00723
00724
00725
00726
00727
00728
00729
00730
00731
00732
00733
00734
00735
00736
00737
00738
00739
00740
00741
00742
00743
00744
00745
00746
00747
00748
00749
00750
00751
00752
00753
00754
00755
00756
00757
00758
00759
00760
00761
00762
00763
00764
00765
00766
00767
00768
00769
00770
00771
00772
00773
00774
00775
00776
00777
00778
00779
00780
00781
00782
00783
00784
00785
00786
00787
00788
00789
00790
00791
00792
00793
00794
00795
00796
00797
00798
00799
00800
00801
00802
00803
00804
00805 }
00806
00807 #endif