Better doc.
2 * lemon/graph_adaptor.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_GRAPH_ADAPTOR_H
18 #define LEMON_GRAPH_ADAPTOR_H
20 ///\ingroup graph_adaptors
22 ///\brief Several graph adaptors.
24 ///This file contains several useful graph adaptor functions.
26 ///\author Marton Makai
28 #include <lemon/invalid.h>
29 #include <lemon/maps.h>
30 #include <lemon/bits/erasable_graph_extender.h>
31 #include <lemon/bits/clearable_graph_extender.h>
32 #include <lemon/bits/extendable_graph_extender.h>
33 #include <lemon/bits/iterable_graph_extender.h>
34 #include <lemon/bits/alteration_notifier.h>
35 #include <lemon/bits/default_map.h>
36 #include <lemon/bits/undir_graph_extender.h>
44 \addtogroup graph_adaptors
49 Base type for the Graph Adaptors
51 \warning Graph adaptors are in even more experimental state than the other
52 parts of the lib. Use them at you own risk.
54 This is the base type for most of LEMON graph adaptors.
55 This class implements a trivial graph adaptor i.e. it only wraps the
56 functions and types of the graph. The purpose of this class is to
57 make easier implementing graph adaptors. E.g. if an adaptor is
58 considered which differs from the wrapped graph only in some of its
59 functions or types, then it can be derived from GraphAdaptor, and only the
60 differences should be implemented.
64 template<typename _Graph>
65 class GraphAdaptorBase {
68 /// \todo Is it needed?
69 typedef Graph BaseGraph;
70 typedef Graph ParentGraph;
74 GraphAdaptorBase() : graph(0) { }
75 void setGraph(Graph& _graph) { graph=&_graph; }
78 GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
80 typedef typename Graph::Node Node;
81 typedef typename Graph::Edge Edge;
83 void first(Node& i) const { graph->first(i); }
84 void first(Edge& i) const { graph->first(i); }
85 void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
86 void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
88 void next(Node& i) const { graph->next(i); }
89 void next(Edge& i) const { graph->next(i); }
90 void nextIn(Edge& i) const { graph->nextIn(i); }
91 void nextOut(Edge& i) const { graph->nextOut(i); }
93 Node source(const Edge& e) const { return graph->source(e); }
94 Node target(const Edge& e) const { return graph->target(e); }
96 int nodeNum() const { return graph->nodeNum(); }
97 int edgeNum() const { return graph->edgeNum(); }
99 Node addNode() const { return Node(graph->addNode()); }
100 Edge addEdge(const Node& source, const Node& target) const {
101 return Edge(graph->addEdge(source, target)); }
103 void erase(const Node& i) const { graph->erase(i); }
104 void erase(const Edge& i) const { graph->erase(i); }
106 void clear() const { graph->clear(); }
108 int id(const Node& v) const { return graph->id(v); }
109 int id(const Edge& e) const { return graph->id(e); }
111 Edge oppositeNode(const Edge& e) const {
112 return Edge(graph->opposite(e));
115 template <typename _Value>
116 class NodeMap : public _Graph::template NodeMap<_Value> {
118 typedef typename _Graph::template NodeMap<_Value> Parent;
119 NodeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
120 NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
121 : Parent(*gw.graph, value) { }
124 template <typename _Value>
125 class EdgeMap : public _Graph::template EdgeMap<_Value> {
127 typedef typename _Graph::template EdgeMap<_Value> Parent;
128 EdgeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
129 EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
130 : Parent(*gw.graph, value) { }
135 template <typename _Graph>
137 public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
139 typedef _Graph Graph;
140 typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
142 GraphAdaptor() : Parent() { }
145 GraphAdaptor(Graph& _graph) { setGraph(_graph); }
148 template <typename _Graph>
149 class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
151 typedef _Graph Graph;
152 typedef GraphAdaptorBase<_Graph> Parent;
154 RevGraphAdaptorBase() : Parent() { }
156 typedef typename Parent::Node Node;
157 typedef typename Parent::Edge Edge;
159 // using Parent::first;
160 void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
161 void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
163 // using Parent::next;
164 void nextIn(Edge& i) const { Parent::nextOut(i); }
165 void nextOut(Edge& i) const { Parent::nextIn(i); }
167 Node source(const Edge& e) const { return Parent::target(e); }
168 Node target(const Edge& e) const { return Parent::source(e); }
172 /// A graph adaptor which reverses the orientation of the edges.
174 ///\warning Graph adaptors are in even more experimental state than the other
175 ///parts of the lib. Use them at you own risk.
177 /// Let \f$G=(V, A)\f$ be a directed graph and
178 /// suppose that a graph instange \c g of type
179 /// \c ListGraph implements \f$G\f$.
183 /// For each directed edge
184 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
185 /// reversing its orientation.
186 /// Then RevGraphAdaptor implements the graph structure with node-set
187 /// \f$V\f$ and edge-set
188 /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
189 /// reversing the orientation of its edges. The following code shows how
190 /// such an instance can be constructed.
192 /// RevGraphAdaptor<ListGraph> gw(g);
194 ///\author Marton Makai
195 template<typename _Graph>
196 class RevGraphAdaptor :
197 public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
199 typedef _Graph Graph;
200 typedef IterableGraphExtender<
201 RevGraphAdaptorBase<_Graph> > Parent;
203 RevGraphAdaptor() { }
205 RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
209 template <typename _Graph, typename NodeFilterMap,
210 typename EdgeFilterMap, bool checked = true>
211 class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
213 typedef _Graph Graph;
214 typedef GraphAdaptorBase<_Graph> Parent;
216 NodeFilterMap* node_filter_map;
217 EdgeFilterMap* edge_filter_map;
218 SubGraphAdaptorBase() : Parent(),
219 node_filter_map(0), edge_filter_map(0) { }
221 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
222 node_filter_map=&_node_filter_map;
224 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
225 edge_filter_map=&_edge_filter_map;
230 typedef typename Parent::Node Node;
231 typedef typename Parent::Edge Edge;
233 void first(Node& i) const {
235 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
238 void first(Edge& i) const {
240 while (i!=INVALID && (!(*edge_filter_map)[i]
241 || !(*node_filter_map)[Parent::source(i)]
242 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
245 void firstIn(Edge& i, const Node& n) const {
246 Parent::firstIn(i, n);
247 while (i!=INVALID && (!(*edge_filter_map)[i]
248 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
251 void firstOut(Edge& i, const Node& n) const {
252 Parent::firstOut(i, n);
253 while (i!=INVALID && (!(*edge_filter_map)[i]
254 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
257 void next(Node& i) const {
259 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
262 void next(Edge& i) const {
264 while (i!=INVALID && (!(*edge_filter_map)[i]
265 || !(*node_filter_map)[Parent::source(i)]
266 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
269 void nextIn(Edge& i) const {
271 while (i!=INVALID && (!(*edge_filter_map)[i]
272 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
275 void nextOut(Edge& i) const {
277 while (i!=INVALID && (!(*edge_filter_map)[i]
278 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
281 /// This function hides \c n in the graph, i.e. the iteration
282 /// jumps over it. This is done by simply setting the value of \c n
283 /// to be false in the corresponding node-map.
284 void hide(const Node& n) const { node_filter_map->set(n, false); }
286 /// This function hides \c e in the graph, i.e. the iteration
287 /// jumps over it. This is done by simply setting the value of \c e
288 /// to be false in the corresponding edge-map.
289 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
291 /// The value of \c n is set to be true in the node-map which stores
292 /// hide information. If \c n was hidden previuosly, then it is shown
294 void unHide(const Node& n) const { node_filter_map->set(n, true); }
296 /// The value of \c e is set to be true in the edge-map which stores
297 /// hide information. If \c e was hidden previuosly, then it is shown
299 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
301 /// Returns true if \c n is hidden.
302 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
304 /// Returns true if \c n is hidden.
305 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
307 /// \warning This is a linear time operation and works only if s
308 /// \c Graph::NodeIt is defined.
309 /// \todo assign tags.
310 int nodeNum() const {
313 for (first(n); n!=INVALID; next(n)) ++i;
317 /// \warning This is a linear time operation and works only if
318 /// \c Graph::EdgeIt is defined.
319 /// \todo assign tags.
320 int edgeNum() const {
323 for (first(e); e!=INVALID; next(e)) ++i;
328 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
329 class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
330 : public GraphAdaptorBase<_Graph> {
332 typedef _Graph Graph;
333 typedef GraphAdaptorBase<_Graph> Parent;
335 NodeFilterMap* node_filter_map;
336 EdgeFilterMap* edge_filter_map;
337 SubGraphAdaptorBase() : Parent(),
338 node_filter_map(0), edge_filter_map(0) { }
340 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
341 node_filter_map=&_node_filter_map;
343 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
344 edge_filter_map=&_edge_filter_map;
349 typedef typename Parent::Node Node;
350 typedef typename Parent::Edge Edge;
352 void first(Node& i) const {
354 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
357 void first(Edge& i) const {
359 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
362 void firstIn(Edge& i, const Node& n) const {
363 Parent::firstIn(i, n);
364 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
367 void firstOut(Edge& i, const Node& n) const {
368 Parent::firstOut(i, n);
369 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
372 void next(Node& i) const {
374 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
376 void next(Edge& i) const {
378 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
380 void nextIn(Edge& i) const {
382 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
385 void nextOut(Edge& i) const {
387 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
390 /// This function hides \c n in the graph, i.e. the iteration
391 /// jumps over it. This is done by simply setting the value of \c n
392 /// to be false in the corresponding node-map.
393 void hide(const Node& n) const { node_filter_map->set(n, false); }
395 /// This function hides \c e in the graph, i.e. the iteration
396 /// jumps over it. This is done by simply setting the value of \c e
397 /// to be false in the corresponding edge-map.
398 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
400 /// The value of \c n is set to be true in the node-map which stores
401 /// hide information. If \c n was hidden previuosly, then it is shown
403 void unHide(const Node& n) const { node_filter_map->set(n, true); }
405 /// The value of \c e is set to be true in the edge-map which stores
406 /// hide information. If \c e was hidden previuosly, then it is shown
408 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
410 /// Returns true if \c n is hidden.
411 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
413 /// Returns true if \c n is hidden.
414 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
416 /// \warning This is a linear time operation and works only if s
417 /// \c Graph::NodeIt is defined.
418 /// \todo assign tags.
419 int nodeNum() const {
422 for (first(n); n!=INVALID; next(n)) ++i;
426 /// \warning This is a linear time operation and works only if
427 /// \c Graph::EdgeIt is defined.
428 /// \todo assign tags.
429 int edgeNum() const {
432 for (first(e); e!=INVALID; next(e)) ++i;
437 /*! \brief A graph adaptor for hiding nodes and edges from a graph.
439 \warning Graph adaptors are in even more experimental state than the other
440 parts of the lib. Use them at you own risk.
442 SubGraphAdaptor shows the graph with filtered node-set and
444 Let \f$G=(V, A)\f$ be a directed graph
445 and suppose that the graph instance \c g of type ListGraph implements
447 Let moreover \f$b_V\f$ and
448 \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
449 SubGraphAdaptor<...>::NodeIt iterates
450 on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
451 SubGraphAdaptor<...>::EdgeIt iterates
452 on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
453 SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
454 only on edges leaving and entering a specific node which have true value.
456 We have to note that this does not mean that an
457 induced subgraph is obtained, the node-iterator cares only the filter
458 on the node-set, and the edge-iterators care only the filter on the
461 typedef ListGraph Graph;
463 typedef Graph::Node Node;
464 typedef Graph::Edge Edge;
465 Node u=g.addNode(); //node of id 0
466 Node v=g.addNode(); //node of id 1
467 Node e=g.addEdge(u, v); //edge of id 0
468 Node f=g.addEdge(v, u); //edge of id 1
469 Graph::NodeMap<bool> nm(g, true);
471 Graph::EdgeMap<bool> em(g, true);
473 typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
475 for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
476 std::cout << ":-)" << std::endl;
477 for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
479 The output of the above code is the following.
485 Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
486 \c Graph::Node that is why \c g.id(n) can be applied.
488 For other examples see also the documentation of NodeSubGraphAdaptor and
493 template<typename _Graph, typename NodeFilterMap,
494 typename EdgeFilterMap, bool checked = true>
495 class SubGraphAdaptor :
496 public IterableGraphExtender<
497 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
499 typedef _Graph Graph;
500 typedef IterableGraphExtender<
501 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
503 SubGraphAdaptor() { }
505 SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
506 EdgeFilterMap& _edge_filter_map) {
508 setNodeFilterMap(_node_filter_map);
509 setEdgeFilterMap(_edge_filter_map);
515 /*! \brief An adaptor for hiding nodes from a graph.
517 \warning Graph adaptors are in even more experimental state than the other
518 parts of the lib. Use them at you own risk.
520 An adaptor for hiding nodes from a graph.
521 This adaptor specializes SubGraphAdaptor in the way that only the node-set
522 can be filtered. Note that this does not mean of considering induced
523 subgraph, the edge-iterators consider the original edge-set.
526 template<typename Graph, typename NodeFilterMap, bool checked = true>
527 class NodeSubGraphAdaptor :
528 public SubGraphAdaptor<Graph, NodeFilterMap,
529 ConstMap<typename Graph::Edge,bool>, checked> {
531 typedef SubGraphAdaptor<Graph, NodeFilterMap,
532 ConstMap<typename Graph::Edge,bool> > Parent;
534 ConstMap<typename Graph::Edge, bool> const_true_map;
536 NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
537 Parent(), const_true_map(true) {
538 Parent::setGraph(_graph);
539 Parent::setNodeFilterMap(_node_filter_map);
540 Parent::setEdgeFilterMap(const_true_map);
545 /*! \brief An adaptor for hiding edges from a graph.
547 \warning Graph adaptors are in even more experimental state than the other
548 parts of the lib. Use them at you own risk.
550 An adaptor for hiding edges from a graph.
551 This adaptor specializes SubGraphAdaptor in the way that only the edge-set
552 can be filtered. The usefulness of this adaptor is demonstrated in the
553 problem of searching a maximum number of edge-disjoint shortest paths
555 two nodes \c s and \c t. Shortest here means being shortest w.r.t.
556 non-negative edge-lengths. Note that
557 the comprehension of the presented solution
558 need's some elementary knowledge from combinatorial optimization.
560 If a single shortest path is to be
561 searched between \c s and \c t, then this can be done easily by
562 applying the Dijkstra algorithm. What happens, if a maximum number of
563 edge-disjoint shortest paths is to be computed. It can be proved that an
564 edge can be in a shortest path if and only if it is tight with respect to
565 the potential function computed by Dijkstra. Moreover, any path containing
566 only such edges is a shortest one. Thus we have to compute a maximum number
567 of edge-disjoint paths between \c s and \c t in the graph which has edge-set
568 all the tight edges. The computation will be demonstrated on the following
569 graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
570 The full source code is available in \ref sub_graph_adaptor_demo.cc.
571 If you are interested in more demo programs, you can use
572 \ref dim_to_dot.cc to generate .dot files from dimacs files.
573 The .dot file of the following figure was generated by
574 the demo program \ref dim_to_dot.cc.
577 digraph lemon_dot_example {
578 node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
579 n0 [ label="0 (s)" ];
585 n6 [ label="6 (t)" ];
586 edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
587 n5 -> n6 [ label="9, length:4" ];
588 n4 -> n6 [ label="8, length:2" ];
589 n3 -> n5 [ label="7, length:1" ];
590 n2 -> n5 [ label="6, length:3" ];
591 n2 -> n6 [ label="5, length:5" ];
592 n2 -> n4 [ label="4, length:2" ];
593 n1 -> n4 [ label="3, length:3" ];
594 n0 -> n3 [ label="2, length:1" ];
595 n0 -> n2 [ label="1, length:2" ];
596 n0 -> n1 [ label="0, length:3" ];
605 readDimacs(std::cin, g, length, s, t);
607 cout << "edges with lengths (of form id, source--length->target): " << endl;
608 for(EdgeIt e(g); e!=INVALID; ++e)
609 cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
610 << length[e] << "->" << g.id(g.target(e)) << endl;
612 cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
614 Next, the potential function is computed with Dijkstra.
616 typedef Dijkstra<Graph, LengthMap> Dijkstra;
617 Dijkstra dijkstra(g, length);
620 Next, we consrtruct a map which filters the edge-set to the tight edges.
622 typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
624 TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
626 typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
627 SubGW gw(g, tight_edge_filter);
629 Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
630 with a max flow algorithm Preflow.
632 ConstMap<Edge, int> const_1_map(1);
633 Graph::EdgeMap<int> flow(g, 0);
635 Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
636 preflow(gw, s, t, const_1_map, flow);
641 cout << "maximum number of edge-disjoint shortest path: "
642 << preflow.flowValue() << endl;
643 cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
645 for(EdgeIt e(g); e!=INVALID; ++e)
647 cout << " " << g.id(g.source(e)) << "--"
648 << length[e] << "->" << g.id(g.target(e)) << endl;
650 The program has the following (expected :-)) output:
652 edges with lengths (of form id, source--length->target):
664 maximum number of edge-disjoint shortest path: 2
665 edges of the maximum number of edge-disjoint shortest s-t paths:
676 template<typename Graph, typename EdgeFilterMap>
677 class EdgeSubGraphAdaptor :
678 public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
679 EdgeFilterMap, false> {
681 typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
682 EdgeFilterMap> Parent;
684 ConstMap<typename Graph::Node, bool> const_true_map;
686 EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
687 Parent(), const_true_map(true) {
688 Parent::setGraph(_graph);
689 Parent::setNodeFilterMap(const_true_map);
690 Parent::setEdgeFilterMap(_edge_filter_map);
694 template <typename _Graph>
695 class UndirGraphAdaptorBase :
696 public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
698 typedef _Graph Graph;
699 typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
701 UndirGraphAdaptorBase() : Parent() { }
703 typedef typename Parent::UndirEdge UndirEdge;
704 typedef typename Parent::Edge Edge;
706 /// \bug Why cant an edge say that it is forward or not???
707 /// By this, a pointer to the graph have to be stored
708 /// The implementation
709 template <typename T>
712 const UndirGraphAdaptorBase<_Graph>* g;
713 template <typename TT> friend class EdgeMap;
714 typename _Graph::template EdgeMap<T> forward_map, backward_map;
719 EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
720 forward_map(*(g->graph)), backward_map(*(g->graph)) { }
722 EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
723 forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
725 void set(Edge e, T a) {
727 forward_map.set(e, a);
729 backward_map.set(e, a);
732 T operator[](Edge e) const {
734 return forward_map[e];
736 return backward_map[e];
740 template <typename T>
742 template <typename TT> friend class UndirEdgeMap;
743 typename _Graph::template EdgeMap<T> map;
746 typedef UndirEdge Key;
748 UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
751 UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
752 map(*(g.graph), a) { }
754 void set(UndirEdge e, T a) {
758 T operator[](UndirEdge e) const {
765 /// \brief An undirected graph is made from a directed graph by an adaptor
767 /// Undocumented, untested!!!
768 /// If somebody knows nice demo application, let's polulate it.
770 /// \author Marton Makai
771 template<typename _Graph>
772 class UndirGraphAdaptor :
773 public IterableUndirGraphExtender<
774 UndirGraphAdaptorBase<_Graph> > {
776 typedef _Graph Graph;
777 typedef IterableUndirGraphExtender<
778 UndirGraphAdaptorBase<_Graph> > Parent;
780 UndirGraphAdaptor() { }
782 UndirGraphAdaptor(_Graph& _graph) {
788 template <typename _Graph,
789 typename ForwardFilterMap, typename BackwardFilterMap>
790 class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
792 typedef _Graph Graph;
793 typedef GraphAdaptorBase<_Graph> Parent;
795 ForwardFilterMap* forward_filter;
796 BackwardFilterMap* backward_filter;
797 SubBidirGraphAdaptorBase() : Parent(),
798 forward_filter(0), backward_filter(0) { }
800 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
801 forward_filter=&_forward_filter;
803 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
804 backward_filter=&_backward_filter;
808 // SubGraphAdaptorBase(Graph& _graph,
809 // NodeFilterMap& _node_filter_map,
810 // EdgeFilterMap& _edge_filter_map) :
812 // node_filter_map(&node_filter_map),
813 // edge_filter_map(&edge_filter_map) { }
815 typedef typename Parent::Node Node;
816 typedef typename _Graph::Edge GraphEdge;
817 template <typename T> class EdgeMap;
818 /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
819 /// _Graph::Edge. It contains an extra bool flag which is true
820 /// if and only if the
821 /// edge is the backward version of the original edge.
822 class Edge : public _Graph::Edge {
823 friend class SubBidirGraphAdaptorBase<
824 Graph, ForwardFilterMap, BackwardFilterMap>;
825 template<typename T> friend class EdgeMap;
827 bool backward; //true, iff backward
830 /// \todo =false is needed, or causes problems?
831 /// If \c _backward is false, then we get an edge corresponding to the
832 /// original one, otherwise its oppositely directed pair is obtained.
833 Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
834 _Graph::Edge(e), backward(_backward) { }
835 Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
836 bool operator==(const Edge& v) const {
837 return (this->backward==v.backward &&
838 static_cast<typename _Graph::Edge>(*this)==
839 static_cast<typename _Graph::Edge>(v));
841 bool operator!=(const Edge& v) const {
842 return (this->backward!=v.backward ||
843 static_cast<typename _Graph::Edge>(*this)!=
844 static_cast<typename _Graph::Edge>(v));
848 void first(Node& i) const {
852 void first(Edge& i) const {
855 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
856 !(*forward_filter)[i]) Parent::next(i);
857 if (*static_cast<GraphEdge*>(&i)==INVALID) {
860 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
861 !(*backward_filter)[i]) Parent::next(i);
865 void firstIn(Edge& i, const Node& n) const {
866 Parent::firstIn(i, n);
868 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
869 !(*forward_filter)[i]) Parent::nextIn(i);
870 if (*static_cast<GraphEdge*>(&i)==INVALID) {
871 Parent::firstOut(i, n);
873 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
874 !(*backward_filter)[i]) Parent::nextOut(i);
878 void firstOut(Edge& i, const Node& n) const {
879 Parent::firstOut(i, n);
881 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
882 !(*forward_filter)[i]) Parent::nextOut(i);
883 if (*static_cast<GraphEdge*>(&i)==INVALID) {
884 Parent::firstIn(i, n);
886 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
887 !(*backward_filter)[i]) Parent::nextIn(i);
891 void next(Node& i) const {
895 void next(Edge& i) const {
898 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
899 !(*forward_filter)[i]) Parent::next(i);
900 if (*static_cast<GraphEdge*>(&i)==INVALID) {
903 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
904 !(*backward_filter)[i]) Parent::next(i);
908 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
909 !(*backward_filter)[i]) Parent::next(i);
913 void nextIn(Edge& i) const {
915 Node n=Parent::target(i);
917 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
918 !(*forward_filter)[i]) Parent::nextIn(i);
919 if (*static_cast<GraphEdge*>(&i)==INVALID) {
920 Parent::firstOut(i, n);
922 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
923 !(*backward_filter)[i]) Parent::nextOut(i);
927 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
928 !(*backward_filter)[i]) Parent::nextOut(i);
932 void nextOut(Edge& i) const {
934 Node n=Parent::source(i);
936 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
937 !(*forward_filter)[i]) Parent::nextOut(i);
938 if (*static_cast<GraphEdge*>(&i)==INVALID) {
939 Parent::firstIn(i, n);
941 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
942 !(*backward_filter)[i]) Parent::nextIn(i);
946 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
947 !(*backward_filter)[i]) Parent::nextIn(i);
951 Node source(Edge e) const {
952 return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
953 Node target(Edge e) const {
954 return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
956 /// Gives back the opposite edge.
957 Edge opposite(const Edge& e) const {
959 f.backward=!f.backward;
963 /// \warning This is a linear time operation and works only if
964 /// \c Graph::EdgeIt is defined.
966 int edgeNum() const {
969 for (first(e); e!=INVALID; next(e)) ++i;
973 bool forward(const Edge& e) const { return !e.backward; }
974 bool backward(const Edge& e) const { return e.backward; }
976 template <typename T>
977 /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
978 /// _Graph::EdgeMap one for the forward edges and
979 /// one for the backward edges.
981 template <typename TT> friend class EdgeMap;
982 typename _Graph::template EdgeMap<T> forward_map, backward_map;
987 EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
988 ForwardFilterMap, BackwardFilterMap>& g) :
989 forward_map(*(g.graph)), backward_map(*(g.graph)) { }
991 EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
992 ForwardFilterMap, BackwardFilterMap>& g, T a) :
993 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
995 void set(Edge e, T a) {
997 forward_map.set(e, a);
999 backward_map.set(e, a);
1002 // typename _Graph::template EdgeMap<T>::ConstReference
1003 // operator[](Edge e) const {
1005 // return forward_map[e];
1007 // return backward_map[e];
1010 // typename _Graph::template EdgeMap<T>::Reference
1011 T operator[](Edge e) const {
1013 return forward_map[e];
1015 return backward_map[e];
1019 forward_map.update();
1020 backward_map.update();
1027 ///\brief An adaptor for composing a subgraph of a
1028 /// bidirected graph made from a directed one.
1030 /// An adaptor for composing a subgraph of a
1031 /// bidirected graph made from a directed one.
1033 ///\warning Graph adaptors are in even more experimental state than the other
1034 ///parts of the lib. Use them at you own risk.
1036 /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
1037 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
1038 /// reversing its orientation. We are given moreover two bool valued
1039 /// maps on the edge-set,
1040 /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
1041 /// SubBidirGraphAdaptor implements the graph structure with node-set
1042 /// \f$V\f$ and edge-set
1043 /// \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$.
1044 /// The purpose of writing + instead of union is because parallel
1045 /// edges can arise. (Similarly, antiparallel edges also can arise).
1046 /// In other words, a subgraph of the bidirected graph obtained, which
1047 /// is given by orienting the edges of the original graph in both directions.
1048 /// As the oppositely directed edges are logically different,
1049 /// the maps are able to attach different values for them.
1051 /// An example for such a construction is \c RevGraphAdaptor where the
1052 /// forward_filter is everywhere false and the backward_filter is
1053 /// everywhere true. We note that for sake of efficiency,
1054 /// \c RevGraphAdaptor is implemented in a different way.
1055 /// But BidirGraphAdaptor is obtained from
1056 /// SubBidirGraphAdaptor by considering everywhere true
1057 /// valued maps both for forward_filter and backward_filter.
1059 /// The most important application of SubBidirGraphAdaptor
1060 /// is ResGraphAdaptor, which stands for the residual graph in directed
1061 /// flow and circulation problems.
1062 /// As adaptors usually, the SubBidirGraphAdaptor implements the
1063 /// above mentioned graph structure without its physical storage,
1064 /// that is the whole stuff is stored in constant memory.
1065 template<typename _Graph,
1066 typename ForwardFilterMap, typename BackwardFilterMap>
1067 class SubBidirGraphAdaptor :
1068 public IterableGraphExtender<
1069 SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
1071 typedef _Graph Graph;
1072 typedef IterableGraphExtender<
1073 SubBidirGraphAdaptorBase<
1074 _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
1076 SubBidirGraphAdaptor() { }
1078 SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
1079 BackwardFilterMap& _backward_filter) {
1081 setForwardFilterMap(_forward_filter);
1082 setBackwardFilterMap(_backward_filter);
1088 ///\brief An adaptor for composing bidirected graph from a directed one.
1090 ///\warning Graph adaptors are in even more experimental state than the other
1091 ///parts of the lib. Use them at you own risk.
1093 /// An adaptor for composing bidirected graph from a directed one.
1094 /// A bidirected graph is composed over the directed one without physical
1095 /// storage. As the oppositely directed edges are logically different ones
1096 /// the maps are able to attach different values for them.
1097 template<typename Graph>
1098 class BidirGraphAdaptor :
1099 public SubBidirGraphAdaptor<
1101 ConstMap<typename Graph::Edge, bool>,
1102 ConstMap<typename Graph::Edge, bool> > {
1104 typedef SubBidirGraphAdaptor<
1106 ConstMap<typename Graph::Edge, bool>,
1107 ConstMap<typename Graph::Edge, bool> > Parent;
1109 ConstMap<typename Graph::Edge, bool> cm;
1111 BidirGraphAdaptor() : Parent(), cm(true) {
1112 Parent::setForwardFilterMap(cm);
1113 Parent::setBackwardFilterMap(cm);
1116 BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
1117 Parent::setGraph(_graph);
1118 Parent::setForwardFilterMap(cm);
1119 Parent::setBackwardFilterMap(cm);
1122 int edgeNum() const {
1123 return 2*this->graph->edgeNum();
1125 // KEEP_MAPS(Parent, BidirGraphAdaptor);
1129 template<typename Graph, typename Number,
1130 typename CapacityMap, typename FlowMap>
1131 class ResForwardFilter {
1132 // const Graph* graph;
1133 const CapacityMap* capacity;
1134 const FlowMap* flow;
1136 ResForwardFilter(/*const Graph& _graph, */
1137 const CapacityMap& _capacity, const FlowMap& _flow) :
1138 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1139 ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1140 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1141 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1142 bool operator[](const typename Graph::Edge& e) const {
1143 return (Number((*flow)[e]) < Number((*capacity)[e]));
1147 template<typename Graph, typename Number,
1148 typename CapacityMap, typename FlowMap>
1149 class ResBackwardFilter {
1150 const CapacityMap* capacity;
1151 const FlowMap* flow;
1153 ResBackwardFilter(/*const Graph& _graph,*/
1154 const CapacityMap& _capacity, const FlowMap& _flow) :
1155 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1156 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1157 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1158 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1159 bool operator[](const typename Graph::Edge& e) const {
1160 return (Number(0) < Number((*flow)[e]));
1165 /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
1167 An adaptor for composing the residual graph for directed flow and circulation problems.
1168 Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
1169 number type. Let moreover
1170 \f$f,c:A\to F\f$, be functions on the edge-set.
1171 In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
1172 and \f$c\f$ for a capacity function.
1173 Suppose that a graph instange \c g of type
1174 \c ListGraph implements \f$G\f$.
1178 Then RevGraphAdaptor implements the graph structure with node-set
1179 \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
1180 \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
1181 \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
1182 i.e. the so called residual graph.
1183 When we take the union \f$A_{forward}\cup A_{backward}\f$,
1184 multilicities are counted, i.e. if an edge is in both
1185 \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
1187 The following code shows how
1188 such an instance can be constructed.
1190 typedef ListGraph Graph;
1191 Graph::EdgeMap<int> f(g);
1192 Graph::EdgeMap<int> c(g);
1193 ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
1195 \author Marton Makai
1197 template<typename Graph, typename Number,
1198 typename CapacityMap, typename FlowMap>
1199 class ResGraphAdaptor :
1200 public SubBidirGraphAdaptor<
1202 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1203 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1205 typedef SubBidirGraphAdaptor<
1207 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1208 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1210 const CapacityMap* capacity;
1212 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1213 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1214 ResGraphAdaptor() : Parent(),
1215 capacity(0), flow(0) { }
1216 void setCapacityMap(const CapacityMap& _capacity) {
1217 capacity=&_capacity;
1218 forward_filter.setCapacity(_capacity);
1219 backward_filter.setCapacity(_capacity);
1221 void setFlowMap(FlowMap& _flow) {
1223 forward_filter.setFlow(_flow);
1224 backward_filter.setFlow(_flow);
1227 ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
1229 Parent(), capacity(&_capacity), flow(&_flow),
1230 forward_filter(/*_graph,*/ _capacity, _flow),
1231 backward_filter(/*_graph,*/ _capacity, _flow) {
1232 Parent::setGraph(_graph);
1233 Parent::setForwardFilterMap(forward_filter);
1234 Parent::setBackwardFilterMap(backward_filter);
1237 typedef typename Parent::Edge Edge;
1239 void augment(const Edge& e, Number a) const {
1240 if (Parent::forward(e))
1241 flow->set(e, (*flow)[e]+a);
1243 flow->set(e, (*flow)[e]-a);
1246 /// \brief Residual capacity map.
1248 /// In generic residual graphs the residual capacity can be obtained
1252 const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
1254 typedef Number Value;
1256 ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
1257 _res_graph) : res_graph(&_res_graph) { }
1258 Number operator[](const Edge& e) const {
1259 if (res_graph->forward(e))
1260 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1262 return (*(res_graph->flow))[e];
1266 // KEEP_MAPS(Parent, ResGraphAdaptor);
1271 template <typename _Graph, typename FirstOutEdgesMap>
1272 class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1274 typedef _Graph Graph;
1275 typedef GraphAdaptorBase<_Graph> Parent;
1277 FirstOutEdgesMap* first_out_edges;
1278 ErasingFirstGraphAdaptorBase() : Parent(),
1279 first_out_edges(0) { }
1281 void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1282 first_out_edges=&_first_out_edges;
1287 typedef typename Parent::Node Node;
1288 typedef typename Parent::Edge Edge;
1290 void firstOut(Edge& i, const Node& n) const {
1291 i=(*first_out_edges)[n];
1294 void erase(const Edge& e) const {
1298 first_out_edges->set(n, f);
1303 /// For blocking flows.
1305 ///\warning Graph adaptors are in even more experimental state than the other
1306 ///parts of the lib. Use them at you own risk.
1308 /// This graph adaptor is used for on-the-fly
1309 /// Dinits blocking flow computations.
1310 /// For each node, an out-edge is stored which is used when the
1312 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1316 /// \author Marton Makai
1317 template <typename _Graph, typename FirstOutEdgesMap>
1318 class ErasingFirstGraphAdaptor :
1319 public IterableGraphExtender<
1320 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
1322 typedef _Graph Graph;
1323 typedef IterableGraphExtender<
1324 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1325 ErasingFirstGraphAdaptor(Graph& _graph,
1326 FirstOutEdgesMap& _first_out_edges) {
1328 setFirstOutEdgesMap(_first_out_edges);
1333 template <typename _Graph>
1334 class NewEdgeSetAdaptorBase {
1337 typedef _Graph Graph;
1338 typedef typename Graph::Node Node;
1339 typedef typename Graph::NodeIt NodeIt;
1344 int first_out, first_in;
1345 NodeT() : first_out(-1), first_in(-1) {}
1348 class NodesImpl : protected Graph::template NodeMap<NodeT> {
1350 typedef typename Graph::template NodeMap<NodeT> Parent;
1351 typedef NewEdgeSetAdaptorBase<Graph> Adaptor;
1357 NodesImpl(Adaptor& _adaptor, const Graph& _graph)
1358 : Parent(_graph), adaptor(_adaptor) {}
1360 virtual ~NodesImpl() {}
1362 virtual void build() {
1366 virtual void clear() {
1371 virtual void add(const Node& node) {
1376 virtual void erase(const Node& node) {
1377 adaptor._erase(node);
1378 Parent::erase(node);
1381 NodeT& operator[](const Node& node) {
1382 return Parent::operator[](node);
1385 const NodeT& operator[](const Node& node) const {
1386 return Parent::operator[](node);
1394 Node source, target;
1395 int next_out, next_in;
1396 int prev_out, prev_in;
1397 EdgeT() : prev_out(-1), prev_in(-1) {}
1400 std::vector<EdgeT> edges;
1403 int first_free_edge;
1405 virtual void _clear() = 0;
1406 virtual void _add(const Node& node) = 0;
1407 virtual void _erase(const Node& node) = 0;
1411 void initalize(const Graph& _graph, NodesImpl& _nodes) {
1419 friend class NewEdgeSetAdaptorBase<Graph>;
1421 Edge(int _id) : id(_id) {}
1425 Edge(Invalid) : id(-1) {}
1426 bool operator==(const Edge& edge) const { return id == edge.id; }
1427 bool operator!=(const Edge& edge) const { return id != edge.id; }
1428 bool operator<(const Edge& edge) const { return id < edge.id; }
1431 NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {}
1432 virtual ~NewEdgeSetAdaptorBase() {}
1434 Edge addEdge(const Node& source, const Node& target) {
1436 if (first_free_edge == -1) {
1438 edges.push_back(EdgeT());
1440 n = first_free_edge;
1441 first_free_edge = edges[first_free_edge].next_in;
1443 edges[n].next_in = (*nodes)[target].first_in;
1444 (*nodes)[target].first_in = n;
1445 edges[n].next_out = (*nodes)[source].first_out;
1446 (*nodes)[source].first_out = n;
1447 edges[n].source = source;
1448 edges[n].target = target;
1452 void erase(const Edge& edge) {
1454 if (edges[n].prev_in != -1) {
1455 edges[edges[n].prev_in].next_in = edges[n].next_in;
1457 (*nodes)[edges[n].target].first_in = edges[n].next_in;
1459 if (edges[n].next_in != -1) {
1460 edges[edges[n].next_in].prev_in = edges[n].prev_in;
1463 if (edges[n].prev_out != -1) {
1464 edges[edges[n].prev_out].next_out = edges[n].next_out;
1466 (*nodes)[edges[n].source].first_out = edges[n].next_out;
1468 if (edges[n].next_out != -1) {
1469 edges[edges[n].next_out].prev_out = edges[n].prev_out;
1474 void first(Node& node) const {
1478 void next(Node& node) const {
1482 void first(Edge& edge) const {
1484 for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
1486 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1489 void next(Edge& edge) const {
1490 if (edges[edge.id].next_in != -1) {
1491 edge.id = edges[edge.id].next_in;
1493 Node node = edges[edge.id].target;
1494 for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
1496 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1500 void firstOut(Edge& edge, const Node& node) const {
1501 edge.id = (*nodes)[node].first_out;
1504 void nextOut(Edge& edge) const {
1505 edge.id = edges[edge.id].next_out;
1508 void firstIn(Edge& edge, const Node& node) const {
1509 edge.id = (*nodes)[node].first_in;
1512 void nextIn(Edge& edge) const {
1513 edge.id = edges[edge.id].next_in;
1516 int id(const Node& node) const { return graph->id(node); }
1517 int id(const Edge& edge) const { return edge.id; }
1519 Node fromId(int id, Node) const { return graph->fromId(id, Node()); }
1520 Edge fromId(int id, Edge) const { return Edge(id); }
1522 int maxId(Node) const { return graph->maxId(Node()); };
1523 int maxId(Edge) const { return edges.size() - 1; }
1525 Node source(const Edge& edge) const { return edges[edge.id].source;}
1526 Node target(const Edge& edge) const { return edges[edge.id].target;}
1531 /// \brief Graph adaptor using a node set of another graph and an
1534 /// This structure can be used to establish another graph over a node set
1535 /// of an existing one. The node iterator will go through the nodes of the
1538 /// \param _Graph The type of the graph which shares its node set with
1539 /// this class. Its interface must conform to the \ref concept::StaticGraph
1540 /// "StaticGraph" concept.
1542 /// In the edge extension and removing it conforms to the
1543 /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
1544 template <typename _Graph>
1545 class NewEdgeSetAdaptor :
1546 public ErasableGraphExtender<
1547 ClearableGraphExtender<
1548 ExtendableGraphExtender<
1549 MappableGraphExtender<
1550 IterableGraphExtender<
1551 AlterableGraphExtender<
1552 NewEdgeSetAdaptorBase<_Graph> > > > > > > {
1556 typedef ErasableGraphExtender<
1557 ClearableGraphExtender<
1558 ExtendableGraphExtender<
1559 MappableGraphExtender<
1560 IterableGraphExtender<
1561 AlterableGraphExtender<
1562 NewEdgeSetAdaptorBase<_Graph> > > > > > > Parent;
1565 typedef typename Parent::Node Node;
1566 typedef typename Parent::Edge Edge;
1570 virtual void _clear() {
1571 Parent::edges.clear();
1572 Parent::first_edge = -1;
1573 Parent::first_free_edge = -1;
1574 Parent::getNotifier(Edge()).clear();
1575 Parent::getNotifier(Node()).clear();
1578 virtual void _add(const Node& node) {
1579 Parent::getNotifier(Node()).add(node);
1582 virtual void _erase(const Node& node) {
1584 Parent::firstOut(edge, node);
1585 while (edge != INVALID) {
1586 Parent::erase(edge);
1587 Parent::firstOut(edge, node);
1590 Parent::firstIn(edge, node);
1591 while (edge != INVALID) {
1592 Parent::erase(edge);
1593 Parent::firstIn(edge, node);
1596 Parent::getNotifier(Node()).erase(node);
1600 typedef typename Parent::NodesImpl NodesImpl;
1606 /// \brief Constructor of the adaptor.
1608 /// Constructor of the adaptor.
1609 NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
1610 Parent::initalize(_graph, nodes);
1614 Parent::getNotifier(Edge()).clear();
1616 Parent::edges.clear();
1617 Parent::first_edge = -1;
1618 Parent::first_free_edge = -1;
1623 /// \brief Graph adaptor using a node set of another graph and an
1624 /// own undir edge set.
1626 /// This structure can be used to establish another undirected graph over
1627 /// a node set of an existing one. The node iterator will go through the
1628 /// nodes of the original graph.
1630 /// \param _Graph The type of the graph which shares its node set with
1631 /// this class. Its interface must conform to the \ref concept::StaticGraph
1632 /// "StaticGraph" concept.
1634 /// In the edge extension and removing it conforms to the
1635 /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
1636 template <typename _Graph>
1637 class NewUndirEdgeSetAdaptor :
1638 public ErasableUndirGraphExtender<
1639 ClearableUndirGraphExtender<
1640 ExtendableUndirGraphExtender<
1641 MappableUndirGraphExtender<
1642 IterableUndirGraphExtender<
1643 AlterableUndirGraphExtender<
1645 NewEdgeSetAdaptorBase<_Graph> > > > > > > > {
1649 typedef ErasableUndirGraphExtender<
1650 ClearableUndirGraphExtender<
1651 ExtendableUndirGraphExtender<
1652 MappableUndirGraphExtender<
1653 IterableUndirGraphExtender<
1654 AlterableUndirGraphExtender<
1656 NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;
1659 typedef typename Parent::Node Node;
1660 typedef typename Parent::Edge Edge;
1661 typedef typename Parent::UndirEdge UndirEdge;
1665 virtual void _clear() {
1666 Parent::edges.clear();
1667 Parent::first_edge = -1;
1668 Parent::first_free_edge = -1;
1669 Parent::getNotifier(Edge()).clear();
1670 Parent::getNotifier(Node()).clear();
1673 virtual void _add(const Node& node) {
1674 Parent::getNotifier(Node()).add(node);
1677 virtual void _erase(const Node& node) {
1679 Parent::firstOut(edge, node);
1680 while (edge != INVALID) {
1681 Parent::erase(edge);
1682 Parent::firstOut(edge, node);
1685 Parent::firstIn(edge, node);
1686 while (edge != INVALID) {
1687 Parent::erase(edge);
1688 Parent::firstIn(edge, node);
1691 Parent::getNotifier(Node()).erase(node);
1694 typedef typename Parent::NodesImpl NodesImpl;
1701 /// \brief Constructor of the adaptor.
1703 /// Constructor of the adaptor.
1704 NewUndirEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
1705 Parent::initalize(_graph, nodes);
1709 Parent::getNotifier(Edge()).clear();
1710 Parent::getNotifier(UndirEdge()).clear();
1712 Parent::edges.clear();
1713 Parent::first_edge = -1;
1714 Parent::first_free_edge = -1;
1723 #endif //LEMON_GRAPH_ADAPTOR_H