COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/graph_adaptor.h @ 415:4b6112235fad

Last change on this file since 415:4b6112235fad was 415:4b6112235fad, checked in by Balazs Dezso <deba@…>, 12 years ago

Improvements in graph adaptors (#67)

Remove DigraphAdaptor? and GraphAdaptor?
Remove docs of base classes
Move the member documentations to real adaptors
Minor improvements in documentation

File size: 37.0 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_GRAPH_ADAPTOR_H
20#define LEMON_GRAPH_ADAPTOR_H
21
22///\ingroup graph_adaptors
23///\file
24///\brief Several graph adaptors.
25///
26///This file contains several useful undirected graph adaptor classes.
27
28#include <lemon/core.h>
29#include <lemon/maps.h>
30#include <lemon/bits/graph_adaptor_extender.h>
31
32namespace lemon {
33
34  template<typename _Graph>
35  class GraphAdaptorBase {
36  public:
37    typedef _Graph Graph;
38    typedef Graph ParentGraph;
39
40  protected:
41    Graph* _graph;
42
43    GraphAdaptorBase() : _graph(0) {}
44
45    void setGraph(Graph& graph) { _graph = &graph; }
46
47  public:
48    GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
49 
50    typedef typename Graph::Node Node;
51    typedef typename Graph::Arc Arc;
52    typedef typename Graph::Edge Edge;
53   
54    void first(Node& i) const { _graph->first(i); }
55    void first(Arc& i) const { _graph->first(i); }
56    void first(Edge& i) const { _graph->first(i); }
57    void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
58    void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
59    void firstInc(Edge &i, bool &d, const Node &n) const {
60      _graph->firstInc(i, d, n);
61    }
62
63    void next(Node& i) const { _graph->next(i); }
64    void next(Arc& i) const { _graph->next(i); }
65    void next(Edge& i) const { _graph->next(i); }
66    void nextIn(Arc& i) const { _graph->nextIn(i); }
67    void nextOut(Arc& i) const { _graph->nextOut(i); }
68    void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
69
70    Node u(const Edge& e) const { return _graph->u(e); }
71    Node v(const Edge& e) const { return _graph->v(e); }
72
73    Node source(const Arc& a) const { return _graph->source(a); }
74    Node target(const Arc& a) const { return _graph->target(a); }
75
76    typedef NodeNumTagIndicator<Graph> NodeNumTag;
77    int nodeNum() const { return _graph->nodeNum(); }
78   
79    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
80    int arcNum() const { return _graph->arcNum(); }
81    int edgeNum() const { return _graph->edgeNum(); }
82
83    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
84    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
85      return _graph->findArc(u, v, prev);
86    }
87    Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
88      return _graph->findEdge(u, v, prev);
89    }
90 
91    Node addNode() { return _graph->addNode(); }
92    Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
93
94    void erase(const Node& i) { _graph->erase(i); }
95    void erase(const Edge& i) { _graph->erase(i); }
96 
97    void clear() { _graph->clear(); }
98   
99    bool direction(const Arc& a) const { return _graph->direction(a); }
100    Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
101
102    int id(const Node& v) const { return _graph->id(v); }
103    int id(const Arc& a) const { return _graph->id(a); }
104    int id(const Edge& e) const { return _graph->id(e); }
105
106    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
107    Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
108    Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
109
110    int maxNodeId() const { return _graph->maxNodeId(); }
111    int maxArcId() const { return _graph->maxArcId(); }
112    int maxEdgeId() const { return _graph->maxEdgeId(); }
113
114    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
115    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
116
117    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
118    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
119
120    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
121    EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
122
123    template <typename _Value>
124    class NodeMap : public Graph::template NodeMap<_Value> {
125    public:
126      typedef typename Graph::template NodeMap<_Value> Parent;
127      explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
128        : Parent(*adapter._graph) {}
129      NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
130        : Parent(*adapter._graph, value) {}
131
132    private:
133      NodeMap& operator=(const NodeMap& cmap) {
134        return operator=<NodeMap>(cmap);
135      }
136
137      template <typename CMap>
138      NodeMap& operator=(const CMap& cmap) {
139        Parent::operator=(cmap);
140        return *this;
141      }
142     
143    };
144
145    template <typename _Value>
146    class ArcMap : public Graph::template ArcMap<_Value> {
147    public:
148      typedef typename Graph::template ArcMap<_Value> Parent;
149      explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
150        : Parent(*adapter._graph) {}
151      ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
152        : Parent(*adapter._graph, value) {}
153
154    private:
155      ArcMap& operator=(const ArcMap& cmap) {
156        return operator=<ArcMap>(cmap);
157      }
158
159      template <typename CMap>
160      ArcMap& operator=(const CMap& cmap) {
161        Parent::operator=(cmap);
162        return *this;
163      }
164    };
165
166    template <typename _Value>
167    class EdgeMap : public Graph::template EdgeMap<_Value> {
168    public:
169      typedef typename Graph::template EdgeMap<_Value> Parent;
170      explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
171        : Parent(*adapter._graph) {}
172      EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
173        : Parent(*adapter._graph, value) {}
174
175    private:
176      EdgeMap& operator=(const EdgeMap& cmap) {
177        return operator=<EdgeMap>(cmap);
178      }
179
180      template <typename CMap>
181      EdgeMap& operator=(const CMap& cmap) {
182        Parent::operator=(cmap);
183        return *this;
184      }
185    };
186
187  };
188
189  template <typename _Graph, typename NodeFilterMap,
190            typename EdgeFilterMap, bool checked = true>
191  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
192  public:
193    typedef _Graph Graph;
194    typedef SubGraphAdaptorBase Adaptor;
195    typedef GraphAdaptorBase<_Graph> Parent;
196  protected:
197
198    NodeFilterMap* _node_filter_map;
199    EdgeFilterMap* _edge_filter_map;
200
201    SubGraphAdaptorBase()
202      : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
203
204    void setNodeFilterMap(NodeFilterMap& node_filter_map) {
205      _node_filter_map=&node_filter_map;
206    }
207    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
208      _edge_filter_map=&edge_filter_map;
209    }
210
211  public:
212
213    typedef typename Parent::Node Node;
214    typedef typename Parent::Arc Arc;
215    typedef typename Parent::Edge Edge;
216
217    void first(Node& i) const {
218      Parent::first(i);
219      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
220    }
221
222    void first(Arc& i) const {
223      Parent::first(i);
224      while (i!=INVALID && (!(*_edge_filter_map)[i]
225             || !(*_node_filter_map)[Parent::source(i)]
226             || !(*_node_filter_map)[Parent::target(i)])) Parent::next(i);
227    }
228
229    void first(Edge& i) const {
230      Parent::first(i);
231      while (i!=INVALID && (!(*_edge_filter_map)[i]
232             || !(*_node_filter_map)[Parent::u(i)]
233             || !(*_node_filter_map)[Parent::v(i)])) Parent::next(i);
234    }
235
236    void firstIn(Arc& i, const Node& n) const {
237      Parent::firstIn(i, n);
238      while (i!=INVALID && (!(*_edge_filter_map)[i]
239             || !(*_node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
240    }
241
242    void firstOut(Arc& i, const Node& n) const {
243      Parent::firstOut(i, n);
244      while (i!=INVALID && (!(*_edge_filter_map)[i]
245             || !(*_node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
246    }
247
248    void firstInc(Edge& i, bool& d, const Node& n) const {
249      Parent::firstInc(i, d, n);
250      while (i!=INVALID && (!(*_edge_filter_map)[i]
251            || !(*_node_filter_map)[Parent::u(i)]
252            || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d);
253    }
254
255    void next(Node& i) const {
256      Parent::next(i);
257      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
258    }
259
260    void next(Arc& i) const {
261      Parent::next(i);
262      while (i!=INVALID && (!(*_edge_filter_map)[i]
263             || !(*_node_filter_map)[Parent::source(i)]
264             || !(*_node_filter_map)[Parent::target(i)])) Parent::next(i);
265    }
266
267    void next(Edge& i) const {
268      Parent::next(i);
269      while (i!=INVALID && (!(*_edge_filter_map)[i]
270             || !(*_node_filter_map)[Parent::u(i)]
271             || !(*_node_filter_map)[Parent::v(i)])) Parent::next(i);
272    }
273
274    void nextIn(Arc& i) const {
275      Parent::nextIn(i);
276      while (i!=INVALID && (!(*_edge_filter_map)[i]
277             || !(*_node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
278    }
279
280    void nextOut(Arc& i) const {
281      Parent::nextOut(i);
282      while (i!=INVALID && (!(*_edge_filter_map)[i]
283             || !(*_node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
284    }
285
286    void nextInc(Edge& i, bool& d) const {
287      Parent::nextInc(i, d);
288      while (i!=INVALID && (!(*_edge_filter_map)[i]
289            || !(*_node_filter_map)[Parent::u(i)]
290            || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d);
291    }
292
293    void hide(const Node& n) const { _node_filter_map->set(n, false); }
294    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
295
296    void unHide(const Node& n) const { _node_filter_map->set(n, true); }
297    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
298
299    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
300    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
301
302    typedef False NodeNumTag;
303    typedef False EdgeNumTag;
304
305    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
306    Arc findArc(const Node& u, const Node& v,
307                  const Arc& prev = INVALID) {
308      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
309        return INVALID;
310      }
311      Arc arc = Parent::findArc(u, v, prev);
312      while (arc != INVALID && !(*_edge_filter_map)[arc]) {
313        arc = Parent::findArc(u, v, arc);
314      }
315      return arc;
316    }
317    Edge findEdge(const Node& u, const Node& v,
318                  const Edge& prev = INVALID) {
319      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
320        return INVALID;
321      }
322      Edge edge = Parent::findEdge(u, v, prev);
323      while (edge != INVALID && !(*_edge_filter_map)[edge]) {
324        edge = Parent::findEdge(u, v, edge);
325      }
326      return edge;
327    }
328
329    template <typename _Value>
330    class NodeMap : public SubMapExtender<Adaptor,
331        typename Parent::template NodeMap<_Value> > {
332    public:
333      typedef _Value Value;
334      typedef SubMapExtender<Adaptor, typename Parent::
335                             template NodeMap<Value> > MapParent;
336   
337      NodeMap(const Adaptor& adaptor)
338        : MapParent(adaptor) {}
339      NodeMap(const Adaptor& adaptor, const Value& value)
340        : MapParent(adaptor, value) {}
341
342    private:
343      NodeMap& operator=(const NodeMap& cmap) {
344        return operator=<NodeMap>(cmap);
345      }
346   
347      template <typename CMap>
348      NodeMap& operator=(const CMap& cmap) {
349        MapParent::operator=(cmap);
350        return *this;
351      }
352    };
353
354    template <typename _Value>
355    class ArcMap : public SubMapExtender<Adaptor,
356        typename Parent::template ArcMap<_Value> > {
357    public:
358      typedef _Value Value;
359      typedef SubMapExtender<Adaptor, typename Parent::
360                             template ArcMap<Value> > MapParent;
361   
362      ArcMap(const Adaptor& adaptor)
363        : MapParent(adaptor) {}
364      ArcMap(const Adaptor& adaptor, const Value& value)
365        : MapParent(adaptor, value) {}
366
367    private:
368      ArcMap& operator=(const ArcMap& cmap) {
369        return operator=<ArcMap>(cmap);
370      }
371   
372      template <typename CMap>
373      ArcMap& operator=(const CMap& cmap) {
374        MapParent::operator=(cmap);
375        return *this;
376      }
377    };
378
379    template <typename _Value>
380    class EdgeMap : public SubMapExtender<Adaptor,
381        typename Parent::template EdgeMap<_Value> > {
382    public:
383      typedef _Value Value;
384      typedef SubMapExtender<Adaptor, typename Parent::
385                             template EdgeMap<Value> > MapParent;
386   
387      EdgeMap(const Adaptor& adaptor)
388        : MapParent(adaptor) {}
389
390      EdgeMap(const Adaptor& adaptor, const Value& value)
391        : MapParent(adaptor, value) {}
392
393    private:
394      EdgeMap& operator=(const EdgeMap& cmap) {
395        return operator=<EdgeMap>(cmap);
396      }
397   
398      template <typename CMap>
399      EdgeMap& operator=(const CMap& cmap) {
400        MapParent::operator=(cmap);
401        return *this;
402      }
403    };
404
405  };
406
407  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
408  class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
409    : public GraphAdaptorBase<_Graph> {
410  public:
411    typedef _Graph Graph;
412    typedef SubGraphAdaptorBase Adaptor;
413    typedef GraphAdaptorBase<_Graph> Parent;
414  protected:
415    NodeFilterMap* _node_filter_map;
416    EdgeFilterMap* _edge_filter_map;
417    SubGraphAdaptorBase() : Parent(),
418                            _node_filter_map(0), _edge_filter_map(0) { }
419
420    void setNodeFilterMap(NodeFilterMap& node_filter_map) {
421      _node_filter_map=&node_filter_map;
422    }
423    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
424      _edge_filter_map=&edge_filter_map;
425    }
426
427  public:
428
429    typedef typename Parent::Node Node;
430    typedef typename Parent::Arc Arc;
431    typedef typename Parent::Edge Edge;
432
433    void first(Node& i) const {
434      Parent::first(i);
435      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
436    }
437
438    void first(Arc& i) const {
439      Parent::first(i);
440      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
441    }
442
443    void first(Edge& i) const {
444      Parent::first(i);
445      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
446    }
447
448    void firstIn(Arc& i, const Node& n) const {
449      Parent::firstIn(i, n);
450      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
451    }
452
453    void firstOut(Arc& i, const Node& n) const {
454      Parent::firstOut(i, n);
455      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
456    }
457
458    void firstInc(Edge& i, bool& d, const Node& n) const {
459      Parent::firstInc(i, d, n);
460      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
461    }
462
463    void next(Node& i) const {
464      Parent::next(i);
465      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
466    }
467    void next(Arc& i) const {
468      Parent::next(i);
469      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
470    }
471    void next(Edge& i) const {
472      Parent::next(i);
473      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
474    }
475    void nextIn(Arc& i) const {
476      Parent::nextIn(i);
477      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
478    }
479
480    void nextOut(Arc& i) const {
481      Parent::nextOut(i);
482      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
483    }
484    void nextInc(Edge& i, bool& d) const {
485      Parent::nextInc(i, d);
486      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
487    }
488
489    void hide(const Node& n) const { _node_filter_map->set(n, false); }
490    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
491
492    void unHide(const Node& n) const { _node_filter_map->set(n, true); }
493    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
494
495    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
496    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
497
498    typedef False NodeNumTag;
499    typedef False EdgeNumTag;
500
501    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
502    Arc findArc(const Node& u, const Node& v,
503                  const Arc& prev = INVALID) {
504      Arc arc = Parent::findArc(u, v, prev);
505      while (arc != INVALID && !(*_edge_filter_map)[arc]) {
506        arc = Parent::findArc(u, v, arc);
507      }
508      return arc;
509    }
510    Edge findEdge(const Node& u, const Node& v,
511                  const Edge& prev = INVALID) {
512      Edge edge = Parent::findEdge(u, v, prev);
513      while (edge != INVALID && !(*_edge_filter_map)[edge]) {
514        edge = Parent::findEdge(u, v, edge);
515      }
516      return edge;
517    }
518
519    template <typename _Value>
520    class NodeMap : public SubMapExtender<Adaptor,
521        typename Parent::template NodeMap<_Value> > {
522    public:
523      typedef _Value Value;
524      typedef SubMapExtender<Adaptor, typename Parent::
525                             template NodeMap<Value> > MapParent;
526   
527      NodeMap(const Adaptor& adaptor)
528        : MapParent(adaptor) {}
529      NodeMap(const Adaptor& adaptor, const Value& value)
530        : MapParent(adaptor, value) {}
531   
532    private:
533      NodeMap& operator=(const NodeMap& cmap) {
534        return operator=<NodeMap>(cmap);
535      }
536   
537      template <typename CMap>
538      NodeMap& operator=(const CMap& cmap) {
539        MapParent::operator=(cmap);
540        return *this;
541      }
542    };
543
544    template <typename _Value>
545    class ArcMap : public SubMapExtender<Adaptor,
546        typename Parent::template ArcMap<_Value> > {
547    public:
548      typedef _Value Value;
549      typedef SubMapExtender<Adaptor, typename Parent::
550                             template ArcMap<Value> > MapParent;
551   
552      ArcMap(const Adaptor& adaptor)
553        : MapParent(adaptor) {}
554      ArcMap(const Adaptor& adaptor, const Value& value)
555        : MapParent(adaptor, value) {}
556
557    private:
558      ArcMap& operator=(const ArcMap& cmap) {
559        return operator=<ArcMap>(cmap);
560      }
561   
562      template <typename CMap>
563      ArcMap& operator=(const CMap& cmap) {
564        MapParent::operator=(cmap);
565        return *this;
566      }
567    };
568
569    template <typename _Value>
570    class EdgeMap : public SubMapExtender<Adaptor,
571        typename Parent::template EdgeMap<_Value> > {
572    public:
573      typedef _Value Value;
574      typedef SubMapExtender<Adaptor, typename Parent::
575                             template EdgeMap<Value> > MapParent;
576   
577      EdgeMap(const Adaptor& adaptor)
578        : MapParent(adaptor) {}
579
580      EdgeMap(const Adaptor& adaptor, const _Value& value)
581        : MapParent(adaptor, value) {}
582
583    private:
584      EdgeMap& operator=(const EdgeMap& cmap) {
585        return operator=<EdgeMap>(cmap);
586      }
587   
588      template <typename CMap>
589      EdgeMap& operator=(const CMap& cmap) {
590        MapParent::operator=(cmap);
591        return *this;
592      }
593    };
594
595  };
596
597  /// \ingroup graph_adaptors
598  ///
599  /// \brief A graph adaptor for hiding nodes and edges from an
600  /// undirected graph.
601  ///
602  /// SubGraphAdaptor shows the graph with filtered node-set and
603  /// edge-set. If the \c checked parameter is true then it filters
604  /// the edge-set to do not get invalid edges which incident node is
605  /// filtered.
606  ///
607  /// If the \c checked template parameter is false then we have to
608  /// note that the node-iterator cares only the filter on the
609  /// node-set, and the edge-iterator cares only the filter on the
610  /// edge-set.  This way the edge-map should filter all arcs which
611  /// has filtered end node.
612  template<typename _Graph, typename NodeFilterMap,
613           typename EdgeFilterMap, bool checked = true>
614  class SubGraphAdaptor :
615    public GraphAdaptorExtender<
616    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
617  public:
618    typedef _Graph Graph;
619    typedef GraphAdaptorExtender<
620      SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
621
622    typedef typename Parent::Node Node;
623    typedef typename Parent::Edge Edge;
624
625  protected:
626    SubGraphAdaptor() { }
627  public:
628   
629    /// \brief Constructor
630    ///
631    /// Creates a sub-graph-adaptor for the given graph with
632    /// given node and edge map filters.
633    SubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map,
634                    EdgeFilterMap& edge_filter_map) {
635      setGraph(_graph);
636      setNodeFilterMap(node_filter_map);
637      setEdgeFilterMap(edge_filter_map);
638    }
639
640    /// \brief Hides the node of the graph
641    ///
642    /// This function hides \c n in the digraph, i.e. the iteration
643    /// jumps over it. This is done by simply setting the value of \c n 
644    /// to be false in the corresponding node-map.
645    void hide(const Node& n) const { Parent::hide(n); }
646
647    /// \brief Hides the edge of the graph
648    ///
649    /// This function hides \c e in the digraph, i.e. the iteration
650    /// jumps over it. This is done by simply setting the value of \c e
651    /// to be false in the corresponding edge-map.
652    void hide(const Edge& e) const { Parent::hide(e); }
653
654    /// \brief Unhides the node of the graph
655    ///
656    /// The value of \c n is set to be true in the node-map which stores
657    /// hide information. If \c n was hidden previuosly, then it is shown
658    /// again
659    void unHide(const Node& n) const { Parent::unHide(n); }
660
661    /// \brief Unhides the edge of the graph
662    ///
663    /// The value of \c e is set to be true in the edge-map which stores
664    /// hide information. If \c e was hidden previuosly, then it is shown
665    /// again
666    void unHide(const Edge& e) const { Parent::unHide(e); }
667
668    /// \brief Returns true if \c n is hidden.
669    ///
670    /// Returns true if \c n is hidden.
671    ///
672    bool hidden(const Node& n) const { return Parent::hidden(n); }
673
674    /// \brief Returns true if \c e is hidden.
675    ///
676    /// Returns true if \c e is hidden.
677    ///
678    bool hidden(const Edge& e) const { return Parent::hidden(e); }
679  };
680
681  /// \brief Just gives back a sub-graph adaptor
682  ///
683  /// Just gives back a sub-graph adaptor
684  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
685  SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>
686  subGraphAdaptor(const Graph& graph,
687                   NodeFilterMap& nfm, ArcFilterMap& efm) {
688    return SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>
689      (graph, nfm, efm);
690  }
691
692  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
693  SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap>
694  subGraphAdaptor(const Graph& graph,
695                   NodeFilterMap& nfm, ArcFilterMap& efm) {
696    return SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap>
697      (graph, nfm, efm);
698  }
699
700  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
701  SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap>
702  subGraphAdaptor(const Graph& graph,
703                   NodeFilterMap& nfm, ArcFilterMap& efm) {
704    return SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap>
705      (graph, nfm, efm);
706  }
707
708  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
709  SubGraphAdaptor<const Graph, const NodeFilterMap, const ArcFilterMap>
710  subGraphAdaptor(const Graph& graph,
711                   NodeFilterMap& nfm, ArcFilterMap& efm) {
712    return SubGraphAdaptor<const Graph, const NodeFilterMap,
713      const ArcFilterMap>(graph, nfm, efm);
714  }
715
716  /// \ingroup graph_adaptors
717  ///
718  /// \brief An adaptor for hiding nodes from an graph.
719  ///
720  /// An adaptor for hiding nodes from an graph.  This
721  /// adaptor specializes SubGraphAdaptor in the way that only the
722  /// node-set can be filtered. In usual case the checked parameter is
723  /// true, we get the induced subgraph. But if the checked parameter
724  /// is false then we can filter only isolated nodes.
725  template<typename _Graph, typename _NodeFilterMap, bool checked = true>
726  class NodeSubGraphAdaptor :
727    public SubGraphAdaptor<_Graph, _NodeFilterMap,
728                           ConstMap<typename _Graph::Edge, bool>, checked> {
729  public:
730    typedef _Graph Graph;
731    typedef _NodeFilterMap NodeFilterMap;
732    typedef SubGraphAdaptor<Graph, NodeFilterMap,
733                            ConstMap<typename Graph::Edge, bool> > Parent;
734
735    typedef typename Parent::Node Node;
736  protected:
737    ConstMap<typename Graph::Edge, bool> const_true_map;
738
739    NodeSubGraphAdaptor() : const_true_map(true) {
740      Parent::setEdgeFilterMap(const_true_map);
741    }
742
743  public:
744
745    /// \brief Constructor
746    ///
747    /// Creates a node-sub-graph-adaptor for the given graph with
748    /// given node map filters.
749    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map) :
750      Parent(), const_true_map(true) {
751      Parent::setGraph(_graph);
752      Parent::setNodeFilterMap(node_filter_map);
753      Parent::setEdgeFilterMap(const_true_map);
754    }
755
756    /// \brief Hides the node of the graph
757    ///
758    /// This function hides \c n in the digraph, i.e. the iteration
759    /// jumps over it. This is done by simply setting the value of \c n 
760    /// to be false in the corresponding node-map.
761    void hide(const Node& n) const { Parent::hide(n); }
762
763    /// \brief Unhides the node of the graph
764    ///
765    /// The value of \c n is set to be true in the node-map which stores
766    /// hide information. If \c n was hidden previuosly, then it is shown
767    /// again
768    void unHide(const Node& n) const { Parent::unHide(n); }
769
770    /// \brief Returns true if \c n is hidden.
771    ///
772    /// Returns true if \c n is hidden.
773    ///
774    bool hidden(const Node& n) const { return Parent::hidden(n); }
775
776  };
777
778  /// \brief Just gives back a node-sub-graph adaptor
779  ///
780  /// Just gives back a node-sub-graph adaptor
781  template<typename Graph, typename NodeFilterMap>
782  NodeSubGraphAdaptor<const Graph, NodeFilterMap>
783  nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
784    return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
785  }
786
787  template<typename Graph, typename NodeFilterMap>
788  NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
789  nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
790    return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
791  }
792
793  /// \ingroup graph_adaptors
794  ///
795  /// \brief An adaptor for hiding edges from an graph.
796  ///
797  /// \warning Graph adaptors are in even more experimental state
798  /// than the other parts of the lib. Use them at you own risk.
799  ///
800  /// An adaptor for hiding edges from an graph.
801  /// This adaptor specializes SubGraphAdaptor in the way that
802  /// only the arc-set
803  /// can be filtered.
804  template<typename _Graph, typename _EdgeFilterMap>
805  class EdgeSubGraphAdaptor :
806    public SubGraphAdaptor<_Graph, ConstMap<typename _Graph::Node,bool>,
807                           _EdgeFilterMap, false> {
808  public:
809    typedef _Graph Graph;
810    typedef _EdgeFilterMap EdgeFilterMap;
811    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
812                            EdgeFilterMap, false> Parent;
813    typedef typename Parent::Edge Edge;
814  protected:
815    ConstMap<typename Graph::Node, bool> const_true_map;
816
817    EdgeSubGraphAdaptor() : const_true_map(true) {
818      Parent::setNodeFilterMap(const_true_map);
819    }
820
821  public:
822
823    /// \brief Constructor
824    ///
825    /// Creates a edge-sub-graph-adaptor for the given graph with
826    /// given node map filters.
827    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& edge_filter_map) :
828      Parent(), const_true_map(true) {
829      Parent::setGraph(_graph);
830      Parent::setNodeFilterMap(const_true_map);
831      Parent::setEdgeFilterMap(edge_filter_map);
832    }
833
834    /// \brief Hides the edge of the graph
835    ///
836    /// This function hides \c e in the digraph, i.e. the iteration
837    /// jumps over it. This is done by simply setting the value of \c e
838    /// to be false in the corresponding edge-map.
839    void hide(const Edge& e) const { Parent::hide(e); }
840
841    /// \brief Unhides the edge of the graph
842    ///
843    /// The value of \c e is set to be true in the edge-map which stores
844    /// hide information. If \c e was hidden previuosly, then it is shown
845    /// again
846    void unHide(const Edge& e) const { Parent::unHide(e); }
847
848    /// \brief Returns true if \c e is hidden.
849    ///
850    /// Returns true if \c e is hidden.
851    ///
852    bool hidden(const Edge& e) const { return Parent::hidden(e); }
853
854  };
855
856  /// \brief Just gives back an edge-sub-graph adaptor
857  ///
858  /// Just gives back an edge-sub-graph adaptor
859  template<typename Graph, typename EdgeFilterMap>
860  EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
861  edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
862    return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
863  }
864
865  template<typename Graph, typename EdgeFilterMap>
866  EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
867  edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
868    return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
869  }
870
871  template <typename _Graph, typename _DirectionMap>
872  class DirGraphAdaptorBase {
873  public:
874   
875    typedef _Graph Graph;
876    typedef _DirectionMap DirectionMap;
877
878    typedef typename Graph::Node Node;
879    typedef typename Graph::Edge Arc;
880   
881    /// \brief Reverse arc
882    ///
883    /// It reverse the given arc. It simply negate the direction in the map.
884    void reverseArc(const Arc& arc) {
885      _direction->set(arc, !(*_direction)[arc]);
886    }
887
888    void first(Node& i) const { _graph->first(i); }
889    void first(Arc& i) const { _graph->first(i); }
890    void firstIn(Arc& i, const Node& n) const {
891      bool d;
892      _graph->firstInc(i, d, n);
893      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
894    }
895    void firstOut(Arc& i, const Node& n ) const {
896      bool d;
897      _graph->firstInc(i, d, n);
898      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
899    }
900
901    void next(Node& i) const { _graph->next(i); }
902    void next(Arc& i) const { _graph->next(i); }
903    void nextIn(Arc& i) const {
904      bool d = !(*_direction)[i];
905      _graph->nextInc(i, d);
906      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
907    }
908    void nextOut(Arc& i) const {
909      bool d = (*_direction)[i];
910      _graph->nextInc(i, d);
911      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
912    }
913
914    Node source(const Arc& e) const {
915      return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
916    }
917    Node target(const Arc& e) const {
918      return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
919    }
920
921    typedef NodeNumTagIndicator<Graph> NodeNumTag;
922    int nodeNum() const { return _graph->nodeNum(); }
923   
924    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
925    int arcNum() const { return _graph->edgeNum(); }
926
927    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
928    Arc findArc(const Node& u, const Node& v,
929                  const Arc& prev = INVALID) {
930      Arc arc = prev;
931      bool d = arc == INVALID ? true : (*_direction)[arc];
932      if (d) {
933        arc = _graph->findEdge(u, v, arc);
934        while (arc != INVALID && !(*_direction)[arc]) {
935          _graph->findEdge(u, v, arc);
936        }
937        if (arc != INVALID) return arc;
938      }
939      _graph->findEdge(v, u, arc);
940      while (arc != INVALID && (*_direction)[arc]) {
941        _graph->findEdge(u, v, arc);
942      }
943      return arc;
944    }
945 
946    Node addNode() {
947      return Node(_graph->addNode());
948    }
949
950    Arc addArc(const Node& u, const Node& v) {
951      Arc arc = _graph->addArc(u, v);
952      _direction->set(arc, _graph->source(arc) == u);
953      return arc;
954    }
955
956    void erase(const Node& i) { _graph->erase(i); }
957    void erase(const Arc& i) { _graph->erase(i); }
958 
959    void clear() { _graph->clear(); }
960   
961    int id(const Node& v) const { return _graph->id(v); }
962    int id(const Arc& e) const { return _graph->id(e); }
963
964    Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
965    Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
966
967    int maxNodeId() const { return _graph->maxNodeId(); }
968    int maxArcId() const { return _graph->maxEdgeId(); }
969
970    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
971    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
972
973    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
974    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
975
976    template <typename _Value>
977    class NodeMap : public _Graph::template NodeMap<_Value> {
978    public:
979
980      typedef typename _Graph::template NodeMap<_Value> Parent;
981
982      explicit NodeMap(const DirGraphAdaptorBase& adapter)
983        : Parent(*adapter._graph) {}
984
985      NodeMap(const DirGraphAdaptorBase& adapter, const _Value& value)
986        : Parent(*adapter._graph, value) {}
987
988    private:
989      NodeMap& operator=(const NodeMap& cmap) {
990        return operator=<NodeMap>(cmap);
991      }
992
993      template <typename CMap>
994      NodeMap& operator=(const CMap& cmap) {
995        Parent::operator=(cmap);
996        return *this;
997      }
998
999    };
1000
1001    template <typename _Value>
1002    class ArcMap : public _Graph::template EdgeMap<_Value> {
1003    public:
1004
1005      typedef typename Graph::template EdgeMap<_Value> Parent;
1006
1007      explicit ArcMap(const DirGraphAdaptorBase& adapter)
1008        : Parent(*adapter._graph) { }
1009
1010      ArcMap(const DirGraphAdaptorBase& adapter, const _Value& value)
1011        : Parent(*adapter._graph, value) { }
1012
1013    private:
1014      ArcMap& operator=(const ArcMap& cmap) {
1015        return operator=<ArcMap>(cmap);
1016      }
1017
1018      template <typename CMap>
1019      ArcMap& operator=(const CMap& cmap) {
1020        Parent::operator=(cmap);
1021        return *this;
1022      }
1023    };
1024
1025   
1026
1027  protected:
1028    Graph* _graph;
1029    DirectionMap* _direction;
1030
1031    void setDirectionMap(DirectionMap& direction) {
1032      _direction = &direction;
1033    }
1034
1035    void setGraph(Graph& graph) {
1036      _graph = &graph;
1037    }
1038
1039  };
1040
1041
1042  /// \ingroup graph_adaptors
1043  ///
1044  /// \brief A directed graph is made from an graph by an adaptor
1045  ///
1046  /// This adaptor gives a direction for each edge in the undirected
1047  /// graph. The direction of the arcs stored in the
1048  /// DirectionMap. This map is a bool map on the edges. If
1049  /// the edge is mapped to true then the direction of the directed
1050  /// arc will be the same as the default direction of the edge. The
1051  /// arcs can be easily reverted by the \ref
1052  /// DirGraphAdaptorBase::reverseArc "reverseArc()" member in the
1053  /// adaptor.
1054  ///
1055  /// It can be used to solve orientation problems on directed graphs.
1056  /// For example how can we orient an graph to get the minimum
1057  /// number of strongly connected components. If we orient the arcs with
1058  /// the dfs algorithm out from the source then we will get such an
1059  /// orientation.
1060  ///
1061  /// We use the \ref DfsVisitor "visitor" interface of the
1062  /// \ref DfsVisit "dfs" algorithm:
1063  ///\code
1064  /// template <typename DirMap>
1065  /// class OrientVisitor : public DfsVisitor<Graph> {
1066  /// public:
1067  ///
1068  ///   OrientVisitor(const Graph& graph, DirMap& dirMap)
1069  ///     : _graph(graph), _dirMap(dirMap), _processed(graph, false) {}
1070  ///
1071  ///   void discover(const Arc& arc) {
1072  ///     _processed.set(arc, true);
1073  ///     _dirMap.set(arc, _graph.direction(arc));
1074  ///   }
1075  ///
1076  ///   void examine(const Arc& arc) {
1077  ///     if (_processed[arc]) return;
1078  ///     _processed.set(arc, true);
1079  ///     _dirMap.set(arc, _graph.direction(arc));
1080  ///   } 
1081  ///
1082  /// private:
1083  ///   const Graph& _graph; 
1084  ///   DirMap& _dirMap;
1085  ///   Graph::EdgeMap<bool> _processed;
1086  /// };
1087  ///\endcode
1088  ///
1089  /// And now we can use the orientation:
1090  ///\code
1091  /// Graph::EdgeMap<bool> dmap(graph);
1092  ///
1093  /// typedef OrientVisitor<Graph::EdgeMap<bool> > Visitor;
1094  /// Visitor visitor(graph, dmap);
1095  ///
1096  /// DfsVisit<Graph, Visitor> dfs(graph, visitor);
1097  ///
1098  /// dfs.run();
1099  ///
1100  /// typedef DirGraphAdaptor<Graph> DGraph;
1101  /// DGraph dgraph(graph, dmap);
1102  ///
1103  /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) ==
1104  ///              countBiArcConnectedComponents(graph), "Wrong Orientation");
1105  ///\endcode
1106  ///
1107  /// The number of the bi-connected components is a lower bound for
1108  /// the number of the strongly connected components in the directed
1109  /// graph because if we contract the bi-connected components to
1110  /// nodes we will get a tree therefore we cannot orient arcs in
1111  /// both direction between bi-connected components. In the other way
1112  /// the algorithm will orient one component to be strongly
1113  /// connected. The two relations proof that the assertion will
1114  /// be always true and the found solution is optimal.
1115  ///
1116  /// \sa DirGraphAdaptorBase
1117  /// \sa dirGraphAdaptor
1118  template<typename _Graph,
1119           typename DirectionMap = typename _Graph::template EdgeMap<bool> >
1120  class DirGraphAdaptor :
1121    public DigraphAdaptorExtender<DirGraphAdaptorBase<_Graph, DirectionMap> > {
1122  public:
1123    typedef _Graph Graph;
1124    typedef DigraphAdaptorExtender<
1125      DirGraphAdaptorBase<_Graph, DirectionMap> > Parent;
1126    typedef typename Parent::Arc Arc;
1127  protected:
1128    DirGraphAdaptor() { }
1129  public:
1130   
1131    /// \brief Constructor of the adaptor
1132    ///
1133    /// Constructor of the adaptor
1134    DirGraphAdaptor(Graph& graph, DirectionMap& direction) {
1135      setGraph(graph);
1136      setDirectionMap(direction);
1137    }
1138
1139    /// \brief Reverse arc
1140    ///
1141    /// It reverse the given arc. It simply negate the direction in the map.
1142    void reverseArc(const Arc& a) {
1143      Parent::reverseArc(a);
1144    }
1145  };
1146
1147  /// \brief Just gives back a DirGraphAdaptor
1148  ///
1149  /// Just gives back a DirGraphAdaptor
1150  template<typename Graph, typename DirectionMap>
1151  DirGraphAdaptor<const Graph, DirectionMap>
1152  dirGraphAdaptor(const Graph& graph, DirectionMap& dm) {
1153    return DirGraphAdaptor<const Graph, DirectionMap>(graph, dm);
1154  }
1155
1156  template<typename Graph, typename DirectionMap>
1157  DirGraphAdaptor<const Graph, const DirectionMap>
1158  dirGraphAdaptor(const Graph& graph, const DirectionMap& dm) {
1159    return DirGraphAdaptor<const Graph, const DirectionMap>(graph, dm);
1160  }
1161
1162}
1163
1164#endif
Note: See TracBrowser for help on using the repository browser.