COIN-OR::LEMON - Graph Library

Changeset 139:701c529ba737 in lemon


Ignore:
Timestamp:
04/22/08 15:04:00 (11 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Renamings in the graph_utils.h + graph_utils_test added

Files:
2 added
6 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/traits.h

    r107 r139  
    217217
    218218  template <typename Graph, typename Enable = void>
    219   struct ArcNumTagIndicator {
    220     static const bool value = false;
    221   };
    222 
    223   template <typename Graph>
    224   struct ArcNumTagIndicator<
    225     Graph,
    226     typename enable_if<typename Graph::ArcNumTag, void>::type
    227   > {
    228     static const bool value = true;
    229   };
    230 
    231   template <typename Graph, typename Enable = void>
    232   struct FindArcTagIndicator {
    233     static const bool value = false;
    234   };
    235 
    236   template <typename Graph>
    237   struct FindArcTagIndicator<
    238     Graph,
    239     typename enable_if<typename Graph::FindArcTag, void>::type
     219  struct EdgeNumTagIndicator {
     220    static const bool value = false;
     221  };
     222
     223  template <typename Graph>
     224  struct EdgeNumTagIndicator<
     225    Graph,
     226    typename enable_if<typename Graph::EdgeNumTag, void>::type
     227  > {
     228    static const bool value = true;
     229  };
     230
     231  template <typename Graph, typename Enable = void>
     232  struct FindEdgeTagIndicator {
     233    static const bool value = false;
     234  };
     235
     236  template <typename Graph>
     237  struct FindEdgeTagIndicator<
     238    Graph,
     239    typename enable_if<typename Graph::FindEdgeTag, void>::type
    240240  > {
    241241    static const bool value = true;
  • lemon/graph_utils.h

    r100 r139  
    3636///\ingroup gutils
    3737///\file
    38 ///\brief Digraph utilities.
     38///\brief Graph utilities.
    3939
    4040namespace lemon {
     
    4747  ///This \c \#define creates convenience typedefs for the following types
    4848  ///of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
    49   ///\c OutArcIt
    50   ///\note If \c G it a template parameter, it should be used in this way.
    51   ///\code
    52   ///  GRAPH_TYPEDEFS(typename G);
    53   ///\endcode
    54   ///
    55   ///\warning There are no typedefs for the digraph maps because of the lack of
    56   ///template typedefs in C++.
    57 #define GRAPH_TYPEDEFS(Digraph)                         \
    58   typedef Digraph::     Node      Node;                 \
    59     typedef Digraph::   NodeIt    NodeIt;                       \
    60     typedef Digraph::   Arc      Arc;                   \
    61     typedef Digraph::   ArcIt    ArcIt;                 \
    62     typedef Digraph:: InArcIt  InArcIt;                 \
    63     typedef Digraph::OutArcIt OutArcIt
     49  ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
     50  ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
     51#define DIGRAPH_TYPEDEFS(Digraph)                                       \
     52  typedef Digraph::Node Node;                                           \
     53  typedef Digraph::NodeIt NodeIt;                                       \
     54  typedef Digraph::Arc Arc;                                             \
     55  typedef Digraph::ArcIt ArcIt;                                         \
     56  typedef Digraph::InArcIt InArcIt;                                     \
     57  typedef Digraph::OutArcIt OutArcIt
    6458
    6559  ///Creates convenience typedefs for the graph types and iterators
    6660
    67   ///This \c \#define creates the same convenience typedefs as defined by
    68   ///\ref GRAPH_TYPEDEFS(Digraph) and three more, namely it creates
    69   ///\c Edge, \c EdgeIt, \c IncArcIt,
    70   ///
    71   ///\note If \c G it a template parameter, it should be used in this way.
    72   ///\code
    73   ///  UGRAPH_TYPEDEFS(typename G);
    74   ///\endcode
    75   ///
    76   ///\warning There are no typedefs for the digraph maps because of the lack of
    77   ///template typedefs in C++.
    78 #define UGRAPH_TYPEDEFS(Digraph)                                \
    79   GRAPH_TYPEDEFS(Digraph);                              \
    80     typedef Digraph:: Edge   Edge;                      \
    81     typedef Digraph:: EdgeIt EdgeIt;                    \
    82     typedef Digraph:: IncArcIt   IncArcIt
    83 
    84   ///\brief Creates convenience typedefs for the bipartite digraph
    85   ///types and iterators
    86 
    87   ///This \c \#define creates the same convenience typedefs as defined by
    88   ///\ref UGRAPH_TYPEDEFS(Digraph) and two more, namely it creates
    89   ///\c RedIt, \c BlueIt,
    90   ///
    91   ///\note If \c G it a template parameter, it should be used in this way.
    92   ///\code
    93   ///  BPUGRAPH_TYPEDEFS(typename G);
    94   ///\endcode
    95   ///
    96   ///\warning There are no typedefs for the digraph maps because of the lack of
    97   ///template typedefs in C++.
    98 #define BPUGRAPH_TYPEDEFS(Digraph)            \
    99   UGRAPH_TYPEDEFS(Digraph);                 \
    100     typedef Digraph::Red Red;             \
    101     typedef Digraph::Blue Blue;             \
    102     typedef Digraph::RedIt RedIt;           \
    103     typedef Digraph::BlueIt BlueIt
    104 
    105   /// \brief Function to count the items in the digraph.
    106   ///
    107   /// This function counts the items (nodes, arcs etc) in the digraph.
     61  ///This \c \#define creates the same convenience typedefs as defined
     62  ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
     63  ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
     64  ///\c DoubleEdgeMap.
     65#define GRAPH_TYPEDEFS(Graph)                                           \
     66  DIGRAPH_TYPEDEFS(Graph);                                              \
     67  typedef Graph::Edge Edge;                                             \
     68  typedef Graph::EdgeIt EdgeIt;                                         \
     69  typedef Graph::IncEdgeIt IncEdgeIt
     70
     71  /// \brief Function to count the items in the graph.
     72  ///
     73  /// This function counts the items (nodes, arcs etc) in the graph.
    10874  /// The complexity of the function is O(n) because
    10975  /// it iterates on all of the items.
    110 
    111   template <typename Digraph, typename Item>
    112   inline int countItems(const Digraph& g) {
    113     typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
     76  template <typename Graph, typename Item>
     77  inline int countItems(const Graph& g) {
     78    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
    11479    int num = 0;
    11580    for (ItemIt it(g); it != INVALID; ++it) {
     
    12186  // Node counting:
    12287
    123   namespace _digraph_utils_bits {
    124    
    125     template <typename Digraph, typename Enable = void>
     88  namespace _graph_utils_bits {
     89   
     90    template <typename Graph, typename Enable = void>
    12691    struct CountNodesSelector {
    127       static int count(const Digraph &g) {
    128         return countItems<Digraph, typename Digraph::Node>(g);
     92      static int count(const Graph &g) {
     93        return countItems<Graph, typename Graph::Node>(g);
    12994      }
    13095    };
    13196
    132     template <typename Digraph>
     97    template <typename Graph>
    13398    struct CountNodesSelector<
    134       Digraph, typename
    135       enable_if<typename Digraph::NodeNumTag, void>::type>
     99      Graph, typename
     100      enable_if<typename Graph::NodeNumTag, void>::type>
    136101    {
    137       static int count(const Digraph &g) {
     102      static int count(const Graph &g) {
    138103        return g.nodeNum();
    139104      }
     
    141106  }
    142107
    143   /// \brief Function to count the nodes in the digraph.
    144   ///
    145   /// This function counts the nodes in the digraph.
     108  /// \brief Function to count the nodes in the graph.
     109  ///
     110  /// This function counts the nodes in the graph.
    146111  /// The complexity of the function is O(n) but for some
    147   /// digraph structures it is specialized to run in O(1).
    148   ///
    149   /// If the digraph contains a \e nodeNum() member function and a
     112  /// graph structures it is specialized to run in O(1).
     113  ///
     114  /// If the graph contains a \e nodeNum() member function and a
    150115  /// \e NodeNumTag tag then this function calls directly the member
    151116  /// function to query the cardinality of the node set.
    152   template <typename Digraph>
    153   inline int countNodes(const Digraph& g) {
    154     return _digraph_utils_bits::CountNodesSelector<Digraph>::count(g);
     117  template <typename Graph>
     118  inline int countNodes(const Graph& g) {
     119    return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
    155120  }
    156121
    157   namespace _digraph_utils_bits {
    158    
    159     template <typename Digraph, typename Enable = void>
    160     struct CountRedsSelector {
    161       static int count(const Digraph &g) {
    162         return countItems<Digraph, typename Digraph::Red>(g);
     122  // Arc counting:
     123
     124  namespace _graph_utils_bits {
     125   
     126    template <typename Graph, typename Enable = void>
     127    struct CountArcsSelector {
     128      static int count(const Graph &g) {
     129        return countItems<Graph, typename Graph::Arc>(g);
    163130      }
    164131    };
    165132
    166     template <typename Digraph>
    167     struct CountRedsSelector<
    168       Digraph, typename
    169       enable_if<typename Digraph::NodeNumTag, void>::type>
     133    template <typename Graph>
     134    struct CountArcsSelector<
     135      Graph,
     136      typename enable_if<typename Graph::ArcNumTag, void>::type>
    170137    {
    171       static int count(const Digraph &g) {
    172         return g.redNum();
     138      static int count(const Graph &g) {
     139        return g.arcNum();
    173140      }
    174141    };   
    175142  }
    176143
    177   /// \brief Function to count the reds in the digraph.
    178   ///
    179   /// This function counts the reds in the digraph.
    180   /// The complexity of the function is O(an) but for some
    181   /// digraph structures it is specialized to run in O(1).
    182   ///
    183   /// If the digraph contains an \e redNum() member function and a
    184   /// \e NodeNumTag tag then this function calls directly the member
    185   /// function to query the cardinality of the A-node set.
    186   template <typename Digraph>
    187   inline int countReds(const Digraph& g) {
    188     return _digraph_utils_bits::CountRedsSelector<Digraph>::count(g);
     144  /// \brief Function to count the arcs in the graph.
     145  ///
     146  /// This function counts the arcs in the graph.
     147  /// The complexity of the function is O(e) but for some
     148  /// graph structures it is specialized to run in O(1).
     149  ///
     150  /// If the graph contains a \e arcNum() member function and a
     151  /// \e EdgeNumTag tag then this function calls directly the member
     152  /// function to query the cardinality of the arc set.
     153  template <typename Graph>
     154  inline int countArcs(const Graph& g) {
     155    return _graph_utils_bits::CountArcsSelector<Graph>::count(g);
    189156  }
    190157
    191   namespace _digraph_utils_bits {
    192    
    193     template <typename Digraph, typename Enable = void>
    194     struct CountBluesSelector {
    195       static int count(const Digraph &g) {
    196         return countItems<Digraph, typename Digraph::Blue>(g);
     158  // Edge counting:
     159  namespace _graph_utils_bits {
     160   
     161    template <typename Graph, typename Enable = void>
     162    struct CountEdgesSelector {
     163      static int count(const Graph &g) {
     164        return countItems<Graph, typename Graph::Edge>(g);
    197165      }
    198166    };
    199167
    200     template <typename Digraph>
    201     struct CountBluesSelector<
    202       Digraph, typename
    203       enable_if<typename Digraph::NodeNumTag, void>::type>
     168    template <typename Graph>
     169    struct CountEdgesSelector<
     170      Graph,
     171      typename enable_if<typename Graph::EdgeNumTag, void>::type>
    204172    {
    205       static int count(const Digraph &g) {
    206         return g.blueNum();
     173      static int count(const Graph &g) {
     174        return g.edgeNum();
    207175      }
    208176    };   
    209177  }
    210178
    211   /// \brief Function to count the blues in the digraph.
    212   ///
    213   /// This function counts the blues in the digraph.
    214   /// The complexity of the function is O(bn) but for some
    215   /// digraph structures it is specialized to run in O(1).
    216   ///
    217   /// If the digraph contains a \e blueNum() member function and a
    218   /// \e NodeNumTag tag then this function calls directly the member
    219   /// function to query the cardinality of the B-node set.
    220   template <typename Digraph>
    221   inline int countBlues(const Digraph& g) {
    222     return _digraph_utils_bits::CountBluesSelector<Digraph>::count(g);
     179  /// \brief Function to count the edges in the graph.
     180  ///
     181  /// This function counts the edges in the graph.
     182  /// The complexity of the function is O(m) but for some
     183  /// graph structures it is specialized to run in O(1).
     184  ///
     185  /// If the graph contains a \e edgeNum() member function and a
     186  /// \e EdgeNumTag tag then this function calls directly the member
     187  /// function to query the cardinality of the edge set.
     188  template <typename Graph>
     189  inline int countEdges(const Graph& g) {
     190    return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
     191
    223192  }
    224193
    225194
    226   // Arc counting:
    227 
    228   namespace _digraph_utils_bits {
    229    
    230     template <typename Digraph, typename Enable = void>
    231     struct CountArcsSelector {
    232       static int count(const Digraph &g) {
    233         return countItems<Digraph, typename Digraph::Arc>(g);
    234       }
    235     };
    236 
    237     template <typename Digraph>
    238     struct CountArcsSelector<
    239       Digraph,
    240       typename enable_if<typename Digraph::ArcNumTag, void>::type>
    241     {
    242       static int count(const Digraph &g) {
    243         return g.arcNum();
    244       }
    245     };   
    246   }
    247 
    248   /// \brief Function to count the arcs in the digraph.
    249   ///
    250   /// This function counts the arcs in the digraph.
    251   /// The complexity of the function is O(e) but for some
    252   /// digraph structures it is specialized to run in O(1).
    253   ///
    254   /// If the digraph contains a \e arcNum() member function and a
    255   /// \e ArcNumTag tag then this function calls directly the member
    256   /// function to query the cardinality of the arc set.
    257   template <typename Digraph>
    258   inline int countArcs(const Digraph& g) {
    259     return _digraph_utils_bits::CountArcsSelector<Digraph>::count(g);
    260   }
    261 
    262   // Undirected arc counting:
    263   namespace _digraph_utils_bits {
    264    
    265     template <typename Digraph, typename Enable = void>
    266     struct CountEdgesSelector {
    267       static int count(const Digraph &g) {
    268         return countItems<Digraph, typename Digraph::Edge>(g);
    269       }
    270     };
    271 
    272     template <typename Digraph>
    273     struct CountEdgesSelector<
    274       Digraph,
    275       typename enable_if<typename Digraph::ArcNumTag, void>::type>
    276     {
    277       static int count(const Digraph &g) {
    278         return g.edgeNum();
    279       }
    280     };   
    281   }
    282 
    283   /// \brief Function to count the edges in the digraph.
    284   ///
    285   /// This function counts the edges in the digraph.
    286   /// The complexity of the function is O(e) but for some
    287   /// digraph structures it is specialized to run in O(1).
    288   ///
    289   /// If the digraph contains a \e edgeNum() member function and a
    290   /// \e ArcNumTag tag then this function calls directly the member
    291   /// function to query the cardinality of the edge set.
    292   template <typename Digraph>
    293   inline int countEdges(const Digraph& g) {
    294     return _digraph_utils_bits::CountEdgesSelector<Digraph>::count(g);
    295 
    296   }
    297 
    298 
    299   template <typename Digraph, typename DegIt>
    300   inline int countNodeDegree(const Digraph& _g, const typename Digraph::Node& _n) {
     195  template <typename Graph, typename DegIt>
     196  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
    301197    int num = 0;
    302198    for (DegIt it(_g, _n); it != INVALID; ++it) {
     
    309205  ///
    310206  /// This function counts the number of the out-arcs from node \c n
    311   /// in the digraph. 
    312   template <typename Digraph>
    313   inline int countOutArcs(const Digraph& _g,  const typename Digraph::Node& _n) {
    314     return countNodeDegree<Digraph, typename Digraph::OutArcIt>(_g, _n);
     207  /// in the graph. 
     208  template <typename Graph>
     209  inline int countOutArcs(const Graph& _g,  const typename Graph::Node& _n) {
     210    return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);
    315211  }
    316212
     
    318214  ///
    319215  /// This function counts the number of the in-arcs to node \c n
    320   /// in the digraph. 
    321   template <typename Digraph>
    322   inline int countInArcs(const Digraph& _g,  const typename Digraph::Node& _n) {
    323     return countNodeDegree<Digraph, typename Digraph::InArcIt>(_g, _n);
     216  /// in the graph. 
     217  template <typename Graph>
     218  inline int countInArcs(const Graph& _g,  const typename Graph::Node& _n) {
     219    return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);
    324220  }
    325221
    326   /// \brief Function to count the number of the inc-arcs to node \c n.
    327   ///
    328   /// This function counts the number of the inc-arcs to node \c n
    329   /// in the digraph. 
    330   template <typename Digraph>
    331   inline int countIncArcs(const Digraph& _g,  const typename Digraph::Node& _n) {
    332     return countNodeDegree<Digraph, typename Digraph::IncArcIt>(_g, _n);
     222  /// \brief Function to count the number of the inc-edges to node \c n.
     223  ///
     224  /// This function counts the number of the inc-edges to node \c n
     225  /// in the graph. 
     226  template <typename Graph>
     227  inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) {
     228    return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
    333229  }
    334230
    335   namespace _digraph_utils_bits {
    336    
    337     template <typename Digraph, typename Enable = void>
     231  namespace _graph_utils_bits {
     232   
     233    template <typename Graph, typename Enable = void>
    338234    struct FindArcSelector {
    339       typedef typename Digraph::Node Node;
    340       typedef typename Digraph::Arc Arc;
    341       static Arc find(const Digraph &g, Node u, Node v, Arc e) {
     235      typedef typename Graph::Node Node;
     236      typedef typename Graph::Arc Arc;
     237      static Arc find(const Graph &g, Node u, Node v, Arc e) {
    342238        if (e == INVALID) {
    343239          g.firstOut(e, u);
     
    352248    };
    353249
    354     template <typename Digraph>
     250    template <typename Graph>
    355251    struct FindArcSelector<
    356       Digraph,
    357       typename enable_if<typename Digraph::FindArcTag, void>::type>
     252      Graph,
     253      typename enable_if<typename Graph::FindEdgeTag, void>::type>
    358254    {
    359       typedef typename Digraph::Node Node;
    360       typedef typename Digraph::Arc Arc;
    361       static Arc find(const Digraph &g, Node u, Node v, Arc prev) {
     255      typedef typename Graph::Node Node;
     256      typedef typename Graph::Arc Arc;
     257      static Arc find(const Graph &g, Node u, Node v, Arc prev) {
    362258        return g.findArc(u, v, prev);
    363259      }
     
    365261  }
    366262
    367   /// \brief Finds an arc between two nodes of a digraph.
    368   ///
    369   /// Finds an arc from node \c u to node \c v in digraph \c g.
     263  /// \brief Finds an arc between two nodes of a graph.
     264  ///
     265  /// Finds an arc from node \c u to node \c v in graph \c g.
    370266  ///
    371267  /// If \c prev is \ref INVALID (this is the default value), then
     
    385281  ///\sa DynArcLookUp
    386282  ///\sa ConArcIt
    387   template <typename Digraph>
    388   inline typename Digraph::Arc
    389   findArc(const Digraph &g, typename Digraph::Node u, typename Digraph::Node v,
    390            typename Digraph::Arc prev = INVALID) {
    391     return _digraph_utils_bits::FindArcSelector<Digraph>::find(g, u, v, prev);
     283  template <typename Graph>
     284  inline typename Graph::Arc
     285  findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
     286           typename Graph::Arc prev = INVALID) {
     287    return _graph_utils_bits::FindArcSelector<Graph>::find(g, u, v, prev);
    392288  }
    393289
     
    398294  /// use it the following way:
    399295  ///\code
    400   /// for (ConArcIt<Digraph> it(g, src, trg); it != INVALID; ++it) {
     296  /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
    401297  ///   ...
    402298  /// }
     
    409305  ///
    410306  /// \author Balazs Dezso
    411   template <typename _Digraph>
    412   class ConArcIt : public _Digraph::Arc {
     307  template <typename _Graph>
     308  class ConArcIt : public _Graph::Arc {
    413309  public:
    414310
    415     typedef _Digraph Digraph;
    416     typedef typename Digraph::Arc Parent;
    417 
    418     typedef typename Digraph::Arc Arc;
    419     typedef typename Digraph::Node Node;
     311    typedef _Graph Graph;
     312    typedef typename Graph::Arc Parent;
     313
     314    typedef typename Graph::Arc Arc;
     315    typedef typename Graph::Node Node;
    420316
    421317    /// \brief Constructor.
     
    423319    /// Construct a new ConArcIt iterating on the arcs which
    424320    /// connects the \c u and \c v node.
    425     ConArcIt(const Digraph& g, Node u, Node v) : digraph(g) {
    426       Parent::operator=(findArc(digraph, u, v));
     321    ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
     322      Parent::operator=(findArc(_graph, u, v));
    427323    }
    428324
     
    431327    /// Construct a new ConArcIt which continues the iterating from
    432328    /// the \c e arc.
    433     ConArcIt(const Digraph& g, Arc e) : Parent(e), digraph(g) {}
     329    ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
    434330   
    435331    /// \brief Increment operator.
     
    437333    /// It increments the iterator and gives back the next arc.
    438334    ConArcIt& operator++() {
    439       Parent::operator=(findArc(digraph, digraph.source(*this),
    440                                  digraph.target(*this), *this));
     335      Parent::operator=(findArc(_graph, _graph.source(*this),
     336                                _graph.target(*this), *this));
    441337      return *this;
    442338    }
    443339  private:
    444     const Digraph& digraph;
     340    const Graph& _graph;
    445341  };
    446342
    447   namespace _digraph_utils_bits {
    448    
    449     template <typename Digraph, typename Enable = void>
     343  namespace _graph_utils_bits {
     344   
     345    template <typename Graph, typename Enable = void>
    450346    struct FindEdgeSelector {
    451       typedef typename Digraph::Node Node;
    452       typedef typename Digraph::Edge Edge;
    453       static Edge find(const Digraph &g, Node u, Node v, Edge e) {
     347      typedef typename Graph::Node Node;
     348      typedef typename Graph::Edge Edge;
     349      static Edge find(const Graph &g, Node u, Node v, Edge e) {
    454350        bool b;
    455351        if (u != v) {
     
    478374    };
    479375
    480     template <typename Digraph>
     376    template <typename Graph>
    481377    struct FindEdgeSelector<
    482       Digraph,
    483       typename enable_if<typename Digraph::FindArcTag, void>::type>
     378      Graph,
     379      typename enable_if<typename Graph::FindEdgeTag, void>::type>
    484380    {
    485       typedef typename Digraph::Node Node;
    486       typedef typename Digraph::Edge Edge;
    487       static Edge find(const Digraph &g, Node u, Node v, Edge prev) {
     381      typedef typename Graph::Node Node;
     382      typedef typename Graph::Edge Edge;
     383      static Edge find(const Graph &g, Node u, Node v, Edge prev) {
    488384        return g.findEdge(u, v, prev);
    489385      }
     
    491387  }
    492388
    493   /// \brief Finds an edge between two nodes of a digraph.
    494   ///
    495   /// Finds an edge from node \c u to node \c v in digraph \c g.
    496   /// If the node \c u and node \c v is equal then each loop arc
    497   /// will be enumerated.
     389  /// \brief Finds an edge between two nodes of a graph.
     390  ///
     391  /// Finds an edge from node \c u to node \c v in graph \c g.
     392  /// If the node \c u and node \c v is equal then each loop edge
     393  /// will be enumerated once.
    498394  ///
    499395  /// If \c prev is \ref INVALID (this is the default value), then
     
    512408  ///\sa ConArcIt
    513409
    514   template <typename Digraph>
    515   inline typename Digraph::Edge
    516   findEdge(const Digraph &g, typename Digraph::Node u, typename Digraph::Node v,
    517             typename Digraph::Edge p = INVALID) {
    518     return _digraph_utils_bits::FindEdgeSelector<Digraph>::find(g, u, v, p);
     410  template <typename Graph>
     411  inline typename Graph::Edge
     412  findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
     413            typename Graph::Edge p = INVALID) {
     414    return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
    519415  }
    520416
     
    525421  /// use it the following way:
    526422  ///\code
    527   /// for (ConEdgeIt<Digraph> it(g, src, trg); it != INVALID; ++it) {
     423  /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
    528424  ///   ...
    529425  /// }
     
    533429  ///
    534430  /// \author Balazs Dezso
    535   template <typename _Digraph>
    536   class ConEdgeIt : public _Digraph::Edge {
     431  template <typename _Graph>
     432  class ConEdgeIt : public _Graph::Edge {
    537433  public:
    538434
    539     typedef _Digraph Digraph;
    540     typedef typename Digraph::Edge Parent;
    541 
    542     typedef typename Digraph::Edge Edge;
    543     typedef typename Digraph::Node Node;
     435    typedef _Graph Graph;
     436    typedef typename Graph::Edge Parent;
     437
     438    typedef typename Graph::Edge Edge;
     439    typedef typename Graph::Node Node;
    544440
    545441    /// \brief Constructor.
    546442    ///
    547     /// Construct a new ConEdgeIt iterating on the arcs which
     443    /// Construct a new ConEdgeIt iterating on the edges which
    548444    /// connects the \c u and \c v node.
    549     ConEdgeIt(const Digraph& g, Node u, Node v) : digraph(g) {
    550       Parent::operator=(findEdge(digraph, u, v));
     445    ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
     446      Parent::operator=(findEdge(_graph, u, v));
    551447    }
    552448
     
    554450    ///
    555451    /// Construct a new ConEdgeIt which continues the iterating from
    556     /// the \c e arc.
    557     ConEdgeIt(const Digraph& g, Edge e) : Parent(e), digraph(g) {}
     452    /// the \c e edge.
     453    ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
    558454   
    559455    /// \brief Increment operator.
    560456    ///
    561     /// It increments the iterator and gives back the next arc.
     457    /// It increments the iterator and gives back the next edge.
    562458    ConEdgeIt& operator++() {
    563       Parent::operator=(findEdge(digraph, digraph.source(*this),
    564                                       digraph.target(*this), *this));
     459      Parent::operator=(findEdge(_graph, _graph.source(*this),
     460                                 _graph.target(*this), *this));
    565461      return *this;
    566462    }
    567463  private:
    568     const Digraph& digraph;
     464    const Graph& _graph;
    569465  };
    570466
    571   /// \brief Copy a map.
    572   ///
    573   /// This function copies the \c from map to the \c to map. It uses the
    574   /// given iterator to iterate on the data structure and it uses the \c ref
    575   /// mapping to convert the from's keys to the to's keys.
    576   template <typename To, typename From,
    577             typename ItemIt, typename Ref>         
    578   void copyMap(To& to, const From& from,
    579                ItemIt it, const Ref& ref) {
    580     for (; it != INVALID; ++it) {
    581       to[ref[it]] = from[it];
    582     }
    583   }
    584 
    585   /// \brief Copy the from map to the to map.
    586   ///
    587   /// Copy the \c from map to the \c to map. It uses the given iterator
    588   /// to iterate on the data structure.
    589   template <typename To, typename From, typename ItemIt>           
    590   void copyMap(To& to, const From& from, ItemIt it) {
    591     for (; it != INVALID; ++it) {
    592       to[it] = from[it];
    593     }
    594   }
    595 
    596   namespace _digraph_utils_bits {
     467  namespace _graph_utils_bits {
    597468
    598469    template <typename Digraph, typename Item, typename RefMap>
     
    728599    };
    729600
    730     template <typename BpGraph, typename Enable = void>
    731     struct BpGraphCopySelector {
    732       template <typename From, typename RedRefMap,
    733                 typename BlueRefMap, typename EdgeRefMap>
    734       static void copy(BpGraph &to, const From& from,
    735                        RedRefMap& redRefMap, BlueRefMap& blueRefMap,
    736                        EdgeRefMap& edgeRefMap) {
    737         for (typename From::RedIt it(from); it != INVALID; ++it) {
    738           redRefMap[it] = to.addRed();
    739         }
    740         for (typename From::BlueIt it(from); it != INVALID; ++it) {
    741           blueRefMap[it] = to.addBlue();
    742         }
    743         for (typename From::EdgeIt it(from); it != INVALID; ++it) {
    744           edgeRefMap[it] = to.addArc(redRefMap[from.red(it)],
    745                                            blueRefMap[from.blue(it)]);
    746         }
    747       }
    748     };
    749 
    750     template <typename BpGraph>
    751     struct BpGraphCopySelector<
    752       BpGraph,
    753       typename enable_if<typename BpGraph::BuildTag, void>::type>
    754     {
    755       template <typename From, typename RedRefMap,
    756                 typename BlueRefMap, typename EdgeRefMap>
    757       static void copy(BpGraph &to, const From& from,
    758                        RedRefMap& redRefMap, BlueRefMap& blueRefMap,
    759                        EdgeRefMap& edgeRefMap) {
    760         to.build(from, redRefMap, blueRefMap, edgeRefMap);
    761       }
    762     };
    763    
    764 
    765601  }
    766602
     
    769605  /// Class to copy a digraph to another digraph (duplicate a digraph). The
    770606  /// simplest way of using it is through the \c copyDigraph() function.
     607  ///
     608  /// This class not just make a copy of a graph, but it can create
     609  /// references and cross references between the nodes and arcs of
     610  /// the two graphs, it can copy maps for use with the newly created
     611  /// graph and copy nodes and arcs.
     612  ///
     613  /// To make a copy from a graph, first an instance of DigraphCopy
     614  /// should be created, then the data belongs to the graph should
     615  /// assigned to copy. In the end, the \c run() member should be
     616  /// called.
     617  ///
     618  /// The next code copies a graph with several data:
     619  ///\code
     620  ///  DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
     621  ///  // create a reference for the nodes
     622  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
     623  ///  dc.nodeRef(nr);
     624  ///  // create a cross reference (inverse) for the arcs
     625  ///  NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
     626  ///  dc.arcCrossRef(acr);
     627  ///  // copy an arc map
     628  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
     629  ///  NewGraph::ArcMap<double> namap(new_graph);
     630  ///  dc.arcMap(namap, oamap);
     631  ///  // copy a node
     632  ///  OrigGraph::Node on;
     633  ///  NewGraph::Node nn;
     634  ///  dc.node(nn, on);
     635  ///  // Executions of copy
     636  ///  dc.run();
     637  ///\endcode
    771638  template <typename To, typename From>
    772639  class DigraphCopy {
     
    792659    /// It copies the content of the \c _from digraph into the
    793660    /// \c _to digraph.
    794     DigraphCopy(To& _to, const From& _from)
    795       : from(_from), to(_to) {}
     661    DigraphCopy(To& to, const From& from)
     662      : _from(from), _to(to) {}
    796663
    797664    /// \brief Destructor of the DigraphCopy
     
    799666    /// Destructor of the DigraphCopy
    800667    ~DigraphCopy() {
    801       for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
    802         delete nodeMapCopies[i];
    803       }
    804       for (int i = 0; i < int(arcMapCopies.size()); ++i) {
    805         delete arcMapCopies[i];
     668      for (int i = 0; i < int(_node_maps.size()); ++i) {
     669        delete _node_maps[i];
     670      }
     671      for (int i = 0; i < int(_arc_maps.size()); ++i) {
     672        delete _arc_maps[i];
    806673      }
    807674
     
    810677    /// \brief Copies the node references into the given map.
    811678    ///
    812     /// Copies the node references into the given map.
     679    /// Copies the node references into the given map. The parameter
     680    /// should be a map, which key type is the Node type of the source
     681    /// graph, while the value type is the Node type of the
     682    /// destination graph.
    813683    template <typename NodeRef>
    814684    DigraphCopy& nodeRef(NodeRef& map) {
    815       nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node,
    816                               NodeRefMap, NodeRef>(map));
     685      _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
     686                           NodeRefMap, NodeRef>(map));
    817687      return *this;
    818688    }
     
    821691    ///
    822692    ///  Copies the node cross references (reverse references) into
    823     ///  the given map.
     693    ///  the given map. The parameter should be a map, which key type
     694    ///  is the Node type of the destination graph, while the value type is
     695    ///  the Node type of the source graph.
    824696    template <typename NodeCrossRef>
    825697    DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
    826       nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,
    827                               NodeRefMap, NodeCrossRef>(map));
     698      _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
     699                           NodeRefMap, NodeCrossRef>(map));
    828700      return *this;
    829701    }
     
    831703    /// \brief Make copy of the given map.
    832704    ///
    833     /// Makes copy of the given map for the newly created digraph.
    834     /// The new map's key type is the to digraph's node type,
    835     /// and the copied map's key type is the from digraph's node
    836     /// type. 
     705    /// Makes copy of the given map for the newly created digraph.
     706    /// The new map's key type is the destination graph's node type,
     707    /// and the copied map's key type is the source graph's node type.
    837708    template <typename ToMap, typename FromMap>
    838709    DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
    839       nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node,
    840                               NodeRefMap, ToMap, FromMap>(tmap, map));
     710      _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
     711                           NodeRefMap, ToMap, FromMap>(tmap, map));
    841712      return *this;
    842713    }
     
    846717    /// Make a copy of the given node.
    847718    DigraphCopy& node(TNode& tnode, const Node& snode) {
    848       nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,
    849                               NodeRefMap, TNode>(tnode, snode));
     719      _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
     720                           NodeRefMap, TNode>(tnode, snode));
    850721      return *this;
    851722    }
     
    856727    template <typename ArcRef>
    857728    DigraphCopy& arcRef(ArcRef& map) {
    858       arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,
    859                               ArcRefMap, ArcRef>(map));
     729      _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
     730                          ArcRefMap, ArcRef>(map));
    860731      return *this;
    861732    }
     
    867738    template <typename ArcCrossRef>
    868739    DigraphCopy& arcCrossRef(ArcCrossRef& map) {
    869       arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,
    870                               ArcRefMap, ArcCrossRef>(map));
     740      _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
     741                          ArcRefMap, ArcCrossRef>(map));
    871742      return *this;
    872743    }
     
    880751    template <typename ToMap, typename FromMap>
    881752    DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
    882       arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,
    883                               ArcRefMap, ToMap, FromMap>(tmap, map));
     753      _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
     754                          ArcRefMap, ToMap, FromMap>(tmap, map));
    884755      return *this;
    885756    }
     
    889760    /// Make a copy of the given arc.
    890761    DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
    891       arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,
    892                               ArcRefMap, TArc>(tarc, sarc));
     762      _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
     763                          ArcRefMap, TArc>(tarc, sarc));
    893764      return *this;
    894765    }
     
    898769    /// Executes the copies.
    899770    void run() {
    900       NodeRefMap nodeRefMap(from);
    901       ArcRefMap arcRefMap(from);
    902       _digraph_utils_bits::DigraphCopySelector<To>::
    903         copy(to, from, nodeRefMap, arcRefMap);
    904       for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
    905         nodeMapCopies[i]->copy(from, nodeRefMap);
    906       }
    907       for (int i = 0; i < int(arcMapCopies.size()); ++i) {
    908         arcMapCopies[i]->copy(from, arcRefMap);
     771      NodeRefMap nodeRefMap(_from);
     772      ArcRefMap arcRefMap(_from);
     773      _graph_utils_bits::DigraphCopySelector<To>::
     774        copy(_to, _from, nodeRefMap, arcRefMap);
     775      for (int i = 0; i < int(_node_maps.size()); ++i) {
     776        _node_maps[i]->copy(_from, nodeRefMap);
     777      }
     778      for (int i = 0; i < int(_arc_maps.size()); ++i) {
     779        _arc_maps[i]->copy(_from, arcRefMap);
    909780      }     
    910781    }
     
    913784
    914785
    915     const From& from;
    916     To& to;
    917 
    918     std::vector<_digraph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
    919     nodeMapCopies;
    920 
    921     std::vector<_digraph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
    922     arcMapCopies;
     786    const From& _from;
     787    To& _to;
     788
     789    std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
     790    _node_maps;
     791
     792    std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
     793    _arc_maps;
    923794
    924795  };
     
    926797  /// \brief Copy a digraph to another digraph.
    927798  ///
    928   /// Copy a digraph to another digraph.
    929   /// The usage of the function:
    930   ///
     799  /// Copy a digraph to another digraph. The complete usage of the
     800  /// function is detailed in the DigraphCopy class, but a short
     801  /// example shows a basic work:
    931802  ///\code
    932803  /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
     
    944815  }
    945816
    946   /// \brief Class to copy an graph.
    947   ///
    948   /// Class to copy an graph to another digraph (duplicate a digraph).
    949   /// The simplest way of using it is through the \c copyGraph() function.
     817  /// \brief Class to copy a graph.
     818  ///
     819  /// Class to copy a graph to another graph (duplicate a graph). The
     820  /// simplest way of using it is through the \c copyGraph() function.
     821  ///
     822  /// This class not just make a copy of a graph, but it can create
     823  /// references and cross references between the nodes, edges and arcs of
     824  /// the two graphs, it can copy maps for use with the newly created
     825  /// graph and copy nodes, edges and arcs.
     826  ///
     827  /// To make a copy from a graph, first an instance of GraphCopy
     828  /// should be created, then the data belongs to the graph should
     829  /// assigned to copy. In the end, the \c run() member should be
     830  /// called.
     831  ///
     832  /// The next code copies a graph with several data:
     833  ///\code
     834  ///  GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
     835  ///  // create a reference for the nodes
     836  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
     837  ///  dc.nodeRef(nr);
     838  ///  // create a cross reference (inverse) for the edges
     839  ///  NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph);
     840  ///  dc.edgeCrossRef(ecr);
     841  ///  // copy an arc map
     842  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
     843  ///  NewGraph::ArcMap<double> namap(new_graph);
     844  ///  dc.arcMap(namap, oamap);
     845  ///  // copy a node
     846  ///  OrigGraph::Node on;
     847  ///  NewGraph::Node nn;
     848  ///  dc.node(nn, on);
     849  ///  // Executions of copy
     850  ///  dc.run();
     851  ///\endcode
    950852  template <typename To, typename From>
    951853  class GraphCopy {
     
    967869
    968870    struct ArcRefMap {
    969       ArcRefMap(const To& _to, const From& _from,
    970                  const EdgeRefMap& _edge_ref, const NodeRefMap& _node_ref)
    971         : to(_to), from(_from),
    972           edge_ref(_edge_ref), node_ref(_node_ref) {}
     871      ArcRefMap(const To& to, const From& from,
     872                const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
     873        : _to(to), _from(from),
     874          _edge_ref(edge_ref), _node_ref(node_ref) {}
    973875
    974876      typedef typename From::Arc Key;
     
    977879      Value operator[](const Key& key) const {
    978880        bool forward =
    979           (from.direction(key) ==
    980            (node_ref[from.source(static_cast<const Edge&>(key))] ==
    981             to.source(edge_ref[static_cast<const Edge&>(key)])));
    982         return to.direct(edge_ref[key], forward);
     881          (_from.direction(key) ==
     882           (_node_ref[_from.source(key)] == _to.source(_edge_ref[key])));
     883        return _to.direct(_edge_ref[key], forward);
    983884      }
    984885     
    985       const To& to;
    986       const From& from;
    987       const EdgeRefMap& edge_ref;
    988       const NodeRefMap& node_ref;
     886      const To& _to;
     887      const From& _from;
     888      const EdgeRefMap& _edge_ref;
     889      const NodeRefMap& _node_ref;
    989890    };
    990891
     
    993894
    994895
    995     /// \brief Constructor for the DigraphCopy.
    996     ///
    997     /// It copies the content of the \c _from digraph into the
    998     /// \c _to digraph.
    999     GraphCopy(To& _to, const From& _from)
    1000       : from(_from), to(_to) {}
    1001 
    1002     /// \brief Destructor of the DigraphCopy
    1003     ///
    1004     /// Destructor of the DigraphCopy
     896    /// \brief Constructor for the GraphCopy.
     897    ///
     898    /// It copies the content of the \c _from graph into the
     899    /// \c _to graph.
     900    GraphCopy(To& to, const From& from)
     901      : _from(from), _to(to) {}
     902
     903    /// \brief Destructor of the GraphCopy
     904    ///
     905    /// Destructor of the GraphCopy
    1005906    ~GraphCopy() {
    1006       for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
    1007         delete nodeMapCopies[i];
    1008       }
    1009       for (int i = 0; i < int(arcMapCopies.size()); ++i) {
    1010         delete arcMapCopies[i];
    1011       }
    1012       for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
    1013         delete edgeMapCopies[i];
     907      for (int i = 0; i < int(_node_maps.size()); ++i) {
     908        delete _node_maps[i];
     909      }
     910      for (int i = 0; i < int(_arc_maps.size()); ++i) {
     911        delete _arc_maps[i];
     912      }
     913      for (int i = 0; i < int(_edge_maps.size()); ++i) {
     914        delete _edge_maps[i];
    1014915      }
    1015916
     
    1021922    template <typename NodeRef>
    1022923    GraphCopy& nodeRef(NodeRef& map) {
    1023       nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node,
    1024                               NodeRefMap, NodeRef>(map));
     924      _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
     925                           NodeRefMap, NodeRef>(map));
    1025926      return *this;
    1026927    }
     
    1032933    template <typename NodeCrossRef>
    1033934    GraphCopy& nodeCrossRef(NodeCrossRef& map) {
    1034       nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,
    1035                               NodeRefMap, NodeCrossRef>(map));
     935      _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
     936                           NodeRefMap, NodeCrossRef>(map));
    1036937      return *this;
    1037938    }
     
    1039940    /// \brief Make copy of the given map.
    1040941    ///
    1041     /// Makes copy of the given map for the newly created digraph.
    1042     /// The new map's key type is the to digraph's node type,
    1043     /// and the copied map's key type is the from digraph's node
     942    /// Makes copy of the given map for the newly created graph.
     943    /// The new map's key type is the to graph's node type,
     944    /// and the copied map's key type is the from graph's node
    1044945    /// type. 
    1045946    template <typename ToMap, typename FromMap>
    1046947    GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
    1047       nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node,
    1048                               NodeRefMap, ToMap, FromMap>(tmap, map));
     948      _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
     949                           NodeRefMap, ToMap, FromMap>(tmap, map));
    1049950      return *this;
    1050951    }
     
    1054955    /// Make a copy of the given node.
    1055956    GraphCopy& node(TNode& tnode, const Node& snode) {
    1056       nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,
    1057                               NodeRefMap, TNode>(tnode, snode));
     957      _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
     958                           NodeRefMap, TNode>(tnode, snode));
    1058959      return *this;
    1059960    }
     
    1064965    template <typename ArcRef>
    1065966    GraphCopy& arcRef(ArcRef& map) {
    1066       arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,
    1067                               ArcRefMap, ArcRef>(map));
     967      _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
     968                          ArcRefMap, ArcRef>(map));
    1068969      return *this;
    1069970    }
     
    1075976    template <typename ArcCrossRef>
    1076977    GraphCopy& arcCrossRef(ArcCrossRef& map) {
    1077       arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,
    1078                               ArcRefMap, ArcCrossRef>(map));
     978      _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
     979                          ArcRefMap, ArcCrossRef>(map));
    1079980      return *this;
    1080981    }
     
    1082983    /// \brief Make copy of the given map.
    1083984    ///
    1084     /// Makes copy of the given map for the newly created digraph.
    1085     /// The new map's key type is the to digraph's arc type,
    1086     /// and the copied map's key type is the from digraph's arc
     985    /// Makes copy of the given map for the newly created graph.
     986    /// The new map's key type is the to graph's arc type,
     987    /// and the copied map's key type is the from graph's arc
    1087988    /// type. 
    1088989    template <typename ToMap, typename FromMap>
    1089990    GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
    1090       arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,
    1091                               ArcRefMap, ToMap, FromMap>(tmap, map));
     991      _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
     992                          ArcRefMap, ToMap, FromMap>(tmap, map));
    1092993      return *this;
    1093994    }
     
    1097998    /// Make a copy of the given arc.
    1098999    GraphCopy& arc(TArc& tarc, const Arc& sarc) {
    1099       arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,
    1100                               ArcRefMap, TArc>(tarc, sarc));
     1000      _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
     1001                          ArcRefMap, TArc>(tarc, sarc));
    11011002      return *this;
    11021003    }
     
    11071008    template <typename EdgeRef>
    11081009    GraphCopy& edgeRef(EdgeRef& map) {
    1109       edgeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Edge,
    1110                                EdgeRefMap, EdgeRef>(map));
     1010      _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge,
     1011                           EdgeRefMap, EdgeRef>(map));
    11111012      return *this;
    11121013    }
     
    11181019    template <typename EdgeCrossRef>
    11191020    GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
    1120       edgeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,
    1121                                Edge, EdgeRefMap, EdgeCrossRef>(map));
     1021      _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From,
     1022                           Edge, EdgeRefMap, EdgeCrossRef>(map));
    11221023      return *this;
    11231024    }
     
    11251026    /// \brief Make copy of the given map.
    11261027    ///
    1127     /// Makes copy of the given map for the newly created digraph.
    1128     /// The new map's key type is the to digraph's edge type,
    1129     /// and the copied map's key type is the from digraph's edge
     1028    /// Makes copy of the given map for the newly created graph.
     1029    /// The new map's key type is the to graph's edge type,
     1030    /// and the copied map's key type is the from graph's edge
    11301031    /// type. 
    11311032    template <typename ToMap, typename FromMap>
    11321033    GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
    1133       edgeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Edge,
    1134                                EdgeRefMap, ToMap, FromMap>(tmap, map));
     1034      _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge,
     1035                           EdgeRefMap, ToMap, FromMap>(tmap, map));
    11351036      return *this;
    11361037    }
     
    11401041    /// Make a copy of the given edge.
    11411042    GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
    1142       edgeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Edge,
    1143                                EdgeRefMap, TEdge>(tedge, sedge));
     1043      _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
     1044                           EdgeRefMap, TEdge>(tedge, sedge));
    11441045      return *this;
    11451046    }
     
    11491050    /// Executes the copies.
    11501051    void run() {
    1151       NodeRefMap nodeRefMap(from);
    1152       EdgeRefMap edgeRefMap(from);
    1153       ArcRefMap arcRefMap(to, from, edgeRefMap, nodeRefMap);
    1154       _digraph_utils_bits::GraphCopySelector<To>::
    1155         copy(to, from, nodeRefMap, edgeRefMap);
    1156       for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
    1157         nodeMapCopies[i]->copy(from, nodeRefMap);
    1158       }
    1159       for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
    1160         edgeMapCopies[i]->copy(from, edgeRefMap);
    1161       }
    1162       for (int i = 0; i < int(arcMapCopies.size()); ++i) {
    1163         arcMapCopies[i]->copy(from, arcRefMap);
     1052      NodeRefMap nodeRefMap(_from);
     1053      EdgeRefMap edgeRefMap(_from);
     1054      ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
     1055      _graph_utils_bits::GraphCopySelector<To>::
     1056        copy(_to, _from, nodeRefMap, edgeRefMap);
     1057      for (int i = 0; i < int(_node_maps.size()); ++i) {
     1058        _node_maps[i]->copy(_from, nodeRefMap);
     1059      }
     1060      for (int i = 0; i < int(_edge_maps.size()); ++i) {
     1061        _edge_maps[i]->copy(_from, edgeRefMap);
     1062      }
     1063      for (int i = 0; i < int(_arc_maps.size()); ++i) {
     1064        _arc_maps[i]->copy(_from, arcRefMap);
    11641065      }
    11651066    }
     
    11671068  private:
    11681069   
    1169     const From& from;
    1170     To& to;
    1171 
    1172     std::vector<_digraph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
    1173     nodeMapCopies;
    1174 
    1175     std::vector<_digraph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
    1176     arcMapCopies;
    1177 
    1178     std::vector<_digraph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
    1179     edgeMapCopies;
     1070    const From& _from;
     1071    To& _to;
     1072
     1073    std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
     1074    _node_maps;
     1075
     1076    std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
     1077    _arc_maps;
     1078
     1079    std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
     1080    _edge_maps;
    11801081
    11811082  };
    11821083
    1183   /// \brief Copy an graph to another digraph.
    1184   ///
    1185   /// Copy an graph to another digraph.
    1186   /// The usage of the function:
    1187   ///
     1084  /// \brief Copy a graph to another graph.
     1085  ///
     1086  /// Copy a graph to another graph. The complete usage of the
     1087  /// function is detailed in the GraphCopy class, but a short
     1088  /// example shows a basic work:
    11881089  ///\code
    11891090  /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
     
    11911092  ///
    11921093  /// After the copy the \c nr map will contain the mapping from the
    1193   /// nodes of the \c from digraph to the nodes of the \c to digraph and
    1194   /// \c ecr will contain the mapping from the arcs of the \c to digraph
    1195   /// to the arcs of the \c from digraph.
     1094  /// nodes of the \c from graph to the nodes of the \c to graph and
     1095  /// \c ecr will contain the mapping from the arcs of the \c to graph
     1096  /// to the arcs of the \c from graph.
    11961097  ///
    11971098  /// \see GraphCopy
     
    12021103  }
    12031104
    1204   /// \brief Class to copy a bipartite digraph.
    1205   ///
    1206   /// Class to copy a bipartite digraph to another digraph
    1207   /// (duplicate a digraph).  The simplest way of using it is through
    1208   /// the \c copyBpGraph() function.
    1209   template <typename To, typename From>
    1210   class BpGraphCopy {
    1211   private:
    1212 
    1213     typedef typename From::Node Node;
    1214     typedef typename From::Red Red;
    1215     typedef typename From::Blue Blue;
    1216     typedef typename From::NodeIt NodeIt;
    1217     typedef typename From::Arc Arc;
    1218     typedef typename From::ArcIt ArcIt;
    1219     typedef typename From::Edge Edge;
    1220     typedef typename From::EdgeIt EdgeIt;
    1221 
    1222     typedef typename To::Node TNode;
    1223     typedef typename To::Arc TArc;
    1224     typedef typename To::Edge TEdge;
    1225 
    1226     typedef typename From::template RedMap<TNode> RedRefMap;
    1227     typedef typename From::template BlueMap<TNode> BlueRefMap;
    1228     typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
    1229 
    1230     struct NodeRefMap {
    1231       NodeRefMap(const From& _from, const RedRefMap& _red_ref,
    1232                  const BlueRefMap& _blue_ref)
    1233         : from(_from), red_ref(_red_ref), blue_ref(_blue_ref) {}
    1234 
    1235       typedef typename From::Node Key;
    1236       typedef typename To::Node Value;
    1237 
    1238       Value operator[](const Key& key) const {
    1239         return from.red(key) ? red_ref[key] : blue_ref[key];
    1240       }
    1241      
    1242       const From& from;
    1243       const RedRefMap& red_ref;
    1244       const BlueRefMap& blue_ref;
    1245     };
    1246 
    1247     struct ArcRefMap {
    1248       ArcRefMap(const To& _to, const From& _from,
    1249                  const EdgeRefMap& _edge_ref, const NodeRefMap& _node_ref)
    1250         : to(_to), from(_from),
    1251           edge_ref(_edge_ref), node_ref(_node_ref) {}
    1252 
    1253       typedef typename From::Arc Key;
    1254       typedef typename To::Arc Value;
    1255 
    1256       Value operator[](const Key& key) const {
    1257         bool forward =
    1258           (from.direction(key) ==
    1259            (node_ref[from.source(static_cast<const Edge&>(key))] ==
    1260             to.source(edge_ref[static_cast<const Edge&>(key)])));
    1261         return to.direct(edge_ref[key], forward);
    1262       }
    1263      
    1264       const To& to;
    1265       const From& from;
    1266       const EdgeRefMap& edge_ref;
    1267       const NodeRefMap& node_ref;
    1268     };
    1269    
    1270   public:
    1271 
    1272 
    1273     /// \brief Constructor for the DigraphCopy.
    1274     ///
    1275     /// It copies the content of the \c _from digraph into the
    1276     /// \c _to digraph.
    1277     BpGraphCopy(To& _to, const From& _from)
    1278       : from(_from), to(_to) {}
    1279 
    1280     /// \brief Destructor of the DigraphCopy
    1281     ///
    1282     /// Destructor of the DigraphCopy
    1283     ~BpGraphCopy() {
    1284       for (int i = 0; i < int(redMapCopies.size()); ++i) {
    1285         delete redMapCopies[i];
    1286       }
    1287       for (int i = 0; i < int(blueMapCopies.size()); ++i) {
    1288         delete blueMapCopies[i];
    1289       }
    1290       for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
    1291         delete nodeMapCopies[i];
    1292       }
    1293       for (int i = 0; i < int(arcMapCopies.size()); ++i) {
    1294         delete arcMapCopies[i];
    1295       }
    1296       for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
    1297         delete edgeMapCopies[i];
    1298       }
    1299 
    1300     }
    1301 
    1302     /// \brief Copies the A-node references into the given map.
    1303     ///
    1304     /// Copies the A-node references into the given map.
    1305     template <typename RedRef>
    1306     BpGraphCopy& redRef(RedRef& map) {
    1307       redMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Red,
    1308                                RedRefMap, RedRef>(map));
    1309       return *this;
    1310     }
    1311 
    1312     /// \brief Copies the A-node cross references into the given map.
    1313     ///
    1314     /// Copies the A-node cross references (reverse references) into
    1315     /// the given map.
    1316     template <typename RedCrossRef>
    1317     BpGraphCopy& redCrossRef(RedCrossRef& map) {
    1318       redMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,
    1319                                Red, RedRefMap, RedCrossRef>(map));
    1320       return *this;
    1321     }
    1322 
    1323     /// \brief Make copy of the given A-node map.
    1324     ///
    1325     /// Makes copy of the given map for the newly created digraph.
    1326     /// The new map's key type is the to digraph's node type,
    1327     /// and the copied map's key type is the from digraph's node
    1328     /// type. 
    1329     template <typename ToMap, typename FromMap>
    1330     BpGraphCopy& redMap(ToMap& tmap, const FromMap& map) {
    1331       redMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Red,
    1332                                RedRefMap, ToMap, FromMap>(tmap, map));
    1333       return *this;
    1334     }
    1335 
    1336     /// \brief Copies the B-node references into the given map.
    1337     ///
    1338     /// Copies the B-node references into the given map.
    1339     template <typename BlueRef>
    1340     BpGraphCopy& blueRef(BlueRef& map) {
    1341       blueMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Blue,
    1342                                BlueRefMap, BlueRef>(map));
    1343       return *this;
    1344     }
    1345 
    1346     /// \brief Copies the B-node cross references into the given map.
    1347     ///
    1348     ///  Copies the B-node cross references (reverse references) into
    1349     ///  the given map.
    1350     template <typename BlueCrossRef>
    1351     BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
    1352       blueMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,
    1353                               Blue, BlueRefMap, BlueCrossRef>(map));
    1354       return *this;
    1355     }
    1356 
    1357     /// \brief Make copy of the given B-node map.
    1358     ///
    1359     /// Makes copy of the given map for the newly created digraph.
    1360     /// The new map's key type is the to digraph's node type,
    1361     /// and the copied map's key type is the from digraph's node
    1362     /// type. 
    1363     template <typename ToMap, typename FromMap>
    1364     BpGraphCopy& blueMap(ToMap& tmap, const FromMap& map) {
    1365       blueMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Blue,
    1366                                BlueRefMap, ToMap, FromMap>(tmap, map));
    1367       return *this;
    1368     }
    1369     /// \brief Copies the node references into the given map.
    1370     ///
    1371     /// Copies the node references into the given map.
    1372     template <typename NodeRef>
    1373     BpGraphCopy& nodeRef(NodeRef& map) {
    1374       nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node,
    1375                               NodeRefMap, NodeRef>(map));
    1376       return *this;
    1377     }
    1378 
    1379     /// \brief Copies the node cross references into the given map.
    1380     ///
    1381     ///  Copies the node cross references (reverse references) into
    1382     ///  the given map.
    1383     template <typename NodeCrossRef>
    1384     BpGraphCopy& nodeCrossRef(NodeCrossRef& map) {
    1385       nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,
    1386                               NodeRefMap, NodeCrossRef>(map));
    1387       return *this;
    1388     }
    1389 
    1390     /// \brief Make copy of the given map.
    1391     ///
    1392     /// Makes copy of the given map for the newly created digraph.
    1393     /// The new map's key type is the to digraph's node type,
    1394     /// and the copied map's key type is the from digraph's node
    1395     /// type. 
    1396     template <typename ToMap, typename FromMap>
    1397     BpGraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
    1398       nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node,
    1399                               NodeRefMap, ToMap, FromMap>(tmap, map));
    1400       return *this;
    1401     }
    1402 
    1403     /// \brief Make a copy of the given node.
    1404     ///
    1405     /// Make a copy of the given node.
    1406     BpGraphCopy& node(TNode& tnode, const Node& snode) {
    1407       nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,
    1408                               NodeRefMap, TNode>(tnode, snode));
    1409       return *this;
    1410     }
    1411 
    1412     /// \brief Copies the arc references into the given map.
    1413     ///
    1414     /// Copies the arc references into the given map.
    1415     template <typename ArcRef>
    1416     BpGraphCopy& arcRef(ArcRef& map) {
    1417       arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,
    1418                               ArcRefMap, ArcRef>(map));
    1419       return *this;
    1420     }
    1421 
    1422     /// \brief Copies the arc cross references into the given map.
    1423     ///
    1424     ///  Copies the arc cross references (reverse references) into
    1425     ///  the given map.
    1426     template <typename ArcCrossRef>
    1427     BpGraphCopy& arcCrossRef(ArcCrossRef& map) {
    1428       arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,
    1429                               ArcRefMap, ArcCrossRef>(map));
    1430       return *this;
    1431     }
    1432 
    1433     /// \brief Make copy of the given map.
    1434     ///
    1435     /// Makes copy of the given map for the newly created digraph.
    1436     /// The new map's key type is the to digraph's arc type,
    1437     /// and the copied map's key type is the from digraph's arc
    1438     /// type. 
    1439     template <typename ToMap, typename FromMap>
    1440     BpGraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
    1441       arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,
    1442                               ArcRefMap, ToMap, FromMap>(tmap, map));
    1443       return *this;
    1444     }
    1445 
    1446     /// \brief Make a copy of the given arc.
    1447     ///
    1448     /// Make a copy of the given arc.
    1449     BpGraphCopy& arc(TArc& tarc, const Arc& sarc) {
    1450       arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,
    1451                               ArcRefMap, TArc>(tarc, sarc));
    1452       return *this;
    1453     }
    1454 
    1455     /// \brief Copies the edge references into the given map.
    1456     ///
    1457     /// Copies the edge references into the given map.
    1458     template <typename EdgeRef>
    1459     BpGraphCopy& edgeRef(EdgeRef& map) {
    1460       edgeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Edge,
    1461                                EdgeRefMap, EdgeRef>(map));
    1462       return *this;
    1463     }
    1464 
    1465     /// \brief Copies the edge cross references into the given map.
    1466     ///
    1467     /// Copies the edge cross references (reverse
    1468     /// references) into the given map.
    1469     template <typename EdgeCrossRef>
    1470     BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
    1471       edgeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,
    1472                                Edge, EdgeRefMap, EdgeCrossRef>(map));
    1473       return *this;
    1474     }
    1475 
    1476     /// \brief Make copy of the given map.
    1477     ///
    1478     /// Makes copy of the given map for the newly created digraph.
    1479     /// The new map's key type is the to digraph's edge type,
    1480     /// and the copied map's key type is the from digraph's edge
    1481     /// type. 
    1482     template <typename ToMap, typename FromMap>
    1483     BpGraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
    1484       edgeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Edge,
    1485                                EdgeRefMap, ToMap, FromMap>(tmap, map));
    1486       return *this;
    1487     }
    1488 
    1489     /// \brief Make a copy of the given edge.
    1490     ///
    1491     /// Make a copy of the given edge.
    1492     BpGraphCopy& edge(TEdge& tedge, const Edge& sedge) {
    1493       edgeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Edge,
    1494                                EdgeRefMap, TEdge>(tedge, sedge));
    1495       return *this;
    1496     }
    1497 
    1498     /// \brief Executes the copies.
    1499     ///
    1500     /// Executes the copies.
    1501     void run() {
    1502       RedRefMap redRefMap(from);
    1503       BlueRefMap blueRefMap(from);
    1504       NodeRefMap nodeRefMap(from, redRefMap, blueRefMap);
    1505       EdgeRefMap edgeRefMap(from);
    1506       ArcRefMap arcRefMap(to, from, edgeRefMap, nodeRefMap);
    1507       _digraph_utils_bits::BpGraphCopySelector<To>::
    1508         copy(to, from, redRefMap, blueRefMap, edgeRefMap);
    1509       for (int i = 0; i < int(redMapCopies.size()); ++i) {
    1510         redMapCopies[i]->copy(from, redRefMap);
    1511       }
    1512       for (int i = 0; i < int(blueMapCopies.size()); ++i) {
    1513         blueMapCopies[i]->copy(from, blueRefMap);
    1514       }
    1515       for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
    1516         nodeMapCopies[i]->copy(from, nodeRefMap);
    1517       }
    1518       for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
    1519         edgeMapCopies[i]->copy(from, edgeRefMap);
    1520       }
    1521       for (int i = 0; i < int(arcMapCopies.size()); ++i) {
    1522         arcMapCopies[i]->copy(from, arcRefMap);
    1523       }
    1524     }
    1525 
    1526   private:
    1527    
    1528     const From& from;
    1529     To& to;
    1530 
    1531     std::vector<_digraph_utils_bits::MapCopyBase<From, Red, RedRefMap>* >
    1532     redMapCopies;
    1533 
    1534     std::vector<_digraph_utils_bits::MapCopyBase<From, Blue, BlueRefMap>* >
    1535     blueMapCopies;
    1536 
    1537     std::vector<_digraph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
    1538     nodeMapCopies;
    1539 
    1540     std::vector<_digraph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
    1541     arcMapCopies;
    1542 
    1543     std::vector<_digraph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
    1544     edgeMapCopies;
    1545 
    1546   };
    1547 
    1548   /// \brief Copy a bipartite digraph to another digraph.
    1549   ///
    1550   /// Copy a bipartite digraph to another digraph.
    1551   /// The usage of the function:
    1552   ///
    1553   ///\code
    1554   /// copyBpGraph(trg, src).redRef(anr).arcCrossRef(ecr).run();
    1555   ///\endcode
    1556   ///
    1557   /// After the copy the \c nr map will contain the mapping from the
    1558   /// nodes of the \c from digraph to the nodes of the \c to digraph and
    1559   /// \c ecr will contain the mapping from the arcs of the \c to digraph
    1560   /// to the arcs of the \c from digraph.
    1561   ///
    1562   /// \see BpGraphCopy
    1563   template <typename To, typename From>
    1564   BpGraphCopy<To, From>
    1565   copyBpGraph(To& to, const From& from) {
    1566     return BpGraphCopy<To, From>(to, from);
    1567   }
    1568 
    1569 
    15701105  /// @}
    15711106
    1572   /// \addtogroup digraph_maps
     1107  /// \addtogroup graph_maps
    15731108  /// @{
    15741109
    1575   /// Provides an immutable and unique id for each item in the digraph.
     1110  /// Provides an immutable and unique id for each item in the graph.
    15761111
    15771112  /// The IdMap class provides a unique and immutable id for each item of the
    1578   /// same type (e.g. node) in the digraph. This id is <ul><li>\b unique:
     1113  /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
    15791114  /// different items (nodes) get different ids <li>\b immutable: the id of an
    15801115  /// item (node) does not change (even if you delete other nodes).  </ul>
    15811116  /// Through this map you get access (i.e. can read) the inner id values of
    1582   /// the items stored in the digraph. This map can be inverted with its member
    1583   /// class \c InverseMap.
    1584   ///
    1585   template <typename _Digraph, typename _Item>
     1117  /// the items stored in the graph. This map can be inverted with its member
     1118  /// class \c InverseMap or with the \c operator() member.
     1119  ///
     1120  template <typename _Graph, typename _Item>
    15861121  class IdMap {
    15871122  public:
    1588     typedef _Digraph Digraph;
     1123    typedef _Graph Graph;
    15891124    typedef int Value;
    15901125    typedef _Item Item;
     
    15941129    ///
    15951130    /// Constructor of the map.
    1596     explicit IdMap(const Digraph& _digraph) : digraph(&_digraph) {}
     1131    explicit IdMap(const Graph& graph) : _graph(&graph) {}
    15971132
    15981133    /// \brief Gives back the \e id of the item.
    15991134    ///
    16001135    /// Gives back the immutable and unique \e id of the item.
    1601     int operator[](const Item& item) const { return digraph->id(item);}
     1136    int operator[](const Item& item) const { return _graph->id(item);}
    16021137
    16031138    /// \brief Gives back the item by its id.
    16041139    ///
    16051140    /// Gives back the item by its id.
    1606     Item operator()(int id) { return digraph->fromId(id, Item()); }
     1141    Item operator()(int id) { return _graph->fromId(id, Item()); }
    16071142
    16081143  private:
    1609     const Digraph* digraph;
     1144    const Graph* _graph;
    16101145
    16111146  public:
     
    16211156      ///
    16221157      /// Constructor for creating an id-to-item map.
    1623       explicit InverseMap(const Digraph& _digraph) : digraph(&_digraph) {}
     1158      explicit InverseMap(const Graph& graph) : _graph(&graph) {}
    16241159
    16251160      /// \brief Constructor.
    16261161      ///
    16271162      /// Constructor for creating an id-to-item map.
    1628       explicit InverseMap(const IdMap& idMap) : digraph(idMap.digraph) {}
     1163      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
    16291164
    16301165      /// \brief Gives back the given item from its id.
     
    16321167      /// Gives back the given item from its id.
    16331168      ///
    1634       Item operator[](int id) const { return digraph->fromId(id, Item());}
     1169      Item operator[](int id) const { return _graph->fromId(id, Item());}
    16351170
    16361171    private:
    1637       const Digraph* digraph;
     1172      const Graph* _graph;
    16381173    };
    16391174
     
    16411176    ///
    16421177    /// Gives back the inverse of the IdMap.
    1643     InverseMap inverse() const { return InverseMap(*digraph);}
     1178    InverseMap inverse() const { return InverseMap(*_graph);}
    16441179
    16451180  };
    16461181
    16471182 
    1648   /// \brief General invertable digraph-map type.
    1649 
    1650   /// This type provides simple invertable digraph-maps.
     1183  /// \brief General invertable graph-map type.
     1184
     1185  /// This type provides simple invertable graph-maps.
    16511186  /// The InvertableMap wraps an arbitrary ReadWriteMap
    16521187  /// and if a key is set to a new value then store it
     
    16561191  /// with stl compatible forward iterator.
    16571192  ///
    1658   /// \param _Digraph The digraph type.
    1659   /// \param _Item The item type of the digraph.
     1193  /// \param _Graph The graph type.
     1194  /// \param _Item The item type of the graph.
    16601195  /// \param _Value The value type of the map.
    16611196  ///
    16621197  /// \see IterableValueMap
    1663   template <typename _Digraph, typename _Item, typename _Value>
    1664   class InvertableMap : protected DefaultMap<_Digraph, _Item, _Value> {
     1198  template <typename _Graph, typename _Item, typename _Value>
     1199  class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
    16651200  private:
    16661201   
    1667     typedef DefaultMap<_Digraph, _Item, _Value> Map;
    1668     typedef _Digraph Digraph;
     1202    typedef DefaultMap<_Graph, _Item, _Value> Map;
     1203    typedef _Graph Graph;
    16691204
    16701205    typedef std::map<_Value, _Item> Container;
    1671     Container invMap;   
     1206    Container _inv_map;   
    16721207
    16731208  public:
     
    16821217    /// \brief Constructor.
    16831218    ///
    1684     /// Construct a new InvertableMap for the digraph.
    1685     ///
    1686     explicit InvertableMap(const Digraph& digraph) : Map(digraph) {}
     1219    /// Construct a new InvertableMap for the graph.
     1220    ///
     1221    explicit InvertableMap(const Graph& graph) : Map(graph) {}
    16871222
    16881223    /// \brief Forward iterator for values.
     
    17261261    /// range.
    17271262    ValueIterator beginValue() const {
    1728       return ValueIterator(invMap.begin());
     1263      return ValueIterator(_inv_map.begin());
    17291264    }
    17301265
     
    17361271    /// range.
    17371272    ValueIterator endValue() const {
    1738       return ValueIterator(invMap.end());
     1273      return ValueIterator(_inv_map.end());
    17391274    }
    17401275   
     
    17441279    void set(const Key& key, const Value& val) {
    17451280      Value oldval = Map::operator[](key);
    1746       typename Container::iterator it = invMap.find(oldval);
    1747       if (it != invMap.end() && it->second == key) {
    1748         invMap.erase(it);
     1281      typename Container::iterator it = _inv_map.find(oldval);
     1282      if (it != _inv_map.end() && it->second == key) {
     1283        _inv_map.erase(it);
    17491284      }     
    1750       invMap.insert(make_pair(val, key));
     1285      _inv_map.insert(make_pair(val, key));
    17511286      Map::set(key, val);
    17521287    }
     
    17641299    /// Gives back the item by its value.
    17651300    Key operator()(const Value& key) const {
    1766       typename Container::const_iterator it = invMap.find(key);
    1767       return it != invMap.end() ? it->second : INVALID;
     1301      typename Container::const_iterator it = _inv_map.find(key);
     1302      return it != _inv_map.end() ? it->second : INVALID;
    17681303    }
    17691304
     
    17761311    virtual void erase(const Key& key) {
    17771312      Value val = Map::operator[](key);
    1778       typename Container::iterator it = invMap.find(val);
    1779       if (it != invMap.end() && it->second == key) {
    1780         invMap.erase(it);
     1313      typename Container::iterator it = _inv_map.find(val);
     1314      if (it != _inv_map.end() && it->second == key) {
     1315        _inv_map.erase(it);
    17811316      }
    17821317      Map::erase(key);
     
    17901325      for (int i = 0; i < int(keys.size()); ++i) {
    17911326        Value val = Map::operator[](keys[i]);
    1792         typename Container::iterator it = invMap.find(val);
    1793         if (it != invMap.end() && it->second == keys[i]) {
    1794           invMap.erase(it);
     1327        typename Container::iterator it = _inv_map.find(val);
     1328        if (it != _inv_map.end() && it->second == keys[i]) {
     1329          _inv_map.erase(it);
    17951330        }
    17961331      }
     
    18031338    /// \c AlterationNotifier.
    18041339    virtual void clear() {
    1805       invMap.clear();
     1340      _inv_map.clear();
    18061341      Map::clear();
    18071342    }
     
    18181353      ///
    18191354      /// Constructor of the InverseMap.
    1820       explicit InverseMap(const InvertableMap& _inverted)
    1821         : inverted(_inverted) {}
     1355      explicit InverseMap(const InvertableMap& inverted)
     1356        : _inverted(inverted) {}
    18221357
    18231358      /// The value type of the InverseMap.
     
    18311366      /// what was last assigned to the value.
    18321367      Value operator[](const Key& key) const {
    1833         return inverted(key);
     1368        return _inverted(key);
    18341369      }
    18351370     
    18361371    private:
    1837       const InvertableMap& inverted;
     1372      const InvertableMap& _inverted;
    18381373    };
    18391374
     
    18501385
    18511386  /// \brief Provides a mutable, continuous and unique descriptor for each
    1852   /// item in the digraph.
     1387  /// item in the graph.
    18531388  ///
    18541389  /// The DescriptorMap class provides a unique and continuous (but mutable)
    18551390  /// descriptor (id) for each item of the same type (e.g. node) in the
    1856   /// digraph. This id is <ul><li>\b unique: different items (nodes) get
     1391  /// graph. This id is <ul><li>\b unique: different items (nodes) get
    18571392  /// different ids <li>\b continuous: the range of the ids is the set of
    18581393  /// integers between 0 and \c n-1, where \c n is the number of the items of
    18591394  /// this type (e.g. nodes) (so the id of a node can change if you delete an
    18601395  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
    1861   /// with its member class \c InverseMap.
    1862   ///
    1863   /// \param _Digraph The digraph class the \c DescriptorMap belongs to.
     1396  /// with its member class \c InverseMap, or with the \c operator() member.
     1397  ///
     1398  /// \param _Graph The graph class the \c DescriptorMap belongs to.
    18641399  /// \param _Item The Item is the Key of the Map. It may be Node, Arc or
    18651400  /// Edge.
    1866   template <typename _Digraph, typename _Item>
    1867   class DescriptorMap : protected DefaultMap<_Digraph, _Item, int> {
     1401  template <typename _Graph, typename _Item>
     1402  class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
    18681403
    18691404    typedef _Item Item;
    1870     typedef DefaultMap<_Digraph, _Item, int> Map;
     1405    typedef DefaultMap<_Graph, _Item, int> Map;
    18711406
    18721407  public:
    1873     /// The digraph class of DescriptorMap.
    1874     typedef _Digraph Digraph;
     1408    /// The graph class of DescriptorMap.
     1409    typedef _Graph Graph;
    18751410
    18761411    /// The key type of DescriptorMap (Node, Arc, Edge).
     
    18821417    ///
    18831418    /// Constructor for descriptor map.
    1884     explicit DescriptorMap(const Digraph& _digraph) : Map(_digraph) {
     1419    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
    18851420      Item it;
    18861421      const typename Map::Notifier* nf = Map::notifier();
    18871422      for (nf->first(it); it != INVALID; nf->next(it)) {
    1888         Map::set(it, invMap.size());
    1889         invMap.push_back(it);   
     1423        Map::set(it, _inv_map.size());
     1424        _inv_map.push_back(it);
    18901425      }     
    18911426    }
     
    18991434    virtual void add(const Item& item) {
    19001435      Map::add(item);
    1901       Map::set(item, invMap.size());
    1902       invMap.push_back(item);
     1436      Map::set(item, _inv_map.size());
     1437      _inv_map.push_back(item);
    19031438    }
    19041439
     
    19101445      Map::add(items);
    19111446      for (int i = 0; i < int(items.size()); ++i) {
    1912         Map::set(items[i], invMap.size());
    1913         invMap.push_back(items[i]);
     1447        Map::set(items[i], _inv_map.size());
     1448        _inv_map.push_back(items[i]);
    19141449      }
    19151450    }
     
    19201455    /// \c AlterationNotifier.
    19211456    virtual void erase(const Item& item) {
    1922       Map::set(invMap.back(), Map::operator[](item));
    1923       invMap[Map::operator[](item)] = invMap.back();
    1924       invMap.pop_back();
     1457      Map::set(_inv_map.back(), Map::operator[](item));
     1458      _inv_map[Map::operator[](item)] = _inv_map.back();
     1459      _inv_map.pop_back();
    19251460      Map::erase(item);
    19261461    }
     
    19321467    virtual void erase(const std::vector<Item>& items) {
    19331468      for (int i = 0; i < int(items.size()); ++i) {
    1934         Map::set(invMap.back(), Map::operator[](items[i]));
    1935         invMap[Map::operator[](items[i])] = invMap.back();
    1936         invMap.pop_back();
     1469        Map::set(_inv_map.back(), Map::operator[](items[i]));
     1470        _inv_map[Map::operator[](items[i])] = _inv_map.back();
     1471        _inv_map.pop_back();
    19371472      }
    19381473      Map::erase(items);
     
    19481483      const typename Map::Notifier* nf = Map::notifier();
    19491484      for (nf->first(it); it != INVALID; nf->next(it)) {
    1950         Map::set(it, invMap.size());
    1951         invMap.push_back(it);   
     1485        Map::set(it, _inv_map.size());
     1486        _inv_map.push_back(it);
    19521487      }     
    19531488    }
     
    19581493    /// \c AlterationNotifier.
    19591494    virtual void clear() {
    1960       invMap.clear();
     1495      _inv_map.clear();
    19611496      Map::clear();
    19621497    }
     
    19681503    /// Returns the maximal value plus one in the map.
    19691504    unsigned int size() const {
    1970       return invMap.size();
     1505      return _inv_map.size();
    19711506    }
    19721507
     
    19781513      int qi = Map::operator[](q);
    19791514      Map::set(p, qi);
    1980       invMap[qi] = p;
     1515      _inv_map[qi] = p;
    19811516      Map::set(q, pi);
    1982       invMap[pi] = q;
     1517      _inv_map[pi] = q;
    19831518    }
    19841519
     
    19941529    /// Gives back th item by its descriptor.
    19951530    Item operator()(int id) const {
    1996       return invMap[id];
     1531      return _inv_map[id];
    19971532    }
    19981533   
     
    20001535
    20011536    typedef std::vector<Item> Container;
    2002     Container invMap;
     1537    Container _inv_map;
    20031538
    20041539  public:
     
    20111546      ///
    20121547      /// Constructor of the InverseMap.
    2013       explicit InverseMap(const DescriptorMap& _inverted)
    2014         : inverted(_inverted) {}
     1548      explicit InverseMap(const DescriptorMap& inverted)
     1549        : _inverted(inverted) {}
    20151550
    20161551
     
    20251560      /// that the descriptor belongs to currently.
    20261561      Value operator[](const Key& key) const {
    2027         return inverted(key);
     1562        return _inverted(key);
    20281563      }
    20291564
     
    20321567      /// Returns the size of the map.
    20331568      unsigned int size() const {
    2034         return inverted.size();
     1569        return _inverted.size();
    20351570      }
    20361571     
    20371572    private:
    2038       const DescriptorMap& inverted;
     1573      const DescriptorMap& _inverted;
    20391574    };
    20401575
     
    20631598    /// Constructor
    20641599    /// \param _digraph The digraph that the map belongs to.
    2065     explicit SourceMap(const Digraph& _digraph) : digraph(_digraph) {}
     1600    explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
    20661601
    20671602    /// \brief The subscript operator.
     
    20711606    /// \return The source of the arc
    20721607    Value operator[](const Key& arc) const {
    2073       return digraph.source(arc);
     1608      return _digraph.source(arc);
    20741609    }
    20751610
    20761611  private:
    2077     const Digraph& digraph;
     1612    const Digraph& _digraph;
    20781613  };
    20791614
     
    21031638    /// Constructor
    21041639    /// \param _digraph The digraph that the map belongs to.
    2105     explicit TargetMap(const Digraph& _digraph) : digraph(_digraph) {}
     1640    explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
    21061641
    21071642    /// \brief The subscript operator.
     
    21111646    /// \return The target of the arc
    21121647    Value operator[](const Key& e) const {
    2113       return digraph.target(e);
     1648      return _digraph.target(e);
    21141649    }
    21151650
    21161651  private:
    2117     const Digraph& digraph;
     1652    const Digraph& _digraph;
    21181653  };
    21191654
     
    21321667  /// \see BackwardMap
    21331668  /// \author Balazs Dezso
    2134   template <typename Digraph>
     1669  template <typename Graph>
    21351670  class ForwardMap {
    21361671  public:
    21371672
    2138     typedef typename Digraph::Arc Value;
    2139     typedef typename Digraph::Edge Key;
     1673    typedef typename Graph::Arc Value;
     1674    typedef typename Graph::Edge Key;
    21401675
    21411676    /// \brief Constructor
    21421677    ///
    21431678    /// Constructor
    2144     /// \param _digraph The digraph that the map belongs to.
    2145     explicit ForwardMap(const Digraph& _digraph) : digraph(_digraph) {}
     1679    /// \param _graph The graph that the map belongs to.
     1680    explicit ForwardMap(const Graph& graph) : _graph(graph) {}
    21461681
    21471682    /// \brief The subscript operator.
     
    21511686    /// \return The "forward" directed arc view of edge
    21521687    Value operator[](const Key& key) const {
    2153       return digraph.direct(key, true);
     1688      return _graph.direct(key, true);
    21541689    }
    21551690
    21561691  private:
    2157     const Digraph& digraph;
     1692    const Graph& _graph;
    21581693  };
    21591694
     
    21621697  /// This function just returns an \ref ForwardMap class.
    21631698  /// \relates ForwardMap
    2164   template <typename Digraph>
    2165   inline ForwardMap<Digraph> forwardMap(const Digraph& digraph) {
    2166     return ForwardMap<Digraph>(digraph);
     1699  template <typename Graph>
     1700  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
     1701    return ForwardMap<Graph>(graph);
    21671702  }
    21681703
     
    21721707  /// \see ForwardMap
    21731708  /// \author Balazs Dezso
    2174   template <typename Digraph>
     1709  template <typename Graph>
    21751710  class BackwardMap {
    21761711  public:
    21771712
    2178     typedef typename Digraph::Arc Value;
    2179     typedef typename Digraph::Edge Key;
     1713    typedef typename Graph::Arc Value;
     1714    typedef typename Graph::Edge Key;
    21801715
    21811716    /// \brief Constructor
    21821717    ///
    21831718    /// Constructor
    2184     /// \param _digraph The digraph that the map belongs to.
    2185     explicit BackwardMap(const Digraph& _digraph) : digraph(_digraph) {}
     1719    /// \param _graph The graph that the map belongs to.
     1720    explicit BackwardMap(const Graph& graph) : _graph(graph) {}
    21861721
    21871722    /// \brief The subscript operator.
     
    21911726    /// \return The "backward" directed arc view of edge
    21921727    Value operator[](const Key& key) const {
    2193       return digraph.direct(key, false);
     1728      return _graph.direct(key, false);
    21941729    }
    21951730
    21961731  private:
    2197     const Digraph& digraph;
     1732    const Graph& _graph;
    21981733  };
    21991734
     
    22021737  /// This function just returns a \ref BackwardMap class.
    22031738  /// \relates BackwardMap
    2204   template <typename Digraph>
    2205   inline BackwardMap<Digraph> backwardMap(const Digraph& digraph) {
    2206     return BackwardMap<Digraph>(digraph);
     1739  template <typename Graph>
     1740  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
     1741    return BackwardMap<Graph>(graph);
    22071742  }
    22081743
     
    22211756    ///
    22221757    /// Contructor of the map
    2223     explicit PotentialDifferenceMap(const Digraph& _digraph,
    2224                                     const NodeMap& _potential)
    2225       : digraph(_digraph), potential(_potential) {}
     1758    explicit PotentialDifferenceMap(const Digraph& digraph,
     1759                                    const NodeMap& potential)
     1760      : _digraph(digraph), _potential(potential) {}
    22261761
    22271762    /// \brief Const subscription operator
     
    22291764    /// Const subscription operator
    22301765    Value operator[](const Key& arc) const {
    2231       return potential[digraph.target(arc)] - potential[digraph.source(arc)];
     1766      return _potential[_digraph.target(arc)] -
     1767        _potential[_digraph.source(arc)];
    22321768    }
    22331769
    22341770  private:
    2235     const Digraph& digraph;
    2236     const NodeMap& potential;
     1771    const Digraph& _digraph;
     1772    const NodeMap& _potential;
    22371773  };
    22381774
     
    22751811    typedef typename Digraph::Node Key;
    22761812
    2277     typedef typename ItemSetTraits<_Digraph, typename _Digraph::Arc>
     1813    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
    22781814    ::ItemNotifier::ObserverBase Parent;
    22791815
    22801816  private:
    22811817
    2282     class AutoNodeMap : public DefaultMap<_Digraph, Key, int> {
     1818    class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
    22831819    public:
    22841820
    2285       typedef DefaultMap<_Digraph, Key, int> Parent;
    2286       typedef typename Parent::Digraph Digraph;
     1821      typedef DefaultMap<Digraph, Key, int> Parent;
    22871822
    22881823      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
     
    23151850    ///
    23161851    /// Constructor for creating in-degree map.
    2317     explicit InDegMap(const Digraph& _digraph) : digraph(_digraph), deg(_digraph) {
    2318       Parent::attach(digraph.notifier(typename _Digraph::Arc()));
     1852    explicit InDegMap(const Digraph& digraph)
     1853      : _digraph(digraph), _deg(digraph) {
     1854      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
    23191855     
    2320       for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
    2321         deg[it] = countInArcs(digraph, it);
     1856      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
     1857        _deg[it] = countInArcs(_digraph, it);
    23221858      }
    23231859    }
     
    23251861    /// Gives back the in-degree of a Node.
    23261862    int operator[](const Key& key) const {
    2327       return deg[key];
     1863      return _deg[key];
    23281864    }
    23291865
     
    23331869
    23341870    virtual void add(const Arc& arc) {
    2335       ++deg[digraph.target(arc)];
     1871      ++_deg[_digraph.target(arc)];
    23361872    }
    23371873
    23381874    virtual void add(const std::vector<Arc>& arcs) {
    23391875      for (int i = 0; i < int(arcs.size()); ++i) {
    2340         ++deg[digraph.target(arcs[i])];
     1876        ++_deg[_digraph.target(arcs[i])];
    23411877      }
    23421878    }
    23431879
    23441880    virtual void erase(const Arc& arc) {
    2345       --deg[digraph.target(arc)];
     1881      --_deg[_digraph.target(arc)];
    23461882    }
    23471883
    23481884    virtual void erase(const std::vector<Arc>& arcs) {
    23491885      for (int i = 0; i < int(arcs.size()); ++i) {
    2350         --deg[digraph.target(arcs[i])];
     1886        --_deg[_digraph.target(arcs[i])];
    23511887      }
    23521888    }
    23531889
    23541890    virtual void build() {
    2355       for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
    2356         deg[it] = countInArcs(digraph, it);
     1891      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
     1892        _deg[it] = countInArcs(_digraph, it);
    23571893      }     
    23581894    }
    23591895
    23601896    virtual void clear() {
    2361       for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
    2362         deg[it] = 0;
     1897      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
     1898        _deg[it] = 0;
    23631899      }
    23641900    }
    23651901  private:
    23661902   
    2367     const _Digraph& digraph;
    2368     AutoNodeMap deg;
     1903    const Digraph& _digraph;
     1904    AutoNodeMap _deg;
    23691905  };
    23701906
     
    23921928
    23931929  public:
    2394 
    2395     typedef typename ItemSetTraits<_Digraph, typename _Digraph::Arc>
    2396     ::ItemNotifier::ObserverBase Parent;
    23971930   
    23981931    typedef _Digraph Digraph;
     
    24001933    typedef typename Digraph::Node Key;
    24011934
     1935    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
     1936    ::ItemNotifier::ObserverBase Parent;
     1937
    24021938  private:
    24031939
    2404     class AutoNodeMap : public DefaultMap<_Digraph, Key, int> {
     1940    class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
    24051941    public:
    24061942
    2407       typedef DefaultMap<_Digraph, Key, int> Parent;
    2408       typedef typename Parent::Digraph Digraph;
     1943      typedef DefaultMap<Digraph, Key, int> Parent;
    24091944
    24101945      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
     
    24351970    ///
    24361971    /// Constructor for creating out-degree map.
    2437     explicit OutDegMap(const Digraph& _digraph) : digraph(_digraph), deg(_digraph) {
    2438       Parent::attach(digraph.notifier(typename _Digraph::Arc()));
     1972    explicit OutDegMap(const Digraph& digraph)
     1973      : _digraph(digraph), _deg(digraph) {
     1974      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
    24391975     
    2440       for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
    2441         deg[it] = countOutArcs(digraph, it);
     1976      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
     1977        _deg[it] = countOutArcs(_digraph, it);
    24421978      }
    24431979    }
     
    24451981    /// Gives back the out-degree of a Node.
    24461982    int operator[](const Key& key) const {
    2447       return deg[key];
     1983      return _deg[key];
    24481984    }
    24491985
     
    24531989
    24541990    virtual void add(const Arc& arc) {
    2455       ++deg[digraph.source(arc)];
     1991      ++_deg[_digraph.source(arc)];
    24561992    }
    24571993
    24581994    virtual void add(const std::vector<Arc>& arcs) {
    24591995      for (int i = 0; i < int(arcs.size()); ++i) {
    2460         ++deg[digraph.source(arcs[i])];
     1996        ++_deg[_digraph.source(arcs[i])];
    24611997      }
    24621998    }
    24631999
    24642000    virtual void erase(const Arc& arc) {
    2465       --deg[digraph.source(arc)];
     2001      --_deg[_digraph.source(arc)];
    24662002    }
    24672003
    24682004    virtual void erase(const std::vector<Arc>& arcs) {
    24692005      for (int i = 0; i < int(arcs.size()); ++i) {
    2470         --deg[digraph.source(arcs[i])];
     2006        --_deg[_digraph.source(arcs[i])];
    24712007      }
    24722008    }
    24732009
    24742010    virtual void build() {
    2475       for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
    2476         deg[it] = countOutArcs(digraph, it);
     2011      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
     2012        _deg[it] = countOutArcs(_digraph, it);
    24772013      }     
    24782014    }
    24792015
    24802016    virtual void clear() {
    2481       for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
    2482         deg[it] = 0;
     2017      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
     2018        _deg[it] = 0;
    24832019      }
    24842020    }
    24852021  private:
    24862022   
    2487     const _Digraph& digraph;
    2488     AutoNodeMap deg;
     2023    const Digraph& _digraph;
     2024    AutoNodeMap _deg;
    24892025  };
    24902026
     
    25012037  ///
    25022038  ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
    2503   ///digraph do not changed so frequently.
     2039  ///digraph is not changed so frequently.
    25042040  ///
    25052041  ///This class uses a self-adjusting binary search tree, Sleator's
     
    25212057    ::ItemNotifier::ObserverBase Parent;
    25222058
    2523     GRAPH_TYPEDEFS(typename G);
     2059    DIGRAPH_TYPEDEFS(typename G);
    25242060    typedef G Digraph;
    25252061
     
    28362372    Arc operator()(Node s, Node t) const
    28372373    {
    2838       Arc e = _head[s];
     2374      Arc a = _head[s];
    28392375      while (true) {
    2840         if (_g.target(e) == t) {
    2841           const_cast<DynArcLookUp&>(*this).splay(e);
    2842           return e;
    2843         } else if (t < _g.target(e)) {
    2844           if (_left[e] == INVALID) {
    2845             const_cast<DynArcLookUp&>(*this).splay(e);
     2376        if (_g.target(a) == t) {
     2377          const_cast<DynArcLookUp&>(*this).splay(a);
     2378          return a;
     2379        } else if (t < _g.target(a)) {
     2380          if (_left[a] == INVALID) {
     2381            const_cast<DynArcLookUp&>(*this).splay(a);
    28462382            return INVALID;
    28472383          } else {
    2848             e = _left[e];
     2384            a = _left[a];
    28492385          }
    28502386        } else  {
    2851           if (_right[e] == INVALID) {
    2852             const_cast<DynArcLookUp&>(*this).splay(e);
     2387          if (_right[a] == INVALID) {
     2388            const_cast<DynArcLookUp&>(*this).splay(a);
    28532389            return INVALID;
    28542390          } else {
    2855             e = _right[e];
     2391            a = _right[a];
    28562392          }
    28572393        }
     
    28702406    Arc findFirst(Node s, Node t) const
    28712407    {
    2872       Arc e = _head[s];
     2408      Arc a = _head[s];
    28732409      Arc r = INVALID;
    28742410      while (true) {
    2875         if (_g.target(e) < t) {
    2876           if (_right[e] == INVALID) {
    2877             const_cast<DynArcLookUp&>(*this).splay(e);
     2411        if (_g.target(a) < t) {
     2412          if (_right[a] == INVALID) {
     2413            const_cast<DynArcLookUp&>(*this).splay(a);
    28782414            return r;
    28792415          } else {
    2880             e = _right[e];
     2416            a = _right[a];
    28812417          }
    28822418        } else {
    2883           if (_g.target(e) == t) {
    2884             r = e;
     2419          if (_g.target(a) == t) {
     2420            r = a;
    28852421          }
    2886           if (_left[e] == INVALID) {
    2887             const_cast<DynArcLookUp&>(*this).splay(e);
     2422          if (_left[a] == INVALID) {
     2423            const_cast<DynArcLookUp&>(*this).splay(a);
    28882424            return r;
    28892425          } else {
    2890             e = _left[e];
     2426            a = _left[a];
    28912427          }
    28922428        }
     
    29072443    ///operation then the amorized time bound can not be guaranteed.
    29082444#ifdef DOXYGEN
    2909     Arc findNext(Node s, Node t, Arc e) const
     2445    Arc findNext(Node s, Node t, Arc a) const
    29102446#else
    2911     Arc findNext(Node, Node t, Arc e) const
     2447    Arc findNext(Node, Node t, Arc a) const
    29122448#endif
    29132449    {
    2914       if (_right[e] != INVALID) {
    2915         e = _right[e];
    2916         while (_left[e] != INVALID) {
    2917           e = _left[e];
     2450      if (_right[a] != INVALID) {
     2451        a = _right[a];
     2452        while (_left[a] != INVALID) {
     2453          a = _left[a];
    29182454        }
    2919         const_cast<DynArcLookUp&>(*this).splay(e);
     2455        const_cast<DynArcLookUp&>(*this).splay(a);
    29202456      } else {
    2921         while (_parent[e] != INVALID && _right[_parent[e]] ==  e) {
    2922           e = _parent[e];
     2457        while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
     2458          a = _parent[a];
    29232459        }
    2924         if (_parent[e] == INVALID) {
     2460        if (_parent[a] == INVALID) {
    29252461          return INVALID;
    29262462        } else {
    2927           e = _parent[e];
    2928           const_cast<DynArcLookUp&>(*this).splay(e);
     2463          a = _parent[a];
     2464          const_cast<DynArcLookUp&>(*this).splay(a);
    29292465        }
    29302466      }
    2931       if (_g.target(e) == t) return e;
     2467      if (_g.target(a) == t) return a;
    29322468      else return INVALID;   
    29332469    }
     
    29582494  {
    29592495  public:
    2960     GRAPH_TYPEDEFS(typename G);
     2496    DIGRAPH_TYPEDEFS(typename G);
    29612497    typedef G Digraph;
    29622498
     
    30752611    using ArcLookUp<G>::_head;
    30762612
    3077     GRAPH_TYPEDEFS(typename G);
     2613    DIGRAPH_TYPEDEFS(typename G);
    30782614    typedef G Digraph;
    30792615   
  • lemon/lgf_reader.h

    r127 r139  
    303303
    304304    typedef _Digraph Digraph;
    305     GRAPH_TYPEDEFS(typename Digraph);
     305    DIGRAPH_TYPEDEFS(typename Digraph);
    306306   
    307307  private:
  • lemon/lgf_writer.h

    r127 r139  
    238238
    239239    typedef _Digraph Digraph;
    240     GRAPH_TYPEDEFS(typename Digraph);
     240    DIGRAPH_TYPEDEFS(typename Digraph);
    241241   
    242242  private:
  • lemon/smart_graph.h

    r138 r139  
    7474   
    7575    typedef True NodeNumTag;
    76     typedef True ArcNumTag;
     76    typedef True EdgeNumTag;
    7777
    7878    int nodeNum() const { return nodes.size(); }
  • test/Makefile.am

    r119 r139  
    44noinst_HEADERS += \
    55        test/digraph_test.h \
     6        test/graph_utils_test.h \
    67        test/heap_test.h \
    78        test/map_test.h \
     
    1617        test/error_test \
    1718        test/graph_test \
     19        test/graph_utils_test \
    1820        test/kruskal_test \
    1921        test/maps_test \
     
    3537test_error_test_SOURCES = test/error_test.cc
    3638test_graph_test_SOURCES = test/graph_test.cc
     39test_graph_utils_test_SOURCES = test/graph_utils_test.cc
    3740# test_heap_test_SOURCES = test/heap_test.cc
    3841test_kruskal_test_SOURCES = test/kruskal_test.cc
Note: See TracChangeset for help on using the changeset viewer.