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/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 typedef Graph ParentGraph;
72 GraphAdaptorBase() : graph(0) { }
73 void setGraph(Graph& _graph) { graph=&_graph; }
76 GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
78 typedef typename Graph::Node Node;
79 typedef typename Graph::Edge Edge;
81 void first(Node& i) const { graph->first(i); }
82 void first(Edge& i) const { graph->first(i); }
83 void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
84 void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
86 void next(Node& i) const { graph->next(i); }
87 void next(Edge& i) const { graph->next(i); }
88 void nextIn(Edge& i) const { graph->nextIn(i); }
89 void nextOut(Edge& i) const { graph->nextOut(i); }
91 Node source(const Edge& e) const { return graph->source(e); }
92 Node target(const Edge& e) const { return graph->target(e); }
94 typedef NodeNumTagIndicator<Graph> NodeNumTag;
95 int nodeNum() const { return graph->nodeNum(); }
97 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
98 int edgeNum() const { return graph->edgeNum(); }
100 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
101 Edge findEdge(const Node& source, const Node& target,
102 const Edge& prev = INVALID) {
103 return graph->findEdge(source, target, prev);
106 Node addNode() const {
107 return Node(graph->addNode());
110 Edge addEdge(const Node& source, const Node& target) const {
111 return Edge(graph->addEdge(source, target));
114 void erase(const Node& i) const { graph->erase(i); }
115 void erase(const Edge& i) const { graph->erase(i); }
117 void clear() const { graph->clear(); }
119 int id(const Node& v) const { return graph->id(v); }
120 int id(const Edge& e) const { return graph->id(e); }
122 Edge oppositeNode(const Edge& e) const {
123 return Edge(graph->opposite(e));
126 template <typename _Value>
127 class NodeMap : public _Graph::template NodeMap<_Value> {
129 typedef typename _Graph::template NodeMap<_Value> Parent;
130 explicit NodeMap(const GraphAdaptorBase<_Graph>& gw)
131 : Parent(*gw.graph) { }
132 NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
133 : Parent(*gw.graph, value) { }
136 template <typename _Value>
137 class EdgeMap : public _Graph::template EdgeMap<_Value> {
139 typedef typename _Graph::template EdgeMap<_Value> Parent;
140 explicit EdgeMap(const GraphAdaptorBase<_Graph>& gw)
141 : Parent(*gw.graph) { }
142 EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
143 : Parent(*gw.graph, value) { }
148 template <typename _Graph>
150 public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
152 typedef _Graph Graph;
153 typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
155 GraphAdaptor() : Parent() { }
158 explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }
161 template <typename _Graph>
162 class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
164 typedef _Graph Graph;
165 typedef GraphAdaptorBase<_Graph> Parent;
167 RevGraphAdaptorBase() : Parent() { }
169 typedef typename Parent::Node Node;
170 typedef typename Parent::Edge Edge;
172 void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
173 void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
175 void nextIn(Edge& i) const { Parent::nextOut(i); }
176 void nextOut(Edge& i) const { Parent::nextIn(i); }
178 Node source(const Edge& e) const { return Parent::target(e); }
179 Node target(const Edge& e) const { return Parent::source(e); }
183 /// A graph adaptor which reverses the orientation of the edges.
185 ///\warning Graph adaptors are in even more experimental state than the other
186 ///parts of the lib. Use them at you own risk.
188 /// Let \f$G=(V, A)\f$ be a directed graph and
189 /// suppose that a graph instange \c g of type
190 /// \c ListGraph implements \f$G\f$.
194 /// For each directed edge
195 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
196 /// reversing its orientation.
197 /// Then RevGraphAdaptor implements the graph structure with node-set
198 /// \f$V\f$ and edge-set
199 /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
200 /// reversing the orientation of its edges. The following code shows how
201 /// such an instance can be constructed.
203 /// RevGraphAdaptor<ListGraph> gw(g);
205 ///\author Marton Makai
206 template<typename _Graph>
207 class RevGraphAdaptor :
208 public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
210 typedef _Graph Graph;
211 typedef IterableGraphExtender<
212 RevGraphAdaptorBase<_Graph> > Parent;
214 RevGraphAdaptor() { }
216 explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
220 template <typename _Graph, typename NodeFilterMap,
221 typename EdgeFilterMap, bool checked = true>
222 class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
224 typedef _Graph Graph;
225 typedef GraphAdaptorBase<_Graph> Parent;
227 NodeFilterMap* node_filter_map;
228 EdgeFilterMap* edge_filter_map;
229 SubGraphAdaptorBase() : Parent(),
230 node_filter_map(0), edge_filter_map(0) { }
232 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
233 node_filter_map=&_node_filter_map;
235 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
236 edge_filter_map=&_edge_filter_map;
241 typedef typename Parent::Node Node;
242 typedef typename Parent::Edge Edge;
244 void first(Node& i) const {
246 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
249 void first(Edge& i) const {
251 while (i!=INVALID && (!(*edge_filter_map)[i]
252 || !(*node_filter_map)[Parent::source(i)]
253 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
256 void firstIn(Edge& i, const Node& n) const {
257 Parent::firstIn(i, n);
258 while (i!=INVALID && (!(*edge_filter_map)[i]
259 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
262 void firstOut(Edge& i, const Node& n) const {
263 Parent::firstOut(i, n);
264 while (i!=INVALID && (!(*edge_filter_map)[i]
265 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
268 void next(Node& i) const {
270 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
273 void next(Edge& i) const {
275 while (i!=INVALID && (!(*edge_filter_map)[i]
276 || !(*node_filter_map)[Parent::source(i)]
277 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
280 void nextIn(Edge& i) const {
282 while (i!=INVALID && (!(*edge_filter_map)[i]
283 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
286 void nextOut(Edge& i) const {
288 while (i!=INVALID && (!(*edge_filter_map)[i]
289 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
292 /// This function hides \c n in the graph, i.e. the iteration
293 /// jumps over it. This is done by simply setting the value of \c n
294 /// to be false in the corresponding node-map.
295 void hide(const Node& n) const { node_filter_map->set(n, false); }
297 /// This function hides \c e in the graph, i.e. the iteration
298 /// jumps over it. This is done by simply setting the value of \c e
299 /// to be false in the corresponding edge-map.
300 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
302 /// The value of \c n is set to be true in the node-map which stores
303 /// hide information. If \c n was hidden previuosly, then it is shown
305 void unHide(const Node& n) const { node_filter_map->set(n, true); }
307 /// The value of \c e is set to be true in the edge-map which stores
308 /// hide information. If \c e was hidden previuosly, then it is shown
310 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
312 /// Returns true if \c n is hidden.
313 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
315 /// Returns true if \c n is hidden.
316 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
318 typedef False NodeNumTag;
319 typedef False EdgeNumTag;
322 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
323 class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
324 : public GraphAdaptorBase<_Graph> {
326 typedef _Graph Graph;
327 typedef GraphAdaptorBase<_Graph> Parent;
329 NodeFilterMap* node_filter_map;
330 EdgeFilterMap* edge_filter_map;
331 SubGraphAdaptorBase() : Parent(),
332 node_filter_map(0), edge_filter_map(0) { }
334 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
335 node_filter_map=&_node_filter_map;
337 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
338 edge_filter_map=&_edge_filter_map;
343 typedef typename Parent::Node Node;
344 typedef typename Parent::Edge Edge;
346 void first(Node& i) const {
348 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
351 void first(Edge& i) const {
353 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
356 void firstIn(Edge& i, const Node& n) const {
357 Parent::firstIn(i, n);
358 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
361 void firstOut(Edge& i, const Node& n) const {
362 Parent::firstOut(i, n);
363 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
366 void next(Node& i) const {
368 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
370 void next(Edge& i) const {
372 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
374 void nextIn(Edge& i) const {
376 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
379 void nextOut(Edge& i) const {
381 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
384 /// This function hides \c n in the graph, i.e. the iteration
385 /// jumps over it. This is done by simply setting the value of \c n
386 /// to be false in the corresponding node-map.
387 void hide(const Node& n) const { node_filter_map->set(n, false); }
389 /// This function hides \c e in the graph, i.e. the iteration
390 /// jumps over it. This is done by simply setting the value of \c e
391 /// to be false in the corresponding edge-map.
392 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
394 /// The value of \c n is set to be true in the node-map which stores
395 /// hide information. If \c n was hidden previuosly, then it is shown
397 void unHide(const Node& n) const { node_filter_map->set(n, true); }
399 /// The value of \c e is set to be true in the edge-map which stores
400 /// hide information. If \c e was hidden previuosly, then it is shown
402 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
404 /// Returns true if \c n is hidden.
405 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
407 /// Returns true if \c n is hidden.
408 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
410 typedef False NodeNumTag;
411 typedef False EdgeNumTag;
414 /*! \brief A graph adaptor for hiding nodes and edges from a graph.
416 \warning Graph adaptors are in even more experimental state than the other
417 parts of the lib. Use them at you own risk.
419 SubGraphAdaptor shows the graph with filtered node-set and
420 edge-set. If the \c checked parameter is true then it filters the edgeset
421 to do not get invalid edges without source or target.
422 Let \f$G=(V, A)\f$ be a directed graph
423 and suppose that the graph instance \c g of type ListGraph implements
425 Let moreover \f$b_V\f$ and
426 \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
427 SubGraphAdaptor<...>::NodeIt iterates
428 on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
429 SubGraphAdaptor<...>::EdgeIt iterates
430 on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
431 SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
432 only on edges leaving and entering a specific node which have true value.
434 If the \c checked template parameter is false then we have to note that
435 the node-iterator cares only the filter on the node-set, and the
436 edge-iterator cares only the filter on the edge-set. This way the edge-map
437 should filter all edges which's source or target is filtered by the
440 typedef ListGraph Graph;
442 typedef Graph::Node Node;
443 typedef Graph::Edge Edge;
444 Node u=g.addNode(); //node of id 0
445 Node v=g.addNode(); //node of id 1
446 Node e=g.addEdge(u, v); //edge of id 0
447 Node f=g.addEdge(v, u); //edge of id 1
448 Graph::NodeMap<bool> nm(g, true);
450 Graph::EdgeMap<bool> em(g, true);
452 typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
454 for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
455 std::cout << ":-)" << std::endl;
456 for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
458 The output of the above code is the following.
464 Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
465 \c Graph::Node that is why \c g.id(n) can be applied.
467 For other examples see also the documentation of NodeSubGraphAdaptor and
472 template<typename _Graph, typename NodeFilterMap,
473 typename EdgeFilterMap, bool checked = true>
474 class SubGraphAdaptor :
475 public IterableGraphExtender<
476 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
478 typedef _Graph Graph;
479 typedef IterableGraphExtender<
480 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
482 SubGraphAdaptor() { }
484 SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
485 EdgeFilterMap& _edge_filter_map) {
487 setNodeFilterMap(_node_filter_map);
488 setEdgeFilterMap(_edge_filter_map);
494 /*! \brief An adaptor for hiding nodes from a graph.
496 \warning Graph adaptors are in even more experimental state than the other
497 parts of the lib. Use them at you own risk.
499 An adaptor for hiding nodes from a graph.
500 This adaptor specializes SubGraphAdaptor in the way that only the node-set
501 can be filtered. In usual case the checked parameter is true, we get the
502 induced subgraph. But if the checked parameter is false then we can only
503 filter only isolated nodes.
506 template<typename Graph, typename NodeFilterMap, bool checked = true>
507 class NodeSubGraphAdaptor :
508 public SubGraphAdaptor<Graph, NodeFilterMap,
509 ConstMap<typename Graph::Edge,bool>, checked> {
511 typedef SubGraphAdaptor<Graph, NodeFilterMap,
512 ConstMap<typename Graph::Edge,bool> > Parent;
514 ConstMap<typename Graph::Edge, bool> const_true_map;
516 NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
517 Parent(), const_true_map(true) {
518 Parent::setGraph(_graph);
519 Parent::setNodeFilterMap(_node_filter_map);
520 Parent::setEdgeFilterMap(const_true_map);
525 /*! \brief An adaptor for hiding edges from a graph.
527 \warning Graph adaptors are in even more experimental state than the other
528 parts of the lib. Use them at you own risk.
530 An adaptor for hiding edges from a graph.
531 This adaptor specializes SubGraphAdaptor in the way that only the edge-set
532 can be filtered. The usefulness of this adaptor is demonstrated in the
533 problem of searching a maximum number of edge-disjoint shortest paths
535 two nodes \c s and \c t. Shortest here means being shortest w.r.t.
536 non-negative edge-lengths. Note that
537 the comprehension of the presented solution
538 need's some elementary knowledge from combinatorial optimization.
540 If a single shortest path is to be
541 searched between \c s and \c t, then this can be done easily by
542 applying the Dijkstra algorithm. What happens, if a maximum number of
543 edge-disjoint shortest paths is to be computed. It can be proved that an
544 edge can be in a shortest path if and only if it is tight with respect to
545 the potential function computed by Dijkstra. Moreover, any path containing
546 only such edges is a shortest one. Thus we have to compute a maximum number
547 of edge-disjoint paths between \c s and \c t in the graph which has edge-set
548 all the tight edges. The computation will be demonstrated on the following
549 graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
550 The full source code is available in \ref sub_graph_adaptor_demo.cc.
551 If you are interested in more demo programs, you can use
552 \ref dim_to_dot.cc to generate .dot files from dimacs files.
553 The .dot file of the following figure was generated by
554 the demo program \ref dim_to_dot.cc.
557 digraph lemon_dot_example {
558 node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
559 n0 [ label="0 (s)" ];
565 n6 [ label="6 (t)" ];
566 edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
567 n5 -> n6 [ label="9, length:4" ];
568 n4 -> n6 [ label="8, length:2" ];
569 n3 -> n5 [ label="7, length:1" ];
570 n2 -> n5 [ label="6, length:3" ];
571 n2 -> n6 [ label="5, length:5" ];
572 n2 -> n4 [ label="4, length:2" ];
573 n1 -> n4 [ label="3, length:3" ];
574 n0 -> n3 [ label="2, length:1" ];
575 n0 -> n2 [ label="1, length:2" ];
576 n0 -> n1 [ label="0, length:3" ];
585 readDimacs(std::cin, g, length, s, t);
587 cout << "edges with lengths (of form id, source--length->target): " << endl;
588 for(EdgeIt e(g); e!=INVALID; ++e)
589 cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
590 << length[e] << "->" << g.id(g.target(e)) << endl;
592 cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
594 Next, the potential function is computed with Dijkstra.
596 typedef Dijkstra<Graph, LengthMap> Dijkstra;
597 Dijkstra dijkstra(g, length);
600 Next, we consrtruct a map which filters the edge-set to the tight edges.
602 typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
604 TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
606 typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
607 SubGW gw(g, tight_edge_filter);
609 Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
610 with a max flow algorithm Preflow.
612 ConstMap<Edge, int> const_1_map(1);
613 Graph::EdgeMap<int> flow(g, 0);
615 Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
616 preflow(gw, s, t, const_1_map, flow);
621 cout << "maximum number of edge-disjoint shortest path: "
622 << preflow.flowValue() << endl;
623 cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
625 for(EdgeIt e(g); e!=INVALID; ++e)
627 cout << " " << g.id(g.source(e)) << "--"
628 << length[e] << "->" << g.id(g.target(e)) << endl;
630 The program has the following (expected :-)) output:
632 edges with lengths (of form id, source--length->target):
644 maximum number of edge-disjoint shortest path: 2
645 edges of the maximum number of edge-disjoint shortest s-t paths:
656 template<typename Graph, typename EdgeFilterMap>
657 class EdgeSubGraphAdaptor :
658 public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
659 EdgeFilterMap, false> {
661 typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
662 EdgeFilterMap, false> Parent;
664 ConstMap<typename Graph::Node, bool> const_true_map;
666 EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
667 Parent(), const_true_map(true) {
668 Parent::setGraph(_graph);
669 Parent::setNodeFilterMap(const_true_map);
670 Parent::setEdgeFilterMap(_edge_filter_map);
674 template <typename _Graph>
675 class UndirGraphAdaptorBase :
676 public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
678 typedef _Graph Graph;
679 typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
681 UndirGraphAdaptorBase() : Parent() { }
683 typedef typename Parent::UndirEdge UndirEdge;
684 typedef typename Parent::Edge Edge;
686 template <typename T>
689 const UndirGraphAdaptorBase<_Graph>* g;
690 template <typename TT> friend class EdgeMap;
691 typename _Graph::template EdgeMap<T> forward_map, backward_map;
696 EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
697 forward_map(*(g->graph)), backward_map(*(g->graph)) { }
699 EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
700 forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
702 void set(Edge e, T a) {
704 forward_map.set(e, a);
706 backward_map.set(e, a);
709 T operator[](Edge e) const {
711 return forward_map[e];
713 return backward_map[e];
717 template <typename T>
719 template <typename TT> friend class UndirEdgeMap;
720 typename _Graph::template EdgeMap<T> map;
723 typedef UndirEdge Key;
725 UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
728 UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
729 map(*(g.graph), a) { }
731 void set(UndirEdge e, T a) {
735 T operator[](UndirEdge e) const {
742 /// \brief An undirected graph is made from a directed graph by an adaptor
744 /// Undocumented, untested!!!
745 /// If somebody knows nice demo application, let's polulate it.
747 /// \author Marton Makai
748 template<typename _Graph>
749 class UndirGraphAdaptor :
750 public IterableUndirGraphExtender<
751 UndirGraphAdaptorBase<_Graph> > {
753 typedef _Graph Graph;
754 typedef IterableUndirGraphExtender<
755 UndirGraphAdaptorBase<_Graph> > Parent;
757 UndirGraphAdaptor() { }
759 UndirGraphAdaptor(_Graph& _graph) {
765 template <typename _Graph,
766 typename ForwardFilterMap, typename BackwardFilterMap>
767 class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
769 typedef _Graph Graph;
770 typedef GraphAdaptorBase<_Graph> Parent;
772 ForwardFilterMap* forward_filter;
773 BackwardFilterMap* backward_filter;
774 SubBidirGraphAdaptorBase() : Parent(),
775 forward_filter(0), backward_filter(0) { }
777 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
778 forward_filter=&_forward_filter;
780 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
781 backward_filter=&_backward_filter;
785 // SubGraphAdaptorBase(Graph& _graph,
786 // NodeFilterMap& _node_filter_map,
787 // EdgeFilterMap& _edge_filter_map) :
789 // node_filter_map(&node_filter_map),
790 // edge_filter_map(&edge_filter_map) { }
792 typedef typename Parent::Node Node;
793 typedef typename _Graph::Edge GraphEdge;
794 template <typename T> class EdgeMap;
795 /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
796 /// _Graph::Edge. It contains an extra bool flag which is true
797 /// if and only if the
798 /// edge is the backward version of the original edge.
799 class Edge : public _Graph::Edge {
800 friend class SubBidirGraphAdaptorBase<
801 Graph, ForwardFilterMap, BackwardFilterMap>;
802 template<typename T> friend class EdgeMap;
804 bool backward; //true, iff backward
807 /// \todo =false is needed, or causes problems?
808 /// If \c _backward is false, then we get an edge corresponding to the
809 /// original one, otherwise its oppositely directed pair is obtained.
810 Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
811 _Graph::Edge(e), backward(_backward) { }
812 Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
813 bool operator==(const Edge& v) const {
814 return (this->backward==v.backward &&
815 static_cast<typename _Graph::Edge>(*this)==
816 static_cast<typename _Graph::Edge>(v));
818 bool operator!=(const Edge& v) const {
819 return (this->backward!=v.backward ||
820 static_cast<typename _Graph::Edge>(*this)!=
821 static_cast<typename _Graph::Edge>(v));
825 void first(Node& i) const {
829 void first(Edge& i) const {
832 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
833 !(*forward_filter)[i]) Parent::next(i);
834 if (*static_cast<GraphEdge*>(&i)==INVALID) {
837 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
838 !(*backward_filter)[i]) Parent::next(i);
842 void firstIn(Edge& i, const Node& n) const {
843 Parent::firstIn(i, n);
845 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
846 !(*forward_filter)[i]) Parent::nextIn(i);
847 if (*static_cast<GraphEdge*>(&i)==INVALID) {
848 Parent::firstOut(i, n);
850 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
851 !(*backward_filter)[i]) Parent::nextOut(i);
855 void firstOut(Edge& i, const Node& n) const {
856 Parent::firstOut(i, n);
858 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
859 !(*forward_filter)[i]) Parent::nextOut(i);
860 if (*static_cast<GraphEdge*>(&i)==INVALID) {
861 Parent::firstIn(i, n);
863 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
864 !(*backward_filter)[i]) Parent::nextIn(i);
868 void next(Node& i) const {
872 void next(Edge& i) const {
875 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
876 !(*forward_filter)[i]) Parent::next(i);
877 if (*static_cast<GraphEdge*>(&i)==INVALID) {
880 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
881 !(*backward_filter)[i]) Parent::next(i);
885 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
886 !(*backward_filter)[i]) Parent::next(i);
890 void nextIn(Edge& i) const {
892 Node n=Parent::target(i);
894 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
895 !(*forward_filter)[i]) Parent::nextIn(i);
896 if (*static_cast<GraphEdge*>(&i)==INVALID) {
897 Parent::firstOut(i, n);
899 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
900 !(*backward_filter)[i]) Parent::nextOut(i);
904 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
905 !(*backward_filter)[i]) Parent::nextOut(i);
909 void nextOut(Edge& i) const {
911 Node n=Parent::source(i);
913 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
914 !(*forward_filter)[i]) Parent::nextOut(i);
915 if (*static_cast<GraphEdge*>(&i)==INVALID) {
916 Parent::firstIn(i, n);
918 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
919 !(*backward_filter)[i]) Parent::nextIn(i);
923 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
924 !(*backward_filter)[i]) Parent::nextIn(i);
928 Node source(Edge e) const {
929 return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
930 Node target(Edge e) const {
931 return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
933 /// Gives back the opposite edge.
934 Edge opposite(const Edge& e) const {
936 f.backward=!f.backward;
940 /// \warning This is a linear time operation and works only if
941 /// \c Graph::EdgeIt is defined.
943 int edgeNum() const {
946 for (first(e); e!=INVALID; next(e)) ++i;
950 bool forward(const Edge& e) const { return !e.backward; }
951 bool backward(const Edge& e) const { return e.backward; }
953 template <typename T>
954 /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
955 /// _Graph::EdgeMap one for the forward edges and
956 /// one for the backward edges.
958 template <typename TT> friend class EdgeMap;
959 typename _Graph::template EdgeMap<T> forward_map, backward_map;
964 EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
965 ForwardFilterMap, BackwardFilterMap>& g) :
966 forward_map(*(g.graph)), backward_map(*(g.graph)) { }
968 EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
969 ForwardFilterMap, BackwardFilterMap>& g, T a) :
970 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
972 void set(Edge e, T a) {
974 forward_map.set(e, a);
976 backward_map.set(e, a);
979 // typename _Graph::template EdgeMap<T>::ConstReference
980 // operator[](Edge e) const {
982 // return forward_map[e];
984 // return backward_map[e];
987 // typename _Graph::template EdgeMap<T>::Reference
988 T operator[](Edge e) const {
990 return forward_map[e];
992 return backward_map[e];
996 forward_map.update();
997 backward_map.update();
1004 ///\brief An adaptor for composing a subgraph of a
1005 /// bidirected graph made from a directed one.
1007 /// An adaptor for composing a subgraph of a
1008 /// bidirected graph made from a directed one.
1010 ///\warning Graph adaptors are in even more experimental state than the other
1011 ///parts of the lib. Use them at you own risk.
1013 /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
1014 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
1015 /// reversing its orientation. We are given moreover two bool valued
1016 /// maps on the edge-set,
1017 /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
1018 /// SubBidirGraphAdaptor implements the graph structure with node-set
1019 /// \f$V\f$ and edge-set
1020 /// \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$.
1021 /// The purpose of writing + instead of union is because parallel
1022 /// edges can arise. (Similarly, antiparallel edges also can arise).
1023 /// In other words, a subgraph of the bidirected graph obtained, which
1024 /// is given by orienting the edges of the original graph in both directions.
1025 /// As the oppositely directed edges are logically different,
1026 /// the maps are able to attach different values for them.
1028 /// An example for such a construction is \c RevGraphAdaptor where the
1029 /// forward_filter is everywhere false and the backward_filter is
1030 /// everywhere true. We note that for sake of efficiency,
1031 /// \c RevGraphAdaptor is implemented in a different way.
1032 /// But BidirGraphAdaptor is obtained from
1033 /// SubBidirGraphAdaptor by considering everywhere true
1034 /// valued maps both for forward_filter and backward_filter.
1036 /// The most important application of SubBidirGraphAdaptor
1037 /// is ResGraphAdaptor, which stands for the residual graph in directed
1038 /// flow and circulation problems.
1039 /// As adaptors usually, the SubBidirGraphAdaptor implements the
1040 /// above mentioned graph structure without its physical storage,
1041 /// that is the whole stuff is stored in constant memory.
1042 template<typename _Graph,
1043 typename ForwardFilterMap, typename BackwardFilterMap>
1044 class SubBidirGraphAdaptor :
1045 public IterableGraphExtender<
1046 SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
1048 typedef _Graph Graph;
1049 typedef IterableGraphExtender<
1050 SubBidirGraphAdaptorBase<
1051 _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
1053 SubBidirGraphAdaptor() { }
1055 SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
1056 BackwardFilterMap& _backward_filter) {
1058 setForwardFilterMap(_forward_filter);
1059 setBackwardFilterMap(_backward_filter);
1065 ///\brief An adaptor for composing bidirected graph from a directed one.
1067 ///\warning Graph adaptors are in even more experimental state than the other
1068 ///parts of the lib. Use them at you own risk.
1070 /// An adaptor for composing bidirected graph from a directed one.
1071 /// A bidirected graph is composed over the directed one without physical
1072 /// storage. As the oppositely directed edges are logically different ones
1073 /// the maps are able to attach different values for them.
1074 template<typename Graph>
1075 class BidirGraphAdaptor :
1076 public SubBidirGraphAdaptor<
1078 ConstMap<typename Graph::Edge, bool>,
1079 ConstMap<typename Graph::Edge, bool> > {
1081 typedef SubBidirGraphAdaptor<
1083 ConstMap<typename Graph::Edge, bool>,
1084 ConstMap<typename Graph::Edge, bool> > Parent;
1086 ConstMap<typename Graph::Edge, bool> cm;
1088 BidirGraphAdaptor() : Parent(), cm(true) {
1089 Parent::setForwardFilterMap(cm);
1090 Parent::setBackwardFilterMap(cm);
1093 BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
1094 Parent::setGraph(_graph);
1095 Parent::setForwardFilterMap(cm);
1096 Parent::setBackwardFilterMap(cm);
1099 int edgeNum() const {
1100 return 2*this->graph->edgeNum();
1105 template<typename Graph, typename Number,
1106 typename CapacityMap, typename FlowMap>
1107 class ResForwardFilter {
1108 // const Graph* graph;
1109 const CapacityMap* capacity;
1110 const FlowMap* flow;
1112 ResForwardFilter(/*const Graph& _graph, */
1113 const CapacityMap& _capacity, const FlowMap& _flow) :
1114 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1115 ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1116 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1117 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1118 bool operator[](const typename Graph::Edge& e) const {
1119 return (Number((*flow)[e]) < Number((*capacity)[e]));
1123 template<typename Graph, typename Number,
1124 typename CapacityMap, typename FlowMap>
1125 class ResBackwardFilter {
1126 const CapacityMap* capacity;
1127 const FlowMap* flow;
1129 ResBackwardFilter(/*const Graph& _graph,*/
1130 const CapacityMap& _capacity, const FlowMap& _flow) :
1131 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1132 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1133 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1134 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1135 bool operator[](const typename Graph::Edge& e) const {
1136 return (Number(0) < Number((*flow)[e]));
1141 /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
1143 An adaptor for composing the residual graph for directed flow and circulation problems.
1144 Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
1145 number type. Let moreover
1146 \f$f,c:A\to F\f$, be functions on the edge-set.
1147 In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
1148 and \f$c\f$ for a capacity function.
1149 Suppose that a graph instange \c g of type
1150 \c ListGraph implements \f$G\f$.
1154 Then RevGraphAdaptor implements the graph structure with node-set
1155 \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
1156 \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
1157 \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
1158 i.e. the so called residual graph.
1159 When we take the union \f$A_{forward}\cup A_{backward}\f$,
1160 multilicities are counted, i.e. if an edge is in both
1161 \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
1163 The following code shows how
1164 such an instance can be constructed.
1166 typedef ListGraph Graph;
1167 Graph::EdgeMap<int> f(g);
1168 Graph::EdgeMap<int> c(g);
1169 ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
1171 \author Marton Makai
1173 template<typename Graph, typename Number,
1174 typename CapacityMap, typename FlowMap>
1175 class ResGraphAdaptor :
1176 public SubBidirGraphAdaptor<
1178 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1179 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1181 typedef SubBidirGraphAdaptor<
1183 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1184 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1186 const CapacityMap* capacity;
1188 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1189 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1190 ResGraphAdaptor() : Parent(),
1191 capacity(0), flow(0) { }
1192 void setCapacityMap(const CapacityMap& _capacity) {
1193 capacity=&_capacity;
1194 forward_filter.setCapacity(_capacity);
1195 backward_filter.setCapacity(_capacity);
1197 void setFlowMap(FlowMap& _flow) {
1199 forward_filter.setFlow(_flow);
1200 backward_filter.setFlow(_flow);
1203 ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
1205 Parent(), capacity(&_capacity), flow(&_flow),
1206 forward_filter(/*_graph,*/ _capacity, _flow),
1207 backward_filter(/*_graph,*/ _capacity, _flow) {
1208 Parent::setGraph(_graph);
1209 Parent::setForwardFilterMap(forward_filter);
1210 Parent::setBackwardFilterMap(backward_filter);
1213 typedef typename Parent::Edge Edge;
1215 void augment(const Edge& e, Number a) const {
1216 if (Parent::forward(e))
1217 flow->set(e, (*flow)[e]+a);
1219 flow->set(e, (*flow)[e]-a);
1222 /// \brief Residual capacity map.
1224 /// In generic residual graphs the residual capacity can be obtained
1228 const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
1230 typedef Number Value;
1232 ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
1233 _res_graph) : res_graph(&_res_graph) { }
1234 Number operator[](const Edge& e) const {
1235 if (res_graph->forward(e))
1236 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1238 return (*(res_graph->flow))[e];
1242 // KEEP_MAPS(Parent, ResGraphAdaptor);
1247 template <typename _Graph, typename FirstOutEdgesMap>
1248 class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1250 typedef _Graph Graph;
1251 typedef GraphAdaptorBase<_Graph> Parent;
1253 FirstOutEdgesMap* first_out_edges;
1254 ErasingFirstGraphAdaptorBase() : Parent(),
1255 first_out_edges(0) { }
1257 void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1258 first_out_edges=&_first_out_edges;
1263 typedef typename Parent::Node Node;
1264 typedef typename Parent::Edge Edge;
1266 void firstOut(Edge& i, const Node& n) const {
1267 i=(*first_out_edges)[n];
1270 void erase(const Edge& e) const {
1274 first_out_edges->set(n, f);
1279 /// For blocking flows.
1281 ///\warning Graph adaptors are in even more experimental state than the other
1282 ///parts of the lib. Use them at you own risk.
1284 /// This graph adaptor is used for on-the-fly
1285 /// Dinits blocking flow computations.
1286 /// For each node, an out-edge is stored which is used when the
1288 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1292 /// \author Marton Makai
1293 template <typename _Graph, typename FirstOutEdgesMap>
1294 class ErasingFirstGraphAdaptor :
1295 public IterableGraphExtender<
1296 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
1298 typedef _Graph Graph;
1299 typedef IterableGraphExtender<
1300 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1301 ErasingFirstGraphAdaptor(Graph& _graph,
1302 FirstOutEdgesMap& _first_out_edges) {
1304 setFirstOutEdgesMap(_first_out_edges);
1309 template <typename _Graph>
1310 class SplitGraphAdaptorBase
1311 : public GraphAdaptorBase<_Graph> {
1313 typedef GraphAdaptorBase<_Graph> Parent;
1317 template <typename T> class NodeMap;
1318 template <typename T> class EdgeMap;
1321 class Node : public Parent::Node {
1322 friend class SplitGraphAdaptorBase;
1323 template <typename T> friend class NodeMap;
1324 typedef typename Parent::Node NodeParent;
1328 Node(typename Parent::Node _node, bool _entry)
1329 : Parent::Node(_node), entry(_entry) {}
1333 Node(Invalid) : NodeParent(INVALID), entry(true) {}
1335 bool operator==(const Node& node) const {
1336 return NodeParent::operator==(node) && entry == node.entry;
1339 bool operator!=(const Node& node) const {
1340 return !(*this == node);
1343 bool operator<(const Node& node) const {
1344 return NodeParent::operator<(node) ||
1345 (NodeParent::operator==(node) && entry < node.entry);
1349 /// \todo May we want VARIANT/union type
1350 class Edge : public Parent::Edge {
1351 friend class SplitGraphAdaptorBase;
1352 template <typename T> friend class EdgeMap;
1354 typedef typename Parent::Edge EdgeParent;
1355 typedef typename Parent::Node NodeParent;
1358 Edge(const EdgeParent& edge, const NodeParent& node)
1359 : EdgeParent(edge), bind(node) {}
1362 Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}
1364 bool operator==(const Edge& edge) const {
1365 return EdgeParent::operator==(edge) && bind == edge.bind;
1368 bool operator!=(const Edge& edge) const {
1369 return !(*this == edge);
1372 bool operator<(const Edge& edge) const {
1373 return EdgeParent::operator<(edge) ||
1374 (EdgeParent::operator==(edge) && bind < edge.bind);
1378 void first(Node& node) const {
1379 Parent::first(node);
1383 void next(Node& node) const {
1392 void first(Edge& edge) const {
1393 Parent::first(edge);
1394 if ((typename Parent::Edge&)edge == INVALID) {
1395 Parent::first(edge.bind);
1397 edge.bind = INVALID;
1401 void next(Edge& edge) const {
1402 if ((typename Parent::Edge&)edge != INVALID) {
1404 if ((typename Parent::Edge&)edge == INVALID) {
1405 Parent::first(edge.bind);
1408 Parent::next(edge.bind);
1412 void firstIn(Edge& edge, const Node& node) const {
1414 Parent::firstIn(edge, node);
1415 edge.bind = INVALID;
1417 (typename Parent::Edge&)edge = INVALID;
1422 void nextIn(Edge& edge) const {
1423 if ((typename Parent::Edge&)edge != INVALID) {
1424 Parent::nextIn(edge);
1426 edge.bind = INVALID;
1430 void firstOut(Edge& edge, const Node& node) const {
1432 Parent::firstOut(edge, node);
1433 edge.bind = INVALID;
1435 (typename Parent::Edge&)edge = INVALID;
1440 void nextOut(Edge& edge) const {
1441 if ((typename Parent::Edge&)edge != INVALID) {
1442 Parent::nextOut(edge);
1444 edge.bind = INVALID;
1448 Node source(const Edge& edge) const {
1449 if ((typename Parent::Edge&)edge != INVALID) {
1450 return Node(Parent::source(edge), false);
1452 return Node(edge.bind, true);
1456 Node target(const Edge& edge) const {
1457 if ((typename Parent::Edge&)edge != INVALID) {
1458 return Node(Parent::target(edge), true);
1460 return Node(edge.bind, false);
1464 static bool entryNode(const Node& node) {
1468 static bool exitNode(const Node& node) {
1472 static Node getEntry(const typename Parent::Node& node) {
1473 return Node(node, true);
1476 static Node getExit(const typename Parent::Node& node) {
1477 return Node(node, false);
1480 static bool originalEdge(const Edge& edge) {
1481 return (typename Parent::Edge&)edge != INVALID;
1484 static bool bindingEdge(const Edge& edge) {
1485 return edge.bind != INVALID;
1488 static Node getBindedNode(const Edge& edge) {
1492 int nodeNum() const {
1493 return Parent::nodeNum() * 2;
1496 typedef CompileTimeAnd<typename Parent::NodeNumTag,
1497 typename Parent::EdgeNumTag> EdgeNumTag;
1499 int edgeNum() const {
1500 return Parent::edgeNum() + Parent::nodeNum();
1503 Edge findEdge(const Node& source, const Node& target,
1504 const Edge& prev = INVALID) const {
1505 if (exitNode(source) && entryNode(target)) {
1506 return Parent::findEdge(source, target, prev);
1508 if (prev == INVALID && entryNode(source) && exitNode(target) &&
1509 (typename Parent::Node&)source == (typename Parent::Node&)target) {
1510 return Edge(INVALID, source);
1517 template <typename T>
1518 class NodeMap : public MapBase<Node, T> {
1519 typedef typename Parent::template NodeMap<T> NodeImpl;
1521 NodeMap(const SplitGraphAdaptorBase& _graph)
1522 : entry(_graph), exit(_graph) {}
1523 NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1524 : entry(_graph, t), exit(_graph, t) {}
1526 void set(const Node& key, const T& val) {
1527 if (key.entry) { entry.set(key, val); }
1528 else {exit.set(key, val); }
1531 typename MapTraits<NodeImpl>::ReturnValue
1532 operator[](const Node& key) {
1533 if (key.entry) { return entry[key]; }
1534 else { return exit[key]; }
1537 typename MapTraits<NodeImpl>::ConstReturnValue
1538 operator[](const Node& key) const {
1539 if (key.entry) { return entry[key]; }
1540 else { return exit[key]; }
1544 NodeImpl entry, exit;
1547 template <typename T>
1548 class EdgeMap : public MapBase<Edge, T> {
1549 typedef typename Parent::template NodeMap<T> NodeImpl;
1550 typedef typename Parent::template EdgeMap<T> EdgeImpl;
1552 EdgeMap(const SplitGraphAdaptorBase& _graph)
1553 : bind(_graph), orig(_graph) {}
1554 EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1555 : bind(_graph, t), orig(_graph, t) {}
1557 void set(const Edge& key, const T& val) {
1558 if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }
1559 else {bind.set(key.bind, val); }
1562 typename MapTraits<EdgeImpl>::ReturnValue
1563 operator[](const Edge& key) {
1564 if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
1565 else {return bind[key.bind]; }
1568 typename MapTraits<EdgeImpl>::ConstReturnValue
1569 operator[](const Edge& key) const {
1570 if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
1571 else {return bind[key.bind]; }
1575 typename Parent::template NodeMap<T> bind;
1576 typename Parent::template EdgeMap<T> orig;
1579 template <typename EntryMap, typename ExitMap>
1580 class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {
1582 typedef MapBase<Node, typename EntryMap::Value> Parent;
1584 typedef typename Parent::Key Key;
1585 typedef typename Parent::Value Value;
1587 CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap)
1588 : entryMap(_entryMap), exitMap(_exitMap) {}
1590 Value& operator[](const Key& key) {
1592 return entryMap[key];
1594 return exitMap[key];
1598 Value operator[](const Key& key) const {
1600 return entryMap[key];
1602 return exitMap[key];
1606 void set(const Key& key, const Value& value) {
1608 entryMap.set(key, value);
1610 exitMap.set(key, value);
1621 template <typename EdgeMap, typename NodeMap>
1622 class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {
1624 typedef MapBase<Edge, typename EdgeMap::Value> Parent;
1626 typedef typename Parent::Key Key;
1627 typedef typename Parent::Value Value;
1629 CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap)
1630 : edgeMap(_edgeMap), nodeMap(_nodeMap) {}
1632 void set(const Edge& edge, const Value& val) {
1633 if (SplitGraphAdaptorBase::originalEdge(edge)) {
1634 edgeMap.set(edge, val);
1636 nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);
1640 Value operator[](const Key& edge) const {
1641 if (SplitGraphAdaptorBase::originalEdge(edge)) {
1642 return edgeMap[edge];
1644 return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
1648 Value& operator[](const Key& edge) {
1649 if (SplitGraphAdaptorBase::originalEdge(edge)) {
1650 return edgeMap[edge];
1652 return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
1663 template <typename _Graph>
1664 class SplitGraphAdaptor
1665 : public IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > {
1667 typedef IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > Parent;
1669 SplitGraphAdaptor(_Graph& graph) {
1670 Parent::setGraph(graph);
1676 template <typename _Graph>
1677 class NewEdgeSetAdaptorBase {
1680 typedef _Graph Graph;
1681 typedef typename Graph::Node Node;
1682 typedef typename Graph::NodeIt NodeIt;
1687 int first_out, first_in;
1688 NodeT() : first_out(-1), first_in(-1) {}
1691 class NodesImpl : protected Graph::template NodeMap<NodeT> {
1693 typedef typename Graph::template NodeMap<NodeT> Parent;
1694 typedef NewEdgeSetAdaptorBase<Graph> Adaptor;
1700 NodesImpl(Adaptor& _adaptor, const Graph& _graph)
1701 : Parent(_graph), adaptor(_adaptor) {}
1703 virtual ~NodesImpl() {}
1705 virtual void build() {
1709 virtual void clear() {
1714 virtual void add(const Node& node) {
1719 virtual void erase(const Node& node) {
1720 adaptor._erase(node);
1721 Parent::erase(node);
1724 NodeT& operator[](const Node& node) {
1725 return Parent::operator[](node);
1728 const NodeT& operator[](const Node& node) const {
1729 return Parent::operator[](node);
1737 Node source, target;
1738 int next_out, next_in;
1739 int prev_out, prev_in;
1740 EdgeT() : prev_out(-1), prev_in(-1) {}
1743 std::vector<EdgeT> edges;
1746 int first_free_edge;
1748 virtual void _clear() = 0;
1749 virtual void _add(const Node& node) = 0;
1750 virtual void _erase(const Node& node) = 0;
1754 void initalize(const Graph& _graph, NodesImpl& _nodes) {
1762 friend class NewEdgeSetAdaptorBase<Graph>;
1764 Edge(int _id) : id(_id) {}
1768 Edge(Invalid) : id(-1) {}
1769 bool operator==(const Edge& edge) const { return id == edge.id; }
1770 bool operator!=(const Edge& edge) const { return id != edge.id; }
1771 bool operator<(const Edge& edge) const { return id < edge.id; }
1774 NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {}
1775 virtual ~NewEdgeSetAdaptorBase() {}
1777 Edge addEdge(const Node& source, const Node& target) {
1779 if (first_free_edge == -1) {
1781 edges.push_back(EdgeT());
1783 n = first_free_edge;
1784 first_free_edge = edges[first_free_edge].next_in;
1786 edges[n].next_in = (*nodes)[target].first_in;
1787 (*nodes)[target].first_in = n;
1788 edges[n].next_out = (*nodes)[source].first_out;
1789 (*nodes)[source].first_out = n;
1790 edges[n].source = source;
1791 edges[n].target = target;
1795 void erase(const Edge& edge) {
1797 if (edges[n].prev_in != -1) {
1798 edges[edges[n].prev_in].next_in = edges[n].next_in;
1800 (*nodes)[edges[n].target].first_in = edges[n].next_in;
1802 if (edges[n].next_in != -1) {
1803 edges[edges[n].next_in].prev_in = edges[n].prev_in;
1806 if (edges[n].prev_out != -1) {
1807 edges[edges[n].prev_out].next_out = edges[n].next_out;
1809 (*nodes)[edges[n].source].first_out = edges[n].next_out;
1811 if (edges[n].next_out != -1) {
1812 edges[edges[n].next_out].prev_out = edges[n].prev_out;
1817 void first(Node& node) const {
1821 void next(Node& node) const {
1825 void first(Edge& edge) const {
1827 for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
1829 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1832 void next(Edge& edge) const {
1833 if (edges[edge.id].next_in != -1) {
1834 edge.id = edges[edge.id].next_in;
1836 Node node = edges[edge.id].target;
1837 for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
1839 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1843 void firstOut(Edge& edge, const Node& node) const {
1844 edge.id = (*nodes)[node].first_out;
1847 void nextOut(Edge& edge) const {
1848 edge.id = edges[edge.id].next_out;
1851 void firstIn(Edge& edge, const Node& node) const {
1852 edge.id = (*nodes)[node].first_in;
1855 void nextIn(Edge& edge) const {
1856 edge.id = edges[edge.id].next_in;
1859 int id(const Node& node) const { return graph->id(node); }
1860 int id(const Edge& edge) const { return edge.id; }
1862 Node nodeFromId(int id) const { return graph->fromId(id, Node()); }
1863 Edge edgeFromId(int id) const { return Edge(id); }
1865 int maxNodeId() const { return graph->maxId(Node()); };
1866 int maxEdgeId() const { return edges.size() - 1; }
1868 Node source(const Edge& edge) const { return edges[edge.id].source;}
1869 Node target(const Edge& edge) const { return edges[edge.id].target;}
1874 /// \brief Graph adaptor using a node set of another graph and an
1877 /// This structure can be used to establish another graph over a node set
1878 /// of an existing one. The node iterator will go through the nodes of the
1881 /// \param _Graph The type of the graph which shares its node set with
1882 /// this class. Its interface must conform to the \ref concept::StaticGraph
1883 /// "StaticGraph" concept.
1885 /// In the edge extension and removing it conforms to the
1886 /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
1887 template <typename _Graph>
1888 class NewEdgeSetAdaptor :
1889 public ErasableGraphExtender<
1890 ClearableGraphExtender<
1891 ExtendableGraphExtender<
1892 MappableGraphExtender<
1893 IterableGraphExtender<
1894 AlterableGraphExtender<
1895 NewEdgeSetAdaptorBase<_Graph> > > > > > > {
1899 typedef ErasableGraphExtender<
1900 ClearableGraphExtender<
1901 ExtendableGraphExtender<
1902 MappableGraphExtender<
1903 IterableGraphExtender<
1904 AlterableGraphExtender<
1905 NewEdgeSetAdaptorBase<_Graph> > > > > > > Parent;
1908 typedef typename Parent::Node Node;
1909 typedef typename Parent::Edge Edge;
1913 virtual void _clear() {
1914 Parent::edges.clear();
1915 Parent::first_edge = -1;
1916 Parent::first_free_edge = -1;
1917 Parent::getNotifier(Edge()).clear();
1918 Parent::getNotifier(Node()).clear();
1921 virtual void _add(const Node& node) {
1922 Parent::getNotifier(Node()).add(node);
1925 virtual void _erase(const Node& node) {
1927 Parent::firstOut(edge, node);
1928 while (edge != INVALID) {
1929 Parent::erase(edge);
1930 Parent::firstOut(edge, node);
1933 Parent::firstIn(edge, node);
1934 while (edge != INVALID) {
1935 Parent::erase(edge);
1936 Parent::firstIn(edge, node);
1939 Parent::getNotifier(Node()).erase(node);
1943 typedef typename Parent::NodesImpl NodesImpl;
1949 /// \brief Constructor of the adaptor.
1951 /// Constructor of the adaptor.
1952 NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
1953 Parent::initalize(_graph, nodes);
1957 Parent::getNotifier(Edge()).clear();
1959 Parent::edges.clear();
1960 Parent::first_edge = -1;
1961 Parent::first_free_edge = -1;
1966 /// \brief Graph adaptor using a node set of another graph and an
1967 /// own undir edge set.
1969 /// This structure can be used to establish another undirected graph over
1970 /// a node set of an existing one. The node iterator will go through the
1971 /// nodes of the original graph.
1973 /// \param _Graph The type of the graph which shares its node set with
1974 /// this class. Its interface must conform to the \ref concept::StaticGraph
1975 /// "StaticGraph" concept.
1977 /// In the edge extension and removing it conforms to the
1978 /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
1979 template <typename _Graph>
1980 class NewUndirEdgeSetAdaptor :
1981 public ErasableUndirGraphExtender<
1982 ClearableUndirGraphExtender<
1983 ExtendableUndirGraphExtender<
1984 MappableUndirGraphExtender<
1985 IterableUndirGraphExtender<
1986 AlterableUndirGraphExtender<
1988 NewEdgeSetAdaptorBase<_Graph> > > > > > > > {
1992 typedef ErasableUndirGraphExtender<
1993 ClearableUndirGraphExtender<
1994 ExtendableUndirGraphExtender<
1995 MappableUndirGraphExtender<
1996 IterableUndirGraphExtender<
1997 AlterableUndirGraphExtender<
1999 NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;
2002 typedef typename Parent::Node Node;
2003 typedef typename Parent::Edge Edge;
2004 typedef typename Parent::UndirEdge UndirEdge;
2008 virtual void _clear() {
2009 Parent::edges.clear();
2010 Parent::first_edge = -1;
2011 Parent::first_free_edge = -1;
2012 Parent::getNotifier(Edge()).clear();
2013 Parent::getNotifier(Node()).clear();
2016 virtual void _add(const Node& node) {
2017 Parent::getNotifier(Node()).add(node);
2020 virtual void _erase(const Node& node) {
2022 Parent::firstOut(edge, node);
2023 while (edge != INVALID) {
2024 Parent::erase(edge);
2025 Parent::firstOut(edge, node);
2028 Parent::firstIn(edge, node);
2029 while (edge != INVALID) {
2030 Parent::erase(edge);
2031 Parent::firstIn(edge, node);
2034 Parent::getNotifier(Node()).erase(node);
2037 typedef typename Parent::NodesImpl NodesImpl;
2044 /// \brief Constructor of the adaptor.
2046 /// Constructor of the adaptor.
2047 NewUndirEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
2048 Parent::initalize(_graph, nodes);
2052 Parent::getNotifier(Edge()).clear();
2053 Parent::getNotifier(UndirEdge()).clear();
2055 Parent::edges.clear();
2056 Parent::first_edge = -1;
2057 Parent::first_free_edge = -1;
2066 #endif //LEMON_GRAPH_ADAPTOR_H