gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
Merge
0 3 0
merge default
3 files changed with 1036 insertions and 778 deletions:
↑ Collapse diff ↑
Ignore white space 6 line context
... ...
@@ -59,79 +59,82 @@
59 59
with any graph structure.
60 60

	
61 61
<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
62 62
*/
63 63

	
64 64
/**
65
@defgroup graph_adaptors Adaptor Classes for graphs
65
@defgroup graph_adaptors Adaptor Classes for Graphs
66 66
@ingroup graphs
67
\brief This group contains several adaptor classes for digraphs and graphs
67
\brief Adaptor classes for digraphs and graphs
68

	
69
This group contains several useful adaptor classes for digraphs and graphs.
68 70

	
69 71
The main parts of LEMON are the different graph structures, generic
70
graph algorithms, graph concepts which couple these, and graph
72
graph algorithms, graph concepts, which couple them, and graph
71 73
adaptors. While the previous notions are more or less clear, the
72 74
latter one needs further explanation. Graph adaptors are graph classes
73 75
which serve for considering graph structures in different ways.
74 76

	
75 77
A short example makes this much clearer.  Suppose that we have an
76
instance \c g of a directed graph type say ListDigraph and an algorithm
78
instance \c g of a directed graph type, say ListDigraph and an algorithm
77 79
\code
78 80
template <typename Digraph>
79 81
int algorithm(const Digraph&);
80 82
\endcode
81 83
is needed to run on the reverse oriented graph.  It may be expensive
82 84
(in time or in memory usage) to copy \c g with the reversed
83 85
arcs.  In this case, an adaptor class is used, which (according
84
to LEMON digraph concepts) works as a digraph.  The adaptor uses the
85
original digraph structure and digraph operations when methods of the
86
reversed oriented graph are called.  This means that the adaptor have
87
minor memory usage, and do not perform sophisticated algorithmic
86
to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
87
The adaptor uses the original digraph structure and digraph operations when
88
methods of the reversed oriented graph are called.  This means that the adaptor
89
have minor memory usage, and do not perform sophisticated algorithmic
88 90
actions.  The purpose of it is to give a tool for the cases when a
89 91
graph have to be used in a specific alteration.  If this alteration is
90
obtained by a usual construction like filtering the arc-set or
92
obtained by a usual construction like filtering the node or the arc set or
91 93
considering a new orientation, then an adaptor is worthwhile to use.
92 94
To come back to the reverse oriented graph, in this situation
93 95
\code
94 96
template<typename Digraph> class ReverseDigraph;
95 97
\endcode
96 98
template class can be used. The code looks as follows
97 99
\code
98 100
ListDigraph g;
99
ReverseDigraph<ListGraph> rg(g);
101
ReverseDigraph<ListDigraph> rg(g);
100 102
int result = algorithm(rg);
101 103
\endcode
102
After running the algorithm, the original graph \c g is untouched.
103
This techniques gives rise to an elegant code, and based on stable
104
During running the algorithm, the original digraph \c g is untouched.
105
This techniques give rise to an elegant code, and based on stable
104 106
graph adaptors, complex algorithms can be implemented easily.
105 107

	
106
In flow, circulation and bipartite matching problems, the residual
108
In flow, circulation and matching problems, the residual
107 109
graph is of particular importance. Combining an adaptor implementing
108
this, shortest path algorithms and minimum mean cycle algorithms,
110
this with shortest path algorithms or minimum mean cycle algorithms,
109 111
a range of weighted and cardinality optimization algorithms can be
110 112
obtained. For other examples, the interested user is referred to the
111 113
detailed documentation of particular adaptors.
112 114

	
113 115
The behavior of graph adaptors can be very different. Some of them keep
114 116
capabilities of the original graph while in other cases this would be
115
meaningless. This means that the concepts that they are models of depend
116
on the graph adaptor, and the wrapped graph(s).
117
If an arc of \c rg is deleted, this is carried out by deleting the
118
corresponding arc of \c g, thus the adaptor modifies the original graph.
117
meaningless. This means that the concepts that they meet depend
118
on the graph adaptor, and the wrapped graph.
119
For example, if an arc of a reversed digraph is deleted, this is carried
120
out by deleting the corresponding arc of the original digraph, thus the
121
adaptor modifies the original digraph.
122
However in case of a residual digraph, this operation has no sense.
119 123

	
120
But for a residual graph, this operation has no sense.
121 124
Let us stand one more example here to simplify your work.
122
RevGraphAdaptor has constructor
125
ReverseDigraph has constructor
123 126
\code
124 127
ReverseDigraph(Digraph& digraph);
125 128
\endcode
126
This means that in a situation, when a <tt>const ListDigraph&</tt>
129
This means that in a situation, when a <tt>const %ListDigraph&</tt>
127 130
reference to a graph is given, then it have to be instantiated with
128
<tt>Digraph=const ListDigraph</tt>.
131
<tt>Digraph=const %ListDigraph</tt>.
129 132
\code
130 133
int algorithm1(const ListDigraph& g) {
131
  RevGraphAdaptor<const ListDigraph> rg(g);
134
  ReverseDigraph<const ListDigraph> rg(g);
132 135
  return algorithm2(rg);
133 136
}
134 137
\endcode
135 138
*/
136 139

	
137 140
/**
Ignore white space 12 line context
... ...
@@ -18,13 +18,13 @@
18 18

	
19 19
#ifndef LEMON_ADAPTORS_H
20 20
#define LEMON_ADAPTORS_H
21 21

	
22 22
/// \ingroup graph_adaptors
23 23
/// \file
24
/// \brief Several graph adaptors
24
/// \brief Adaptor classes for digraphs and graphs
25 25
///
26 26
/// This file contains several useful adaptors for digraphs and graphs.
27 27

	
28 28
#include <lemon/core.h>
29 29
#include <lemon/maps.h>
30 30
#include <lemon/bits/variant.h>
... ...
@@ -67,27 +67,27 @@
67 67
    Node source(const Arc& a) const { return _digraph->source(a); }
68 68
    Node target(const Arc& a) const { return _digraph->target(a); }
69 69

	
70 70
    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
71 71
    int nodeNum() const { return _digraph->nodeNum(); }
72 72

	
73
    typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
73
    typedef ArcNumTagIndicator<Digraph> ArcNumTag;
74 74
    int arcNum() const { return _digraph->arcNum(); }
75 75

	
76
    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
77
    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
76
    typedef FindArcTagIndicator<Digraph> FindArcTag;
77
    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {
78 78
      return _digraph->findArc(u, v, prev);
79 79
    }
80 80

	
81 81
    Node addNode() { return _digraph->addNode(); }
82 82
    Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
83 83

	
84
    void erase(const Node& n) const { _digraph->erase(n); }
85
    void erase(const Arc& a) const { _digraph->erase(a); }
86

	
87
    void clear() const { _digraph->clear(); }
84
    void erase(const Node& n) { _digraph->erase(n); }
85
    void erase(const Arc& a) { _digraph->erase(a); }
86

	
87
    void clear() { _digraph->clear(); }
88 88

	
89 89
    int id(const Node& n) const { return _digraph->id(n); }
90 90
    int id(const Arc& a) const { return _digraph->id(a); }
91 91

	
92 92
    Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
93 93
    Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
... ...
@@ -195,21 +195,27 @@
195 195
    Node source(const Arc& a) const { return _graph->source(a); }
196 196
    Node target(const Arc& a) const { return _graph->target(a); }
197 197

	
198 198
    typedef NodeNumTagIndicator<Graph> NodeNumTag;
199 199
    int nodeNum() const { return _graph->nodeNum(); }
200 200

	
201
    typedef ArcNumTagIndicator<Graph> ArcNumTag;
202
    int arcNum() const { return _graph->arcNum(); }
203

	
201 204
    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
202
    int arcNum() const { return _graph->arcNum(); }
203 205
    int edgeNum() const { return _graph->edgeNum(); }
204 206

	
205
    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
206
    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
207
    typedef FindArcTagIndicator<Graph> FindArcTag;
208
    Arc findArc(const Node& u, const Node& v,
209
                const Arc& prev = INVALID) const {
207 210
      return _graph->findArc(u, v, prev);
208 211
    }
209
    Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
212

	
213
    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
214
    Edge findEdge(const Node& u, const Node& v,
215
                  const Edge& prev = INVALID) const {
210 216
      return _graph->findEdge(u, v, prev);
211 217
    }
212 218

	
213 219
    Node addNode() { return _graph->addNode(); }
214 220
    Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
215 221

	
... ...
@@ -327,57 +333,72 @@
327 333

	
328 334
    Node source(const Arc& a) const { return Parent::target(a); }
329 335
    Node target(const Arc& a) const { return Parent::source(a); }
330 336

	
331 337
    Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
332 338

	
333
    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
339
    typedef FindArcTagIndicator<Digraph> FindArcTag;
334 340
    Arc findArc(const Node& u, const Node& v,
335
                const Arc& prev = INVALID) {
341
                const Arc& prev = INVALID) const {
336 342
      return Parent::findArc(v, u, prev);
337 343
    }
338 344

	
339 345
  };
340 346

	
341 347
  /// \ingroup graph_adaptors
342 348
  ///
343
  /// \brief A digraph adaptor which reverses the orientation of the arcs.
349
  /// \brief Adaptor class for reversing the orientation of the arcs in
350
  /// a digraph.
344 351
  ///
345
  /// ReverseDigraph reverses the arcs in the adapted digraph. The
346
  /// SubDigraph is conform to the \ref concepts::Digraph
347
  /// "Digraph concept".
352
  /// ReverseDigraph can be used for reversing the arcs in a digraph.
353
  /// It conforms to the \ref concepts::Digraph "Digraph" concept.
348 354
  ///
349
  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
350
  /// "Digraph concept". The type can be specified to be const.
351
  template<typename _Digraph>
355
  /// The adapted digraph can also be modified through this adaptor
356
  /// by adding or removing nodes or arcs, unless the \c GR template
357
  /// parameter is set to be \c const.
358
  ///
359
  /// \tparam GR The type of the adapted digraph.
360
  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
361
  /// It can also be specified to be \c const.
362
  ///
363
  /// \note The \c Node and \c Arc types of this adaptor and the adapted
364
  /// digraph are convertible to each other.
365
  template<typename GR>
366
#ifdef DOXYGEN
367
  class ReverseDigraph {
368
#else
352 369
  class ReverseDigraph :
353
    public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {
370
    public DigraphAdaptorExtender<ReverseDigraphBase<GR> > {
371
#endif
354 372
  public:
355
    typedef _Digraph Digraph;
356
    typedef DigraphAdaptorExtender<
357
      ReverseDigraphBase<_Digraph> > Parent;
373
    /// The type of the adapted digraph.
374
    typedef GR Digraph;
375
    typedef DigraphAdaptorExtender<ReverseDigraphBase<GR> > Parent;
358 376
  protected:
359 377
    ReverseDigraph() { }
360 378
  public:
361 379

	
362 380
    /// \brief Constructor
363 381
    ///
364
    /// Creates a reverse digraph adaptor for the given digraph
382
    /// Creates a reverse digraph adaptor for the given digraph.
365 383
    explicit ReverseDigraph(Digraph& digraph) {
366 384
      Parent::setDigraph(digraph);
367 385
    }
368 386
  };
369 387

	
370
  /// \brief Just gives back a reverse digraph adaptor
388
  /// \brief Returns a read-only ReverseDigraph adaptor
371 389
  ///
372
  /// Just gives back a reverse digraph adaptor
373
  template<typename Digraph>
374
  ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {
375
    return ReverseDigraph<const Digraph>(digraph);
390
  /// This function just returns a read-only \ref ReverseDigraph adaptor.
391
  /// \ingroup graph_adaptors
392
  /// \relates ReverseDigraph
393
  template<typename GR>
394
  ReverseDigraph<const GR> reverseDigraph(const GR& digraph) {
395
    return ReverseDigraph<const GR>(digraph);
376 396
  }
377 397

	
398

	
378 399
  template <typename _Digraph, typename _NodeFilterMap,
379 400
            typename _ArcFilterMap, bool _checked = true>
380 401
  class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
381 402
  public:
382 403
    typedef _Digraph Digraph;
383 404
    typedef _NodeFilterMap NodeFilterMap;
... ...
@@ -454,27 +475,24 @@
454 475
      Parent::nextOut(i);
455 476
      while (i != INVALID && (!(*_arc_filter)[i]
456 477
                              || !(*_node_filter)[Parent::target(i)]))
457 478
        Parent::nextOut(i);
458 479
    }
459 480

	
460
    void hide(const Node& n) const { _node_filter->set(n, false); }
461
    void hide(const Arc& a) const { _arc_filter->set(a, false); }
462

	
463
    void unHide(const Node& n) const { _node_filter->set(n, true); }
464
    void unHide(const Arc& a) const { _arc_filter->set(a, true); }
465

	
466
    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
467
    bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
481
    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
482
    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
483

	
484
    bool status(const Node& n) const { return (*_node_filter)[n]; }
485
    bool status(const Arc& a) const { return (*_arc_filter)[a]; }
468 486

	
469 487
    typedef False NodeNumTag;
470
    typedef False EdgeNumTag;
471

	
472
    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
488
    typedef False ArcNumTag;
489

	
490
    typedef FindArcTagIndicator<Digraph> FindArcTag;
473 491
    Arc findArc(const Node& source, const Node& target,
474
                const Arc& prev = INVALID) {
492
                const Arc& prev = INVALID) const {
475 493
      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
476 494
        return INVALID;
477 495
      }
478 496
      Arc arc = Parent::findArc(source, target, prev);
479 497
      while (arc != INVALID && !(*_arc_filter)[arc]) {
480 498
        arc = Parent::findArc(source, target, arc);
... ...
@@ -597,27 +615,24 @@
597 615

	
598 616
    void nextOut(Arc& i) const {
599 617
      Parent::nextOut(i);
600 618
      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
601 619
    }
602 620

	
603
    void hide(const Node& n) const { _node_filter->set(n, false); }
604
    void hide(const Arc& e) const { _arc_filter->set(e, false); }
605

	
606
    void unHide(const Node& n) const { _node_filter->set(n, true); }
607
    void unHide(const Arc& e) const { _arc_filter->set(e, true); }
608

	
609
    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
610
    bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
621
    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
622
    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
623

	
624
    bool status(const Node& n) const { return (*_node_filter)[n]; }
625
    bool status(const Arc& a) const { return (*_arc_filter)[a]; }
611 626

	
612 627
    typedef False NodeNumTag;
613
    typedef False EdgeNumTag;
614

	
615
    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
628
    typedef False ArcNumTag;
629

	
630
    typedef FindArcTagIndicator<Digraph> FindArcTag;
616 631
    Arc findArc(const Node& source, const Node& target,
617
                const Arc& prev = INVALID) {
632
                const Arc& prev = INVALID) const {
618 633
      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
619 634
        return INVALID;
620 635
      }
621 636
      Arc arc = Parent::findArc(source, target, prev);
622 637
      while (arc != INVALID && !(*_arc_filter)[arc]) {
623 638
        arc = Parent::findArc(source, target, arc);
... ...
@@ -676,149 +691,182 @@
676 691
    };
677 692

	
678 693
  };
679 694

	
680 695
  /// \ingroup graph_adaptors
681 696
  ///
682
  /// \brief An adaptor for hiding nodes and arcs in a digraph
697
  /// \brief Adaptor class for hiding nodes and arcs in a digraph
683 698
  ///
684
  /// SubDigraph hides nodes and arcs in a digraph. A bool node map
685
  /// and a bool arc map must be specified, which define the filters
686
  /// for nodes and arcs. Just the nodes and arcs with true value are
687
  /// shown in the subdigraph. The SubDigraph is conform to the \ref
688
  /// concepts::Digraph "Digraph concept". If the \c _checked parameter
689
  /// is true, then the arcs incident to filtered nodes are also
690
  /// filtered out.
699
  /// SubDigraph can be used for hiding nodes and arcs in a digraph.
700
  /// A \c bool node map and a \c bool arc map must be specified, which
701
  /// define the filters for nodes and arcs.
702
  /// Only the nodes and arcs with \c true filter value are
703
  /// shown in the subdigraph. The arcs that are incident to hidden
704
  /// nodes are also filtered out.
705
  /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept.
691 706
  ///
692
  /// \tparam _Digraph It must be conform to the \ref
693
  /// concepts::Digraph "Digraph concept". The type can be specified
694
  /// to const.
695
  /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph.
696
  /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph.
697
  /// \tparam _checked If the parameter is false then the arc filtering
698
  /// is not checked with respect to node filter. Otherwise, each arc
699
  /// is automatically filtered, which is incident to a filtered node.
707
  /// The adapted digraph can also be modified through this adaptor
708
  /// by adding or removing nodes or arcs, unless the \c GR template
709
  /// parameter is set to be \c const.
710
  ///
711
  /// \tparam GR The type of the adapted digraph.
712
  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
713
  /// It can also be specified to be \c const.
714
  /// \tparam NF The type of the node filter map.
715
  /// It must be a \c bool (or convertible) node map of the
716
  /// adapted digraph. The default type is
717
  /// \ref concepts::Digraph::NodeMap "GR::NodeMap<bool>".
718
  /// \tparam AF The type of the arc filter map.
719
  /// It must be \c bool (or convertible) arc map of the
720
  /// adapted digraph. The default type is
721
  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>".
722
  ///
723
  /// \note The \c Node and \c Arc types of this adaptor and the adapted
724
  /// digraph are convertible to each other.
700 725
  ///
701 726
  /// \see FilterNodes
702 727
  /// \see FilterArcs
703
  template<typename _Digraph,
704
           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
705
           typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
706
           bool _checked = true>
707
  class SubDigraph
708
    : public DigraphAdaptorExtender<
709
      SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
728
#ifdef DOXYGEN
729
  template<typename GR, typename NF, typename AF>
730
  class SubDigraph {
731
#else
732
  template<typename GR,
733
           typename NF = typename GR::template NodeMap<bool>,
734
           typename AF = typename GR::template ArcMap<bool> >
735
  class SubDigraph :
736
    public DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> > {
737
#endif
710 738
  public:
711
    typedef _Digraph Digraph;
712
    typedef _NodeFilterMap NodeFilterMap;
713
    typedef _ArcFilterMap ArcFilterMap;
714

	
715
    typedef DigraphAdaptorExtender<
716
      SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> >
717
    Parent;
739
    /// The type of the adapted digraph.
740
    typedef GR Digraph;
741
    /// The type of the node filter map.
742
    typedef NF NodeFilterMap;
743
    /// The type of the arc filter map.
744
    typedef AF ArcFilterMap;
745

	
746
    typedef DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> >
747
      Parent;
718 748

	
719 749
    typedef typename Parent::Node Node;
720 750
    typedef typename Parent::Arc Arc;
721 751

	
722 752
  protected:
723 753
    SubDigraph() { }
724 754
  public:
725 755

	
726 756
    /// \brief Constructor
727 757
    ///
728
    /// Creates a subdigraph for the given digraph with
729
    /// given node and arc map filters.
758
    /// Creates a subdigraph for the given digraph with the
759
    /// given node and arc filter maps.
730 760
    SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
731 761
               ArcFilterMap& arc_filter) {
732 762
      setDigraph(digraph);
733 763
      setNodeFilterMap(node_filter);
734 764
      setArcFilterMap(arc_filter);
735 765
    }
736 766

	
737
    /// \brief Hides the node of the graph
767
    /// \brief Sets the status of the given node
738 768
    ///
739
    /// This function hides \c n in the digraph, i.e. the iteration
740
    /// jumps over it. This is done by simply setting the value of \c n
741
    /// to be false in the corresponding node-map.
742
    void hide(const Node& n) const { Parent::hide(n); }
743

	
744
    /// \brief Hides the arc of the graph
769
    /// This function sets the status of the given node.
770
    /// It is done by simply setting the assigned value of \c n
771
    /// to \c v in the node filter map.
772
    void status(const Node& n, bool v) const { Parent::status(n, v); }
773

	
774
    /// \brief Sets the status of the given arc
745 775
    ///
746
    /// This function hides \c a in the digraph, i.e. the iteration
747
    /// jumps over it. This is done by simply setting the value of \c a
748
    /// to be false in the corresponding arc-map.
749
    void hide(const Arc& a) const { Parent::hide(a); }
750

	
751
    /// \brief Unhides the node of the graph
776
    /// This function sets the status of the given arc.
777
    /// It is done by simply setting the assigned value of \c a
778
    /// to \c v in the arc filter map.
779
    void status(const Arc& a, bool v) const { Parent::status(a, v); }
780

	
781
    /// \brief Returns the status of the given node
752 782
    ///
753
    /// The value of \c n is set to be true in the node-map which stores
754
    /// hide information. If \c n was hidden previuosly, then it is shown
755
    /// again
756
    void unHide(const Node& n) const { Parent::unHide(n); }
757

	
758
    /// \brief Unhides the arc of the graph
783
    /// This function returns the status of the given node.
784
    /// It is \c true if the given node is enabled (i.e. not hidden).
785
    bool status(const Node& n) const { return Parent::status(n); }
786

	
787
    /// \brief Returns the status of the given arc
759 788
    ///
760
    /// The value of \c a is set to be true in the arc-map which stores
761
    /// hide information. If \c a was hidden previuosly, then it is shown
762
    /// again
763
    void unHide(const Arc& a) const { Parent::unHide(a); }
764

	
765
    /// \brief Returns true if \c n is hidden.
789
    /// This function returns the status of the given arc.
790
    /// It is \c true if the given arc is enabled (i.e. not hidden).
791
    bool status(const Arc& a) const { return Parent::status(a); }
792

	
793
    /// \brief Disables the given node
766 794
    ///
767
    /// Returns true if \c n is hidden.
795
    /// This function disables the given node in the subdigraph,
796
    /// so the iteration jumps over it.
797
    /// It is the same as \ref status() "status(n, false)".
798
    void disable(const Node& n) const { Parent::status(n, false); }
799

	
800
    /// \brief Disables the given arc
768 801
    ///
769
    bool hidden(const Node& n) const { return Parent::hidden(n); }
770

	
771
    /// \brief Returns true if \c a is hidden.
802
    /// This function disables the given arc in the subdigraph,
803
    /// so the iteration jumps over it.
804
    /// It is the same as \ref status() "status(a, false)".
805
    void disable(const Arc& a) const { Parent::status(a, false); }
806

	
807
    /// \brief Enables the given node
772 808
    ///
773
    /// Returns true if \c a is hidden.
809
    /// This function enables the given node in the subdigraph.
810
    /// It is the same as \ref status() "status(n, true)".
811
    void enable(const Node& n) const { Parent::status(n, true); }
812

	
813
    /// \brief Enables the given arc
774 814
    ///
775
    bool hidden(const Arc& a) const { return Parent::hidden(a); }
815
    /// This function enables the given arc in the subdigraph.
816
    /// It is the same as \ref status() "status(a, true)".
817
    void enable(const Arc& a) const { Parent::status(a, true); }
776 818

	
777 819
  };
778 820

	
779
  /// \brief Just gives back a subdigraph
821
  /// \brief Returns a read-only SubDigraph adaptor
780 822
  ///
781
  /// Just gives back a subdigraph
782
  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
783
  SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
784
  subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
785
    return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
786
      (digraph, nfm, afm);
823
  /// This function just returns a read-only \ref SubDigraph adaptor.
824
  /// \ingroup graph_adaptors
825
  /// \relates SubDigraph
826
  template<typename GR, typename NF, typename AF>
827
  SubDigraph<const GR, NF, AF>
828
  subDigraph(const GR& digraph,
829
             NF& node_filter_map, AF& arc_filter_map) {
830
    return SubDigraph<const GR, NF, AF>
831
      (digraph, node_filter_map, arc_filter_map);
787 832
  }
788 833

	
789
  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
790
  SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
791
  subDigraph(const Digraph& digraph,
792
             const NodeFilterMap& nfm, ArcFilterMap& afm) {
793
    return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
794
      (digraph, nfm, afm);
834
  template<typename GR, typename NF, typename AF>
835
  SubDigraph<const GR, const NF, AF>
836
  subDigraph(const GR& digraph,
837
             const NF& node_filter_map, AF& arc_filter_map) {
838
    return SubDigraph<const GR, const NF, AF>
839
      (digraph, node_filter_map, arc_filter_map);
795 840
  }
796 841

	
797
  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
798
  SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
799
  subDigraph(const Digraph& digraph,
800
             NodeFilterMap& nfm, const ArcFilterMap& afm) {
801
    return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
802
      (digraph, nfm, afm);
842
  template<typename GR, typename NF, typename AF>
843
  SubDigraph<const GR, NF, const AF>
844
  subDigraph(const GR& digraph,
845
             NF& node_filter_map, const AF& arc_filter_map) {
846
    return SubDigraph<const GR, NF, const AF>
847
      (digraph, node_filter_map, arc_filter_map);
803 848
  }
804 849

	
805
  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
806
  SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>
807
  subDigraph(const Digraph& digraph,
808
             const NodeFilterMap& nfm, const ArcFilterMap& afm) {
809
    return SubDigraph<const Digraph, const NodeFilterMap,
810
      const ArcFilterMap>(digraph, nfm, afm);
850
  template<typename GR, typename NF, typename AF>
851
  SubDigraph<const GR, const NF, const AF>
852
  subDigraph(const GR& digraph,
853
             const NF& node_filter_map, const AF& arc_filter_map) {
854
    return SubDigraph<const GR, const NF, const AF>
855
      (digraph, node_filter_map, arc_filter_map);
811 856
  }
812 857

	
813 858

	
814
  template <typename _Graph, typename NodeFilterMap,
815
            typename EdgeFilterMap, bool _checked = true>
859
  template <typename _Graph, typename _NodeFilterMap,
860
            typename _EdgeFilterMap, bool _checked = true>
816 861
  class SubGraphBase : public GraphAdaptorBase<_Graph> {
817 862
  public:
818 863
    typedef _Graph Graph;
864
    typedef _NodeFilterMap NodeFilterMap;
865
    typedef _EdgeFilterMap EdgeFilterMap;
866

	
819 867
    typedef SubGraphBase Adaptor;
820 868
    typedef GraphAdaptorBase<_Graph> Parent;
821 869
  protected:
822 870

	
823 871
    NodeFilterMap* _node_filter_map;
824 872
    EdgeFilterMap* _edge_filter_map;
... ...
@@ -922,38 +970,38 @@
922 970
      while (i!=INVALID && (!(*_edge_filter_map)[i]
923 971
                            || !(*_node_filter_map)[Parent::u(i)]
924 972
                            || !(*_node_filter_map)[Parent::v(i)]))
925 973
        Parent::nextInc(i, d);
926 974
    }
927 975

	
928
    void hide(const Node& n) const { _node_filter_map->set(n, false); }
929
    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
930

	
931
    void unHide(const Node& n) const { _node_filter_map->set(n, true); }
932
    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
933

	
934
    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
935
    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
976
    void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
977
    void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
978

	
979
    bool status(const Node& n) const { return (*_node_filter_map)[n]; }
980
    bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
936 981

	
937 982
    typedef False NodeNumTag;
983
    typedef False ArcNumTag;
938 984
    typedef False EdgeNumTag;
939 985

	
940
    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
986
    typedef FindArcTagIndicator<Graph> FindArcTag;
941 987
    Arc findArc(const Node& u, const Node& v,
942
                const Arc& prev = INVALID) {
988
                const Arc& prev = INVALID) const {
943 989
      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
944 990
        return INVALID;
945 991
      }
946 992
      Arc arc = Parent::findArc(u, v, prev);
947 993
      while (arc != INVALID && !(*_edge_filter_map)[arc]) {
948 994
        arc = Parent::findArc(u, v, arc);
949 995
      }
950 996
      return arc;
951 997
    }
998

	
999
    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
952 1000
    Edge findEdge(const Node& u, const Node& v,
953
                  const Edge& prev = INVALID) {
1001
                  const Edge& prev = INVALID) const {
954 1002
      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
955 1003
        return INVALID;
956 1004
      }
957 1005
      Edge edge = Parent::findEdge(u, v, prev);
958 1006
      while (edge != INVALID && !(*_edge_filter_map)[edge]) {
959 1007
        edge = Parent::findEdge(u, v, edge);
... ...
@@ -1036,17 +1084,20 @@
1036 1084
        return *this;
1037 1085
      }
1038 1086
    };
1039 1087

	
1040 1088
  };
1041 1089

	
1042
  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
1043
  class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
1090
  template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap>
1091
  class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false>
1044 1092
    : public GraphAdaptorBase<_Graph> {
1045 1093
  public:
1046 1094
    typedef _Graph Graph;
1095
    typedef _NodeFilterMap NodeFilterMap;
1096
    typedef _EdgeFilterMap EdgeFilterMap;
1097

	
1047 1098
    typedef SubGraphBase Adaptor;
1048 1099
    typedef GraphAdaptorBase<_Graph> Parent;
1049 1100
  protected:
1050 1101
    NodeFilterMap* _node_filter_map;
1051 1102
    EdgeFilterMap* _edge_filter_map;
1052 1103
    SubGraphBase() : Parent(),
... ...
@@ -1118,35 +1169,35 @@
1118 1169
    }
1119 1170
    void nextInc(Edge& i, bool& d) const {
1120 1171
      Parent::nextInc(i, d);
1121 1172
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
1122 1173
    }
1123 1174

	
1124
    void hide(const Node& n) const { _node_filter_map->set(n, false); }
1125
    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
1126

	
1127
    void unHide(const Node& n) const { _node_filter_map->set(n, true); }
1128
    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
1129

	
1130
    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
1131
    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
1175
    void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
1176
    void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
1177

	
1178
    bool status(const Node& n) const { return (*_node_filter_map)[n]; }
1179
    bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
1132 1180

	
1133 1181
    typedef False NodeNumTag;
1182
    typedef False ArcNumTag;
1134 1183
    typedef False EdgeNumTag;
1135 1184

	
1136
    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1185
    typedef FindArcTagIndicator<Graph> FindArcTag;
1137 1186
    Arc findArc(const Node& u, const Node& v,
1138
                const Arc& prev = INVALID) {
1187
                const Arc& prev = INVALID) const {
1139 1188
      Arc arc = Parent::findArc(u, v, prev);
1140 1189
      while (arc != INVALID && !(*_edge_filter_map)[arc]) {
1141 1190
        arc = Parent::findArc(u, v, arc);
1142 1191
      }
1143 1192
      return arc;
1144 1193
    }
1194

	
1195
    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1145 1196
    Edge findEdge(const Node& u, const Node& v,
1146
                  const Edge& prev = INVALID) {
1197
                  const Edge& prev = INVALID) const {
1147 1198
      Edge edge = Parent::findEdge(u, v, prev);
1148 1199
      while (edge != INVALID && !(*_edge_filter_map)[edge]) {
1149 1200
        edge = Parent::findEdge(u, v, edge);
1150 1201
      }
1151 1202
      return edge;
1152 1203
    }
... ...
@@ -1228,179 +1279,221 @@
1228 1279
    };
1229 1280

	
1230 1281
  };
1231 1282

	
1232 1283
  /// \ingroup graph_adaptors
1233 1284
  ///
1234
  /// \brief A graph adaptor for hiding nodes and edges in an
1235
  /// undirected graph.
1285
  /// \brief Adaptor class for hiding nodes and edges in an undirected
1286
  /// graph.
1236 1287
  ///
1237
  /// SubGraph hides nodes and edges in a graph. A bool node map and a
1238
  /// bool edge map must be specified, which define the filters for
1239
  /// nodes and edges. Just the nodes and edges with true value are
1240
  /// shown in the subgraph. The SubGraph is conform to the \ref
1241
  /// concepts::Graph "Graph concept". If the \c _checked parameter is
1242
  /// true, then the edges incident to filtered nodes are also
1243
  /// filtered out.
1288
  /// SubGraph can be used for hiding nodes and edges in a graph.
1289
  /// A \c bool node map and a \c bool edge map must be specified, which
1290
  /// define the filters for nodes and edges.
1291
  /// Only the nodes and edges with \c true filter value are
1292
  /// shown in the subgraph. The edges that are incident to hidden
1293
  /// nodes are also filtered out.
1294
  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
1244 1295
  ///
1245
  /// \tparam _Graph It must be conform to the \ref
1246
  /// concepts::Graph "Graph concept". The type can be specified
1247
  /// to const.
1248
  /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
1249
  /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph.
1250
  /// \tparam _checked If the parameter is false then the edge filtering
1251
  /// is not checked with respect to node filter. Otherwise, each edge
1252
  /// is automatically filtered, which is incident to a filtered node.
1296
  /// The adapted graph can also be modified through this adaptor
1297
  /// by adding or removing nodes or edges, unless the \c GR template
1298
  /// parameter is set to be \c const.
1299
  ///
1300
  /// \tparam GR The type of the adapted graph.
1301
  /// It must conform to the \ref concepts::Graph "Graph" concept.
1302
  /// It can also be specified to be \c const.
1303
  /// \tparam NF The type of the node filter map.
1304
  /// It must be a \c bool (or convertible) node map of the
1305
  /// adapted graph. The default type is
1306
  /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".
1307
  /// \tparam EF The type of the edge filter map.
1308
  /// It must be a \c bool (or convertible) edge map of the
1309
  /// adapted graph. The default type is
1310
  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
1311
  ///
1312
  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
1313
  /// adapted graph are convertible to each other.
1253 1314
  ///
1254 1315
  /// \see FilterNodes
1255 1316
  /// \see FilterEdges
1256
  template<typename _Graph, typename NodeFilterMap,
1257
           typename EdgeFilterMap, bool _checked = true>
1258
  class SubGraph
1259
    : public GraphAdaptorExtender<
1260
      SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > {
1317
#ifdef DOXYGEN
1318
  template<typename GR, typename NF, typename EF>
1319
  class SubGraph {
1320
#else
1321
  template<typename GR,
1322
           typename NF = typename GR::template NodeMap<bool>,
1323
           typename EF = typename GR::template EdgeMap<bool> >
1324
  class SubGraph :
1325
    public GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> > {
1326
#endif
1261 1327
  public:
1262
    typedef _Graph Graph;
1263
    typedef GraphAdaptorExtender<
1264
      SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
1328
    /// The type of the adapted graph.
1329
    typedef GR Graph;
1330
    /// The type of the node filter map.
1331
    typedef NF NodeFilterMap;
1332
    /// The type of the edge filter map.
1333
    typedef EF EdgeFilterMap;
1334

	
1335
    typedef GraphAdaptorExtender< SubGraphBase<GR, NF, EF, true> >
1336
      Parent;
1265 1337

	
1266 1338
    typedef typename Parent::Node Node;
1267 1339
    typedef typename Parent::Edge Edge;
1268 1340

	
1269 1341
  protected:
1270 1342
    SubGraph() { }
1271 1343
  public:
1272 1344

	
1273 1345
    /// \brief Constructor
1274 1346
    ///
1275
    /// Creates a subgraph for the given graph with given node and
1276
    /// edge map filters.
1277
    SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,
1347
    /// Creates a subgraph for the given graph with the given node
1348
    /// and edge filter maps.
1349
    SubGraph(Graph& graph, NodeFilterMap& node_filter_map,
1278 1350
             EdgeFilterMap& edge_filter_map) {
1279
      setGraph(_graph);
1351
      setGraph(graph);
1280 1352
      setNodeFilterMap(node_filter_map);
1281 1353
      setEdgeFilterMap(edge_filter_map);
1282 1354
    }
1283 1355

	
1284
    /// \brief Hides the node of the graph
1356
    /// \brief Sets the status of the given node
1285 1357
    ///
1286
    /// This function hides \c n in the graph, i.e. the iteration
1287
    /// jumps over it. This is done by simply setting the value of \c n
1288
    /// to be false in the corresponding node-map.
1289
    void hide(const Node& n) const { Parent::hide(n); }
1290

	
1291
    /// \brief Hides the edge of the graph
1358
    /// This function sets the status of the given node.
1359
    /// It is done by simply setting the assigned value of \c n
1360
    /// to \c v in the node filter map.
1361
    void status(const Node& n, bool v) const { Parent::status(n, v); }
1362

	
1363
    /// \brief Sets the status of the given edge
1292 1364
    ///
1293
    /// This function hides \c e in the graph, i.e. the iteration
1294
    /// jumps over it. This is done by simply setting the value of \c e
1295
    /// to be false in the corresponding edge-map.
1296
    void hide(const Edge& e) const { Parent::hide(e); }
1297

	
1298
    /// \brief Unhides the node of the graph
1365
    /// This function sets the status of the given edge.
1366
    /// It is done by simply setting the assigned value of \c e
1367
    /// to \c v in the edge filter map.
1368
    void status(const Edge& e, bool v) const { Parent::status(e, v); }
1369

	
1370
    /// \brief Returns the status of the given node
1299 1371
    ///
1300
    /// The value of \c n is set to be true in the node-map which stores
1301
    /// hide information. If \c n was hidden previuosly, then it is shown
1302
    /// again
1303
    void unHide(const Node& n) const { Parent::unHide(n); }
1304

	
1305
    /// \brief Unhides the edge of the graph
1372
    /// This function returns the status of the given node.
1373
    /// It is \c true if the given node is enabled (i.e. not hidden).
1374
    bool status(const Node& n) const { return Parent::status(n); }
1375

	
1376
    /// \brief Returns the status of the given edge
1306 1377
    ///
1307
    /// The value of \c e is set to be true in the edge-map which stores
1308
    /// hide information. If \c e was hidden previuosly, then it is shown
1309
    /// again
1310
    void unHide(const Edge& e) const { Parent::unHide(e); }
1311

	
1312
    /// \brief Returns true if \c n is hidden.
1378
    /// This function returns the status of the given edge.
1379
    /// It is \c true if the given edge is enabled (i.e. not hidden).
1380
    bool status(const Edge& e) const { return Parent::status(e); }
1381

	
1382
    /// \brief Disables the given node
1313 1383
    ///
1314
    /// Returns true if \c n is hidden.
1384
    /// This function disables the given node in the subdigraph,
1385
    /// so the iteration jumps over it.
1386
    /// It is the same as \ref status() "status(n, false)".
1387
    void disable(const Node& n) const { Parent::status(n, false); }
1388

	
1389
    /// \brief Disables the given edge
1315 1390
    ///
1316
    bool hidden(const Node& n) const { return Parent::hidden(n); }
1317

	
1318
    /// \brief Returns true if \c e is hidden.
1391
    /// This function disables the given edge in the subgraph,
1392
    /// so the iteration jumps over it.
1393
    /// It is the same as \ref status() "status(e, false)".
1394
    void disable(const Edge& e) const { Parent::status(e, false); }
1395

	
1396
    /// \brief Enables the given node
1319 1397
    ///
1320
    /// Returns true if \c e is hidden.
1398
    /// This function enables the given node in the subdigraph.
1399
    /// It is the same as \ref status() "status(n, true)".
1400
    void enable(const Node& n) const { Parent::status(n, true); }
1401

	
1402
    /// \brief Enables the given edge
1321 1403
    ///
1322
    bool hidden(const Edge& e) const { return Parent::hidden(e); }
1404
    /// This function enables the given edge in the subgraph.
1405
    /// It is the same as \ref status() "status(e, true)".
1406
    void enable(const Edge& e) const { Parent::status(e, true); }
1407

	
1323 1408
  };
1324 1409

	
1325
  /// \brief Just gives back a subgraph
1410
  /// \brief Returns a read-only SubGraph adaptor
1326 1411
  ///
1327
  /// Just gives back a subgraph
1328
  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1329
  SubGraph<const Graph, NodeFilterMap, ArcFilterMap>
1330
  subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
1331
    return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);
1412
  /// This function just returns a read-only \ref SubGraph adaptor.
1413
  /// \ingroup graph_adaptors
1414
  /// \relates SubGraph
1415
  template<typename GR, typename NF, typename EF>
1416
  SubGraph<const GR, NF, EF>
1417
  subGraph(const GR& graph,
1418
           NF& node_filter_map, EF& edge_filter_map) {
1419
    return SubGraph<const GR, NF, EF>
1420
      (graph, node_filter_map, edge_filter_map);
1332 1421
  }
1333 1422

	
1334
  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1335
  SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
1336
  subGraph(const Graph& graph,
1337
           const NodeFilterMap& nfm, ArcFilterMap& efm) {
1338
    return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
1339
      (graph, nfm, efm);
1423
  template<typename GR, typename NF, typename EF>
1424
  SubGraph<const GR, const NF, EF>
1425
  subGraph(const GR& graph,
1426
           const NF& node_filter_map, EF& edge_filter_map) {
1427
    return SubGraph<const GR, const NF, EF>
1428
      (graph, node_filter_map, edge_filter_map);
1340 1429
  }
1341 1430

	
1342
  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1343
  SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
1344
  subGraph(const Graph& graph,
1345
           NodeFilterMap& nfm, const ArcFilterMap& efm) {
1346
    return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
1347
      (graph, nfm, efm);
1431
  template<typename GR, typename NF, typename EF>
1432
  SubGraph<const GR, NF, const EF>
1433
  subGraph(const GR& graph,
1434
           NF& node_filter_map, const EF& edge_filter_map) {
1435
    return SubGraph<const GR, NF, const EF>
1436
      (graph, node_filter_map, edge_filter_map);
1348 1437
  }
1349 1438

	
1350
  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1351
  SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
1352
  subGraph(const Graph& graph,
1353
           const NodeFilterMap& nfm, const ArcFilterMap& efm) {
1354
    return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
1355
      (graph, nfm, efm);
1439
  template<typename GR, typename NF, typename EF>
1440
  SubGraph<const GR, const NF, const EF>
1441
  subGraph(const GR& graph,
1442
           const NF& node_filter_map, const EF& edge_filter_map) {
1443
    return SubGraph<const GR, const NF, const EF>
1444
      (graph, node_filter_map, edge_filter_map);
1356 1445
  }
1357 1446

	
1447

	
1358 1448
  /// \ingroup graph_adaptors
1359 1449
  ///
1360
  /// \brief An adaptor for hiding nodes from a digraph or a graph.
1450
  /// \brief Adaptor class for hiding nodes in a digraph or a graph.
1361 1451
  ///
1362
  /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool
1363
  /// node map must be specified, which defines the filters for
1364
  /// nodes. Just the unfiltered nodes and the arcs or edges incident
1365
  /// to unfiltered nodes are shown in the subdigraph or subgraph. The
1366
  /// FilterNodes is conform to the \ref concepts::Digraph
1367
  /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending
1368
  /// on the \c _Digraph template parameter. If the \c _checked
1369
  /// parameter is true, then the arc or edges incident to filtered nodes
1370
  /// are also filtered out.
1452
  /// FilterNodes adaptor can be used for hiding nodes in a digraph or a
1453
  /// graph. A \c bool node map must be specified, which defines the filter
1454
  /// for the nodes. Only the nodes with \c true filter value and the
1455
  /// arcs/edges incident to nodes both with \c true filter value are shown
1456
  /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph
1457
  /// "Digraph" concept or the \ref concepts::Graph "Graph" concept
1458
  /// depending on the \c GR template parameter.
1371 1459
  ///
1372
  /// \tparam _Digraph It must be conform to the \ref
1373
  /// concepts::Digraph "Digraph concept" or \ref concepts::Graph
1374
  /// "Graph concept". The type can be specified to be const.
1375
  /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
1376
  /// \tparam _checked If the parameter is false then the arc or edge
1377
  /// filtering is not checked with respect to node filter. In this
1378
  /// case just isolated nodes can be filtered out from the
1379
  /// graph.
1460
  /// The adapted (di)graph can also be modified through this adaptor
1461
  /// by adding or removing nodes or arcs/edges, unless the \c GR template
1462
  /// parameter is set to be \c const.
1463
  ///
1464
  /// \tparam GR The type of the adapted digraph or graph.
1465
  /// It must conform to the \ref concepts::Digraph "Digraph" concept
1466
  /// or the \ref concepts::Graph "Graph" concept.
1467
  /// It can also be specified to be \c const.
1468
  /// \tparam NF The type of the node filter map.
1469
  /// It must be a \c bool (or convertible) node map of the
1470
  /// adapted (di)graph. The default type is
1471
  /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".
1472
  ///
1473
  /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the
1474
  /// adapted (di)graph are convertible to each other.
1380 1475
#ifdef DOXYGEN
1381
  template<typename _Digraph,
1382
           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
1383
           bool _checked = true>
1476
  template<typename GR, typename NF>
1477
  class FilterNodes {
1384 1478
#else
1385
  template<typename _Digraph,
1386
           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
1387
           bool _checked = true,
1479
  template<typename GR,
1480
           typename NF = typename GR::template NodeMap<bool>,
1388 1481
           typename Enable = void>
1482
  class FilterNodes :
1483
    public DigraphAdaptorExtender<
1484
      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> > {
1389 1485
#endif
1390
  class FilterNodes
1391
    : public SubDigraph<_Digraph, _NodeFilterMap,
1392
                        ConstMap<typename _Digraph::Arc, bool>, _checked> {
1393 1486
  public:
1394 1487

	
1395
    typedef _Digraph Digraph;
1396
    typedef _NodeFilterMap NodeFilterMap;
1397

	
1398
    typedef SubDigraph<Digraph, NodeFilterMap,
1399
                       ConstMap<typename Digraph::Arc, bool>, _checked>
1400
    Parent;
1488
    typedef GR Digraph;
1489
    typedef NF NodeFilterMap;
1490

	
1491
    typedef DigraphAdaptorExtender<
1492
      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> >
1493
      Parent;
1401 1494

	
1402 1495
    typedef typename Parent::Node Node;
1403 1496

	
1404 1497
  protected:
1405 1498
    ConstMap<typename Digraph::Arc, bool> const_true_map;
1406 1499

	
... ...
@@ -1409,53 +1502,62 @@
1409 1502
    }
1410 1503

	
1411 1504
  public:
1412 1505

	
1413 1506
    /// \brief Constructor
1414 1507
    ///
1415
    /// Creates an adaptor for the given digraph or graph with
1508
    /// Creates a subgraph for the given digraph or graph with the
1416 1509
    /// given node filter map.
1417
    FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :
1418
      Parent(), const_true_map(true) {
1419
      Parent::setDigraph(_digraph);
1510
    FilterNodes(GR& graph, NodeFilterMap& node_filter) :
1511
      Parent(), const_true_map(true)
1512
    {
1513
      Parent::setDigraph(graph);
1420 1514
      Parent::setNodeFilterMap(node_filter);
1421 1515
      Parent::setArcFilterMap(const_true_map);
1422 1516
    }
1423 1517

	
1424
    /// \brief Hides the node of the graph
1518
    /// \brief Sets the status of the given node
1425 1519
    ///
1426
    /// This function hides \c n in the digraph or graph, i.e. the iteration
1427
    /// jumps over it. This is done by simply setting the value of \c n
1428
    /// to be false in the corresponding node map.
1429
    void hide(const Node& n) const { Parent::hide(n); }
1430

	
1431
    /// \brief Unhides the node of the graph
1520
    /// This function sets the status of the given node.
1521
    /// It is done by simply setting the assigned value of \c n
1522
    /// to \c v in the node filter map.
1523
    void status(const Node& n, bool v) const { Parent::status(n, v); }
1524

	
1525
    /// \brief Returns the status of the given node
1432 1526
    ///
1433
    /// The value of \c n is set to be true in the node-map which stores
1434
    /// hide information. If \c n was hidden previuosly, then it is shown
1435
    /// again
1436
    void unHide(const Node& n) const { Parent::unHide(n); }
1437

	
1438
    /// \brief Returns true if \c n is hidden.
1527
    /// This function returns the status of the given node.
1528
    /// It is \c true if the given node is enabled (i.e. not hidden).
1529
    bool status(const Node& n) const { return Parent::status(n); }
1530

	
1531
    /// \brief Disables the given node
1439 1532
    ///
1440
    /// Returns true if \c n is hidden.
1533
    /// This function disables the given node, so the iteration
1534
    /// jumps over it.
1535
    /// It is the same as \ref status() "status(n, false)".
1536
    void disable(const Node& n) const { Parent::status(n, false); }
1537

	
1538
    /// \brief Enables the given node
1441 1539
    ///
1442
    bool hidden(const Node& n) const { return Parent::hidden(n); }
1540
    /// This function enables the given node.
1541
    /// It is the same as \ref status() "status(n, true)".
1542
    void enable(const Node& n) const { Parent::status(n, true); }
1443 1543

	
1444 1544
  };
1445 1545

	
1446
  template<typename _Graph, typename _NodeFilterMap, bool _checked>
1447
  class FilterNodes<_Graph, _NodeFilterMap, _checked,
1448
                    typename enable_if<UndirectedTagIndicator<_Graph> >::type>
1449
    : public SubGraph<_Graph, _NodeFilterMap,
1450
                      ConstMap<typename _Graph::Edge, bool>, _checked> {
1546
  template<typename GR, typename NF>
1547
  class FilterNodes<GR, NF,
1548
                    typename enable_if<UndirectedTagIndicator<GR> >::type> :
1549
    public GraphAdaptorExtender<
1550
      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> > {
1551

	
1451 1552
  public:
1452
    typedef _Graph Graph;
1453
    typedef _NodeFilterMap NodeFilterMap;
1454
    typedef SubGraph<Graph, NodeFilterMap,
1455
                     ConstMap<typename Graph::Edge, bool> > Parent;
1553
    typedef GR Graph;
1554
    typedef NF NodeFilterMap;
1555
    typedef GraphAdaptorExtender<
1556
      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> >
1557
      Parent;
1456 1558

	
1457 1559
    typedef typename Parent::Node Node;
1458 1560
  protected:
1459 1561
    ConstMap<typename Graph::Edge, bool> const_true_map;
1460 1562

	
1461 1563
    FilterNodes() : const_true_map(true) {
... ...
@@ -1468,57 +1570,81 @@
1468 1570
      Parent(), const_true_map(true) {
1469 1571
      Parent::setGraph(_graph);
1470 1572
      Parent::setNodeFilterMap(node_filter_map);
1471 1573
      Parent::setEdgeFilterMap(const_true_map);
1472 1574
    }
1473 1575

	
1474
    void hide(const Node& n) const { Parent::hide(n); }
1475
    void unHide(const Node& n) const { Parent::unHide(n); }
1476
    bool hidden(const Node& n) const { return Parent::hidden(n); }
1576
    void status(const Node& n, bool v) const { Parent::status(n, v); }
1577
    bool status(const Node& n) const { return Parent::status(n); }
1578
    void disable(const Node& n) const { Parent::status(n, false); }
1579
    void enable(const Node& n) const { Parent::status(n, true); }
1477 1580

	
1478 1581
  };
1479 1582

	
1480 1583

	
1481
  /// \brief Just gives back a FilterNodes adaptor
1584
  /// \brief Returns a read-only FilterNodes adaptor
1482 1585
  ///
1483
  /// Just gives back a FilterNodes adaptor
1484
  template<typename Digraph, typename NodeFilterMap>
1485
  FilterNodes<const Digraph, NodeFilterMap>
1486
  filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
1487
    return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
1586
  /// This function just returns a read-only \ref FilterNodes adaptor.
1587
  /// \ingroup graph_adaptors
1588
  /// \relates FilterNodes
1589
  template<typename GR, typename NF>
1590
  FilterNodes<const GR, NF>
1591
  filterNodes(const GR& graph, NF& node_filter_map) {
1592
    return FilterNodes<const GR, NF>(graph, node_filter_map);
1488 1593
  }
1489 1594

	
1490
  template<typename Digraph, typename NodeFilterMap>
1491
  FilterNodes<const Digraph, const NodeFilterMap>
1492
  filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
1493
    return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
1595
  template<typename GR, typename NF>
1596
  FilterNodes<const GR, const NF>
1597
  filterNodes(const GR& graph, const NF& node_filter_map) {
1598
    return FilterNodes<const GR, const NF>(graph, node_filter_map);
1494 1599
  }
1495 1600

	
1496 1601
  /// \ingroup graph_adaptors
1497 1602
  ///
1498
  /// \brief An adaptor for hiding arcs from a digraph.
1603
  /// \brief Adaptor class for hiding arcs in a digraph.
1499 1604
  ///
1500
  /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must
1501
  /// be specified, which defines the filters for arcs. Just the
1502
  /// unfiltered arcs are shown in the subdigraph. The FilterArcs is
1503
  /// conform to the \ref concepts::Digraph "Digraph concept".
1605
  /// FilterArcs adaptor can be used for hiding arcs in a digraph.
1606
  /// A \c bool arc map must be specified, which defines the filter for
1607
  /// the arcs. Only the arcs with \c true filter value are shown in the
1608
  /// subdigraph. This adaptor conforms to the \ref concepts::Digraph
1609
  /// "Digraph" concept.
1504 1610
  ///
1505
  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
1506
  /// "Digraph concept". The type can be specified to be const.
1507
  /// \tparam _ArcFilterMap A bool valued arc map of the the adapted
1508
  /// graph.
1509
  template<typename _Digraph, typename _ArcFilterMap>
1611
  /// The adapted digraph can also be modified through this adaptor
1612
  /// by adding or removing nodes or arcs, unless the \c GR template
1613
  /// parameter is set to be \c const.
1614
  ///
1615
  /// \tparam GR The type of the adapted digraph.
1616
  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1617
  /// It can also be specified to be \c const.
1618
  /// \tparam AF The type of the arc filter map.
1619
  /// It must be a \c bool (or convertible) arc map of the
1620
  /// adapted digraph. The default type is
1621
  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>".
1622
  ///
1623
  /// \note The \c Node and \c Arc types of this adaptor and the adapted
1624
  /// digraph are convertible to each other.
1625
#ifdef DOXYGEN
1626
  template<typename GR,
1627
           typename AF>
1628
  class FilterArcs {
1629
#else
1630
  template<typename GR,
1631
           typename AF = typename GR::template ArcMap<bool> >
1510 1632
  class FilterArcs :
1511
    public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
1512
                      _ArcFilterMap, false> {
1633
    public DigraphAdaptorExtender<
1634
      SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> > {
1635
#endif
1513 1636
  public:
1514
    typedef _Digraph Digraph;
1515
    typedef _ArcFilterMap ArcFilterMap;
1516

	
1517
    typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
1518
                       ArcFilterMap, false> Parent;
1637
    /// The type of the adapted digraph.
1638
    typedef GR Digraph;
1639
    /// The type of the arc filter map.
1640
    typedef AF ArcFilterMap;
1641

	
1642
    typedef DigraphAdaptorExtender<
1643
      SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> >
1644
      Parent;
1519 1645

	
1520 1646
    typedef typename Parent::Arc Arc;
1521 1647

	
1522 1648
  protected:
1523 1649
    ConstMap<typename Digraph::Node, bool> const_true_map;
1524 1650

	
... ...
@@ -1527,138 +1653,179 @@
1527 1653
    }
1528 1654

	
1529 1655
  public:
1530 1656

	
1531 1657
    /// \brief Constructor
1532 1658
    ///
1533
    /// Creates a FilterArcs adaptor for the given graph with
1534
    /// given arc map filter.
1659
    /// Creates a subdigraph for the given digraph with the given arc
1660
    /// filter map.
1535 1661
    FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
1536 1662
      : Parent(), const_true_map(true) {
1537 1663
      Parent::setDigraph(digraph);
1538 1664
      Parent::setNodeFilterMap(const_true_map);
1539 1665
      Parent::setArcFilterMap(arc_filter);
1540 1666
    }
1541 1667

	
1542
    /// \brief Hides the arc of the graph
1668
    /// \brief Sets the status of the given arc
1543 1669
    ///
1544
    /// This function hides \c a in the graph, i.e. the iteration
1545
    /// jumps over it. This is done by simply setting the value of \c a
1546
    /// to be false in the corresponding arc map.
1547
    void hide(const Arc& a) const { Parent::hide(a); }
1548

	
1549
    /// \brief Unhides the arc of the graph
1670
    /// This function sets the status of the given arc.
1671
    /// It is done by simply setting the assigned value of \c a
1672
    /// to \c v in the arc filter map.
1673
    void status(const Arc& a, bool v) const { Parent::status(a, v); }
1674

	
1675
    /// \brief Returns the status of the given arc
1550 1676
    ///
1551
    /// The value of \c a is set to be true in the arc-map which stores
1552
    /// hide information. If \c a was hidden previuosly, then it is shown
1553
    /// again
1554
    void unHide(const Arc& a) const { Parent::unHide(a); }
1555

	
1556
    /// \brief Returns true if \c a is hidden.
1677
    /// This function returns the status of the given arc.
1678
    /// It is \c true if the given arc is enabled (i.e. not hidden).
1679
    bool status(const Arc& a) const { return Parent::status(a); }
1680

	
1681
    /// \brief Disables the given arc
1557 1682
    ///
1558
    /// Returns true if \c a is hidden.
1683
    /// This function disables the given arc in the subdigraph,
1684
    /// so the iteration jumps over it.
1685
    /// It is the same as \ref status() "status(a, false)".
1686
    void disable(const Arc& a) const { Parent::status(a, false); }
1687

	
1688
    /// \brief Enables the given arc
1559 1689
    ///
1560
    bool hidden(const Arc& a) const { return Parent::hidden(a); }
1690
    /// This function enables the given arc in the subdigraph.
1691
    /// It is the same as \ref status() "status(a, true)".
1692
    void enable(const Arc& a) const { Parent::status(a, true); }
1561 1693

	
1562 1694
  };
1563 1695

	
1564
  /// \brief Just gives back an FilterArcs adaptor
1696
  /// \brief Returns a read-only FilterArcs adaptor
1565 1697
  ///
1566
  /// Just gives back an FilterArcs adaptor
1567
  template<typename Digraph, typename ArcFilterMap>
1568
  FilterArcs<const Digraph, ArcFilterMap>
1569
  filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
1570
    return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
1698
  /// This function just returns a read-only \ref FilterArcs adaptor.
1699
  /// \ingroup graph_adaptors
1700
  /// \relates FilterArcs
1701
  template<typename GR, typename AF>
1702
  FilterArcs<const GR, AF>
1703
  filterArcs(const GR& digraph, AF& arc_filter_map) {
1704
    return FilterArcs<const GR, AF>(digraph, arc_filter_map);
1571 1705
  }
1572 1706

	
1573
  template<typename Digraph, typename ArcFilterMap>
1574
  FilterArcs<const Digraph, const ArcFilterMap>
1575
  filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
1576
    return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);
1707
  template<typename GR, typename AF>
1708
  FilterArcs<const GR, const AF>
1709
  filterArcs(const GR& digraph, const AF& arc_filter_map) {
1710
    return FilterArcs<const GR, const AF>(digraph, arc_filter_map);
1577 1711
  }
1578 1712

	
1579 1713
  /// \ingroup graph_adaptors
1580 1714
  ///
1581
  /// \brief An adaptor for hiding edges from a graph.
1715
  /// \brief Adaptor class for hiding edges in a graph.
1582 1716
  ///
1583
  /// FilterEdges adaptor hides edges in a digraph. A bool edge map must
1584
  /// be specified, which defines the filters for edges. Just the
1585
  /// unfiltered edges are shown in the subdigraph. The FilterEdges is
1586
  /// conform to the \ref concepts::Graph "Graph concept".
1717
  /// FilterEdges adaptor can be used for hiding edges in a graph.
1718
  /// A \c bool edge map must be specified, which defines the filter for
1719
  /// the edges. Only the edges with \c true filter value are shown in the
1720
  /// subgraph. This adaptor conforms to the \ref concepts::Graph
1721
  /// "Graph" concept.
1587 1722
  ///
1588
  /// \tparam _Graph It must be conform to the \ref concepts::Graph
1589
  /// "Graph concept". The type can be specified to be const.
1590
  /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted
1591
  /// graph.
1592
  template<typename _Graph, typename _EdgeFilterMap>
1723
  /// The adapted graph can also be modified through this adaptor
1724
  /// by adding or removing nodes or edges, unless the \c GR template
1725
  /// parameter is set to be \c const.
1726
  ///
1727
  /// \tparam GR The type of the adapted graph.
1728
  /// It must conform to the \ref concepts::Graph "Graph" concept.
1729
  /// It can also be specified to be \c const.
1730
  /// \tparam EF The type of the edge filter map.
1731
  /// It must be a \c bool (or convertible) edge map of the
1732
  /// adapted graph. The default type is
1733
  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
1734
  ///
1735
  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
1736
  /// adapted graph are convertible to each other.
1737
#ifdef DOXYGEN
1738
  template<typename GR,
1739
           typename EF>
1740
  class FilterEdges {
1741
#else
1742
  template<typename GR,
1743
           typename EF = typename GR::template EdgeMap<bool> >
1593 1744
  class FilterEdges :
1594
    public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,
1595
                    _EdgeFilterMap, false> {
1745
    public GraphAdaptorExtender<
1746
      SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> > {
1747
#endif
1596 1748
  public:
1597
    typedef _Graph Graph;
1598
    typedef _EdgeFilterMap EdgeFilterMap;
1599
    typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,
1600
                     EdgeFilterMap, false> Parent;
1749
    /// The type of the adapted graph.
1750
    typedef GR Graph;
1751
    /// The type of the edge filter map.
1752
    typedef EF EdgeFilterMap;
1753

	
1754
    typedef GraphAdaptorExtender<
1755
      SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> >
1756
      Parent;
1757

	
1601 1758
    typedef typename Parent::Edge Edge;
1759

	
1602 1760
  protected:
1603 1761
    ConstMap<typename Graph::Node, bool> const_true_map;
1604 1762

	
1605 1763
    FilterEdges() : const_true_map(true) {
1606 1764
      Parent::setNodeFilterMap(const_true_map);
1607 1765
    }
1608 1766

	
1609 1767
  public:
1610 1768

	
1611 1769
    /// \brief Constructor
1612 1770
    ///
1613
    /// Creates a FilterEdges adaptor for the given graph with
1614
    /// given edge map filters.
1615
    FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :
1771
    /// Creates a subgraph for the given graph with the given edge
1772
    /// filter map.
1773
    FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) :
1616 1774
      Parent(), const_true_map(true) {
1617
      Parent::setGraph(_graph);
1775
      Parent::setGraph(graph);
1618 1776
      Parent::setNodeFilterMap(const_true_map);
1619 1777
      Parent::setEdgeFilterMap(edge_filter_map);
1620 1778
    }
1621 1779

	
1622
    /// \brief Hides the edge of the graph
1780
    /// \brief Sets the status of the given edge
1623 1781
    ///
1624
    /// This function hides \c e in the graph, i.e. the iteration
1625
    /// jumps over it. This is done by simply setting the value of \c e
1626
    /// to be false in the corresponding edge-map.
1627
    void hide(const Edge& e) const { Parent::hide(e); }
1628

	
1629
    /// \brief Unhides the edge of the graph
1782
    /// This function sets the status of the given edge.
1783
    /// It is done by simply setting the assigned value of \c e
1784
    /// to \c v in the edge filter map.
1785
    void status(const Edge& e, bool v) const { Parent::status(e, v); }
1786

	
1787
    /// \brief Returns the status of the given edge
1630 1788
    ///
1631
    /// The value of \c e is set to be true in the edge-map which stores
1632
    /// hide information. If \c e was hidden previuosly, then it is shown
1633
    /// again
1634
    void unHide(const Edge& e) const { Parent::unHide(e); }
1635

	
1636
    /// \brief Returns true if \c e is hidden.
1789
    /// This function returns the status of the given edge.
1790
    /// It is \c true if the given edge is enabled (i.e. not hidden).
1791
    bool status(const Edge& e) const { return Parent::status(e); }
1792

	
1793
    /// \brief Disables the given edge
1637 1794
    ///
1638
    /// Returns true if \c e is hidden.
1795
    /// This function disables the given edge in the subgraph,
1796
    /// so the iteration jumps over it.
1797
    /// It is the same as \ref status() "status(e, false)".
1798
    void disable(const Edge& e) const { Parent::status(e, false); }
1799

	
1800
    /// \brief Enables the given edge
1639 1801
    ///
1640
    bool hidden(const Edge& e) const { return Parent::hidden(e); }
1802
    /// This function enables the given edge in the subgraph.
1803
    /// It is the same as \ref status() "status(e, true)".
1804
    void enable(const Edge& e) const { Parent::status(e, true); }
1641 1805

	
1642 1806
  };
1643 1807

	
1644
  /// \brief Just gives back a FilterEdges adaptor
1808
  /// \brief Returns a read-only FilterEdges adaptor
1645 1809
  ///
1646
  /// Just gives back a FilterEdges adaptor
1647
  template<typename Graph, typename EdgeFilterMap>
1648
  FilterEdges<const Graph, EdgeFilterMap>
1649
  filterEdges(const Graph& graph, EdgeFilterMap& efm) {
1650
    return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);
1810
  /// This function just returns a read-only \ref FilterEdges adaptor.
1811
  /// \ingroup graph_adaptors
1812
  /// \relates FilterEdges
1813
  template<typename GR, typename EF>
1814
  FilterEdges<const GR, EF>
1815
  filterEdges(const GR& graph, EF& edge_filter_map) {
1816
    return FilterEdges<const GR, EF>(graph, edge_filter_map);
1651 1817
  }
1652 1818

	
1653
  template<typename Graph, typename EdgeFilterMap>
1654
  FilterEdges<const Graph, const EdgeFilterMap>
1655
  filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
1656
    return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);
1819
  template<typename GR, typename EF>
1820
  FilterEdges<const GR, const EF>
1821
  filterEdges(const GR& graph, const EF& edge_filter_map) {
1822
    return FilterEdges<const GR, const EF>(graph, edge_filter_map);
1657 1823
  }
1658 1824

	
1825

	
1659 1826
  template <typename _Digraph>
1660 1827
  class UndirectorBase {
1661 1828
  public:
1662 1829
    typedef _Digraph Digraph;
1663 1830
    typedef UndirectorBase Adaptor;
1664 1831

	
... ...
@@ -1692,14 +1859,12 @@
1692 1859
        return _forward < other._forward ||
1693 1860
          (_forward == other._forward &&
1694 1861
           static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
1695 1862
      }
1696 1863
    };
1697 1864

	
1698

	
1699

	
1700 1865
    void first(Node& n) const {
1701 1866
      _digraph->first(n);
1702 1867
    }
1703 1868

	
1704 1869
    void next(Node& n) const {
1705 1870
      _digraph->next(n);
... ...
@@ -1842,18 +2007,21 @@
1842 2007
    void erase(const Node& i) { _digraph->erase(i); }
1843 2008
    void erase(const Edge& i) { _digraph->erase(i); }
1844 2009

	
1845 2010
    void clear() { _digraph->clear(); }
1846 2011

	
1847 2012
    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
1848
    int nodeNum() const { return 2 * _digraph->arcNum(); }
1849
    typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
2013
    int nodeNum() const { return _digraph->nodeNum(); }
2014

	
2015
    typedef ArcNumTagIndicator<Digraph> ArcNumTag;
1850 2016
    int arcNum() const { return 2 * _digraph->arcNum(); }
2017

	
2018
    typedef ArcNumTag EdgeNumTag;
1851 2019
    int edgeNum() const { return _digraph->arcNum(); }
1852 2020

	
1853
    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
2021
    typedef FindArcTagIndicator<Digraph> FindArcTag;
1854 2022
    Arc findArc(Node s, Node t, Arc p = INVALID) const {
1855 2023
      if (p == INVALID) {
1856 2024
        Edge arc = _digraph->findArc(s, t);
1857 2025
        if (arc != INVALID) return direct(arc, true);
1858 2026
        arc = _digraph->findArc(t, s);
1859 2027
        if (arc != INVALID) return direct(arc, false);
... ...
@@ -1866,20 +2034,21 @@
1866 2034
        Edge arc = _digraph->findArc(t, s, p);
1867 2035
        if (arc != INVALID) return direct(arc, false);
1868 2036
      }
1869 2037
      return INVALID;
1870 2038
    }
1871 2039

	
2040
    typedef FindArcTag FindEdgeTag;
1872 2041
    Edge findEdge(Node s, Node t, Edge p = INVALID) const {
1873 2042
      if (s != t) {
1874 2043
        if (p == INVALID) {
1875 2044
          Edge arc = _digraph->findArc(s, t);
1876 2045
          if (arc != INVALID) return arc;
1877 2046
          arc = _digraph->findArc(t, s);
1878 2047
          if (arc != INVALID) return arc;
1879
        } else if (_digraph->s(p) == s) {
2048
        } else if (_digraph->source(p) == s) {
1880 2049
          Edge arc = _digraph->findArc(s, t, p);
1881 2050
          if (arc != INVALID) return arc;
1882 2051
          arc = _digraph->findArc(t, s);
1883 2052
          if (arc != INVALID) return arc;
1884 2053
        } else {
1885 2054
          Edge arc = _digraph->findArc(t, s, p);
... ...
@@ -1902,12 +2071,16 @@
1902 2071
    public:
1903 2072

	
1904 2073
      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
1905 2074

	
1906 2075
      typedef _Value Value;
1907 2076
      typedef Arc Key;
2077
      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
2078
      typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;
2079
      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;
2080
      typedef typename MapTraits<MapImpl>::ReturnValue Reference;
1908 2081

	
1909 2082
      ArcMapBase(const Adaptor& adaptor) :
1910 2083
        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
1911 2084

	
1912 2085
      ArcMapBase(const Adaptor& adaptor, const Value& v)
1913 2086
        : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
... ...
@@ -1917,23 +2090,21 @@
1917 2090
          _forward.set(a, v);
1918 2091
        } else {
1919 2092
          _backward.set(a, v);
1920 2093
        }
1921 2094
      }
1922 2095

	
1923
      typename MapTraits<MapImpl>::ConstReturnValue
1924
      operator[](const Arc& a) const {
2096
      ConstReturnValue operator[](const Arc& a) const {
1925 2097
        if (direction(a)) {
1926 2098
          return _forward[a];
1927 2099
        } else {
1928 2100
          return _backward[a];
1929 2101
        }
1930 2102
      }
1931 2103

	
1932
      typename MapTraits<MapImpl>::ReturnValue
1933
      operator[](const Arc& a) {
2104
      ReturnValue operator[](const Arc& a) {
1934 2105
        if (direction(a)) {
1935 2106
          return _forward[a];
1936 2107
        } else {
1937 2108
          return _backward[a];
1938 2109
        }
1939 2110
      }
... ...
@@ -1977,13 +2148,13 @@
1977 2148
      : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
1978 2149
    {
1979 2150
    public:
1980 2151
      typedef _Value Value;
1981 2152
      typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
1982 2153

	
1983
      ArcMap(const Adaptor& adaptor)
2154
      explicit ArcMap(const Adaptor& adaptor)
1984 2155
        : Parent(adaptor) {}
1985 2156

	
1986 2157
      ArcMap(const Adaptor& adaptor, const Value& value)
1987 2158
        : Parent(adaptor, value) {}
1988 2159

	
1989 2160
    private:
... ...
@@ -2024,12 +2195,15 @@
2024 2195

	
2025 2196
    };
2026 2197

	
2027 2198
    typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
2028 2199
    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
2029 2200

	
2201
    typedef typename ItemSetTraits<Digraph, Edge>::ItemNotifier EdgeNotifier;
2202
    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
2203

	
2030 2204
  protected:
2031 2205

	
2032 2206
    UndirectorBase() : _digraph(0) {}
2033 2207

	
2034 2208
    Digraph* _digraph;
2035 2209

	
... ...
@@ -2038,90 +2212,101 @@
2038 2212
    }
2039 2213

	
2040 2214
  };
2041 2215

	
2042 2216
  /// \ingroup graph_adaptors
2043 2217
  ///
2044
  /// \brief Undirect the graph
2218
  /// \brief Adaptor class for viewing a digraph as an undirected graph.
2045 2219
  ///
2046
  /// This adaptor makes an undirected graph from a directed
2047
  /// graph. All arcs of the underlying digraph will be showed in the
2048
  /// adaptor as an edge. The Orienter adaptor is conform to the \ref
2049
  /// concepts::Graph "Graph concept".
2220
  /// Undirector adaptor can be used for viewing a digraph as an undirected
2221
  /// graph. All arcs of the underlying digraph are showed in the
2222
  /// adaptor as an edge (and also as a pair of arcs, of course).
2223
  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
2050 2224
  ///
2051
  /// \tparam _Digraph It must be conform to the \ref
2052
  /// concepts::Digraph "Digraph concept". The type can be specified
2053
  /// to const.
2054
  template<typename _Digraph>
2055
  class Undirector
2056
    : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
2225
  /// The adapted digraph can also be modified through this adaptor
2226
  /// by adding or removing nodes or edges, unless the \c GR template
2227
  /// parameter is set to be \c const.
2228
  ///
2229
  /// \tparam GR The type of the adapted digraph.
2230
  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
2231
  /// It can also be specified to be \c const.
2232
  ///
2233
  /// \note The \c Node type of this adaptor and the adapted digraph are
2234
  /// convertible to each other, moreover the \c Edge type of the adaptor
2235
  /// and the \c Arc type of the adapted digraph are also convertible to
2236
  /// each other.
2237
  /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type
2238
  /// of the adapted digraph.)
2239
  template<typename GR>
2240
#ifdef DOXYGEN
2241
  class Undirector {
2242
#else
2243
  class Undirector :
2244
    public GraphAdaptorExtender<UndirectorBase<GR> > {
2245
#endif
2057 2246
  public:
2058
    typedef _Digraph Digraph;
2059
    typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
2247
    /// The type of the adapted digraph.
2248
    typedef GR Digraph;
2249
    typedef GraphAdaptorExtender<UndirectorBase<GR> > Parent;
2060 2250
  protected:
2061 2251
    Undirector() { }
2062 2252
  public:
2063 2253

	
2064 2254
    /// \brief Constructor
2065 2255
    ///
2066
    /// Creates a undirected graph from the given digraph
2067
    Undirector(_Digraph& digraph) {
2256
    /// Creates an undirected graph from the given digraph.
2257
    Undirector(Digraph& digraph) {
2068 2258
      setDigraph(digraph);
2069 2259
    }
2070 2260

	
2071
    /// \brief ArcMap combined from two original ArcMap
2261
    /// \brief Arc map combined from two original arc maps
2072 2262
    ///
2073
    /// This class adapts two original digraph ArcMap to
2074
    /// get an arc map on the undirected graph.
2075
    template <typename _ForwardMap, typename _BackwardMap>
2263
    /// This map adaptor class adapts two arc maps of the underlying
2264
    /// digraph to get an arc map of the undirected graph.
2265
    /// Its value type is inherited from the first arc map type
2266
    /// (\c %ForwardMap).
2267
    template <typename ForwardMap, typename BackwardMap>
2076 2268
    class CombinedArcMap {
2077 2269
    public:
2078 2270

	
2079
      typedef _ForwardMap ForwardMap;
2080
      typedef _BackwardMap BackwardMap;
2271
      /// The key type of the map
2272
      typedef typename Parent::Arc Key;
2273
      /// The value type of the map
2274
      typedef typename ForwardMap::Value Value;
2081 2275

	
2082 2276
      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
2083 2277

	
2084
      typedef typename ForwardMap::Value Value;
2085
      typedef typename Parent::Arc Key;
2086

	
2087
      /// \brief Constructor
2088
      ///
2278
      typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;
2279
      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;
2280
      typedef typename MapTraits<ForwardMap>::ReturnValue Reference;
2281
      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;
2282

	
2089 2283
      /// Constructor
2090 2284
      CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
2091 2285
        : _forward(&forward), _backward(&backward) {}
2092 2286

	
2093

	
2094
      /// \brief Sets the value associated with a key.
2095
      ///
2096
      /// Sets the value associated with a key.
2287
      /// Sets the value associated with the given key.
2097 2288
      void set(const Key& e, const Value& a) {
2098 2289
        if (Parent::direction(e)) {
2099 2290
          _forward->set(e, a);
2100 2291
        } else {
2101 2292
          _backward->set(e, a);
2102 2293
        }
2103 2294
      }
2104 2295

	
2105
      /// \brief Returns the value associated with a key.
2106
      ///
2107
      /// Returns the value associated with a key.
2108
      typename MapTraits<ForwardMap>::ConstReturnValue
2109
      operator[](const Key& e) const {
2296
      /// Returns the value associated with the given key.
2297
      ConstReturnValue operator[](const Key& e) const {
2110 2298
        if (Parent::direction(e)) {
2111 2299
          return (*_forward)[e];
2112 2300
        } else {
2113 2301
          return (*_backward)[e];
2114 2302
        }
2115 2303
      }
2116 2304

	
2117
      /// \brief Returns the value associated with a key.
2118
      ///
2119
      /// Returns the value associated with a key.
2120
      typename MapTraits<ForwardMap>::ReturnValue
2121
      operator[](const Key& e) {
2305
      /// Returns a reference to the value associated with the given key.
2306
      ReturnValue operator[](const Key& e) {
2122 2307
        if (Parent::direction(e)) {
2123 2308
          return (*_forward)[e];
2124 2309
        } else {
2125 2310
          return (*_backward)[e];
2126 2311
        }
2127 2312
      }
... ...
@@ -2130,15 +2315,15 @@
2130 2315

	
2131 2316
      ForwardMap* _forward;
2132 2317
      BackwardMap* _backward;
2133 2318

	
2134 2319
    };
2135 2320

	
2136
    /// \brief Just gives back a combined arc map
2321
    /// \brief Returns a combined arc map
2137 2322
    ///
2138
    /// Just gives back a combined arc map
2323
    /// This function just returns a combined arc map.
2139 2324
    template <typename ForwardMap, typename BackwardMap>
2140 2325
    static CombinedArcMap<ForwardMap, BackwardMap>
2141 2326
    combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
2142 2327
      return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
2143 2328
    }
2144 2329

	
... ...
@@ -2162,21 +2347,23 @@
2162 2347
      return CombinedArcMap<const ForwardMap,
2163 2348
        const BackwardMap>(forward, backward);
2164 2349
    }
2165 2350

	
2166 2351
  };
2167 2352

	
2168
  /// \brief Just gives back an undirected view of the given digraph
2353
  /// \brief Returns a read-only Undirector adaptor
2169 2354
  ///
2170
  /// Just gives back an undirected view of the given digraph
2171
  template<typename Digraph>
2172
  Undirector<const Digraph>
2173
  undirector(const Digraph& digraph) {
2174
    return Undirector<const Digraph>(digraph);
2355
  /// This function just returns a read-only \ref Undirector adaptor.
2356
  /// \ingroup graph_adaptors
2357
  /// \relates Undirector
2358
  template<typename GR>
2359
  Undirector<const GR> undirector(const GR& digraph) {
2360
    return Undirector<const GR>(digraph);
2175 2361
  }
2176 2362

	
2363

	
2177 2364
  template <typename _Graph, typename _DirectionMap>
2178 2365
  class OrienterBase {
2179 2366
  public:
2180 2367

	
2181 2368
    typedef _Graph Graph;
2182 2369
    typedef _DirectionMap DirectionMap;
... ...
@@ -2188,18 +2375,18 @@
2188 2375
      _direction->set(arc, !(*_direction)[arc]);
2189 2376
    }
2190 2377

	
2191 2378
    void first(Node& i) const { _graph->first(i); }
2192 2379
    void first(Arc& i) const { _graph->first(i); }
2193 2380
    void firstIn(Arc& i, const Node& n) const {
2194
      bool d;
2381
      bool d = true;
2195 2382
      _graph->firstInc(i, d, n);
2196 2383
      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
2197 2384
    }
2198 2385
    void firstOut(Arc& i, const Node& n ) const {
2199
      bool d;
2386
      bool d = true;
2200 2387
      _graph->firstInc(i, d, n);
2201 2388
      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
2202 2389
    }
2203 2390

	
2204 2391
    void next(Node& i) const { _graph->next(i); }
2205 2392
    void next(Arc& i) const { _graph->next(i); }
... ...
@@ -2221,41 +2408,32 @@
2221 2408
      return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
2222 2409
    }
2223 2410

	
2224 2411
    typedef NodeNumTagIndicator<Graph> NodeNumTag;
2225 2412
    int nodeNum() const { return _graph->nodeNum(); }
2226 2413

	
2227
    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
2414
    typedef EdgeNumTagIndicator<Graph> ArcNumTag;
2228 2415
    int arcNum() const { return _graph->edgeNum(); }
2229 2416

	
2230
    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
2417
    typedef FindEdgeTagIndicator<Graph> FindArcTag;
2231 2418
    Arc findArc(const Node& u, const Node& v,
2232
                const Arc& prev = INVALID) {
2233
      Arc arc = prev;
2234
      bool d = arc == INVALID ? true : (*_direction)[arc];
2235
      if (d) {
2419
                const Arc& prev = INVALID) const {
2420
      Arc arc = _graph->findEdge(u, v, prev);
2421
      while (arc != INVALID && source(arc) != u) {
2236 2422
        arc = _graph->findEdge(u, v, arc);
2237
        while (arc != INVALID && !(*_direction)[arc]) {
2238
          _graph->findEdge(u, v, arc);
2239
        }
2240
        if (arc != INVALID) return arc;
2241
      }
2242
      _graph->findEdge(v, u, arc);
2243
      while (arc != INVALID && (*_direction)[arc]) {
2244
        _graph->findEdge(u, v, arc);
2245 2423
      }
2246 2424
      return arc;
2247 2425
    }
2248 2426

	
2249 2427
    Node addNode() {
2250 2428
      return Node(_graph->addNode());
2251 2429
    }
2252 2430

	
2253 2431
    Arc addArc(const Node& u, const Node& v) {
2254
      Arc arc = _graph->addArc(u, v);
2255
      _direction->set(arc, _graph->source(arc) == u);
2432
      Arc arc = _graph->addEdge(u, v);
2433
      _direction->set(arc, _graph->u(arc) == u);
2256 2434
      return arc;
2257 2435
    }
2258 2436

	
2259 2437
    void erase(const Node& i) { _graph->erase(i); }
2260 2438
    void erase(const Arc& i) { _graph->erase(i); }
2261 2439

	
... ...
@@ -2340,84 +2518,104 @@
2340 2518
    }
2341 2519

	
2342 2520
  };
2343 2521

	
2344 2522
  /// \ingroup graph_adaptors
2345 2523
  ///
2346
  /// \brief Orients the edges of the graph to get a digraph
2524
  /// \brief Adaptor class for orienting the edges of a graph to get a digraph
2347 2525
  ///
2348
  /// This adaptor orients each edge in the undirected graph. The
2349
  /// direction of the arcs stored in an edge node map.  The arcs can
2350
  /// be easily reverted by the \c reverseArc() member function in the
2351
  /// adaptor. The Orienter adaptor is conform to the \ref
2352
  /// concepts::Digraph "Digraph concept".
2526
  /// Orienter adaptor can be used for orienting the edges of a graph to
2527
  /// get a digraph. A \c bool edge map of the underlying graph must be
2528
  /// specified, which define the direction of the arcs in the adaptor.
2529
  /// The arcs can be easily reversed by the \c reverseArc() member function
2530
  /// of the adaptor.
2531
  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
2353 2532
  ///
2354
  /// \tparam _Graph It must be conform to the \ref concepts::Graph
2355
  /// "Graph concept". The type can be specified to be const.
2356
  /// \tparam _DirectionMap A bool valued edge map of the the adapted
2357
  /// graph.
2533
  /// The adapted graph can also be modified through this adaptor
2534
  /// by adding or removing nodes or arcs, unless the \c GR template
2535
  /// parameter is set to be \c const.
2358 2536
  ///
2359
  /// \sa orienter
2360
  template<typename _Graph,
2361
           typename DirectionMap = typename _Graph::template EdgeMap<bool> >
2537
  /// \tparam GR The type of the adapted graph.
2538
  /// It must conform to the \ref concepts::Graph "Graph" concept.
2539
  /// It can also be specified to be \c const.
2540
  /// \tparam DM The type of the direction map.
2541
  /// It must be a \c bool (or convertible) edge map of the
2542
  /// adapted graph. The default type is
2543
  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
2544
  ///
2545
  /// \note The \c Node type of this adaptor and the adapted graph are
2546
  /// convertible to each other, moreover the \c Arc type of the adaptor
2547
  /// and the \c Edge type of the adapted graph are also convertible to
2548
  /// each other.
2549
#ifdef DOXYGEN
2550
  template<typename GR,
2551
           typename DM>
2552
  class Orienter {
2553
#else
2554
  template<typename GR,
2555
           typename DM = typename GR::template EdgeMap<bool> >
2362 2556
  class Orienter :
2363
    public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {
2557
    public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
2558
#endif
2364 2559
  public:
2365
    typedef _Graph Graph;
2366
    typedef DigraphAdaptorExtender<
2367
      OrienterBase<_Graph, DirectionMap> > Parent;
2560

	
2561
    /// The type of the adapted graph.
2562
    typedef GR Graph;
2563
    /// The type of the direction edge map.
2564
    typedef DM DirectionMap;
2565

	
2566
    typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
2368 2567
    typedef typename Parent::Arc Arc;
2369 2568
  protected:
2370 2569
    Orienter() { }
2371 2570
  public:
2372 2571

	
2373
    /// \brief Constructor of the adaptor
2572
    /// \brief Constructor
2374 2573
    ///
2375
    /// Constructor of the adaptor
2574
    /// Constructor of the adaptor.
2376 2575
    Orienter(Graph& graph, DirectionMap& direction) {
2377 2576
      setGraph(graph);
2378 2577
      setDirectionMap(direction);
2379 2578
    }
2380 2579

	
2381
    /// \brief Reverse arc
2580
    /// \brief Reverses the given arc
2382 2581
    ///
2383
    /// It reverse the given arc. It simply negate the direction in the map.
2582
    /// This function reverses the given arc.
2583
    /// It is done by simply negate the assigned value of \c a
2584
    /// in the direction map.
2384 2585
    void reverseArc(const Arc& a) {
2385 2586
      Parent::reverseArc(a);
2386 2587
    }
2387 2588
  };
2388 2589

	
2389
  /// \brief Just gives back a Orienter
2590
  /// \brief Returns a read-only Orienter adaptor
2390 2591
  ///
2391
  /// Just gives back a Orienter
2392
  template<typename Graph, typename DirectionMap>
2393
  Orienter<const Graph, DirectionMap>
2394
  orienter(const Graph& graph, DirectionMap& dm) {
2395
    return Orienter<const Graph, DirectionMap>(graph, dm);
2592
  /// This function just returns a read-only \ref Orienter adaptor.
2593
  /// \ingroup graph_adaptors
2594
  /// \relates Orienter
2595
  template<typename GR, typename DM>
2596
  Orienter<const GR, DM>
2597
  orienter(const GR& graph, DM& direction_map) {
2598
    return Orienter<const GR, DM>(graph, direction_map);
2396 2599
  }
2397 2600

	
2398
  template<typename Graph, typename DirectionMap>
2399
  Orienter<const Graph, const DirectionMap>
2400
  orienter(const Graph& graph, const DirectionMap& dm) {
2401
    return Orienter<const Graph, const DirectionMap>(graph, dm);
2601
  template<typename GR, typename DM>
2602
  Orienter<const GR, const DM>
2603
  orienter(const GR& graph, const DM& direction_map) {
2604
    return Orienter<const GR, const DM>(graph, direction_map);
2402 2605
  }
2403 2606

	
2404 2607
  namespace _adaptor_bits {
2405 2608

	
2406
    template<typename _Digraph,
2407
             typename _CapacityMap = typename _Digraph::template ArcMap<int>,
2408
             typename _FlowMap = _CapacityMap,
2409
             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
2609
    template<typename Digraph,
2610
             typename CapacityMap,
2611
             typename FlowMap,
2612
             typename Tolerance>
2410 2613
    class ResForwardFilter {
2411 2614
    public:
2412 2615

	
2413
      typedef _Digraph Digraph;
2414
      typedef _CapacityMap CapacityMap;
2415
      typedef _FlowMap FlowMap;
2416
      typedef _Tolerance Tolerance;
2417

	
2418 2616
      typedef typename Digraph::Arc Key;
2419 2617
      typedef bool Value;
2420 2618

	
2421 2619
    private:
2422 2620

	
2423 2621
      const CapacityMap* _capacity;
... ...
@@ -2431,24 +2629,19 @@
2431 2629

	
2432 2630
      bool operator[](const typename Digraph::Arc& a) const {
2433 2631
        return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
2434 2632
      }
2435 2633
    };
2436 2634

	
2437
    template<typename _Digraph,
2438
             typename _CapacityMap = typename _Digraph::template ArcMap<int>,
2439
             typename _FlowMap = _CapacityMap,
2440
             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
2635
    template<typename Digraph,
2636
             typename CapacityMap,
2637
             typename FlowMap,
2638
             typename Tolerance>
2441 2639
    class ResBackwardFilter {
2442 2640
    public:
2443 2641

	
2444
      typedef _Digraph Digraph;
2445
      typedef _CapacityMap CapacityMap;
2446
      typedef _FlowMap FlowMap;
2447
      typedef _Tolerance Tolerance;
2448

	
2449 2642
      typedef typename Digraph::Arc Key;
2450 2643
      typedef bool Value;
2451 2644

	
2452 2645
    private:
2453 2646

	
2454 2647
      const CapacityMap* _capacity;
... ...
@@ -2467,56 +2660,77 @@
2467 2660
    };
2468 2661

	
2469 2662
  }
2470 2663

	
2471 2664
  /// \ingroup graph_adaptors
2472 2665
  ///
2473
  /// \brief An adaptor for composing the residual graph for directed
2666
  /// \brief Adaptor class for composing the residual digraph for directed
2474 2667
  /// flow and circulation problems.
2475 2668
  ///
2476
  /// An adaptor for composing the residual graph for directed flow and
2477
  /// circulation problems.  Let \f$ G=(V, A) \f$ be a directed graph
2478
  /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
2479
  /// be functions on the arc-set.
2669
  /// Residual can be used for composing the \e residual digraph for directed
2670
  /// flow and circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
2671
  /// and let \f$ F \f$ be a number type. Let \f$ flow, cap: A\to F \f$ be
2672
  /// functions on the arcs.
2673
  /// This adaptor implements a digraph structure with node set \f$ V \f$
2674
  /// and arc set \f$ A_{forward}\cup A_{backward} \f$,
2675
  /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and
2676
  /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so
2677
  /// called residual digraph.
2678
  /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,
2679
  /// multiplicities are counted, i.e. the adaptor has exactly
2680
  /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel
2681
  /// arcs).
2682
  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
2480 2683
  ///
2481
  /// Then Residual implements the digraph structure with
2482
  /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$,
2483
  /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
2484
  /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
2485
  /// called residual graph.  When we take the union
2486
  /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted,
2487
  /// i.e.  if an arc is in both \f$ A_{forward} \f$ and
2488
  /// \f$ A_{backward} \f$, then in the adaptor it appears in both
2489
  /// orientation.
2684
  /// \tparam GR The type of the adapted digraph.
2685
  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
2686
  /// It is implicitly \c const.
2687
  /// \tparam CM The type of the capacity map.
2688
  /// It must be an arc map of some numerical type, which defines
2689
  /// the capacities in the flow problem. It is implicitly \c const.
2690
  /// The default type is
2691
  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
2692
  /// \tparam FM The type of the flow map.
2693
  /// It must be an arc map of some numerical type, which defines
2694
  /// the flow values in the flow problem. The default type is \c CM.
2695
  /// \tparam TL The tolerance type for handling inexact computation.
2696
  /// The default tolerance type depends on the value type of the
2697
  /// capacity map.
2490 2698
  ///
2491
  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
2492
  /// "Digraph concept". The type is implicitly const.
2493
  /// \tparam _CapacityMap An arc map of some numeric type, it defines
2494
  /// the capacities in the flow problem. The map is implicitly const.
2495
  /// \tparam _FlowMap An arc map of some numeric type, it defines
2496
  /// the capacities in the flow problem.
2497
  /// \tparam _Tolerance Handler for inexact computation.
2498
  template<typename _Digraph,
2499
           typename _CapacityMap = typename _Digraph::template ArcMap<int>,
2500
           typename _FlowMap = _CapacityMap,
2501
           typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
2699
  /// \note This adaptor is implemented using Undirector and FilterArcs
2700
  /// adaptors.
2701
  ///
2702
  /// \note The \c Node type of this adaptor and the adapted digraph are
2703
  /// convertible to each other, moreover the \c Arc type of the adaptor
2704
  /// is convertible to the \c Arc type of the adapted digraph.
2705
#ifdef DOXYGEN
2706
  template<typename GR, typename CM, typename FM, typename TL>
2707
  class Residual
2708
#else
2709
  template<typename GR,
2710
           typename CM = typename GR::template ArcMap<int>,
2711
           typename FM = CM,
2712
           typename TL = Tolerance<typename CM::Value> >
2502 2713
  class Residual :
2503 2714
    public FilterArcs<
2504
    Undirector<const _Digraph>,
2505
    typename Undirector<const _Digraph>::template CombinedArcMap<
2506
      _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,
2507
                                      _FlowMap, _Tolerance>,
2508
      _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,
2509
                                       _FlowMap, _Tolerance> > >
2715
      Undirector<const GR>,
2716
      typename Undirector<const GR>::template CombinedArcMap<
2717
        _adaptor_bits::ResForwardFilter<const GR, CM, FM, TL>,
2718
        _adaptor_bits::ResBackwardFilter<const GR, CM, FM, TL> > >
2719
#endif
2510 2720
  {
2511 2721
  public:
2512 2722

	
2513
    typedef _Digraph Digraph;
2514
    typedef _CapacityMap CapacityMap;
2515
    typedef _FlowMap FlowMap;
2516
    typedef _Tolerance Tolerance;
2723
    /// The type of the underlying digraph.
2724
    typedef GR Digraph;
2725
    /// The type of the capacity map.
2726
    typedef CM CapacityMap;
2727
    /// The type of the flow map.
2728
    typedef FM FlowMap;
2729
    /// The tolerance type.
2730
    typedef TL Tolerance;
2517 2731

	
2518 2732
    typedef typename CapacityMap::Value Value;
2519 2733
    typedef Residual Adaptor;
2520 2734

	
2521 2735
  protected:
2522 2736

	
... ...
@@ -2526,13 +2740,13 @@
2526 2740
                                            FlowMap, Tolerance> ForwardFilter;
2527 2741

	
2528 2742
    typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
2529 2743
                                             FlowMap, Tolerance> BackwardFilter;
2530 2744

	
2531 2745
    typedef typename Undirected::
2532
    template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
2746
      template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
2533 2747

	
2534 2748
    typedef FilterArcs<Undirected, ArcFilter> Parent;
2535 2749

	
2536 2750
    const CapacityMap* _capacity;
2537 2751
    FlowMap* _flow;
2538 2752

	
... ...
@@ -2540,16 +2754,16 @@
2540 2754
    ForwardFilter _forward_filter;
2541 2755
    BackwardFilter _backward_filter;
2542 2756
    ArcFilter _arc_filter;
2543 2757

	
2544 2758
  public:
2545 2759

	
2546
    /// \brief Constructor of the residual digraph.
2760
    /// \brief Constructor
2547 2761
    ///
2548
    /// Constructor of the residual graph. The parameters are the digraph,
2549
    /// the flow map, the capacity map and a tolerance object.
2762
    /// Constructor of the residual digraph adaptor. The parameters are the
2763
    /// digraph, the capacity map, the flow map, and a tolerance object.
2550 2764
    Residual(const Digraph& digraph, const CapacityMap& capacity,
2551 2765
             FlowMap& flow, const Tolerance& tolerance = Tolerance())
2552 2766
      : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
2553 2767
        _forward_filter(capacity, flow, tolerance),
2554 2768
        _backward_filter(capacity, flow, tolerance),
2555 2769
        _arc_filter(_forward_filter, _backward_filter)
... ...
@@ -2557,89 +2771,114 @@
2557 2771
      Parent::setDigraph(_graph);
2558 2772
      Parent::setArcFilterMap(_arc_filter);
2559 2773
    }
2560 2774

	
2561 2775
    typedef typename Parent::Arc Arc;
2562 2776

	
2563
    /// \brief Gives back the residual capacity of the arc.
2777
    /// \brief Returns the residual capacity of the given arc.
2564 2778
    ///
2565
    /// Gives back the residual capacity of the arc.
2779
    /// Returns the residual capacity of the given arc.
2566 2780
    Value residualCapacity(const Arc& a) const {
2567 2781
      if (Undirected::direction(a)) {
2568 2782
        return (*_capacity)[a] - (*_flow)[a];
2569 2783
      } else {
2570 2784
        return (*_flow)[a];
2571 2785
      }
2572 2786
    }
2573 2787

	
2574
    /// \brief Augment on the given arc in the residual graph.
2788
    /// \brief Augments on the given arc in the residual digraph.
2575 2789
    ///
2576
    /// Augment on the given arc in the residual graph. It increase
2577
    /// or decrease the flow on the original arc depend on the direction
2578
    /// of the residual arc.
2790
    /// Augments on the given arc in the residual digraph. It increases
2791
    /// or decreases the flow value on the original arc according to the
2792
    /// direction of the residual arc.
2579 2793
    void augment(const Arc& a, const Value& v) const {
2580 2794
      if (Undirected::direction(a)) {
2581 2795
        _flow->set(a, (*_flow)[a] + v);
2582 2796
      } else {
2583 2797
        _flow->set(a, (*_flow)[a] - v);
2584 2798
      }
2585 2799
    }
2586 2800

	
2587
    /// \brief Returns the direction of the arc.
2801
    /// \brief Returns \c true if the given residual arc is a forward arc.
2588 2802
    ///
2589
    /// Returns true when the arc is same oriented as the original arc.
2803
    /// Returns \c true if the given residual arc has the same orientation
2804
    /// as the original arc, i.e. it is a so called forward arc.
2590 2805
    static bool forward(const Arc& a) {
2591 2806
      return Undirected::direction(a);
2592 2807
    }
2593 2808

	
2594
    /// \brief Returns the direction of the arc.
2809
    /// \brief Returns \c true if the given residual arc is a backward arc.
2595 2810
    ///
2596
    /// Returns true when the arc is opposite oriented as the original arc.
2811
    /// Returns \c true if the given residual arc has the opposite orientation
2812
    /// than the original arc, i.e. it is a so called backward arc.
2597 2813
    static bool backward(const Arc& a) {
2598 2814
      return !Undirected::direction(a);
2599 2815
    }
2600 2816

	
2601
    /// \brief Gives back the forward oriented residual arc.
2817
    /// \brief Returns the forward oriented residual arc.
2602 2818
    ///
2603
    /// Gives back the forward oriented residual arc.
2819
    /// Returns the forward oriented residual arc related to the given
2820
    /// arc of the underlying digraph.
2604 2821
    static Arc forward(const typename Digraph::Arc& a) {
2605 2822
      return Undirected::direct(a, true);
2606 2823
    }
2607 2824

	
2608
    /// \brief Gives back the backward oriented residual arc.
2825
    /// \brief Returns the backward oriented residual arc.
2609 2826
    ///
2610
    /// Gives back the backward oriented residual arc.
2827
    /// Returns the backward oriented residual arc related to the given
2828
    /// arc of the underlying digraph.
2611 2829
    static Arc backward(const typename Digraph::Arc& a) {
2612 2830
      return Undirected::direct(a, false);
2613 2831
    }
2614 2832

	
2615 2833
    /// \brief Residual capacity map.
2616 2834
    ///
2617
    /// In generic residual graph the residual capacity can be obtained
2618
    /// as a map.
2835
    /// This map adaptor class can be used for obtaining the residual
2836
    /// capacities as an arc map of the residual digraph.
2837
    /// Its value type is inherited from the capacity map.
2619 2838
    class ResidualCapacity {
2620 2839
    protected:
2621 2840
      const Adaptor* _adaptor;
2622 2841
    public:
2623
      /// The Key type
2842
      /// The key type of the map
2624 2843
      typedef Arc Key;
2625
      /// The Value type
2626
      typedef typename _CapacityMap::Value Value;
2844
      /// The value type of the map
2845
      typedef typename CapacityMap::Value Value;
2627 2846

	
2628 2847
      /// Constructor
2629 2848
      ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
2630 2849

	
2631
      /// \e
2850
      /// Returns the value associated with the given residual arc
2632 2851
      Value operator[](const Arc& a) const {
2633 2852
        return _adaptor->residualCapacity(a);
2634 2853
      }
2635 2854

	
2636 2855
    };
2637 2856

	
2857
    /// \brief Returns a residual capacity map
2858
    ///
2859
    /// This function just returns a residual capacity map.
2860
    ResidualCapacity residualCapacity() const {
2861
      return ResidualCapacity(*this);
2862
    }
2863

	
2638 2864
  };
2639 2865

	
2866
  /// \brief Returns a (read-only) Residual adaptor
2867
  ///
2868
  /// This function just returns a (read-only) \ref Residual adaptor.
2869
  /// \ingroup graph_adaptors
2870
  /// \relates Residual
2871
  template<typename GR, typename CM, typename FM>
2872
  Residual<GR, CM, FM> residual(const GR& digraph,
2873
                                const CM& capacity_map,
2874
                                FM& flow_map) {
2875
    return Residual<GR, CM, FM> (digraph, capacity_map, flow_map);
2876
  }
2877

	
2878

	
2640 2879
  template <typename _Digraph>
2641 2880
  class SplitNodesBase {
2642 2881
  public:
2643 2882

	
2644 2883
    typedef _Digraph Digraph;
2645 2884
    typedef DigraphAdaptorBase<const _Digraph> Parent;
... ...
@@ -2881,36 +3120,32 @@
2881 3120

	
2882 3121
    static Arc arc(const DigraphArc& e) {
2883 3122
      return Arc(e);
2884 3123
    }
2885 3124

	
2886 3125
    typedef True NodeNumTag;
2887

	
2888 3126
    int nodeNum() const {
2889 3127
      return  2 * countNodes(*_digraph);
2890 3128
    }
2891 3129

	
2892
    typedef True EdgeNumTag;
3130
    typedef True ArcNumTag;
2893 3131
    int arcNum() const {
2894 3132
      return countArcs(*_digraph) + countNodes(*_digraph);
2895 3133
    }
2896 3134

	
2897
    typedef True FindEdgeTag;
3135
    typedef True FindArcTag;
2898 3136
    Arc findArc(const Node& u, const Node& v,
2899 3137
                const Arc& prev = INVALID) const {
2900
      if (inNode(u)) {
2901
        if (outNode(v)) {
2902
          if (static_cast<const DigraphNode&>(u) ==
2903
              static_cast<const DigraphNode&>(v) && prev == INVALID) {
2904
            return Arc(u);
2905
          }
3138
      if (inNode(u) && outNode(v)) {
3139
        if (static_cast<const DigraphNode&>(u) ==
3140
            static_cast<const DigraphNode&>(v) && prev == INVALID) {
3141
          return Arc(u);
2906 3142
        }
2907
      } else {
2908
        if (inNode(v)) {
2909
          return Arc(::lemon::findArc(*_digraph, u, v, prev));
2910
        }
3143
      }
3144
      else if (outNode(u) && inNode(v)) {
3145
        return Arc(::lemon::findArc(*_digraph, u, v, prev));
2911 3146
      }
2912 3147
      return INVALID;
2913 3148
    }
2914 3149

	
2915 3150
  private:
2916 3151

	
... ...
@@ -2918,32 +3153,35 @@
2918 3153
    class NodeMapBase
2919 3154
      : public MapTraits<typename Parent::template NodeMap<_Value> > {
2920 3155
      typedef typename Parent::template NodeMap<_Value> NodeImpl;
2921 3156
    public:
2922 3157
      typedef Node Key;
2923 3158
      typedef _Value Value;
3159
      typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
3160
      typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
3161
      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;
3162
      typedef typename MapTraits<NodeImpl>::ReturnValue Reference;
3163
      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
2924 3164

	
2925 3165
      NodeMapBase(const Adaptor& adaptor)
2926 3166
        : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
2927 3167
      NodeMapBase(const Adaptor& adaptor, const Value& value)
2928 3168
        : _in_map(*adaptor._digraph, value),
2929 3169
          _out_map(*adaptor._digraph, value) {}
2930 3170

	
2931 3171
      void set(const Node& key, const Value& val) {
2932 3172
        if (Adaptor::inNode(key)) { _in_map.set(key, val); }
2933 3173
        else {_out_map.set(key, val); }
2934 3174
      }
2935 3175

	
2936
      typename MapTraits<NodeImpl>::ReturnValue
2937
      operator[](const Node& key) {
3176
      ReturnValue operator[](const Node& key) {
2938 3177
        if (Adaptor::inNode(key)) { return _in_map[key]; }
2939 3178
        else { return _out_map[key]; }
2940 3179
      }
2941 3180

	
2942
      typename MapTraits<NodeImpl>::ConstReturnValue
2943
      operator[](const Node& key) const {
3181
      ConstReturnValue operator[](const Node& key) const {
2944 3182
        if (Adaptor::inNode(key)) { return _in_map[key]; }
2945 3183
        else { return _out_map[key]; }
2946 3184
      }
2947 3185

	
2948 3186
    private:
2949 3187
      NodeImpl _in_map, _out_map;
... ...
@@ -2954,12 +3192,17 @@
2954 3192
      : public MapTraits<typename Parent::template ArcMap<_Value> > {
2955 3193
      typedef typename Parent::template ArcMap<_Value> ArcImpl;
2956 3194
      typedef typename Parent::template NodeMap<_Value> NodeImpl;
2957 3195
    public:
2958 3196
      typedef Arc Key;
2959 3197
      typedef _Value Value;
3198
      typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
3199
      typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
3200
      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;
3201
      typedef typename MapTraits<ArcImpl>::ReturnValue Reference;
3202
      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
2960 3203

	
2961 3204
      ArcMapBase(const Adaptor& adaptor)
2962 3205
        : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
2963 3206
      ArcMapBase(const Adaptor& adaptor, const Value& value)
2964 3207
        : _arc_map(*adaptor._digraph, value),
2965 3208
          _node_map(*adaptor._digraph, value) {}
... ...
@@ -2969,23 +3212,21 @@
2969 3212
          _arc_map.set(key._item.first(), val);
2970 3213
        } else {
2971 3214
          _node_map.set(key._item.second(), val);
2972 3215
        }
2973 3216
      }
2974 3217

	
2975
      typename MapTraits<ArcImpl>::ReturnValue
2976
      operator[](const Arc& key) {
3218
      ReturnValue operator[](const Arc& key) {
2977 3219
        if (Adaptor::origArc(key)) {
2978 3220
          return _arc_map[key._item.first()];
2979 3221
        } else {
2980 3222
          return _node_map[key._item.second()];
2981 3223
        }
2982 3224
      }
2983 3225

	
2984
      typename MapTraits<ArcImpl>::ConstReturnValue
2985
      operator[](const Arc& key) const {
3226
      ConstReturnValue operator[](const Arc& key) const {
2986 3227
        if (Adaptor::origArc(key)) {
2987 3228
          return _arc_map[key._item.first()];
2988 3229
        } else {
2989 3230
          return _node_map[key._item.second()];
2990 3231
        }
2991 3232
      }
... ...
@@ -3060,149 +3301,167 @@
3060 3301
    }
3061 3302

	
3062 3303
  };
3063 3304

	
3064 3305
  /// \ingroup graph_adaptors
3065 3306
  ///
3066
  /// \brief Split the nodes of a directed graph
3307
  /// \brief Adaptor class for splitting the nodes of a digraph.
3067 3308
  ///
3068
  /// The SplitNodes adaptor splits each node into an in-node and an
3069
  /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in
3070
  /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node
3071
  /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the
3072
  /// original digraph the new target of the arc will be \f$ u_{in} \f$
3073
  /// and similarly the source of the original \f$ (u, v) \f$ arc
3074
  /// will be \f$ u_{out} \f$.  The adaptor will add for each node in
3075
  /// the original digraph an additional arc which connects
3076
  /// \f$ (u_{in}, u_{out}) \f$.
3309
  /// SplitNodes adaptor can be used for splitting each node into an
3310
  /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor
3311
  /// replaces each node \f$ u \f$ in the digraph with two nodes,
3312
  /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.
3313
  /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the
3314
  /// new target of the arc will be \f$ u_{in} \f$ and similarly the
3315
  /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.
3316
  /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$
3317
  /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.
3077 3318
  ///
3078
  /// The aim of this class is to run algorithm with node costs if the
3079
  /// algorithm can use directly just arc costs. In this case we should use
3080
  /// a \c SplitNodes and set the node cost of the graph to the
3081
  /// bind arc in the adapted graph.
3319
  /// The aim of this class is running an algorithm with respect to node
3320
  /// costs or capacities if the algorithm considers only arc costs or
3321
  /// capacities directly.
3322
  /// In this case you can use \c SplitNodes adaptor, and set the node
3323
  /// costs/capacities of the original digraph to the \e bind \e arcs
3324
  /// in the adaptor.
3082 3325
  ///
3083
  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
3084
  /// "Digraph concept". The type can be specified to be const.
3085
  template <typename _Digraph>
3326
  /// \tparam GR The type of the adapted digraph.
3327
  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
3328
  /// It is implicitly \c const.
3329
  ///
3330
  /// \note The \c Node type of this adaptor is converible to the \c Node
3331
  /// type of the adapted digraph.
3332
  template <typename GR>
3333
#ifdef DOXYGEN
3334
  class SplitNodes {
3335
#else
3086 3336
  class SplitNodes
3087
    : public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > {
3337
    : public DigraphAdaptorExtender<SplitNodesBase<const GR> > {
3338
#endif
3088 3339
  public:
3089
    typedef _Digraph Digraph;
3090
    typedef DigraphAdaptorExtender<SplitNodesBase<Digraph> > Parent;
3340
    typedef GR Digraph;
3341
    typedef DigraphAdaptorExtender<SplitNodesBase<const GR> > Parent;
3091 3342

	
3092 3343
    typedef typename Digraph::Node DigraphNode;
3093 3344
    typedef typename Digraph::Arc DigraphArc;
3094 3345

	
3095 3346
    typedef typename Parent::Node Node;
3096 3347
    typedef typename Parent::Arc Arc;
3097 3348

	
3098
    /// \brief Constructor of the adaptor.
3349
    /// \brief Constructor
3099 3350
    ///
3100 3351
    /// Constructor of the adaptor.
3101
    SplitNodes(Digraph& g) {
3352
    SplitNodes(const Digraph& g) {
3102 3353
      Parent::setDigraph(g);
3103 3354
    }
3104 3355

	
3105
    /// \brief Returns true when the node is in-node.
3356
    /// \brief Returns \c true if the given node is an in-node.
3106 3357
    ///
3107
    /// Returns true when the node is in-node.
3358
    /// Returns \c true if the given node is an in-node.
3108 3359
    static bool inNode(const Node& n) {
3109 3360
      return Parent::inNode(n);
3110 3361
    }
3111 3362

	
3112
    /// \brief Returns true when the node is out-node.
3363
    /// \brief Returns \c true if the given node is an out-node.
3113 3364
    ///
3114
    /// Returns true when the node is out-node.
3365
    /// Returns \c true if the given node is an out-node.
3115 3366
    static bool outNode(const Node& n) {
3116 3367
      return Parent::outNode(n);
3117 3368
    }
3118 3369

	
3119
    /// \brief Returns true when the arc is arc in the original digraph.
3370
    /// \brief Returns \c true if the given arc is an original arc.
3120 3371
    ///
3121
    /// Returns true when the arc is arc in the original digraph.
3372
    /// Returns \c true if the given arc is one of the arcs in the
3373
    /// original digraph.
3122 3374
    static bool origArc(const Arc& a) {
3123 3375
      return Parent::origArc(a);
3124 3376
    }
3125 3377

	
3126
    /// \brief Returns true when the arc binds an in-node and an out-node.
3378
    /// \brief Returns \c true if the given arc is a bind arc.
3127 3379
    ///
3128
    /// Returns true when the arc binds an in-node and an out-node.
3380
    /// Returns \c true if the given arc is a bind arc, i.e. it connects
3381
    /// an in-node and an out-node.
3129 3382
    static bool bindArc(const Arc& a) {
3130 3383
      return Parent::bindArc(a);
3131 3384
    }
3132 3385

	
3133
    /// \brief Gives back the in-node created from the \c node.
3386
    /// \brief Returns the in-node created from the given original node.
3134 3387
    ///
3135
    /// Gives back the in-node created from the \c node.
3388
    /// Returns the in-node created from the given original node.
3136 3389
    static Node inNode(const DigraphNode& n) {
3137 3390
      return Parent::inNode(n);
3138 3391
    }
3139 3392

	
3140
    /// \brief Gives back the out-node created from the \c node.
3393
    /// \brief Returns the out-node created from the given original node.
3141 3394
    ///
3142
    /// Gives back the out-node created from the \c node.
3395
    /// Returns the out-node created from the given original node.
3143 3396
    static Node outNode(const DigraphNode& n) {
3144 3397
      return Parent::outNode(n);
3145 3398
    }
3146 3399

	
3147
    /// \brief Gives back the arc binds the two part of the node.
3400
    /// \brief Returns the bind arc that corresponds to the given
3401
    /// original node.
3148 3402
    ///
3149
    /// Gives back the arc binds the two part of the node.
3403
    /// Returns the bind arc in the adaptor that corresponds to the given
3404
    /// original node, i.e. the arc connecting the in-node and out-node
3405
    /// of \c n.
3150 3406
    static Arc arc(const DigraphNode& n) {
3151 3407
      return Parent::arc(n);
3152 3408
    }
3153 3409

	
3154
    /// \brief Gives back the arc of the original arc.
3410
    /// \brief Returns the arc that corresponds to the given original arc.
3155 3411
    ///
3156
    /// Gives back the arc of the original arc.
3412
    /// Returns the arc in the adaptor that corresponds to the given
3413
    /// original arc.
3157 3414
    static Arc arc(const DigraphArc& a) {
3158 3415
      return Parent::arc(a);
3159 3416
    }
3160 3417

	
3161
    /// \brief NodeMap combined from two original NodeMap
3418
    /// \brief Node map combined from two original node maps
3162 3419
    ///
3163
    /// This class adapt two of the original digraph NodeMap to
3164
    /// get a node map on the adapted digraph.
3420
    /// This map adaptor class adapts two node maps of the original digraph
3421
    /// to get a node map of the split digraph.
3422
    /// Its value type is inherited from the first node map type
3423
    /// (\c InNodeMap).
3165 3424
    template <typename InNodeMap, typename OutNodeMap>
3166 3425
    class CombinedNodeMap {
3167 3426
    public:
3168 3427

	
3428
      /// The key type of the map
3169 3429
      typedef Node Key;
3430
      /// The value type of the map
3170 3431
      typedef typename InNodeMap::Value Value;
3171 3432

	
3172
      /// \brief Constructor
3173
      ///
3174
      /// Constructor.
3433
      typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
3434
      typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
3435
      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;
3436
      typedef typename MapTraits<InNodeMap>::ReturnValue Reference;
3437
      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;
3438

	
3439
      /// Constructor
3175 3440
      CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
3176 3441
        : _in_map(in_map), _out_map(out_map) {}
3177 3442

	
3178
      /// \brief The subscript operator.
3179
      ///
3180
      /// The subscript operator.
3443
      /// Returns the value associated with the given key.
3444
      Value operator[](const Key& key) const {
3445
        if (Parent::inNode(key)) {
3446
          return _in_map[key];
3447
        } else {
3448
          return _out_map[key];
3449
        }
3450
      }
3451

	
3452
      /// Returns a reference to the value associated with the given key.
3181 3453
      Value& operator[](const Key& key) {
3182 3454
        if (Parent::inNode(key)) {
3183 3455
          return _in_map[key];
3184 3456
        } else {
3185 3457
          return _out_map[key];
3186 3458
        }
3187 3459
      }
3188 3460

	
3189
      /// \brief The const subscript operator.
3190
      ///
3191
      /// The const subscript operator.
3192
      Value operator[](const Key& key) const {
3193
        if (Parent::inNode(key)) {
3194
          return _in_map[key];
3195
        } else {
3196
          return _out_map[key];
3197
        }
3198
      }
3199

	
3200
      /// \brief The setter function of the map.
3201
      ///
3202
      /// The setter function of the map.
3461
      /// Sets the value associated with the given key.
3203 3462
      void set(const Key& key, const Value& value) {
3204 3463
        if (Parent::inNode(key)) {
3205 3464
          _in_map.set(key, value);
3206 3465
        } else {
3207 3466
          _out_map.set(key, value);
3208 3467
        }
... ...
@@ -3213,15 +3472,15 @@
3213 3472
      InNodeMap& _in_map;
3214 3473
      OutNodeMap& _out_map;
3215 3474

	
3216 3475
    };
3217 3476

	
3218 3477

	
3219
    /// \brief Just gives back a combined node map
3478
    /// \brief Returns a combined node map
3220 3479
    ///
3221
    /// Just gives back a combined node map
3480
    /// This function just returns a combined node map.
3222 3481
    template <typename InNodeMap, typename OutNodeMap>
3223 3482
    static CombinedNodeMap<InNodeMap, OutNodeMap>
3224 3483
    combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
3225 3484
      return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
3226 3485
    }
3227 3486

	
... ...
@@ -3241,107 +3500,107 @@
3241 3500
    static CombinedNodeMap<const InNodeMap, const OutNodeMap>
3242 3501
    combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
3243 3502
      return CombinedNodeMap<const InNodeMap,
3244 3503
        const OutNodeMap>(in_map, out_map);
3245 3504
    }
3246 3505

	
3247
    /// \brief ArcMap combined from an original ArcMap and a NodeMap
3506
    /// \brief Arc map combined from an arc map and a node map of the
3507
    /// original digraph.
3248 3508
    ///
3249
    /// This class adapt an original ArcMap and a NodeMap to get an
3250
    /// arc map on the adapted digraph
3251
    template <typename DigraphArcMap, typename DigraphNodeMap>
3509
    /// This map adaptor class adapts an arc map and a node map of the
3510
    /// original digraph to get an arc map of the split digraph.
3511
    /// Its value type is inherited from the original arc map type
3512
    /// (\c ArcMap).
3513
    template <typename ArcMap, typename NodeMap>
3252 3514
    class CombinedArcMap {
3253 3515
    public:
3254 3516

	
3517
      /// The key type of the map
3255 3518
      typedef Arc Key;
3256
      typedef typename DigraphArcMap::Value Value;
3257

	
3258
      /// \brief Constructor
3259
      ///
3260
      /// Constructor.
3261
      CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
3519
      /// The value type of the map
3520
      typedef typename ArcMap::Value Value;
3521

	
3522
      typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag;
3523
      typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue;
3524
      typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue;
3525
      typedef typename MapTraits<ArcMap>::ReturnValue Reference;
3526
      typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReference;
3527

	
3528
      /// Constructor
3529
      CombinedArcMap(ArcMap& arc_map, NodeMap& node_map)
3262 3530
        : _arc_map(arc_map), _node_map(node_map) {}
3263 3531

	
3264
      /// \brief The subscript operator.
3265
      ///
3266
      /// The subscript operator.
3532
      /// Returns the value associated with the given key.
3533
      Value operator[](const Key& arc) const {
3534
        if (Parent::origArc(arc)) {
3535
          return _arc_map[arc];
3536
        } else {
3537
          return _node_map[arc];
3538
        }
3539
      }
3540

	
3541
      /// Returns a reference to the value associated with the given key.
3542
      Value& operator[](const Key& arc) {
3543
        if (Parent::origArc(arc)) {
3544
          return _arc_map[arc];
3545
        } else {
3546
          return _node_map[arc];
3547
        }
3548
      }
3549

	
3550
      /// Sets the value associated with the given key.
3267 3551
      void set(const Arc& arc, const Value& val) {
3268 3552
        if (Parent::origArc(arc)) {
3269 3553
          _arc_map.set(arc, val);
3270 3554
        } else {
3271 3555
          _node_map.set(arc, val);
3272 3556
        }
3273 3557
      }
3274 3558

	
3275
      /// \brief The const subscript operator.
3276
      ///
3277
      /// The const subscript operator.
3278
      Value operator[](const Key& arc) const {
3279
        if (Parent::origArc(arc)) {
3280
          return _arc_map[arc];
3281
        } else {
3282
          return _node_map[arc];
3283
        }
3284
      }
3285

	
3286
      /// \brief The const subscript operator.
3287
      ///
3288
      /// The const subscript operator.
3289
      Value& operator[](const Key& arc) {
3290
        if (Parent::origArc(arc)) {
3291
          return _arc_map[arc];
3292
        } else {
3293
          return _node_map[arc];
3294
        }
3295
      }
3296

	
3297 3559
    private:
3298
      DigraphArcMap& _arc_map;
3299
      DigraphNodeMap& _node_map;
3560
      ArcMap& _arc_map;
3561
      NodeMap& _node_map;
3300 3562
    };
3301 3563

	
3302
    /// \brief Just gives back a combined arc map
3564
    /// \brief Returns a combined arc map
3303 3565
    ///
3304
    /// Just gives back a combined arc map
3305
    template <typename DigraphArcMap, typename DigraphNodeMap>
3306
    static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
3307
    combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
3308
      return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
3566
    /// This function just returns a combined arc map.
3567
    template <typename ArcMap, typename NodeMap>
3568
    static CombinedArcMap<ArcMap, NodeMap>
3569
    combinedArcMap(ArcMap& arc_map, NodeMap& node_map) {
3570
      return CombinedArcMap<ArcMap, NodeMap>(arc_map, node_map);
3309 3571
    }
3310 3572

	
3311
    template <typename DigraphArcMap, typename DigraphNodeMap>
3312
    static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
3313
    combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
3314
      return CombinedArcMap<const DigraphArcMap,
3315
        DigraphNodeMap>(arc_map, node_map);
3573
    template <typename ArcMap, typename NodeMap>
3574
    static CombinedArcMap<const ArcMap, NodeMap>
3575
    combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) {
3576
      return CombinedArcMap<const ArcMap, NodeMap>(arc_map, node_map);
3316 3577
    }
3317 3578

	
3318
    template <typename DigraphArcMap, typename DigraphNodeMap>
3319
    static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
3320
    combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
3321
      return CombinedArcMap<DigraphArcMap,
3322
        const DigraphNodeMap>(arc_map, node_map);
3579
    template <typename ArcMap, typename NodeMap>
3580
    static CombinedArcMap<ArcMap, const NodeMap>
3581
    combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) {
3582
      return CombinedArcMap<ArcMap, const NodeMap>(arc_map, node_map);
3323 3583
    }
3324 3584

	
3325
    template <typename DigraphArcMap, typename DigraphNodeMap>
3326
    static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
3327
    combinedArcMap(const DigraphArcMap& arc_map,
3328
                   const DigraphNodeMap& node_map) {
3329
      return CombinedArcMap<const DigraphArcMap,
3330
        const DigraphNodeMap>(arc_map, node_map);
3585
    template <typename ArcMap, typename NodeMap>
3586
    static CombinedArcMap<const ArcMap, const NodeMap>
3587
    combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) {
3588
      return CombinedArcMap<const ArcMap, const NodeMap>(arc_map, node_map);
3331 3589
    }
3332 3590

	
3333 3591
  };
3334 3592

	
3335
  /// \brief Just gives back a node splitter
3593
  /// \brief Returns a (read-only) SplitNodes adaptor
3336 3594
  ///
3337
  /// Just gives back a node splitter
3338
  template<typename Digraph>
3339
  SplitNodes<Digraph>
3340
  splitNodes(const Digraph& digraph) {
3341
    return SplitNodes<Digraph>(digraph);
3595
  /// This function just returns a (read-only) \ref SplitNodes adaptor.
3596
  /// \ingroup graph_adaptors
3597
  /// \relates SplitNodes
3598
  template<typename GR>
3599
  SplitNodes<GR>
3600
  splitNodes(const GR& digraph) {
3601
    return SplitNodes<GR>(digraph);
3342 3602
  }
3343 3603

	
3344

	
3345 3604
} //namespace lemon
3346 3605

	
3347 3606
#endif //LEMON_ADAPTORS_H
... ...
@@ -170,16 +170,12 @@
170 170
    Node runningNode(const InArcIt &e) const {
171 171
      return Parent::source(e);
172 172
    }
173 173

	
174 174
  };
175 175

	
176

	
177
  /// \ingroup digraphbits
178
  ///
179
  /// \brief Extender for the GraphAdaptors
180 176
  template <typename _Graph>
181 177
  class GraphAdaptorExtender : public _Graph {
182 178
  public:
183 179

	
184 180
    typedef _Graph Parent;
185 181
    typedef _Graph Graph;
0 comments (0 inline)