COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 209:765619b7cbb2 in lemon-1.2 for lemon/graph_utils.h


Ignore:
Timestamp:
07/13/08 20:51:02 (17 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Apply unify-sources.sh to the source tree

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/graph_utils.h

    r199 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    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, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, 
     49  ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
    5050  ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
    5151  ///
    … …  
    5353  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
    5454  ///macro.
    55 #define DIGRAPH_TYPEDEFS(Digraph)                                       \
    56   typedef Digraph::Node Node;                                           \
    57   typedef Digraph::NodeIt NodeIt;                                       \
    58   typedef Digraph::Arc Arc;                                             \
    59   typedef Digraph::ArcIt ArcIt;                                         \
    60   typedef Digraph::InArcIt InArcIt;                                     \
    61   typedef Digraph::OutArcIt OutArcIt;                                   \
    62   typedef Digraph::NodeMap<bool> BoolNodeMap;                           \
    63   typedef Digraph::NodeMap<int> IntNodeMap;                             \
    64   typedef Digraph::NodeMap<double> DoubleNodeMap;                       \
    65   typedef Digraph::ArcMap<bool> BoolArcMap;                             \
    66   typedef Digraph::ArcMap<int> IntArcMap;                               \
     55#define DIGRAPH_TYPEDEFS(Digraph)                                        \
     56  typedef Digraph::Node Node;                                                \
     57  typedef Digraph::NodeIt NodeIt;                                        \
     58  typedef Digraph::Arc Arc;                                                \
     59  typedef Digraph::ArcIt ArcIt;                                                \
     60  typedef Digraph::InArcIt InArcIt;                                        \
     61  typedef Digraph::OutArcIt OutArcIt;                                        \
     62  typedef Digraph::NodeMap<bool> BoolNodeMap;                                \
     63  typedef Digraph::NodeMap<int> IntNodeMap;                                \
     64  typedef Digraph::NodeMap<double> DoubleNodeMap;                        \
     65  typedef Digraph::ArcMap<bool> BoolArcMap;                                \
     66  typedef Digraph::ArcMap<int> IntArcMap;                                \
    6767  typedef Digraph::ArcMap<double> DoubleArcMap
    6868
    … …  
    7373  ///\note Use this macro, if the graph type is a dependent type,
    7474  ///ie. the graph type depend on a template parameter.
    75 #define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph)                              \
    76   typedef typename Digraph::Node Node;                                  \
    77   typedef typename Digraph::NodeIt NodeIt;                              \
    78   typedef typename Digraph::Arc Arc;                                    \
    79   typedef typename Digraph::ArcIt ArcIt;                                \
    80   typedef typename Digraph::InArcIt InArcIt;                            \
    81   typedef typename Digraph::OutArcIt OutArcIt;                          \
    82   typedef typename Digraph::template NodeMap<bool> BoolNodeMap;         \
    83   typedef typename Digraph::template NodeMap<int> IntNodeMap;           \
    84   typedef typename Digraph::template NodeMap<double> DoubleNodeMap;     \
    85   typedef typename Digraph::template ArcMap<bool> BoolArcMap;           \
    86   typedef typename Digraph::template ArcMap<int> IntArcMap;             \
     75#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph)                                \
     76  typedef typename Digraph::Node Node;                                        \
     77  typedef typename Digraph::NodeIt NodeIt;                                \
     78  typedef typename Digraph::Arc Arc;                                        \
     79  typedef typename Digraph::ArcIt ArcIt;                                \
     80  typedef typename Digraph::InArcIt InArcIt;                                \
     81  typedef typename Digraph::OutArcIt OutArcIt;                                \
     82  typedef typename Digraph::template NodeMap<bool> BoolNodeMap;                \
     83  typedef typename Digraph::template NodeMap<int> IntNodeMap;                \
     84  typedef typename Digraph::template NodeMap<double> DoubleNodeMap;        \
     85  typedef typename Digraph::template ArcMap<bool> BoolArcMap;                \
     86  typedef typename Digraph::template ArcMap<int> IntArcMap;                \
    8787  typedef typename Digraph::template ArcMap<double> DoubleArcMap
    88  
     88
    8989  ///Creates convenience typedefs for the graph types and iterators
    9090
    … …  
    9797  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
    9898  ///macro.
    99 #define GRAPH_TYPEDEFS(Graph)                                           \
    100   DIGRAPH_TYPEDEFS(Graph);                                              \
    101   typedef Graph::Edge Edge;                                             \
    102   typedef Graph::EdgeIt EdgeIt;                                         \
    103   typedef Graph::IncEdgeIt IncEdgeIt;                                   \
    104   typedef Graph::EdgeMap<bool> BoolEdgeMap;                             \
    105   typedef Graph::EdgeMap<int> IntEdgeMap;                               \
     99#define GRAPH_TYPEDEFS(Graph)                                                \
     100  DIGRAPH_TYPEDEFS(Graph);                                                \
     101  typedef Graph::Edge Edge;                                                \
     102  typedef Graph::EdgeIt EdgeIt;                                                \
     103  typedef Graph::IncEdgeIt IncEdgeIt;                                        \
     104  typedef Graph::EdgeMap<bool> BoolEdgeMap;                                \
     105  typedef Graph::EdgeMap<int> IntEdgeMap;                                \
    106106  typedef Graph::EdgeMap<double> DoubleEdgeMap
    107107
    … …  
    112112  ///\note Use this macro, if the graph type is a dependent type,
    113113  ///ie. the graph type depend on a template parameter.
    114 #define TEMPLATE_GRAPH_TYPEDEFS(Graph)                                  \
    115   TEMPLATE_DIGRAPH_TYPEDEFS(Graph);                                     \
    116   typedef typename Graph::Edge Edge;                                    \
    117   typedef typename Graph::EdgeIt EdgeIt;                                \
    118   typedef typename Graph::IncEdgeIt IncEdgeIt;                          \
    119   typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;           \
    120   typedef typename Graph::template EdgeMap<int> IntEdgeMap;             \
     114#define TEMPLATE_GRAPH_TYPEDEFS(Graph)                                        \
     115  TEMPLATE_DIGRAPH_TYPEDEFS(Graph);                                        \
     116  typedef typename Graph::Edge Edge;                                        \
     117  typedef typename Graph::EdgeIt EdgeIt;                                \
     118  typedef typename Graph::IncEdgeIt IncEdgeIt;                                \
     119  typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;                \
     120  typedef typename Graph::template EdgeMap<int> IntEdgeMap;                \
    121121  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
    122122
    … …  
    139139
    140140  namespace _graph_utils_bits {
    141    
     141
    142142    template <typename Graph, typename Enable = void>
    143143    struct CountNodesSelector {
    … …  
    149149    template <typename Graph>
    150150    struct CountNodesSelector<
    151       Graph, typename 
    152       enable_if<typename Graph::NodeNumTag, void>::type> 
     151      Graph, typename
     152      enable_if<typename Graph::NodeNumTag, void>::type>
    153153    {
    154154      static int count(const Graph &g) {
    155155        return g.nodeNum();
    156156      }
    157     };   
     157    };
    158158  }
    159159
    … …  
    164164  /// graph structures it is specialized to run in O(1).
    165165  ///
    166   /// If the graph contains a \e nodeNum() member function and a 
     166  /// If the graph contains a \e nodeNum() member function and a
    167167  /// \e NodeNumTag tag then this function calls directly the member
    168168  /// function to query the cardinality of the node set.
    … …  
    175175
    176176  namespace _graph_utils_bits {
    177    
     177
    178178    template <typename Graph, typename Enable = void>
    179179    struct CountArcsSelector {
    … …  
    185185    template <typename Graph>
    186186    struct CountArcsSelector<
    187       Graph, 
    188       typename enable_if<typename Graph::ArcNumTag, void>::type> 
     187      Graph,
     188      typename enable_if<typename Graph::ArcNumTag, void>::type>
    189189    {
    190190      static int count(const Graph &g) {
    191191        return g.arcNum();
    192192      }
    193     };   
     193    };
    194194  }
    195195
    … …  
    200200  /// graph structures it is specialized to run in O(1).
    201201  ///
    202   /// If the graph contains a \e arcNum() member function and a 
     202  /// If the graph contains a \e arcNum() member function and a
    203203  /// \e EdgeNumTag tag then this function calls directly the member
    204204  /// function to query the cardinality of the arc set.
    … …  
    210210  // Edge counting:
    211211  namespace _graph_utils_bits {
    212    
     212
    213213    template <typename Graph, typename Enable = void>
    214214    struct CountEdgesSelector {
    … …  
    220220    template <typename Graph>
    221221    struct CountEdgesSelector<
    222       Graph, 
    223       typename enable_if<typename Graph::EdgeNumTag, void>::type> 
     222      Graph,
     223      typename enable_if<typename Graph::EdgeNumTag, void>::type>
    224224    {
    225225      static int count(const Graph &g) {
    226226        return g.edgeNum();
    227227      }
    228     };   
     228    };
    229229  }
    230230
    … …  
    235235  /// graph structures it is specialized to run in O(1).
    236236  ///
    237   /// If the graph contains a \e edgeNum() member function and a 
     237  /// If the graph contains a \e edgeNum() member function and a
    238238  /// \e EdgeNumTag tag then this function calls directly the member
    239239  /// function to query the cardinality of the edge set.
    … …  
    257257  ///
    258258  /// This function counts the number of the out-arcs from node \c n
    259   /// in the graph. 
     259  /// in the graph.
    260260  template <typename Graph>
    261261  inline int countOutArcs(const Graph& _g,  const typename Graph::Node& _n) {
    … …  
    266266  ///
    267267  /// This function counts the number of the in-arcs to node \c n
    268   /// in the graph. 
     268  /// in the graph.
    269269  template <typename Graph>
    270270  inline int countInArcs(const Graph& _g,  const typename Graph::Node& _n) {
    … …  
    275275  ///
    276276  /// This function counts the number of the inc-edges to node \c n
    277   /// in the graph. 
     277  /// in the graph.
    278278  template <typename Graph>
    279279  inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) {
    … …  
    282282
    283283  namespace _graph_utils_bits {
    284    
     284
    285285    template <typename Graph, typename Enable = void>
    286286    struct FindArcSelector {
    … …  
    302302    template <typename Graph>
    303303    struct FindArcSelector<
    304       Graph, 
    305       typename enable_if<typename Graph::FindEdgeTag, void>::type> 
     304      Graph,
     305      typename enable_if<typename Graph::FindEdgeTag, void>::type>
    306306    {
    307307      typedef typename Graph::Node Node;
    … …  
    310310        return g.findArc(u, v, prev);
    311311      }
    312     };   
     312    };
    313313  }
    314314
    … …  
    334334  ///\sa ConArcIt
    335335  template <typename Graph>
    336   inline typename Graph::Arc 
     336  inline typename Graph::Arc
    337337  findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
    338338           typename Graph::Arc prev = INVALID) {
    … …  
    342342  /// \brief Iterator for iterating on arcs connected the same nodes.
    343343  ///
    344   /// Iterator for iterating on arcs connected the same nodes. It is 
     344  /// Iterator for iterating on arcs connected the same nodes. It is
    345345  /// higher level interface for the findArc() function. You can
    346346  /// use it the following way:
    … …  
    350350  /// }
    351351  ///\endcode
    352   /// 
     352  ///
    353353  ///\sa findArc()
    354354  ///\sa ArcLookUp
    … …  
    375375    /// \brief Constructor.
    376376    ///
    377     /// Construct a new ConArcIt which continues the iterating from 
     377    /// Construct a new ConArcIt which continues the iterating from
    378378    /// the \c e arc.
    379379    ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
    380    
     380
    381381    /// \brief Increment operator.
    382382    ///
    383383    /// It increments the iterator and gives back the next arc.
    384384    ConArcIt& operator++() {
    385       Parent::operator=(findArc(_graph, _graph.source(*this), 
    386                                 _graph.target(*this), *this));
     385      Parent::operator=(findArc(_graph, _graph.source(*this),
     386                                _graph.target(*this), *this));
    387387      return *this;
    388388    }
    … …  
    392392
    393393  namespace _graph_utils_bits {
    394    
     394
    395395    template <typename Graph, typename Enable = void>
    396396    struct FindEdgeSelector {
    … …  
    426426    template <typename Graph>
    427427    struct FindEdgeSelector<
    428       Graph, 
    429       typename enable_if<typename Graph::FindEdgeTag, void>::type> 
     428      Graph,
     429      typename enable_if<typename Graph::FindEdgeTag, void>::type>
    430430    {
    431431      typedef typename Graph::Node Node;
    … …  
    434434        return g.findEdge(u, v, prev);
    435435      }
    436     };   
     436    };
    437437  }
    438438
    … …  
    450450  /// Thus you can iterate through each arc from \c u to \c v as it follows.
    451451  ///\code
    452   /// for(Edge e = findEdge(g,u,v); e != INVALID; 
     452  /// for(Edge e = findEdge(g,u,v); e != INVALID;
    453453  ///     e = findEdge(g,u,v,e)) {
    454454  ///   ...
    … …  
    459459
    460460  template <typename Graph>
    461   inline typename Graph::Edge 
     461  inline typename Graph::Edge
    462462  findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
    463463            typename Graph::Edge p = INVALID) {
    … …  
    467467  /// \brief Iterator for iterating on edges connected the same nodes.
    468468  ///
    469   /// Iterator for iterating on edges connected the same nodes. It is 
     469  /// Iterator for iterating on edges connected the same nodes. It is
    470470  /// higher level interface for the findEdge() function. You can
    471471  /// use it the following way:
    … …  
    497497    /// \brief Constructor.
    498498    ///
    499     /// Construct a new ConEdgeIt which continues the iterating from 
     499    /// Construct a new ConEdgeIt which continues the iterating from
    500500    /// the \c e edge.
    501501    ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
    502    
     502
    503503    /// \brief Increment operator.
    504504    ///
    505505    /// It increments the iterator and gives back the next edge.
    506506    ConEdgeIt& operator++() {
    507       Parent::operator=(findEdge(_graph, _graph.u(*this), 
    508                                 _graph.v(*this), *this));
     507      Parent::operator=(findEdge(_graph, _graph.u(*this),
     508                                _graph.v(*this), *this));
    509509      return *this;
    510510    }
    … …  
    519519    public:
    520520      virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
    521      
     521
    522522      virtual ~MapCopyBase() {}
    523523    };
    524524
    525     template <typename Digraph, typename Item, typename RefMap, 
     525    template <typename Digraph, typename Item, typename RefMap,
    526526              typename ToMap, typename FromMap>
    527527    class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
    528528    public:
    529529
    530       MapCopy(ToMap& tmap, const FromMap& map) 
     530      MapCopy(ToMap& tmap, const FromMap& map)
    531531        : _tmap(tmap), _map(map) {}
    532      
     532
    533533      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
    534534        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
    … …  
    548548
    549549      ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
    550      
     550
    551551      virtual void copy(const Digraph&, const RefMap& refMap) {
    552552        _it = refMap[_item];
    … …  
    563563
    564564      RefCopy(Ref& map) : _map(map) {}
    565      
     565
    566566      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
    567567        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
    … …  
    575575    };
    576576
    577     template <typename Digraph, typename Item, typename RefMap, 
     577    template <typename Digraph, typename Item, typename RefMap,
    578578              typename CrossRef>
    579579    class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
    … …  
    581581
    582582      CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
    583      
     583
    584584      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
    585585        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
    … …  
    602602        }
    603603        for (typename From::ArcIt it(from); it != INVALID; ++it) {
    604           arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)], 
    605                                     nodeRefMap[from.target(it)]);
     604          arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
     605                                    nodeRefMap[from.target(it)]);
    606606        }
    607607      }
    … …  
    610610    template <typename Digraph>
    611611    struct DigraphCopySelector<
    612       Digraph, 
    613       typename enable_if<typename Digraph::BuildTag, void>::type> 
     612      Digraph,
     613      typename enable_if<typename Digraph::BuildTag, void>::type>
    614614    {
    615615      template <typename From, typename NodeRefMap, typename ArcRefMap>
    … …  
    629629        }
    630630        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
    631           edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)], 
    632                                       nodeRefMap[from.v(it)]);
     631          edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
     632                                      nodeRefMap[from.v(it)]);
    633633        }
    634634      }
    … …  
    637637    template <typename Graph>
    638638    struct GraphCopySelector<
    639       Graph, 
    640       typename enable_if<typename Graph::BuildTag, void>::type> 
     639      Graph,
     640      typename enable_if<typename Graph::BuildTag, void>::type>
    641641    {
    642642      template <typename From, typename NodeRefMap, typename EdgeRefMap>
    … …  
    698698    typedef typename From::template NodeMap<TNode> NodeRefMap;
    699699    typedef typename From::template ArcMap<TArc> ArcRefMap;
    700    
    701    
    702   public: 
     700
     701
     702  public:
    703703
    704704
    … …  
    707707    /// It copies the content of the \c _from digraph into the
    708708    /// \c _to digraph.
    709     DigraphCopy(To& to, const From& from) 
     709    DigraphCopy(To& to, const From& from)
    710710      : _from(from), _to(to) {}
    711711
    … …  
    731731    template <typename NodeRef>
    732732    DigraphCopy& nodeRef(NodeRef& map) {
    733       _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node, 
    734                            NodeRefMap, NodeRef>(map));
     733      _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
     734                           NodeRefMap, NodeRef>(map));
    735735      return *this;
    736736    }
    … …  
    745745    DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
    746746      _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
    747                            NodeRefMap, NodeCrossRef>(map));
     747                           NodeRefMap, NodeCrossRef>(map));
    748748      return *this;
    749749    }
    … …  
    756756    template <typename ToMap, typename FromMap>
    757757    DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
    758       _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node, 
    759                            NodeRefMap, ToMap, FromMap>(tmap, map));
     758      _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
     759                           NodeRefMap, ToMap, FromMap>(tmap, map));
    760760      return *this;
    761761    }
    … …  
    765765    /// Make a copy of the given node.
    766766    DigraphCopy& node(TNode& tnode, const Node& snode) {
    767       _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node, 
    768                            NodeRefMap, TNode>(tnode, snode));
     767      _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
     768                           NodeRefMap, TNode>(tnode, snode));
    769769      return *this;
    770770    }
    … …  
    775775    template <typename ArcRef>
    776776    DigraphCopy& arcRef(ArcRef& map) {
    777       _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc, 
    778                           ArcRefMap, ArcRef>(map));
     777      _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
     778                          ArcRefMap, ArcRef>(map));
    779779      return *this;
    780780    }
    … …  
    787787    DigraphCopy& arcCrossRef(ArcCrossRef& map) {
    788788      _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
    789                           ArcRefMap, ArcCrossRef>(map));
     789                          ArcRefMap, ArcCrossRef>(map));
    790790      return *this;
    791791    }
    … …  
    793793    /// \brief Make copy of the given map.
    794794    ///
    795     /// Makes copy of the given map for the newly created digraph. 
     795    /// Makes copy of the given map for the newly created digraph.
    796796    /// The new map's key type is the to digraph's arc type,
    797797    /// and the copied map's key type is the from digraph's arc
    798     /// type. 
     798    /// type.
    799799    template <typename ToMap, typename FromMap>
    800800    DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
    801       _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc, 
    802                           ArcRefMap, ToMap, FromMap>(tmap, map));
     801      _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
     802                          ArcRefMap, ToMap, FromMap>(tmap, map));
    803803      return *this;
    804804    }
    … …  
    808808    /// Make a copy of the given arc.
    809809    DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
    810       _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc, 
    811                           ArcRefMap, TArc>(tarc, sarc));
     810      _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
     811                          ArcRefMap, TArc>(tarc, sarc));
    812812      return *this;
    813813    }
    … …  
    826826      for (int i = 0; i < int(_arc_maps.size()); ++i) {
    827827        _arc_maps[i]->copy(_from, arcRefMap);
    828       }     
     828      }
    829829    }
    830830
    … …  
    835835    To& _to;
    836836
    837     std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* > 
     837    std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
    838838    _node_maps;
    839839
    840     std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* > 
     840    std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
    841841    _arc_maps;
    842842
    … …  
    851851  /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
    852852  ///\endcode
    853   /// 
     853  ///
    854854  /// After the copy the \c nr map will contain the mapping from the
    855855  /// nodes of the \c from digraph to the nodes of the \c to digraph and
    … …  
    857857  /// to the arcs of the \c from digraph.
    858858  ///
    859   /// \see DigraphCopy 
     859  /// \see DigraphCopy
    860860  template <typename To, typename From>
    861861  DigraphCopy<To, From> copyDigraph(To& to, const From& from) {
    … …  
    918918    struct ArcRefMap {
    919919      ArcRefMap(const To& to, const From& from,
    920                 const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
    921         : _to(to), _from(from), 
     920                const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
     921        : _to(to), _from(from),
    922922          _edge_ref(edge_ref), _node_ref(node_ref) {}
    923923
    … …  
    927927      Value operator[](const Key& key) const {
    928928        bool forward = _from.u(key) != _from.v(key) ?
    929           _node_ref[_from.source(key)] ==
    930           _to.source(_to.direct(_edge_ref[key], true)) :
    931           _from.direction(key);
    932         return _to.direct(_edge_ref[key], forward);
    933       }
    934      
     929          _node_ref[_from.source(key)] ==
     930          _to.source(_to.direct(_edge_ref[key], true)) :
     931          _from.direction(key);
     932        return _to.direct(_edge_ref[key], forward);
     933      }
     934
    935935      const To& _to;
    936936      const From& _from;
    … …  
    939939    };
    940940
    941    
    942   public: 
     941
     942  public:
    943943
    944944
    … …  
    947947    /// It copies the content of the \c _from graph into the
    948948    /// \c _to graph.
    949     GraphCopy(To& to, const From& from) 
     949    GraphCopy(To& to, const From& from)
    950950      : _from(from), _to(to) {}
    951951
    … …  
    971971    template <typename NodeRef>
    972972    GraphCopy& nodeRef(NodeRef& map) {
    973       _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node, 
    974                            NodeRefMap, NodeRef>(map));
     973      _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
     974                           NodeRefMap, NodeRef>(map));
    975975      return *this;
    976976    }
    … …  
    983983    GraphCopy& nodeCrossRef(NodeCrossRef& map) {
    984984      _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
    985                            NodeRefMap, NodeCrossRef>(map));
     985                           NodeRefMap, NodeCrossRef>(map));
    986986      return *this;
    987987    }
    … …  
    989989    /// \brief Make copy of the given map.
    990990    ///
    991     /// Makes copy of the given map for the newly created graph. 
     991    /// Makes copy of the given map for the newly created graph.
    992992    /// The new map's key type is the to graph's node type,
    993993    /// and the copied map's key type is the from graph's node
    994     /// type. 
     994    /// type.
    995995    template <typename ToMap, typename FromMap>
    996996    GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
    997       _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node, 
    998                            NodeRefMap, ToMap, FromMap>(tmap, map));
     997      _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
     998                           NodeRefMap, ToMap, FromMap>(tmap, map));
    999999      return *this;
    10001000    }
    … …  
    10041004    /// Make a copy of the given node.
    10051005    GraphCopy& node(TNode& tnode, const Node& snode) {
    1006       _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node, 
    1007                            NodeRefMap, TNode>(tnode, snode));
     1006      _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
     1007                           NodeRefMap, TNode>(tnode, snode));
    10081008      return *this;
    10091009    }
    … …  
    10141014    template <typename ArcRef>
    10151015    GraphCopy& arcRef(ArcRef& map) {
    1016       _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc, 
    1017                           ArcRefMap, ArcRef>(map));
     1016      _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
     1017                          ArcRefMap, ArcRef>(map));
    10181018      return *this;
    10191019    }
    … …  
    10261026    GraphCopy& arcCrossRef(ArcCrossRef& map) {
    10271027      _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
    1028                           ArcRefMap, ArcCrossRef>(map));
     1028                          ArcRefMap, ArcCrossRef>(map));
    10291029      return *this;
    10301030    }
    … …  
    10321032    /// \brief Make copy of the given map.
    10331033    ///
    1034     /// Makes copy of the given map for the newly created graph. 
     1034    /// Makes copy of the given map for the newly created graph.
    10351035    /// The new map's key type is the to graph's arc type,
    10361036    /// and the copied map's key type is the from graph's arc
    1037     /// type. 
     1037    /// type.
    10381038    template <typename ToMap, typename FromMap>
    10391039    GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
    1040       _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc, 
    1041                           ArcRefMap, ToMap, FromMap>(tmap, map));
     1040      _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
     1041                          ArcRefMap, ToMap, FromMap>(tmap, map));
    10421042      return *this;
    10431043    }
    … …  
    10471047    /// Make a copy of the given arc.
    10481048    GraphCopy& arc(TArc& tarc, const Arc& sarc) {
    1049       _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc, 
    1050                           ArcRefMap, TArc>(tarc, sarc));
     1049      _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
     1050                          ArcRefMap, TArc>(tarc, sarc));
    10511051      return *this;
    10521052    }
    … …  
    10571057    template <typename EdgeRef>
    10581058    GraphCopy& edgeRef(EdgeRef& map) {
    1059       _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge, 
    1060                            EdgeRefMap, EdgeRef>(map));
     1059      _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge,
     1060                           EdgeRefMap, EdgeRef>(map));
    10611061      return *this;
    10621062    }
    … …  
    10681068    template <typename EdgeCrossRef>
    10691069    GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
    1070       _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, 
    1071                            Edge, EdgeRefMap, EdgeCrossRef>(map));
     1070      _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From,
     1071                           Edge, EdgeRefMap, EdgeCrossRef>(map));
    10721072      return *this;
    10731073    }
    … …  
    10751075    /// \brief Make copy of the given map.
    10761076    ///
    1077     /// Makes copy of the given map for the newly created graph. 
     1077    /// Makes copy of the given map for the newly created graph.
    10781078    /// The new map's key type is the to graph's edge type,
    10791079    /// and the copied map's key type is the from graph's edge
    1080     /// type. 
     1080    /// type.
    10811081    template <typename ToMap, typename FromMap>
    10821082    GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
    1083       _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge, 
    1084                            EdgeRefMap, ToMap, FromMap>(tmap, map));
     1083      _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge,
     1084                           EdgeRefMap, ToMap, FromMap>(tmap, map));
    10851085      return *this;
    10861086    }
    … …  
    10901090    /// Make a copy of the given edge.
    10911091    GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
    1092       _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge, 
    1093                            EdgeRefMap, TEdge>(tedge, sedge));
     1092      _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
     1093                           EdgeRefMap, TEdge>(tedge, sedge));
    10941094      return *this;
    10951095    }
    … …  
    11161116
    11171117  private:
    1118    
     1118
    11191119    const From& _from;
    11201120    To& _to;
    11211121
    1122     std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* > 
     1122    std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
    11231123    _node_maps;
    11241124
    1125     std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* > 
     1125    std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
    11261126    _arc_maps;
    11271127
    1128     std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* > 
     1128    std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
    11291129    _edge_maps;
    11301130
    … …  
    11391139  /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
    11401140  ///\endcode
    1141   /// 
     1141  ///
    11421142  /// After the copy the \c nr map will contain the mapping from the
    11431143  /// nodes of the \c from graph to the nodes of the \c to graph and
    … …  
    11451145  /// to the arcs of the \c from graph.
    11461146  ///
    1147   /// \see GraphCopy 
     1147  /// \see GraphCopy
    11481148  template <typename To, typename From>
    1149   GraphCopy<To, From> 
     1149  GraphCopy<To, From>
    11501150  copyGraph(To& to, const From& from) {
    11511151    return GraphCopy<To, From>(to, from);
    … …  
    12151215      ///
    12161216      /// Gives back the given item from its id.
    1217       /// 
     1217      ///
    12181218      Item operator[](int id) const { return _graph->fromId(id, Item());}
    12191219
    … …  
    12251225    ///
    12261226    /// Gives back the inverse of the IdMap.
    1227     InverseMap inverse() const { return InverseMap(*_graph);} 
     1227    InverseMap inverse() const { return InverseMap(*_graph);}
    12281228
    12291229  };
    12301230
    1231  
     1231
    12321232  /// \brief General invertable graph-map type.
    12331233
    1234   /// This type provides simple invertable graph-maps. 
    1235   /// The InvertableMap wraps an arbitrary ReadWriteMap 
     1234  /// This type provides simple invertable graph-maps.
     1235  /// The InvertableMap wraps an arbitrary ReadWriteMap
    12361236  /// and if a key is set to a new value then store it
    12371237  /// in the inverse map.
    … …  
    12481248  class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
    12491249  private:
    1250    
     1250
    12511251    typedef DefaultMap<_Graph, _Item, _Value> Map;
    12521252    typedef _Graph Graph;
    12531253
    12541254    typedef std::map<_Value, _Item> Container;
    1255     Container _inv_map;   
     1255    Container _inv_map;
    12561256
    12571257  public:
    1258  
     1258
    12591259    /// The key type of InvertableMap (Node, Arc, Edge).
    12601260    typedef typename Map::Key Key;
    … …  
    12681268    /// Construct a new InvertableMap for the graph.
    12691269    ///
    1270     explicit InvertableMap(const Graph& graph) : Map(graph) {} 
     1270    explicit InvertableMap(const Graph& graph) : Map(graph) {}
    12711271
    12721272    /// \brief Forward iterator for values.
    … …  
    12761276    /// be accessed in the [beginValue, endValue) range.
    12771277    ///
    1278     class ValueIterator 
     1278    class ValueIterator
    12791279      : public std::iterator<std::forward_iterator_tag, Value> {
    12801280      friend class InvertableMap;
    12811281    private:
    1282       ValueIterator(typename Container::const_iterator _it) 
     1282      ValueIterator(typename Container::const_iterator _it)
    12831283        : it(_it) {}
    12841284    public:
    1285      
     1285
    12861286      ValueIterator() {}
    12871287
    12881288      ValueIterator& operator++() { ++it; return *this; }
    1289       ValueIterator operator++(int) { 
    1290         ValueIterator tmp(*this); 
     1289      ValueIterator operator++(int) {
     1290        ValueIterator tmp(*this);
    12911291        operator++();
    1292         return tmp; 
     1292        return tmp;
    12931293      }
    12941294
    … …  
    12981298      bool operator==(ValueIterator jt) const { return it == jt.it; }
    12991299      bool operator!=(ValueIterator jt) const { return it != jt.it; }
    1300      
     1300
    13011301    private:
    13021302      typename Container::const_iterator it;
    … …  
    13051305    /// \brief Returns an iterator to the first value.
    13061306    ///
    1307     /// Returns an stl compatible iterator to the 
     1307    /// Returns an stl compatible iterator to the
    13081308    /// first value of the map. The values of the
    13091309    /// map can be accessed in the [beginValue, endValue)
    … …  
    13151315    /// \brief Returns an iterator after the last value.
    13161316    ///
    1317     /// Returns an stl compatible iterator after the 
     1317    /// Returns an stl compatible iterator after the
    13181318    /// last value of the map. The values of the
    13191319    /// map can be accessed in the [beginValue, endValue)
    … …  
    13221322      return ValueIterator(_inv_map.end());
    13231323    }
    1324    
     1324
    13251325    /// \brief The setter function of the map.
    13261326    ///
    … …  
    13301330      typename Container::iterator it = _inv_map.find(oldval);
    13311331      if (it != _inv_map.end() && it->second == key) {
    1332         _inv_map.erase(it);
    1333       }     
     1332        _inv_map.erase(it);
     1333      }
    13341334      _inv_map.insert(make_pair(val, key));
    13351335      Map::set(key, val);
    … …  
    13391339    ///
    13401340    /// It gives back the value associated with the key.
    1341     typename MapTraits<Map>::ConstReturnValue 
     1341    typename MapTraits<Map>::ConstReturnValue
    13421342    operator[](const Key& key) const {
    13431343      return Map::operator[](key);
    … …  
    13621362      typename Container::iterator it = _inv_map.find(val);
    13631363      if (it != _inv_map.end() && it->second == key) {
    1364         _inv_map.erase(it);
     1364        _inv_map.erase(it);
    13651365      }
    13661366      Map::erase(key);
    … …  
    13731373    virtual void erase(const std::vector<Key>& keys) {
    13741374      for (int i = 0; i < int(keys.size()); ++i) {
    1375         Value val = Map::operator[](keys[i]);
    1376         typename Container::iterator it = _inv_map.find(val);
    1377         if (it != _inv_map.end() && it->second == keys[i]) {
    1378           _inv_map.erase(it);
    1379         }
     1375        Value val = Map::operator[](keys[i]);
     1376        typename Container::iterator it = _inv_map.find(val);
     1377        if (it != _inv_map.end() && it->second == keys[i]) {
     1378          _inv_map.erase(it);
     1379        }
    13801380      }
    13811381      Map::erase(keys);
    … …  
    13961396    ///
    13971397    /// The inverse of this map. The subscript operator of the map
    1398     /// gives back always the item what was last assigned to the value. 
     1398    /// gives back always the item what was last assigned to the value.
    13991399    class InverseMap {
    14001400    public:
    … …  
    14021402      ///
    14031403      /// Constructor of the InverseMap.
    1404       explicit InverseMap(const InvertableMap& inverted) 
     1404      explicit InverseMap(const InvertableMap& inverted)
    14051405        : _inverted(inverted) {}
    14061406
    … …  
    14081408      typedef typename InvertableMap::Key Value;
    14091409      /// The key type of the InverseMap.
    1410       typedef typename InvertableMap::Value Key; 
    1411 
    1412       /// \brief Subscript operator. 
     1410      typedef typename InvertableMap::Value Key;
     1411
     1412      /// \brief Subscript operator.
    14131413      ///
    1414       /// Subscript operator. It gives back always the item 
     1414      /// Subscript operator. It gives back always the item
    14151415      /// what was last assigned to the value.
    14161416      Value operator[](const Key& key) const {
    1417         return _inverted(key);
    1418       }
    1419      
     1417        return _inverted(key);
     1418      }
     1419
    14201420    private:
    14211421      const InvertableMap& _inverted;
    … …  
    14271427    InverseMap inverse() const {
    14281428      return InverseMap(*this);
    1429     } 
    1430 
    1431 
    1432    
     1429    }
     1430
     1431
     1432
    14331433  };
    14341434
    1435   /// \brief Provides a mutable, continuous and unique descriptor for each 
     1435  /// \brief Provides a mutable, continuous and unique descriptor for each
    14361436  /// item in the graph.
    14371437  ///
    … …  
    14461446  ///
    14471447  /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
    1448   /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or 
     1448  /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
    14491449  /// Edge.
    14501450  template <typename _Graph, typename _Item>
    … …  
    14681468    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
    14691469      Item it;
    1470       const typename Map::Notifier* nf = Map::notifier(); 
     1470      const typename Map::Notifier* nf = Map::notifier();
    14711471      for (nf->first(it); it != INVALID; nf->next(it)) {
    1472         Map::set(it, _inv_map.size());
    1473         _inv_map.push_back(it);
    1474       }     
     1472        Map::set(it, _inv_map.size());
     1473        _inv_map.push_back(it);
     1474      }
    14751475    }
    14761476
    … …  
    14941494      Map::add(items);
    14951495      for (int i = 0; i < int(items.size()); ++i) {
    1496         Map::set(items[i], _inv_map.size());
    1497         _inv_map.push_back(items[i]);
     1496        Map::set(items[i], _inv_map.size());
     1497        _inv_map.push_back(items[i]);
    14981498      }
    14991499    }
    … …  
    15161516    virtual void erase(const std::vector<Item>& items) {
    15171517      for (int i = 0; i < int(items.size()); ++i) {
    1518         Map::set(_inv_map.back(), Map::operator[](items[i]));
    1519         _inv_map[Map::operator[](items[i])] = _inv_map.back();
    1520         _inv_map.pop_back();
     1518        Map::set(_inv_map.back(), Map::operator[](items[i]));
     1519        _inv_map[Map::operator[](items[i])] = _inv_map.back();
     1520        _inv_map.pop_back();
    15211521      }
    15221522      Map::erase(items);
    … …  
    15301530      Map::build();
    15311531      Item it;
    1532       const typename Map::Notifier* nf = Map::notifier(); 
     1532      const typename Map::Notifier* nf = Map::notifier();
    15331533      for (nf->first(it); it != INVALID; nf->next(it)) {
    1534         Map::set(it, _inv_map.size());
    1535         _inv_map.push_back(it);
    1536       }     
    1537     }
    1538    
     1534        Map::set(it, _inv_map.size());
     1535        _inv_map.push_back(it);
     1536      }
     1537    }
     1538
    15391539    /// \brief Clear the keys from the map.
    15401540    ///
    … …  
    15801580      return _inv_map[id];
    15811581    }
    1582    
     1582
    15831583  private:
    15841584
    … …  
    15951595      ///
    15961596      /// Constructor of the InverseMap.
    1597       explicit InverseMap(const DescriptorMap& inverted) 
    1598         : _inverted(inverted) {}
     1597      explicit InverseMap(const DescriptorMap& inverted)
     1598        : _inverted(inverted) {}
    15991599
    16001600
    … …  
    16021602      typedef typename DescriptorMap::Key Value;
    16031603      /// The key type of the InverseMap.
    1604       typedef typename DescriptorMap::Value Key; 
    1605 
    1606       /// \brief Subscript operator. 
     1604      typedef typename DescriptorMap::Value Key;
     1605
     1606      /// \brief Subscript operator.
    16071607      ///
    1608       /// Subscript operator. It gives back the item 
     1608      /// Subscript operator. It gives back the item
    16091609      /// that the descriptor belongs to currently.
    16101610      Value operator[](const Key& key) const {
    1611         return _inverted(key);
     1611        return _inverted(key);
    16121612      }
    16131613
    … …  
    16161616      /// Returns the size of the map.
    16171617      unsigned int size() const {
    1618         return _inverted.size();
    1619       }
    1620      
     1618        return _inverted.size();
     1619      }
     1620
    16211621    private:
    16221622      const DescriptorMap& _inverted;
    … …  
    16331633  /// \brief Returns the source of the given arc.
    16341634  ///
    1635   /// The SourceMap gives back the source Node of the given arc. 
     1635  /// The SourceMap gives back the source Node of the given arc.
    16361636  /// \see TargetMap
    16371637  template <typename Digraph>
    … …  
    16511651    ///
    16521652    /// The subscript operator.
    1653     /// \param arc The arc 
    1654     /// \return The source of the arc 
     1653    /// \param arc The arc
     1654    /// \return The source of the arc
    16551655    Value operator[](const Key& arc) const {
    16561656      return _digraph.source(arc);
    … …  
    16681668  inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
    16691669    return SourceMap<Digraph>(digraph);
    1670   } 
     1670  }
    16711671
    16721672  /// \brief Returns the target of the given arc.
    16731673  ///
    1674   /// The TargetMap gives back the target Node of the given arc. 
     1674  /// The TargetMap gives back the target Node of the given arc.
    16751675  /// \see SourceMap
    16761676  template <typename Digraph>
    … …  
    16901690    ///
    16911691    /// The subscript operator.
    1692     /// \param e The arc 
    1693     /// \return The target of the arc 
     1692    /// \param e The arc
     1693    /// \return The target of the arc
    16941694    Value operator[](const Key& e) const {
    16951695      return _digraph.target(e);
    … …  
    17291729    ///
    17301730    /// The subscript operator.
    1731     /// \param key An edge 
    1732     /// \return The "forward" directed arc view of edge 
     1731    /// \param key An edge
     1732    /// \return The "forward" directed arc view of edge
    17331733    Value operator[](const Key& key) const {
    17341734      return _graph.direct(key, true);
    … …  
    17681768    ///
    17691769    /// The subscript operator.
    1770     /// \param key An edge 
    1771     /// \return The "backward" directed arc view of edge 
     1770    /// \param key An edge
     1771    /// \return The "backward" directed arc view of edge
    17721772    Value operator[](const Key& key) const {
    17731773      return _graph.direct(key, false);
    … …  
    18011801    ///
    18021802    /// Contructor of the map
    1803     explicit PotentialDifferenceMap(const Digraph& digraph, 
    1804                                     const NodeMap& potential) 
     1803    explicit PotentialDifferenceMap(const Digraph& digraph,
     1804                                    const NodeMap& potential)
    18051805      : _digraph(digraph), _potential(potential) {}
    18061806
    … …  
    18091809    /// Const subscription operator
    18101810    Value operator[](const Key& arc) const {
    1811       return _potential[_digraph.target(arc)] - 
    1812         _potential[_digraph.source(arc)];
     1811      return _potential[_digraph.target(arc)] -
     1812        _potential[_digraph.source(arc)];
    18131813    }
    18141814
    … …  
    18231823  /// \relates PotentialDifferenceMap
    18241824  template <typename Digraph, typename NodeMap>
    1825   PotentialDifferenceMap<Digraph, NodeMap> 
     1825  PotentialDifferenceMap<Digraph, NodeMap>
    18261826  potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
    18271827    return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
    … …  
    18461846
    18471847  template <typename _Digraph>
    1848   class InDegMap 
     1848  class InDegMap
    18491849    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
    18501850      ::ItemNotifier::ObserverBase {
    18511851
    18521852  public:
    1853    
     1853
    18541854    typedef _Digraph Digraph;
    18551855    typedef int Value;
    … …  
    18671867
    18681868      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
    1869      
     1869
    18701870      virtual void add(const Key& key) {
    1871         Parent::add(key);
    1872         Parent::set(key, 0);
     1871        Parent::add(key);
     1872        Parent::set(key, 0);
    18731873      }
    18741874
    18751875      virtual void add(const std::vector<Key>& keys) {
    1876         Parent::add(keys);
    1877         for (int i = 0; i < int(keys.size()); ++i) {
    1878           Parent::set(keys[i], 0);
    1879         }
     1876        Parent::add(keys);
     1877        for (int i = 0; i < int(keys.size()); ++i) {
     1878          Parent::set(keys[i], 0);
     1879        }
    18801880      }
    18811881
    18821882      virtual void build() {
    1883         Parent::build();
    1884         Key it;
    1885         typename Parent::Notifier* nf = Parent::notifier();
    1886         for (nf->first(it); it != INVALID; nf->next(it)) {
    1887           Parent::set(it, 0);
    1888         }
     1883        Parent::build();
     1884        Key it;
     1885        typename Parent::Notifier* nf = Parent::notifier();
     1886        for (nf->first(it); it != INVALID; nf->next(it)) {
     1887          Parent::set(it, 0);
     1888        }
    18891889      }
    18901890    };
    … …  
    18951895    ///
    18961896    /// Constructor for creating in-degree map.
    1897     explicit InDegMap(const Digraph& digraph) 
     1897    explicit InDegMap(const Digraph& digraph)
    18981898      : _digraph(digraph), _deg(digraph) {
    18991899      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
    1900      
     1900
    19011901      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
    1902         _deg[it] = countInArcs(_digraph, it);
    1903       }
    1904     }
    1905    
     1902        _deg[it] = countInArcs(_digraph, it);
     1903      }
     1904    }
     1905
    19061906    /// Gives back the in-degree of a Node.
    19071907    int operator[](const Key& key) const {
    … …  
    19101910
    19111911  protected:
    1912    
     1912
    19131913    typedef typename Digraph::Arc Arc;
    19141914
    … …  
    19351935    virtual void build() {
    19361936      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
    1937         _deg[it] = countInArcs(_digraph, it);
    1938       }     
     1937        _deg[it] = countInArcs(_digraph, it);
     1938      }
    19391939    }
    19401940
    19411941    virtual void clear() {
    19421942      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
    1943         _deg[it] = 0;
     1943        _deg[it] = 0;
    19441944      }
    19451945    }
    19461946  private:
    1947    
     1947
    19481948    const Digraph& _digraph;
    19491949    AutoNodeMap _deg;
    … …  
    19681968
    19691969  template <typename _Digraph>
    1970   class OutDegMap 
     1970  class OutDegMap
    19711971    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
    19721972      ::ItemNotifier::ObserverBase {
    19731973
    19741974  public:
    1975    
     1975
    19761976    typedef _Digraph Digraph;
    19771977    typedef int Value;
    … …  
    19891989
    19901990      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
    1991      
     1991
    19921992      virtual void add(const Key& key) {
    1993         Parent::add(key);
    1994         Parent::set(key, 0);
     1993        Parent::add(key);
     1994        Parent::set(key, 0);
    19951995      }
    19961996      virtual void add(const std::vector<Key>& keys) {
    1997         Parent::add(keys);
    1998         for (int i = 0; i < int(keys.size()); ++i) {
    1999           Parent::set(keys[i], 0);
    2000         }
     1997        Parent::add(keys);
     1998        for (int i = 0; i < int(keys.size()); ++i) {
     1999          Parent::set(keys[i], 0);
     2000        }
    20012001      }
    20022002      virtual void build() {
    2003         Parent::build();
    2004         Key it;
    2005         typename Parent::Notifier* nf = Parent::notifier();
    2006         for (nf->first(it); it != INVALID; nf->next(it)) {
    2007           Parent::set(it, 0);
    2008         }
     2003        Parent::build();
     2004        Key it;
     2005        typename Parent::Notifier* nf = Parent::notifier();
     2006        for (nf->first(it); it != INVALID; nf->next(it)) {
     2007          Parent::set(it, 0);
     2008        }
    20092009      }
    20102010    };
    … …  
    20152015    ///
    20162016    /// Constructor for creating out-degree map.
    2017     explicit OutDegMap(const Digraph& digraph) 
     2017    explicit OutDegMap(const Digraph& digraph)
    20182018      : _digraph(digraph), _deg(digraph) {
    20192019      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
    2020      
     2020
    20212021      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
    2022         _deg[it] = countOutArcs(_digraph, it);
     2022        _deg[it] = countOutArcs(_digraph, it);
    20232023      }
    20242024    }
    … …  
    20302030
    20312031  protected:
    2032    
     2032
    20332033    typedef typename Digraph::Arc Arc;
    20342034
    … …  
    20552055    virtual void build() {
    20562056      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
    2057         _deg[it] = countOutArcs(_digraph, it);
    2058       }     
     2057        _deg[it] = countOutArcs(_digraph, it);
     2058      }
    20592059    }
    20602060
    20612061    virtual void clear() {
    20622062      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
    2063         _deg[it] = 0;
     2063        _deg[it] = 0;
    20642064      }
    20652065    }
    20662066  private:
    2067    
     2067
    20682068    const Digraph& _digraph;
    20692069    AutoNodeMap _deg;
    … …  
    20722072
    20732073  ///Dynamic arc look up between given endpoints.
    2074  
     2074
    20752075  ///\ingroup gutils
    20762076  ///Using this class, you can find an arc in a digraph from a given
    … …  
    20902090  ///queries.
    20912091  ///
    2092   ///\tparam G The type of the underlying digraph. 
    2093   ///
    2094   ///\sa ArcLookUp 
    2095   ///\sa AllArcLookUp 
     2092  ///\tparam G The type of the underlying digraph.
     2093  ///
     2094  ///\sa ArcLookUp
     2095  ///\sa AllArcLookUp
    20962096  template<class G>
    2097   class DynArcLookUp 
     2097  class DynArcLookUp
    20982098    : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
    20992099  {
    … …  
    21132113
    21142114      AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
    2115      
     2115
    21162116      virtual void add(const Node& node) {
    2117         Parent::add(node);
    2118         Parent::set(node, INVALID);
     2117        Parent::add(node);
     2118        Parent::set(node, INVALID);
    21192119      }
    21202120
    21212121      virtual void add(const std::vector<Node>& nodes) {
    2122         Parent::add(nodes);
    2123         for (int i = 0; i < int(nodes.size()); ++i) {
    2124           Parent::set(nodes[i], INVALID);
    2125         }
     2122        Parent::add(nodes);
     2123        for (int i = 0; i < int(nodes.size()); ++i) {
     2124          Parent::set(nodes[i], INVALID);
     2125        }
    21262126      }
    21272127
    21282128      virtual void build() {
    2129         Parent::build();
    2130         Node it;
    2131         typename Parent::Notifier* nf = Parent::notifier();
    2132         for (nf->first(it); it != INVALID; nf->next(it)) {
    2133           Parent::set(it, INVALID);
    2134         }
     2129        Parent::build();
     2130        Node it;
     2131        typename Parent::Notifier* nf = Parent::notifier();
     2132        for (nf->first(it); it != INVALID; nf->next(it)) {
     2133          Parent::set(it, INVALID);
     2134        }
    21352135      }
    21362136    };
    … …  
    21412141    typename Digraph::template ArcMap<Arc> _left;
    21422142    typename Digraph::template ArcMap<Arc> _right;
    2143    
     2143
    21442144    class ArcLess {
    21452145      const Digraph &g;
    21462146    public:
    21472147      ArcLess(const Digraph &_g) : g(_g) {}
    2148       bool operator()(Arc a,Arc b) const 
     2148      bool operator()(Arc a,Arc b) const
    21492149      {
    2150         return g.target(a)<g.target(b);
    2151       }
    2152     };
    2153    
     2150        return g.target(a)<g.target(b);
     2151      }
     2152    };
     2153
    21542154  public:
    2155    
     2155
    21562156    ///Constructor
    21572157
    … …  
    21592159    ///
    21602160    ///It builds up the search database.
    2161     DynArcLookUp(const Digraph &g) 
    2162       : _g(g),_head(g),_parent(g),_left(g),_right(g) 
    2163     { 
     2161    DynArcLookUp(const Digraph &g)
     2162      : _g(g),_head(g),_parent(g),_left(g),_right(g)
     2163    {
    21642164      Parent::attach(_g.notifier(typename Digraph::Arc()));
    2165       refresh(); 
    2166     }
    2167    
     2165      refresh();
     2166    }
     2167
    21682168  protected:
    21692169
    … …  
    21742174    virtual void add(const std::vector<Arc>& arcs) {
    21752175      for (int i = 0; i < int(arcs.size()); ++i) {
    2176         insert(arcs[i]);
     2176        insert(arcs[i]);
    21772177      }
    21782178    }
    … …  
    21842184    virtual void erase(const std::vector<Arc>& arcs) {
    21852185      for (int i = 0; i < int(arcs.size()); ++i) {
    2186         remove(arcs[i]);
    2187       }     
     2186        remove(arcs[i]);
     2187      }
    21882188    }
    21892189
    … …  
    21942194    virtual void clear() {
    21952195      for(NodeIt n(_g);n!=INVALID;++n) {
    2196         _head.set(n, INVALID);
     2196        _head.set(n, INVALID);
    21972197      }
    21982198    }
    … …  
    22032203      _left.set(arc, INVALID);
    22042204      _right.set(arc, INVALID);
    2205      
     2205
    22062206      Arc e = _head[s];
    22072207      if (e == INVALID) {
    2208         _head.set(s, arc);
    2209         _parent.set(arc, INVALID);
    2210         return;
     2208        _head.set(s, arc);
     2209        _parent.set(arc, INVALID);
     2210        return;
    22112211      }
    22122212      while (true) {
    2213         if (t < _g.target(e)) {
    2214           if (_left[e] == INVALID) {
    2215             _left.set(e, arc);
    2216             _parent.set(arc, e);
    2217             splay(arc);
    2218             return;
    2219           } else {
    2220             e = _left[e];
    2221           }
    2222         } else {
    2223           if (_right[e] == INVALID) {
    2224             _right.set(e, arc);
    2225             _parent.set(arc, e);
    2226             splay(arc);
    2227             return;
    2228           } else {
    2229             e = _right[e];
    2230           }
    2231         }
     2213        if (t < _g.target(e)) {
     2214          if (_left[e] == INVALID) {
     2215            _left.set(e, arc);
     2216            _parent.set(arc, e);
     2217            splay(arc);
     2218            return;
     2219          } else {
     2220            e = _left[e];
     2221          }
     2222        } else {
     2223          if (_right[e] == INVALID) {
     2224            _right.set(e, arc);
     2225            _parent.set(arc, e);
     2226            splay(arc);
     2227            return;
     2228          } else {
     2229            e = _right[e];
     2230          }
     2231        }
    22322232      }
    22332233    }
    … …  
    22352235    void remove(Arc arc) {
    22362236      if (_left[arc] == INVALID) {
    2237         if (_right[arc] != INVALID) {
    2238           _parent.set(_right[arc], _parent[arc]);
    2239         }
    2240         if (_parent[arc] != INVALID) {
    2241           if (_left[_parent[arc]] == arc) {
    2242             _left.set(_parent[arc], _right[arc]);
    2243           } else {
    2244             _right.set(_parent[arc], _right[arc]);
    2245           }
    2246         } else {
    2247           _head.set(_g.source(arc), _right[arc]);
    2248         }
     2237        if (_right[arc] != INVALID) {
     2238          _parent.set(_right[arc], _parent[arc]);
     2239        }
     2240        if (_parent[arc] != INVALID) {
     2241          if (_left[_parent[arc]] == arc) {
     2242            _left.set(_parent[arc], _right[arc]);
     2243          } else {
     2244            _right.set(_parent[arc], _right[arc]);
     2245          }
     2246        } else {
     2247          _head.set(_g.source(arc), _right[arc]);
     2248        }
    22492249      } else if (_right[arc] == INVALID) {
    2250         _parent.set(_left[arc], _parent[arc]);
    2251         if (_parent[arc] != INVALID) {
    2252           if (_left[_parent[arc]] == arc) {
    2253             _left.set(_parent[arc], _left[arc]);
    2254           } else {
    2255             _right.set(_parent[arc], _left[arc]);
    2256           }
    2257         } else {
    2258           _head.set(_g.source(arc), _left[arc]);
    2259         }
     2250        _parent.set(_left[arc], _parent[arc]);
     2251        if (_parent[arc] != INVALID) {
     2252          if (_left[_parent[arc]] == arc) {
     2253            _left.set(_parent[arc], _left[arc]);
     2254          } else {
     2255            _right.set(_parent[arc], _left[arc]);
     2256          }
     2257        } else {
     2258          _head.set(_g.source(arc), _left[arc]);
     2259        }
    22602260      } else {
    2261         Arc e = _left[arc];
    2262         if (_right[e] != INVALID) {
    2263           e = _right[e];         
    2264           while (_right[e] != INVALID) {
    2265             e = _right[e];
    2266           }
    2267           Arc s = _parent[e];
    2268           _right.set(_parent[e], _left[e]);
    2269           if (_left[e] != INVALID) {
    2270             _parent.set(_left[e], _parent[e]);
    2271           }
    2272          
    2273           _left.set(e, _left[arc]);
    2274           _parent.set(_left[arc], e);
    2275           _right.set(e, _right[arc]);
    2276           _parent.set(_right[arc], e);
    2277 
    2278           _parent.set(e, _parent[arc]);
    2279           if (_parent[arc] != INVALID) {
    2280             if (_left[_parent[arc]] == arc) {
    2281               _left.set(_parent[arc], e);
    2282             } else {
    2283               _right.set(_parent[arc], e);
    2284             }
    2285           }
    2286           splay(s);
    2287         } else {
    2288           _right.set(e, _right[arc]);
    2289           _parent.set(_right[arc], e);
    2290 
    2291           if (_parent[arc] != INVALID) {
    2292             if (_left[_parent[arc]] == arc) {
    2293               _left.set(_parent[arc], e);
    2294             } else {
    2295               _right.set(_parent[arc], e);
    2296             }
    2297           } else {
    2298             _head.set(_g.source(arc), e);
    2299           }
    2300         }
    2301       }
    2302     }
    2303 
    2304     Arc refreshRec(std::vector<Arc> &v,int a,int b) 
     2261        Arc e = _left[arc];
     2262        if (_right[e] != INVALID) {
     2263          e = _right[e];
     2264          while (_right[e] != INVALID) {
     2265            e = _right[e];
     2266          }
     2267          Arc s = _parent[e];
     2268          _right.set(_parent[e], _left[e]);
     2269          if (_left[e] != INVALID) {
     2270            _parent.set(_left[e], _parent[e]);
     2271          }
     2272
     2273          _left.set(e, _left[arc]);
     2274          _parent.set(_left[arc], e);
     2275          _right.set(e, _right[arc]);
     2276          _parent.set(_right[arc], e);
     2277
     2278          _parent.set(e, _parent[arc]);
     2279          if (_parent[arc] != INVALID) {
     2280            if (_left[_parent[arc]] == arc) {
     2281              _left.set(_parent[arc], e);
     2282            } else {
     2283              _right.set(_parent[arc], e);
     2284            }
     2285          }
     2286          splay(s);
     2287        } else {
     2288          _right.set(e, _right[arc]);
     2289          _parent.set(_right[arc], e);
     2290
     2291          if (_parent[arc] != INVALID) {
     2292            if (_left[_parent[arc]] == arc) {
     2293              _left.set(_parent[arc], e);
     2294            } else {
     2295              _right.set(_parent[arc], e);
     2296            }
     2297          } else {
     2298            _head.set(_g.source(arc), e);
     2299          }
     2300        }
     2301      }
     2302    }
     2303
     2304    Arc refreshRec(std::vector<Arc> &v,int a,int b)
    23052305    {
    23062306      int m=(a+b)/2;
    23072307      Arc me=v[m];
    23082308      if (a < m) {
    2309         Arc left = refreshRec(v,a,m-1);
    2310         _left.set(me, left);
    2311         _parent.set(left, me);
     2309        Arc left = refreshRec(v,a,m-1);
     2310        _left.set(me, left);
     2311        _parent.set(left, me);
    23122312      } else {
    2313         _left.set(me, INVALID);
     2313        _left.set(me, INVALID);
    23142314      }
    23152315      if (m < b) {
    2316         Arc right = refreshRec(v,m+1,b);
    2317         _right.set(me, right);
    2318         _parent.set(right, me);
     2316        Arc right = refreshRec(v,m+1,b);
     2317        _right.set(me, right);
     2318        _parent.set(right, me);
    23192319      } else {
    2320         _right.set(me, INVALID);
     2320        _right.set(me, INVALID);
    23212321      }
    23222322      return me;
    … …  
    23252325    void refresh() {
    23262326      for(NodeIt n(_g);n!=INVALID;++n) {
    2327         std::vector<Arc> v;
    2328         for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
    2329         if(v.size()) {
    2330           std::sort(v.begin(),v.end(),ArcLess(_g));
    2331           Arc head = refreshRec(v,0,v.size()-1);
    2332           _head.set(n, head);
    2333           _parent.set(head, INVALID);
    2334         }
    2335         else _head.set(n, INVALID);
    2336       }
    2337     }
    2338 
    2339     void zig(Arc v) {       
     2327        std::vector<Arc> v;
     2328        for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
     2329        if(v.size()) {
     2330          std::sort(v.begin(),v.end(),ArcLess(_g));
     2331          Arc head = refreshRec(v,0,v.size()-1);
     2332          _head.set(n, head);
     2333          _parent.set(head, INVALID);
     2334        }
     2335        else _head.set(n, INVALID);
     2336      }
     2337    }
     2338
     2339    void zig(Arc v) {
    23402340      Arc w = _parent[v];
    23412341      _parent.set(v, _parent[w]);
    … …  
    23442344      _right.set(v, w);
    23452345      if (_parent[v] != INVALID) {
    2346         if (_right[_parent[v]] == w) {
    2347           _right.set(_parent[v], v);
    2348         } else {
    2349           _left.set(_parent[v], v);
    2350         }
     2346        if (_right[_parent[v]] == w) {
     2347          _right.set(_parent[v], v);
     2348        } else {
     2349          _left.set(_parent[v], v);
     2350        }
    23512351      }
    23522352      if (_left[w] != INVALID){
    2353         _parent.set(_left[w], w);
    2354       }
    2355     }
    2356 
    2357     void zag(Arc v) {       
     2353        _parent.set(_left[w], w);
     2354      }
     2355    }
     2356
     2357    void zag(Arc v) {
    23582358      Arc w = _parent[v];
    23592359      _parent.set(v, _parent[w]);
    … …  
    23622362      _left.set(v, w);
    23632363      if (_parent[v] != INVALID){
    2364         if (_left[_parent[v]] == w) {
    2365           _left.set(_parent[v], v);
    2366         } else {
    2367           _right.set(_parent[v], v);
    2368         }
     2364        if (_left[_parent[v]] == w) {
     2365          _left.set(_parent[v], v);
     2366        } else {
     2367          _right.set(_parent[v], v);
     2368        }
    23692369      }
    23702370      if (_right[w] != INVALID){
    2371         _parent.set(_right[w], w);
     2371        _parent.set(_right[w], w);
    23722372      }
    23732373    }
    … …  
    23752375    void splay(Arc v) {
    23762376      while (_parent[v] != INVALID) {
    2377         if (v == _left[_parent[v]]) {
    2378           if (_parent[_parent[v]] == INVALID) {
    2379             zig(v);
    2380           } else {
    2381             if (_parent[v] == _left[_parent[_parent[v]]]) {
    2382               zig(_parent[v]);
    2383               zig(v);
    2384             } else {
    2385               zig(v);
    2386               zag(v);
    2387             }
    2388           }
    2389         } else {
    2390           if (_parent[_parent[v]] == INVALID) {
    2391             zag(v);
    2392           } else {
    2393             if (_parent[v] == _left[_parent[_parent[v]]]) {
    2394               zag(v);
    2395               zig(v);
    2396             } else {
    2397               zag(_parent[v]);
    2398               zag(v);
    2399             }
    2400           }
    2401         }
     2377        if (v == _left[_parent[v]]) {
     2378          if (_parent[_parent[v]] == INVALID) {
     2379            zig(v);
     2380          } else {
     2381            if (_parent[v] == _left[_parent[_parent[v]]]) {
     2382              zig(_parent[v]);
     2383              zig(v);
     2384            } else {
     2385              zig(v);
     2386              zag(v);
     2387            }
     2388          }
     2389        } else {
     2390          if (_parent[_parent[v]] == INVALID) {
     2391            zag(v);
     2392          } else {
     2393            if (_parent[v] == _left[_parent[_parent[v]]]) {
     2394              zag(v);
     2395              zig(v);
     2396            } else {
     2397              zag(_parent[v]);
     2398              zag(v);
     2399            }
     2400          }
     2401        }
    24022402      }
    24032403      _head[_g.source(v)] = v;
    … …  
    24062406
    24072407  public:
    2408    
     2408
    24092409    ///Find an arc between two nodes.
    2410    
     2410
    24112411    ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
    24122412    /// <em>d</em> is the number of outgoing arcs of \c s.
    … …  
    24192419      Arc a = _head[s];
    24202420      while (true) {
    2421         if (_g.target(a) == t) {
    2422           const_cast<DynArcLookUp&>(*this).splay(a);
    2423           return a;
    2424         } else if (t < _g.target(a)) {
    2425           if (_left[a] == INVALID) {
    2426             const_cast<DynArcLookUp&>(*this).splay(a);
    2427             return INVALID;
    2428           } else {
    2429             a = _left[a];
    2430           }
    2431         } else  {
    2432           if (_right[a] == INVALID) {
    2433             const_cast<DynArcLookUp&>(*this).splay(a);
    2434             return INVALID;
    2435           } else {
    2436             a = _right[a];
    2437           }
    2438         }
     2421        if (_g.target(a) == t) {
     2422          const_cast<DynArcLookUp&>(*this).splay(a);
     2423          return a;
     2424        } else if (t < _g.target(a)) {
     2425          if (_left[a] == INVALID) {
     2426            const_cast<DynArcLookUp&>(*this).splay(a);
     2427            return INVALID;
     2428          } else {
     2429            a = _left[a];
     2430          }
     2431        } else  {
     2432          if (_right[a] == INVALID) {
     2433            const_cast<DynArcLookUp&>(*this).splay(a);
     2434            return INVALID;
     2435          } else {
     2436            a = _right[a];
     2437          }
     2438        }
    24392439      }
    24402440    }
    24412441
    24422442    ///Find the first arc between two nodes.
    2443    
     2443
    24442444    ///Find the first arc between two nodes in time
    24452445    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
    2446     /// outgoing arcs of \c s. 
    2447     ///\param s The source node 
     2446    /// outgoing arcs of \c s.
     2447    ///\param s The source node
    24482448    ///\param t The target node
    24492449    ///\return An arc from \c s to \c t if there exists, \ref INVALID
    … …  
    24542454      Arc r = INVALID;
    24552455      while (true) {
    2456         if (_g.target(a) < t) {
    2457           if (_right[a] == INVALID) {
    2458             const_cast<DynArcLookUp&>(*this).splay(a);
    2459             return r;
    2460           } else {
    2461             a = _right[a];
    2462           }
    2463         } else {
    2464           if (_g.target(a) == t) {
    2465             r = a;
    2466           }
    2467           if (_left[a] == INVALID) {
    2468             const_cast<DynArcLookUp&>(*this).splay(a);
    2469             return r;
    2470           } else {
    2471             a = _left[a];
    2472           }
    2473         }
     2456        if (_g.target(a) < t) {
     2457          if (_right[a] == INVALID) {
     2458            const_cast<DynArcLookUp&>(*this).splay(a);
     2459            return r;
     2460          } else {
     2461            a = _right[a];
     2462          }
     2463        } else {
     2464          if (_g.target(a) == t) {
     2465            r = a;
     2466          }
     2467          if (_left[a] == INVALID) {
     2468            const_cast<DynArcLookUp&>(*this).splay(a);
     2469            return r;
     2470          } else {
     2471            a = _left[a];
     2472          }
     2473        }
    24742474      }
    24752475    }
    24762476
    24772477    ///Find the next arc between two nodes.
    2478    
     2478
    24792479    ///Find the next arc between two nodes in time
    24802480    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
    2481     /// outgoing arcs of \c s. 
    2482     ///\param s The source node 
     2481    /// outgoing arcs of \c s.
     2482    ///\param s The source node
    24832483    ///\param t The target node
    24842484    ///\return An arc from \c s to \c t if there exists, \ref INVALID
    … …  
    24942494    {
    24952495      if (_right[a] != INVALID) {
    2496         a = _right[a];
    2497         while (_left[a] != INVALID) {
    2498           a = _left[a];
    2499         }
    2500         const_cast<DynArcLookUp&>(*this).splay(a);
     2496        a = _right[a];
     2497        while (_left[a] != INVALID) {
     2498          a = _left[a];
     2499        }
     2500        const_cast<DynArcLookUp&>(*this).splay(a);
    25012501      } else {
    2502         while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
    2503           a = _parent[a];
    2504         }
    2505         if (_parent[a] == INVALID) {
    2506           return INVALID;
    2507         } else {
    2508           a = _parent[a];
    2509           const_cast<DynArcLookUp&>(*this).splay(a);
    2510         }
     2502        while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
     2503          a = _parent[a];
     2504        }
     2505        if (_parent[a] == INVALID) {
     2506          return INVALID;
     2507        } else {
     2508          a = _parent[a];
     2509          const_cast<DynArcLookUp&>(*this).splay(a);
     2510        }
    25112511      }
    25122512      if (_g.target(a) == t) return a;
    2513       else return INVALID;   
     2513      else return INVALID;
    25142514    }
    25152515
    … …  
    25172517
    25182518  ///Fast arc look up between given endpoints.
    2519  
     2519
    25202520  ///\ingroup gutils
    25212521  ///Using this class, you can find an arc in a digraph from a given
    … …  
    25342534  ///
    25352535  ///\sa DynArcLookUp
    2536   ///\sa AllArcLookUp 
     2536  ///\sa AllArcLookUp
    25372537  template<class G>
    2538   class ArcLookUp 
     2538  class ArcLookUp
    25392539  {
    25402540  public:
    … …  
    25472547    typename Digraph::template ArcMap<Arc> _left;
    25482548    typename Digraph::template ArcMap<Arc> _right;
    2549    
     2549
    25502550    class ArcLess {
    25512551      const Digraph &g;
    25522552    public:
    25532553      ArcLess(const Digraph &_g) : g(_g) {}
    2554       bool operator()(Arc a,Arc b) const 
     2554      bool operator()(Arc a,Arc b) const
    25552555      {
    2556         return g.target(a)<g.target(b);
    2557       }
    2558     };
    2559    
     2556        return g.target(a)<g.target(b);
     2557      }
     2558    };
     2559
    25602560  public:
    2561    
     2561
    25622562    ///Constructor
    25632563
    … …  
    25672567    ///changes.
    25682568    ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
    2569    
     2569
    25702570  private:
    2571     Arc refreshRec(std::vector<Arc> &v,int a,int b) 
     2571    Arc refreshRec(std::vector<Arc> &v,int a,int b)
    25722572    {
    25732573      int m=(a+b)/2;
    … …  
    25842584    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
    25852585    ///the number of the outgoing arcs of \c n.
    2586     void refresh(Node n) 
     2586    void refresh(Node n)
    25872587    {
    25882588      std::vector<Arc> v;
    25892589      for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
    25902590      if(v.size()) {
    2591         std::sort(v.begin(),v.end(),ArcLess(_g));
    2592         _head[n]=refreshRec(v,0,v.size()-1);
     2591        std::sort(v.begin(),v.end(),ArcLess(_g));
     2592        _head[n]=refreshRec(v,0,v.size()-1);
    25932593      }
    25942594      else _head[n]=INVALID;
    … …  
    26032603    ///out-degree of the digraph.
    26042604
    2605     void refresh() 
     2605    void refresh()
    26062606    {
    26072607      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
    26082608    }
    2609    
     2609
    26102610    ///Find an arc between two nodes.
    2611    
     2611
    26122612    ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
    26132613    /// <em>d</em> is the number of outgoing arcs of \c s.
    … …  
    26262626      Arc e;
    26272627      for(e=_head[s];
    2628           e!=INVALID&&_g.target(e)!=t;
    2629           e = t < _g.target(e)?_left[e]:_right[e]) ;
     2628          e!=INVALID&&_g.target(e)!=t;
     2629          e = t < _g.target(e)?_left[e]:_right[e]) ;
    26302630      return e;
    26312631    }
    … …  
    26342634
    26352635  ///Fast look up of all arcs between given endpoints.
    2636  
     2636
    26372637  ///\ingroup gutils
    26382638  ///This class is the same as \ref ArcLookUp, with the addition
    … …  
    26472647  ///
    26482648  ///\sa DynArcLookUp
    2649   ///\sa ArcLookUp 
     2649  ///\sa ArcLookUp
    26502650  template<class G>
    26512651  class AllArcLookUp : public ArcLookUp<G>
    … …  
    26582658    TEMPLATE_DIGRAPH_TYPEDEFS(G);
    26592659    typedef G Digraph;
    2660    
     2660
    26612661    typename Digraph::template ArcMap<Arc> _next;
    2662    
     2662
    26632663    Arc refreshNext(Arc head,Arc next=INVALID)
    26642664    {
    26652665      if(head==INVALID) return next;
    26662666      else {
    2667         next=refreshNext(_right[head],next);
    2668 //      _next[head]=next;
    2669         _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
    2670           ? next : INVALID;
    2671         return refreshNext(_left[head],head);
    2672       }
    2673     }
    2674    
     2667        next=refreshNext(_right[head],next);
     2668//         _next[head]=next;
     2669        _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
     2670          ? next : INVALID;
     2671        return refreshNext(_left[head],head);
     2672      }
     2673    }
     2674
    26752675    void refreshNext()
    26762676    {
    26772677      for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
    26782678    }
    2679    
     2679
    26802680  public:
    26812681    ///Constructor
    … …  
    26932693    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
    26942694    ///the number of the outgoing arcs of \c n.
    2695    
    2696     void refresh(Node n) 
     2695
     2696    void refresh(Node n)
    26972697    {
    26982698      ArcLookUp<G>::refresh(n);
    26992699      refreshNext(_head[n]);
    27002700    }
    2701    
     2701
    27022702    ///Refresh the full data structure.
    27032703
    … …  
    27092709    ///out-degree of the digraph.
    27102710
    2711     void refresh() 
     2711    void refresh()
    27122712    {
    27132713      for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
    27142714    }
    2715    
     2715
    27162716    ///Find an arc between two nodes.
    2717    
     2717
    27182718    ///Find an arc between two nodes.
    27192719    ///\param s The source node
    … …  
    27512751    }
    27522752#endif
    2753      
     2753
    27542754  };
    27552755
Note: See TracChangeset for help on using the changeset viewer.