COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [153:976a014b3797:154:f4e4dbc1d467] in lemon-main


Ignore:
Files:
6 added
6 deleted
20 edited

Legend:

Unmodified
Added
Removed

  • .hgignore

    r153 r154  
    3737^test/[a-z_]*$
    3838^demo/.*_demo$
     39^build/.*
     40CMakeFiles
     41DartTestfile.txt
     42cmake_install.cmake
     43CMakeCache.txt

  • Makefile.am

    r70 r146  
    88        m4/lx_check_cplex.m4 \
    99        m4/lx_check_glpk.m4 \
    10         m4/lx_check_soplex.m4
     10        m4/lx_check_soplex.m4 \
     11        CMakeLists.txt
    1112
    1213pkgconfigdir = $(libdir)/pkgconfig
    … …  
    4546        build-aux/ltmain.sh \
    4647        build-aux/missing \
    47         doc/Makefile.in \
    48         doc/doxygen.log \
    49         Makefile.in \
    50         lemon/Makefile.in \
    51         test/Makefile.in \
    52         benchmark/Makefile.in \
    53         demo/Makefile.in
     48        doc/doxygen.log
    5449
    5550mrproper:

  • benchmark/Makefile.am

    r1 r146  
    1 EXTRA_DIST += \
    2         benchmark/Makefile
    3 
    41if WANT_BENCHMARK
    52

  • demo/Makefile.am

    r135 r146  
    11EXTRA_DIST += \
    2         demo/Makefile
     2        demo/CMakeLists.txt
    33
    44if WANT_DEMO
    … …  
    1414demo_graph_to_eps_demo_SOURCES = demo/graph_to_eps_demo.cc
    1515demo_lgf_demo_SOURCES = demo/lgf_demo.cc
    16 

  • demo/lgf_demo.cc

    r127 r143  
    3838int main(int argc, const char *argv[]) {
    3939  const int n = argc > 1 ? std::atoi(argv[1]) : 20;
    40   const int e = argc > 2 ? std::atoi(argv[2]) : static_cast<int>(n * log(n));
     40  const int e = argc > 2 ? std::atoi(argv[2]) : static_cast<int>(n * std::log(double(n)));
    4141  const int m = argc > 3 ? std::atoi(argv[3]) : 100;
    4242

  • doc/Makefile.am

    r153 r154  
    11EXTRA_DIST += \
    2         doc/Makefile \
    32        doc/Doxyfile.in \
    43        doc/coding_style.dox \

  • lemon/Makefile.am

    r135 r146  
    11EXTRA_DIST += \
    2         lemon/Makefile \
    3         lemon/lemon.pc.in
     2        lemon/lemon.pc.in \
     3        lemon/CMakeLists.txt
    44
    55pkgconfig_DATA += lemon/lemon.pc

  • lemon/assert.h

    r118 r142  
    104104
    105105#ifndef LEMON_FUNCTION_NAME
    106 #  define LEMON_FUNCTION_NAME (__PRETTY_FUNCTION__)
     106#  if defined __GNUC__
     107#    define LEMON_FUNCTION_NAME (__PRETTY_FUNCTION__)
     108#  elif defined _MSC_VER
     109#    define LEMON_FUNCTION_NAME (__FUNCSIG__)
     110#  else
     111#    define LEMON_FUNCTION_NAME (__func__)
     112#  endif
    107113#endif
    108114

  • 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_to_eps.h

    r134 r143  
    3030#include<ctime>
    3131#else
     32#define WIN32_LEAN_AND_MEAN
     33#define NOMINMAX
    3234#include<windows.h>
    3335#endif

  • lemon/graph_utils.h

    r100 r148  
    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
    64 
     49  ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
     50  ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
     51  ///
     52  ///\note If the graph type is a dependent type, ie. the graph type depend
     53  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
     54  ///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;                               \
     67  typedef Digraph::ArcMap<double> DoubleArcMap
     68
     69  ///Creates convenience typedefs for the digraph types and iterators
     70
     71  ///\see DIGRAPH_TYPEDEFS
     72  ///
     73  ///\note Use this macro, if the graph type is a dependent type,
     74  ///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;             \
     87  typedef typename Digraph::template ArcMap<double> DoubleArcMap
     88 
    6589  ///Creates convenience typedefs for the graph types and iterators
    6690
    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.
     91  ///This \c \#define creates the same convenience typedefs as defined
     92  ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
     93  ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
     94  ///\c DoubleEdgeMap.
     95  ///
     96  ///\note If the graph type is a dependent type, ie. the graph type depend
     97  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
     98  ///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;                               \
     106  typedef Graph::EdgeMap<double> DoubleEdgeMap
     107
     108  ///Creates convenience typedefs for the graph types and iterators
     109
     110  ///\see GRAPH_TYPEDEFS
     111  ///
     112  ///\note Use this macro, if the graph type is a dependent type,
     113  ///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;             \
     121  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
     122
     123  /// \brief Function to count the items in the graph.
     124  ///
     125  /// This function counts the items (nodes, arcs etc) in the graph.
    108126  /// The complexity of the function is O(n) because
    109127  /// 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;
     128  template <typename Graph, typename Item>
     129  inline int countItems(const Graph& g) {
     130    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
    114131    int num = 0;
    115132    for (ItemIt it(g); it != INVALID; ++it) {
    … …  
    121138  // Node counting:
    122139
    123   namespace _digraph_utils_bits {
    124    
    125     template <typename Digraph, typename Enable = void>
     140  namespace _graph_utils_bits {
     141   
     142    template <typename Graph, typename Enable = void>
    126143    struct CountNodesSelector {
    127       static int count(const Digraph &g) {
    128         return countItems<Digraph, typename Digraph::Node>(g);
     144      static int count(const Graph &g) {
     145        return countItems<Graph, typename Graph::Node>(g);
    129146      }
    130147    };
    131148
    132     template <typename Digraph>
     149    template <typename Graph>
    133150    struct CountNodesSelector<
    134       Digraph, typename
    135       enable_if<typename Digraph::NodeNumTag, void>::type>
     151      Graph, typename
     152      enable_if<typename Graph::NodeNumTag, void>::type>
    136153    {
    137       static int count(const Digraph &g) {
     154      static int count(const Graph &g) {
    138155        return g.nodeNum();
    139156      }
    … …  
    141158  }
    142159
    143   /// \brief Function to count the nodes in the digraph.
    144   ///
    145   /// This function counts the nodes in the digraph.
     160  /// \brief Function to count the nodes in the graph.
     161  ///
     162  /// This function counts the nodes in the graph.
    146163  /// 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
     164  /// graph structures it is specialized to run in O(1).
     165  ///
     166  /// If the graph contains a \e nodeNum() member function and a
    150167  /// \e NodeNumTag tag then this function calls directly the member
    151168  /// 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);
     169  template <typename Graph>
     170  inline int countNodes(const Graph& g) {
     171    return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
    155172  }
    156173
    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);
     174  // Arc counting:
     175
     176  namespace _graph_utils_bits {
     177   
     178    template <typename Graph, typename Enable = void>
     179    struct CountArcsSelector {
     180      static int count(const Graph &g) {
     181        return countItems<Graph, typename Graph::Arc>(g);
    163182      }
    164183    };
    165184
    166     template <typename Digraph>
    167     struct CountRedsSelector<
    168       Digraph, typename
    169       enable_if<typename Digraph::NodeNumTag, void>::type>
     185    template <typename Graph>
     186    struct CountArcsSelector<
     187      Graph,
     188      typename enable_if<typename Graph::ArcNumTag, void>::type>
    170189    {
    171       static int count(const Digraph &g) {
    172         return g.redNum();
     190      static int count(const Graph &g) {
     191        return g.arcNum();
    173192      }
    174193    };   
    175194  }
    176195
    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);
     196  /// \brief Function to count the arcs in the graph.
     197  ///
     198  /// This function counts the arcs in the graph.
     199  /// The complexity of the function is O(e) but for some
     200  /// graph structures it is specialized to run in O(1).
     201  ///
     202  /// If the graph contains a \e arcNum() member function and a
     203  /// \e EdgeNumTag tag then this function calls directly the member
     204  /// function to query the cardinality of the arc set.
     205  template <typename Graph>
     206  inline int countArcs(const Graph& g) {
     207    return _graph_utils_bits::CountArcsSelector<Graph>::count(g);
    189208  }
    190209
    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);
     210  // Edge counting:
     211  namespace _graph_utils_bits {
     212   
     213    template <typename Graph, typename Enable = void>
     214    struct CountEdgesSelector {
     215      static int count(const Graph &g) {
     216        return countItems<Graph, typename Graph::Edge>(g);
    197217      }
    198218    };
    199219
    200     template <typename Digraph>
    201     struct CountBluesSelector<
    202       Digraph, typename
    203       enable_if<typename Digraph::NodeNumTag, void>::type>
     220    template <typename Graph>
     221    struct CountEdgesSelector<
     222      Graph,
     223      typename enable_if<typename Graph::EdgeNumTag, void>::type>
    204224    {
    205       static int count(const Digraph &g) {
    206         return g.blueNum();
     225      static int count(const Graph &g) {
     226        return g.edgeNum();
    207227      }
    208228    };   
    209229  }
    210230
    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);
     231  /// \brief Function to count the edges in the graph.
     232  ///
     233  /// This function counts the edges in the graph.
     234  /// The complexity of the function is O(m) but for some
     235  /// graph structures it is specialized to run in O(1).
     236  ///
     237  /// If the graph contains a \e edgeNum() member function and a
     238  /// \e EdgeNumTag tag then this function calls directly the member
     239  /// function to query the cardinality of the edge set.
     240  template <typename Graph>
     241  inline int countEdges(const Graph& g) {
     242    return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
     243
    223244  }
    224245
    225246
    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) {
     247  template <typename Graph, typename DegIt>
     248  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
    301249    int num = 0;
    302250    for (DegIt it(_g, _n); it != INVALID; ++it) {
    … …  
    309257  ///
    310258  /// 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);
     259  /// in the graph. 
     260  template <typename Graph>
     261  inline int countOutArcs(const Graph& _g,  const typename Graph::Node& _n) {
     262    return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);
    315263  }
    316264
    … …  
    318266  ///
    319267  /// 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);
     268  /// in the graph. 
     269  template <typename Graph>
     270  inline int countInArcs(const Graph& _g,  const typename Graph::Node& _n) {
     271    return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);
    324272  }
    325273
    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);
     274  /// \brief Function to count the number of the inc-edges to node \c n.
     275  ///
     276  /// This function counts the number of the inc-edges to node \c n
     277  /// in the graph. 
     278  template <typename Graph>
     279  inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) {
     280    return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
    333281  }
    334282
    335   namespace _digraph_utils_bits {
    336    
    337     template <typename Digraph, typename Enable = void>
     283  namespace _graph_utils_bits {
     284   
     285    template <typename Graph, typename Enable = void>
    338286    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) {
     287      typedef typename Graph::Node Node;
     288      typedef typename Graph::Arc Arc;
     289      static Arc find(const Graph &g, Node u, Node v, Arc e) {
    342290        if (e == INVALID) {
    343291          g.firstOut(e, u);
    … …  
    352300    };
    353301
    354     template <typename Digraph>
     302    template <typename Graph>
    355303    struct FindArcSelector<
    356       Digraph,
    357       typename enable_if<typename Digraph::FindArcTag, void>::type>
     304      Graph,
     305      typename enable_if<typename Graph::FindEdgeTag, void>::type>
    358306    {
    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) {
     307      typedef typename Graph::Node Node;
     308      typedef typename Graph::Arc Arc;
     309      static Arc find(const Graph &g, Node u, Node v, Arc prev) {
    362310        return g.findArc(u, v, prev);
    363311      }
    … …  
    365313  }
    366314
    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.
     315  /// \brief Finds an arc between two nodes of a graph.
     316  ///
     317  /// Finds an arc from node \c u to node \c v in graph \c g.
    370318  ///
    371319  /// If \c prev is \ref INVALID (this is the default value), then
    … …  
    385333  ///\sa DynArcLookUp
    386334  ///\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);
     335  template <typename Graph>
     336  inline typename Graph::Arc
     337  findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
     338           typename Graph::Arc prev = INVALID) {
     339    return _graph_utils_bits::FindArcSelector<Graph>::find(g, u, v, prev);
    392340  }
    393341
    … …  
    398346  /// use it the following way:
    399347  ///\code
    400   /// for (ConArcIt<Digraph> it(g, src, trg); it != INVALID; ++it) {
     348  /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
    401349  ///   ...
    402350  /// }
    … …  
    409357  ///
    410358  /// \author Balazs Dezso
    411   template <typename _Digraph>
    412   class ConArcIt : public _Digraph::Arc {
     359  template <typename _Graph>
     360  class ConArcIt : public _Graph::Arc {
    413361  public:
    414362
    415     typedef _Digraph Digraph;
    416     typedef typename Digraph::Arc Parent;
    417 
    418     typedef typename Digraph::Arc Arc;
    419     typedef typename Digraph::Node Node;
     363    typedef _Graph Graph;
     364    typedef typename Graph::Arc Parent;
     365
     366    typedef typename Graph::Arc Arc;
     367    typedef typename Graph::Node Node;
    420368
    421369    /// \brief Constructor.
    … …  
    423371    /// Construct a new ConArcIt iterating on the arcs which
    424372    /// 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));
     373    ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
     374      Parent::operator=(findArc(_graph, u, v));
    427375    }
    428376
    … …  
    431379    /// Construct a new ConArcIt which continues the iterating from
    432380    /// the \c e arc.
    433     ConArcIt(const Digraph& g, Arc e) : Parent(e), digraph(g) {}
     381    ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
    434382   
    435383    /// \brief Increment operator.
    … …  
    437385    /// It increments the iterator and gives back the next arc.
    438386    ConArcIt& operator++() {
    439       Parent::operator=(findArc(digraph, digraph.source(*this),
    440                                  digraph.target(*this), *this));
     387      Parent::operator=(findArc(_graph, _graph.source(*this),
     388                                _graph.target(*this), *this));
    441389      return *this;
    442390    }
    443391  private:
    444     const Digraph& digraph;
     392    const Graph& _graph;
    445393  };
    446394
    447   namespace _digraph_utils_bits {
    448    
    449     template <typename Digraph, typename Enable = void>
     395  namespace _graph_utils_bits {
     396   
     397    template <typename Graph, typename Enable = void>
    450398    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) {
     399      typedef typename Graph::Node Node;
     400      typedef typename Graph::Edge Edge;
     401      static Edge find(const Graph &g, Node u, Node v, Edge e) {
    454402        bool b;
    455403        if (u != v) {
    … …  
    478426    };
    479427
    480     template <typename Digraph>
     428    template <typename Graph>
    481429    struct FindEdgeSelector<
    482       Digraph,
    483       typename enable_if<typename Digraph::FindArcTag, void>::type>
     430      Graph,
     431      typename enable_if<typename Graph::FindEdgeTag, void>::type>
    484432    {
    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) {
     433      typedef typename Graph::Node Node;
     434      typedef typename Graph::Edge Edge;
     435      static Edge find(const Graph &g, Node u, Node v, Edge prev) {
    488436        return g.findEdge(u, v, prev);
    489437      }
    … …  
    491439  }
    492440
    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.
     441  /// \brief Finds an edge between two nodes of a graph.
     442  ///
     443  /// Finds an edge from node \c u to node \c v in graph \c g.
     444  /// If the node \c u and node \c v is equal then each loop edge
     445  /// will be enumerated once.
    498446  ///
    499447  /// If \c prev is \ref INVALID (this is the default value), then
    … …  
    512460  ///\sa ConArcIt
    513461
    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);
     462  template <typename Graph>
     463  inline typename Graph::Edge
     464  findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
     465            typename Graph::Edge p = INVALID) {
     466    return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
    519467  }
    520468
    … …  
    525473  /// use it the following way:
    526474  ///\code
    527   /// for (ConEdgeIt<Digraph> it(g, src, trg); it != INVALID; ++it) {
     475  /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
    528476  ///   ...
    529477  /// }
    … …  
    533481  ///
    534482  /// \author Balazs Dezso
    535   template <typename _Digraph>
    536   class ConEdgeIt : public _Digraph::Edge {
     483  template <typename _Graph>
     484  class ConEdgeIt : public _Graph::Edge {
    537485  public:
    538486
    539     typedef _Digraph Digraph;
    540     typedef typename Digraph::Edge Parent;
    541 
    542     typedef typename Digraph::Edge Edge;
    543     typedef typename Digraph::Node Node;
     487    typedef _Graph Graph;
     488    typedef typename Graph::Edge Parent;
     489
     490    typedef typename Graph::Edge Edge;
     491    typedef typename Graph::Node Node;
    544492
    545493    /// \brief Constructor.
    546494    ///
    547     /// Construct a new ConEdgeIt iterating on the arcs which
     495    /// Construct a new ConEdgeIt iterating on the edges which
    548496    /// 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));
     497    ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
     498      Parent::operator=(findEdge(_graph, u, v));
    551499    }
    552500
    … …  
    554502    ///
    555503    /// 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) {}
     504    /// the \c e edge.
     505    ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
    558506   
    559507    /// \brief Increment operator.
    560508    ///
    561     /// It increments the iterator and gives back the next arc.
     509    /// It increments the iterator and gives back the next edge.
    562510    ConEdgeIt& operator++() {
    563       Parent::operator=(findEdge(digraph, digraph.source(*this),
    564                                       digraph.target(*this), *this));
     511      Parent::operator=(findEdge(_graph, _graph.source(*this),
     512                                 _graph.target(*this), *this));
    565513      return *this;
    566514    }
    567515  private:
    568     const Digraph& digraph;
     516    const Graph& _graph;
    569517  };
    570518
    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 {
     519  namespace _graph_utils_bits {
    597520
    598521    template <typename Digraph, typename Item, typename RefMap>
    … …  
    728651    };
    729652
    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 
    765653  }
    766654
    … …  
    769657  /// Class to copy a digraph to another digraph (duplicate a digraph). The
    770658  /// simplest way of using it is through the \c copyDigraph() function.
     659  ///
     660  /// This class not just make a copy of a graph, but it can create
     661  /// references and cross references between the nodes and arcs of
     662  /// the two graphs, it can copy maps for use with the newly created
     663  /// graph and copy nodes and arcs.
     664  ///
     665  /// To make a copy from a graph, first an instance of DigraphCopy
     666  /// should be created, then the data belongs to the graph should
     667  /// assigned to copy. In the end, the \c run() member should be
     668  /// called.
     669  ///
     670  /// The next code copies a graph with several data:
     671  ///\code
     672  ///  DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
     673  ///  // create a reference for the nodes
     674  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
     675  ///  dc.nodeRef(nr);
     676  ///  // create a cross reference (inverse) for the arcs
     677  ///  NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
     678  ///  dc.arcCrossRef(acr);
     679  ///  // copy an arc map
     680  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
     681  ///  NewGraph::ArcMap<double> namap(new_graph);
     682  ///  dc.arcMap(namap, oamap);
     683  ///  // copy a node
     684  ///  OrigGraph::Node on;
     685  ///  NewGraph::Node nn;
     686  ///  dc.node(nn, on);
     687  ///  // Executions of copy
     688  ///  dc.run();
     689  ///\endcode
    771690  template <typename To, typename From>
    772691  class DigraphCopy {
    … …  
    792711    /// It copies the content of the \c _from digraph into the
    793712    /// \c _to digraph.
    794     DigraphCopy(To& _to, const From& _from)
    795       : from(_from), to(_to) {}
     713    DigraphCopy(To& to, const From& from)
     714      : _from(from), _to(to) {}
    796715
    797716    /// \brief Destructor of the DigraphCopy
    … …  
    799718    /// Destructor of the DigraphCopy
    800719    ~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];
     720      for (int i = 0; i < int(_node_maps.size()); ++i) {
     721        delete _node_maps[i];
     722      }
     723      for (int i = 0; i < int(_arc_maps.size()); ++i) {
     724        delete _arc_maps[i];
    806725      }
    807726
    … …  
    810729    /// \brief Copies the node references into the given map.
    811730    ///
    812     /// Copies the node references into the given map.
     731    /// Copies the node references into the given map. The parameter
     732    /// should be a map, which key type is the Node type of the source
     733    /// graph, while the value type is the Node type of the
     734    /// destination graph.
    813735    template <typename NodeRef>
    814736    DigraphCopy& nodeRef(NodeRef& map) {
    815       nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node,
    816                               NodeRefMap, NodeRef>(map));
     737      _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
     738                           NodeRefMap, NodeRef>(map));
    817739      return *this;
    818740    }
    … …  
    821743    ///
    822744    ///  Copies the node cross references (reverse references) into
    823     ///  the given map.
     745    ///  the given map. The parameter should be a map, which key type
     746    ///  is the Node type of the destination graph, while the value type is
     747    ///  the Node type of the source graph.
    824748    template <typename NodeCrossRef>
    825749    DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
    826       nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,
    827                               NodeRefMap, NodeCrossRef>(map));
     750      _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
     751                           NodeRefMap, NodeCrossRef>(map));
    828752      return *this;
    829753    }
    … …  
    831755    /// \brief Make copy of the given map.
    832756    ///
    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. 
     757    /// Makes copy of the given map for the newly created digraph.
     758    /// The new map's key type is the destination graph's node type,
     759    /// and the copied map's key type is the source graph's node type.
    837760    template <typename ToMap, typename FromMap>
    838761    DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
    839       nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node,
    840                               NodeRefMap, ToMap, FromMap>(tmap, map));
     762      _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
     763                           NodeRefMap, ToMap, FromMap>(tmap, map));
    841764      return *this;
    842765    }
    … …  
    846769    /// Make a copy of the given node.
    847770    DigraphCopy& node(TNode& tnode, const Node& snode) {
    848       nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,
    849                               NodeRefMap, TNode>(tnode, snode));
     771      _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
     772                           NodeRefMap, TNode>(tnode, snode));
    850773      return *this;
    851774    }
    … …  
    856779    template <typename ArcRef>
    857780    DigraphCopy& arcRef(ArcRef& map) {
    858       arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,
    859                               ArcRefMap, ArcRef>(map));
     781      _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
     782                          ArcRefMap, ArcRef>(map));
    860783      return *this;
    861784    }
    … …  
    867790    template <typename ArcCrossRef>
    868791    DigraphCopy& arcCrossRef(ArcCrossRef& map) {
    869       arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,
    870                               ArcRefMap, ArcCrossRef>(map));
     792      _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
     793                          ArcRefMap, ArcCrossRef>(map));
    871794      return *this;
    872795    }
    … …  
    880803    template <typename ToMap, typename FromMap>
    881804    DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
    882       arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,
    883                               ArcRefMap, ToMap, FromMap>(tmap, map));
     805      _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
     806                          ArcRefMap, ToMap, FromMap>(tmap, map));
    884807      return *this;
    885808    }
    … …  
    889812    /// Make a copy of the given arc.
    890813    DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
    891       arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,
    892                               ArcRefMap, TArc>(tarc, sarc));
     814      _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
     815                          ArcRefMap, TArc>(tarc, sarc));
    893816      return *this;
    894817    }
    … …  
    898821    /// Executes the copies.
    899822    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);
     823      NodeRefMap nodeRefMap(_from);
     824      ArcRefMap arcRefMap(_from);
     825      _graph_utils_bits::DigraphCopySelector<To>::
     826        copy(_to, _from, nodeRefMap, arcRefMap);
     827      for (int i = 0; i < int(_node_maps.size()); ++i) {
     828        _node_maps[i]->copy(_from, nodeRefMap);
     829      }
     830      for (int i = 0; i < int(_arc_maps.size()); ++i) {
     831        _arc_maps[i]->copy(_from, arcRefMap);
    909832      }     
    910833    }
    … …  
    913836
    914837
    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;
     838    const From& _from;
     839    To& _to;
     840
     841    std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
     842    _node_maps;
     843
     844    std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
     845    _arc_maps;
    923846
    924847  };
    … …  
    926849  /// \brief Copy a digraph to another digraph.
    927850  ///
    928   /// Copy a digraph to another digraph.
    929   /// The usage of the function:
    930   ///
     851  /// Copy a digraph to another digraph. The complete usage of the
     852  /// function is detailed in the DigraphCopy class, but a short
     853  /// example shows a basic work:
    931854  ///\code
    932855  /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
    … …  
    944867  }
    945868
    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.
     869  /// \brief Class to copy a graph.
     870  ///
     871  /// Class to copy a graph to another graph (duplicate a graph). The
     872  /// simplest way of using it is through the \c copyGraph() function.
     873  ///
     874  /// This class not just make a copy of a graph, but it can create
     875  /// references and cross references between the nodes, edges and arcs of
     876  /// the two graphs, it can copy maps for use with the newly created
     877  /// graph and copy nodes, edges and arcs.
     878  ///
     879  /// To make a copy from a graph, first an instance of GraphCopy
     880  /// should be created, then the data belongs to the graph should
     881  /// assigned to copy. In the end, the \c run() member should be
     882  /// called.
     883  ///
     884  /// The next code copies a graph with several data:
     885  ///\code
     886  ///  GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
     887  ///  // create a reference for the nodes
     888  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
     889  ///  dc.nodeRef(nr);
     890  ///  // create a cross reference (inverse) for the edges
     891  ///  NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph);
     892  ///  dc.edgeCrossRef(ecr);
     893  ///  // copy an arc map
     894  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
     895  ///  NewGraph::ArcMap<double> namap(new_graph);
     896  ///  dc.arcMap(namap, oamap);
     897  ///  // copy a node
     898  ///  OrigGraph::Node on;
     899  ///  NewGraph::Node nn;
     900  ///  dc.node(nn, on);
     901  ///  // Executions of copy
     902  ///  dc.run();
     903  ///\endcode
    950904  template <typename To, typename From>
    951905  class GraphCopy {
    … …  
    967921
    968922    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) {}
     923      ArcRefMap(const To& to, const From& from,
     924                const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
     925        : _to(to), _from(from),
     926          _edge_ref(edge_ref), _node_ref(node_ref) {}
    973927
    974928      typedef typename From::Arc Key;
    … …  
    977931      Value operator[](const Key& key) const {
    978932        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);
     933          (_from.direction(key) ==
     934           (_node_ref[_from.source(key)] == _to.source(_edge_ref[key])));
     935        return _to.direct(_edge_ref[key], forward);
    983936      }
    984937     
    985       const To& to;
    986       const From& from;
    987       const EdgeRefMap& edge_ref;
    988       const NodeRefMap& node_ref;
     938      const To& _to;
     939      const From& _from;
     940      const EdgeRefMap& _edge_ref;
     941      const NodeRefMap& _node_ref;
    989942    };
    990943
    … …  
    993946
    994947
    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
     948    /// \brief Constructor for the GraphCopy.
     949    ///
     950    /// It copies the content of the \c _from graph into the
     951    /// \c _to graph.
     952    GraphCopy(To& to, const From& from)
     953      : _from(from), _to(to) {}
     954
     955    /// \brief Destructor of the GraphCopy
     956    ///
     957    /// Destructor of the GraphCopy
    1005958    ~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];
     959      for (int i = 0; i < int(_node_maps.size()); ++i) {
     960        delete _node_maps[i];
     961      }
     962      for (int i = 0; i < int(_arc_maps.size()); ++i) {
     963        delete _arc_maps[i];
     964      }
     965      for (int i = 0; i < int(_edge_maps.size()); ++i) {
     966        delete _edge_maps[i];
    1014967      }
    1015968
    … …  
    1021974    template <typename NodeRef>
    1022975    GraphCopy& nodeRef(NodeRef& map) {
    1023       nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node,
    1024                               NodeRefMap, NodeRef>(map));
     976      _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
     977                           NodeRefMap, NodeRef>(map));
    1025978      return *this;
    1026979    }
    … …  
    1032985    template <typename NodeCrossRef>
    1033986    GraphCopy& nodeCrossRef(NodeCrossRef& map) {
    1034       nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,
    1035                               NodeRefMap, NodeCrossRef>(map));
     987      _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
     988                           NodeRefMap, NodeCrossRef>(map));
    1036989      return *this;
    1037990    }
    … …  
    1039992    /// \brief Make copy of the given map.
    1040993    ///
    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
     994    /// Makes copy of the given map for the newly created graph.
     995    /// The new map's key type is the to graph's node type,
     996    /// and the copied map's key type is the from graph's node
    1044997    /// type. 
    1045998    template <typename ToMap, typename FromMap>
    1046999    GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
    1047       nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node,
    1048                               NodeRefMap, ToMap, FromMap>(tmap, map));
     1000      _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
     1001                           NodeRefMap, ToMap, FromMap>(tmap, map));
    10491002      return *this;
    10501003    }
    … …  
    10541007    /// Make a copy of the given node.
    10551008    GraphCopy& node(TNode& tnode, const Node& snode) {
    1056       nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,
    1057                               NodeRefMap, TNode>(tnode, snode));
     1009      _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
     1010                           NodeRefMap, TNode>(tnode, snode));
    10581011      return *this;
    10591012    }
    … …  
    10641017    template <typename ArcRef>
    10651018    GraphCopy& arcRef(ArcRef& map) {
    1066       arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,
    1067                               ArcRefMap, ArcRef>(map));
     1019      _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
     1020                          ArcRefMap, ArcRef>(map));
    10681021      return *this;
    10691022    }
    … …  
    10751028    template <typename ArcCrossRef>
    10761029    GraphCopy& arcCrossRef(ArcCrossRef& map) {
    1077       arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,
    1078                               ArcRefMap, ArcCrossRef>(map));
     1030      _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
     1031                          ArcRefMap, ArcCrossRef>(map));
    10791032      return *this;
    10801033    }
    … …  
    10821035    /// \brief Make copy of the given map.
    10831036    ///
    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
     1037    /// Makes copy of the given map for the newly created graph.
     1038    /// The new map's key type is the to graph's arc type,
     1039    /// and the copied map's key type is the from graph's arc
    10871040    /// type. 
    10881041    template <typename ToMap, typename FromMap>
    10891042    GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
    1090       arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,
    1091                               ArcRefMap, ToMap, FromMap>(tmap, map));
     1043      _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
     1044                          ArcRefMap, ToMap, FromMap>(tmap, map));
    10921045      return *this;
    10931046    }
    … …  
    10971050    /// Make a copy of the given arc.
    10981051    GraphCopy& arc(TArc& tarc, const Arc& sarc) {
    1099       arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,
    1100                               ArcRefMap, TArc>(tarc, sarc));
     1052      _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
     1053                          ArcRefMap, TArc>(tarc, sarc));
    11011054      return *this;
    11021055    }
    … …  
    11071060    template <typename EdgeRef>
    11081061    GraphCopy& edgeRef(EdgeRef& map) {
    1109       edgeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Edge,
    1110                                EdgeRefMap, EdgeRef>(map));
     1062      _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge,
     1063                           EdgeRefMap, EdgeRef>(map));
    11111064      return *this;
    11121065    }
    … …  
    11181071    template <typename EdgeCrossRef>
    11191072    GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
    1120       edgeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,
    1121                                Edge, EdgeRefMap, EdgeCrossRef>(map));
     1073      _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From,
     1074                           Edge, EdgeRefMap, EdgeCrossRef>(map));
    11221075      return *this;
    11231076    }
    … …  
    11251078    /// \brief Make copy of the given map.
    11261079    ///
    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
     1080    /// Makes copy of the given map for the newly created graph.
     1081    /// The new map's key type is the to graph's edge type,
     1082    /// and the copied map's key type is the from graph's edge
    11301083    /// type. 
    11311084    template <typename ToMap, typename FromMap>
    11321085    GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
    1133       edgeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Edge,
    1134                                EdgeRefMap, ToMap, FromMap>(tmap, map));
     1086      _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge,
     1087                           EdgeRefMap, ToMap, FromMap>(tmap, map));
    11351088      return *this;
    11361089    }
    … …  
    11401093    /// Make a copy of the given edge.
    11411094    GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
    1142       edgeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Edge,
    1143                                EdgeRefMap, TEdge>(tedge, sedge));
     1095      _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
     1096                           EdgeRefMap, TEdge>(tedge, sedge));
    11441097      return *this;
    11451098    }
    … …  
    11491102    /// Executes the copies.
    11501103    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);
     1104      NodeRefMap nodeRefMap(_from);
     1105      EdgeRefMap edgeRefMap(_from);
     1106      ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
     1107      _graph_utils_bits::GraphCopySelector<To>::
     1108        copy(_to, _from, nodeRefMap, edgeRefMap);
     1109      for (int i = 0; i < int(_node_maps.size()); ++i) {
     1110        _node_maps[i]->copy(_from, nodeRefMap);
     1111      }
     1112      for (int i = 0; i < int(_edge_maps.size()); ++i) {
     1113        _edge_maps[i]->copy(_from, edgeRefMap);
     1114      }
     1115      for (int i = 0; i < int(_arc_maps.size()); ++i) {
     1116        _arc_maps[i]->copy(_from, arcRefMap);
    11641117      }
    11651118    }
    … …  
    11671120  private:
    11681121   
    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;
     1122    const From& _from;
     1123    To& _to;
     1124
     1125    std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
     1126    _node_maps;
     1127
     1128    std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
     1129    _arc_maps;
     1130
     1131    std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
     1132    _edge_maps;
    11801133
    11811134  };
    11821135
    1183   /// \brief Copy an graph to another digraph.
    1184   ///
    1185   /// Copy an graph to another digraph.
    1186   /// The usage of the function:
    1187   ///
     1136  /// \brief Copy a graph to another graph.
     1137  ///
     1138  /// Copy a graph to another graph. The complete usage of the
     1139  /// function is detailed in the GraphCopy class, but a short
     1140  /// example shows a basic work:
    11881141  ///\code
    11891142  /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
    … …  
    11911144  ///
    11921145  /// 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.
     1146  /// nodes of the \c from graph to the nodes of the \c to graph and
     1147  /// \c ecr will contain the mapping from the arcs of the \c to graph
     1148  /// to the arcs of the \c from graph.
    11961149  ///
    11971150  /// \see GraphCopy
    … …  
    12021155  }
    12031156
    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 
    15701157  /// @}
    15711158
    1572   /// \addtogroup digraph_maps
     1159  /// \addtogroup graph_maps
    15731160  /// @{
    15741161
    1575   /// Provides an immutable and unique id for each item in the digraph.
     1162  /// Provides an immutable and unique id for each item in the graph.
    15761163
    15771164  /// 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:
     1165  /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
    15791166  /// different items (nodes) get different ids <li>\b immutable: the id of an
    15801167  /// item (node) does not change (even if you delete other nodes).  </ul>
    15811168  /// 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>
     1169  /// the items stored in the graph. This map can be inverted with its member
     1170  /// class \c InverseMap or with the \c operator() member.
     1171  ///
     1172  template <typename _Graph, typename _Item>
    15861173  class IdMap {
    15871174  public:
    1588     typedef _Digraph Digraph;
     1175    typedef _Graph Graph;
    15891176    typedef int Value;
    15901177    typedef _Item Item;
    … …  
    15941181    ///
    15951182    /// Constructor of the map.
    1596     explicit IdMap(const Digraph& _digraph) : digraph(&_digraph) {}
     1183    explicit IdMap(const Graph& graph) : _graph(&graph) {}
    15971184
    15981185    /// \brief Gives back the \e id of the item.
    15991186    ///
    16001187    /// Gives back the immutable and unique \e id of the item.
    1601     int operator[](const Item& item) const { return digraph->id(item);}
     1188    int operator[](const Item& item) const { return _graph->id(item);}
    16021189
    16031190    /// \brief Gives back the item by its id.
    16041191    ///
    16051192    /// Gives back the item by its id.
    1606     Item operator()(int id) { return digraph->fromId(id, Item()); }
     1193    Item operator()(int id) { return _graph->fromId(id, Item()); }
    16071194
    16081195  private:
    1609     const Digraph* digraph;
     1196    const Graph* _graph;
    16101197
    16111198  public:
    … …  
    16211208      ///
    16221209      /// Constructor for creating an id-to-item map.
    1623       explicit InverseMap(const Digraph& _digraph) : digraph(&_digraph) {}
     1210      explicit InverseMap(const Graph& graph) : _graph(&graph) {}
    16241211
    16251212      /// \brief Constructor.
    16261213      ///
    16271214      /// Constructor for creating an id-to-item map.
    1628       explicit InverseMap(const IdMap& idMap) : digraph(idMap.digraph) {}
     1215      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
    16291216
    16301217      /// \brief Gives back the given item from its id.
    … …  
    16321219      /// Gives back the given item from its id.
    16331220      ///
    1634       Item operator[](int id) const { return digraph->fromId(id, Item());}
     1221      Item operator[](int id) const { return _graph->fromId(id, Item());}
    16351222
    16361223    private:
    1637       const Digraph* digraph;
     1224      const Graph* _graph;
    16381225    };
    16391226
    … …  
    16411228    ///
    16421229    /// Gives back the inverse of the IdMap.
    1643     InverseMap inverse() const { return InverseMap(*digraph);}
     1230    InverseMap inverse() const { return InverseMap(*_graph);}
    16441231
    16451232  };
    16461233
    16471234 
    1648   /// \brief General invertable digraph-map type.
    1649 
    1650   /// This type provides simple invertable digraph-maps.
     1235  /// \brief General invertable graph-map type.
     1236
     1237  /// This type provides simple invertable graph-maps.
    16511238  /// The InvertableMap wraps an arbitrary ReadWriteMap
    16521239  /// and if a key is set to a new value then store it
    … …  
    16561243  /// with stl compatible forward iterator.
    16571244  ///
    1658   /// \param _Digraph The digraph type.
    1659   /// \param _Item The item type of the digraph.
     1245  /// \param _Graph The graph type.
     1246  /// \param _Item The item type of the graph.
    16601247  /// \param _Value The value type of the map.
    16611248  ///
    16621249  /// \see IterableValueMap
    1663   template <typename _Digraph, typename _Item, typename _Value>
    1664   class InvertableMap : protected DefaultMap<_Digraph, _Item, _Value> {
     1250  template <typename _Graph, typename _Item, typename _Value>
     1251  class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
    16651252  private:
    16661253   
    1667     typedef DefaultMap<_Digraph, _Item, _Value> Map;
    1668     typedef _Digraph Digraph;
     1254    typedef DefaultMap<_Graph, _Item, _Value> Map;
     1255    typedef _Graph Graph;
    16691256
    16701257    typedef std::map<_Value, _Item> Container;
    1671     Container invMap;   
     1258    Container _inv_map;   
    16721259
    16731260  public:
    … …  
    16821269    /// \brief Constructor.
    16831270    ///
    1684     /// Construct a new InvertableMap for the digraph.
    1685     ///
    1686     explicit InvertableMap(const Digraph& digraph) : Map(digraph) {}
     1271    /// Construct a new InvertableMap for the graph.
     1272    ///
     1273    explicit InvertableMap(const Graph& graph) : Map(graph) {}
    16871274
    16881275    /// \brief Forward iterator for values.
    … …  
    17261313    /// range.
    17271314    ValueIterator beginValue() const {
    1728       return ValueIterator(invMap.begin());
     1315      return ValueIterator(_inv_map.begin());
    17291316    }
    17301317
    … …  
    17361323    /// range.
    17371324    ValueIterator endValue() const {
    1738       return ValueIterator(invMap.end());
     1325      return ValueIterator(_inv_map.end());
    17391326    }
    17401327   
    … …  
    17441331    void set(const Key& key, const Value& val) {
    17451332      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);
     1333      typename Container::iterator it = _inv_map.find(oldval);
     1334      if (it != _inv_map.end() && it->second == key) {
     1335        _inv_map.erase(it);
    17491336      }     
    1750       invMap.insert(make_pair(val, key));
     1337      _inv_map.insert(make_pair(val, key));
    17511338      Map::set(key, val);
    17521339    }
    … …  
    17641351    /// Gives back the item by its value.
    17651352    Key operator()(const Value& key) const {
    1766       typename Container::const_iterator it = invMap.find(key);
    1767       return it != invMap.end() ? it->second : INVALID;
     1353      typename Container::const_iterator it = _inv_map.find(key);
     1354      return it != _inv_map.end() ? it->second : INVALID;
    17681355    }
    17691356
    … …  
    17761363    virtual void erase(const Key& key) {
    17771364      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);
     1365      typename Container::iterator it = _inv_map.find(val);
     1366      if (it != _inv_map.end() && it->second == key) {
     1367        _inv_map.erase(it);
    17811368      }
    17821369      Map::erase(key);
    … …  
    17901377      for (int i = 0; i < int(keys.size()); ++i) {
    17911378        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);
     1379        typename Container::iterator it = _inv_map.find(val);
     1380        if (it != _inv_map.end() && it->second == keys[i]) {
     1381          _inv_map.erase(it);
    17951382        }
    17961383      }
    … …  
    18031390    /// \c AlterationNotifier.
    18041391    virtual void clear() {
    1805       invMap.clear();
     1392      _inv_map.clear();
    18061393      Map::clear();
    18071394    }
    … …  
    18181405      ///
    18191406      /// Constructor of the InverseMap.
    1820       explicit InverseMap(const InvertableMap& _inverted)
    1821         : inverted(_inverted) {}
     1407      explicit InverseMap(const InvertableMap& inverted)
     1408        : _inverted(inverted) {}
    18221409
    18231410      /// The value type of the InverseMap.
    … …  
    18311418      /// what was last assigned to the value.
    18321419      Value operator[](const Key& key) const {
    1833         return inverted(key);
     1420        return _inverted(key);
    18341421      }
    18351422     
    18361423    private:
    1837       const InvertableMap& inverted;
     1424      const InvertableMap& _inverted;
    18381425    };
    18391426
    … …  
    18501437
    18511438  /// \brief Provides a mutable, continuous and unique descriptor for each
    1852   /// item in the digraph.
     1439  /// item in the graph.
    18531440  ///
    18541441  /// The DescriptorMap class provides a unique and continuous (but mutable)
    18551442  /// 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
     1443  /// graph. This id is <ul><li>\b unique: different items (nodes) get
    18571444  /// different ids <li>\b continuous: the range of the ids is the set of
    18581445  /// integers between 0 and \c n-1, where \c n is the number of the items of
    18591446  /// this type (e.g. nodes) (so the id of a node can change if you delete an
    18601447  /// 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.
     1448  /// with its member class \c InverseMap, or with the \c operator() member.
     1449  ///
     1450  /// \param _Graph The graph class the \c DescriptorMap belongs to.
    18641451  /// \param _Item The Item is the Key of the Map. It may be Node, Arc or
    18651452  /// Edge.
    1866   template <typename _Digraph, typename _Item>
    1867   class DescriptorMap : protected DefaultMap<_Digraph, _Item, int> {
     1453  template <typename _Graph, typename _Item>
     1454  class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
    18681455
    18691456    typedef _Item Item;
    1870     typedef DefaultMap<_Digraph, _Item, int> Map;
     1457    typedef DefaultMap<_Graph, _Item, int> Map;
    18711458
    18721459  public:
    1873     /// The digraph class of DescriptorMap.
    1874     typedef _Digraph Digraph;
     1460    /// The graph class of DescriptorMap.
     1461    typedef _Graph Graph;
    18751462
    18761463    /// The key type of DescriptorMap (Node, Arc, Edge).
    … …  
    18821469    ///
    18831470    /// Constructor for descriptor map.
    1884     explicit DescriptorMap(const Digraph& _digraph) : Map(_digraph) {
     1471    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
    18851472      Item it;
    18861473      const typename Map::Notifier* nf = Map::notifier();
    18871474      for (nf->first(it); it != INVALID; nf->next(it)) {
    1888         Map::set(it, invMap.size());
    1889         invMap.push_back(it);   
     1475        Map::set(it, _inv_map.size());
     1476        _inv_map.push_back(it);
    18901477      }     
    18911478    }
    … …  
    18991486    virtual void add(const Item& item) {
    19001487      Map::add(item);
    1901       Map::set(item, invMap.size());
    1902       invMap.push_back(item);
     1488      Map::set(item, _inv_map.size());
     1489      _inv_map.push_back(item);
    19031490    }
    19041491
    … …  
    19101497      Map::add(items);
    19111498      for (int i = 0; i < int(items.size()); ++i) {
    1912         Map::set(items[i], invMap.size());
    1913         invMap.push_back(items[i]);
     1499        Map::set(items[i], _inv_map.size());
     1500        _inv_map.push_back(items[i]);
    19141501      }
    19151502    }
    … …  
    19201507    /// \c AlterationNotifier.
    19211508    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();
     1509      Map::set(_inv_map.back(), Map::operator[](item));
     1510      _inv_map[Map::operator[](item)] = _inv_map.back();
     1511      _inv_map.pop_back();
    19251512      Map::erase(item);
    19261513    }
    … …  
    19321519    virtual void erase(const std::vector<Item>& items) {
    19331520      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();
     1521        Map::set(_inv_map.back(), Map::operator[](items[i]));
     1522        _inv_map[Map::operator[](items[i])] = _inv_map.back();
     1523        _inv_map.pop_back();
    19371524      }
    19381525      Map::erase(items);
    … …  
    19481535      const typename Map::Notifier* nf = Map::notifier();
    19491536      for (nf->first(it); it != INVALID; nf->next(it)) {
    1950         Map::set(it, invMap.size());
    1951         invMap.push_back(it);   
     1537        Map::set(it, _inv_map.size());
     1538        _inv_map.push_back(it);
    19521539      }     
    19531540    }
    … …  
    19581545    /// \c AlterationNotifier.
    19591546    virtual void clear() {
    1960       invMap.clear();
     1547      _inv_map.clear();
    19611548      Map::clear();
    19621549    }
    … …  
    19681555    /// Returns the maximal value plus one in the map.
    19691556    unsigned int size() const {
    1970       return invMap.size();
     1557      return _inv_map.size();
    19711558    }
    19721559
    … …  
    19781565      int qi = Map::operator[](q);
    19791566      Map::set(p, qi);
    1980       invMap[qi] = p;
     1567      _inv_map[qi] = p;
    19811568      Map::set(q, pi);
    1982       invMap[pi] = q;
     1569      _inv_map[pi] = q;
    19831570    }
    19841571
    … …  
    19941581    /// Gives back th item by its descriptor.
    19951582    Item operator()(int id) const {
    1996       return invMap[id];
     1583      return _inv_map[id];
    19971584    }
    19981585   
    … …  
    20001587
    20011588    typedef std::vector<Item> Container;
    2002     Container invMap;
     1589    Container _inv_map;
    20031590
    20041591  public:
    … …  
    20111598      ///
    20121599      /// Constructor of the InverseMap.
    2013       explicit InverseMap(const DescriptorMap& _inverted)
    2014         : inverted(_inverted) {}
     1600      explicit InverseMap(const DescriptorMap& inverted)
     1601        : _inverted(inverted) {}
    20151602
    20161603
    … …  
    20251612      /// that the descriptor belongs to currently.
    20261613      Value operator[](const Key& key) const {
    2027         return inverted(key);
     1614        return _inverted(key);
    20281615      }
    20291616
    … …  
    20321619      /// Returns the size of the map.
    20331620      unsigned int size() const {
    2034         return inverted.size();
     1621        return _inverted.size();
    20351622      }
    20361623     
    20371624    private:
    2038       const DescriptorMap& inverted;
     1625      const DescriptorMap& _inverted;
    20391626    };
    20401627
    … …  
    20631650    /// Constructor
    20641651    /// \param _digraph The digraph that the map belongs to.
    2065     explicit SourceMap(const Digraph& _digraph) : digraph(_digraph) {}
     1652    explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
    20661653
    20671654    /// \brief The subscript operator.
    … …  
    20711658    /// \return The source of the arc
    20721659    Value operator[](const Key& arc) const {
    2073       return digraph.source(arc);
     1660      return _digraph.source(arc);
    20741661    }
    20751662
    20761663  private:
    2077     const Digraph& digraph;
     1664    const Digraph& _digraph;
    20781665  };
    20791666
    … …  
    21031690    /// Constructor
    21041691    /// \param _digraph The digraph that the map belongs to.
    2105     explicit TargetMap(const Digraph& _digraph) : digraph(_digraph) {}
     1692    explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
    21061693
    21071694    /// \brief The subscript operator.
    … …  
    21111698    /// \return The target of the arc
    21121699    Value operator[](const Key& e) const {
    2113       return digraph.target(e);
     1700      return _digraph.target(e);
    21141701    }
    21151702
    21161703  private:
    2117     const Digraph& digraph;
     1704    const Digraph& _digraph;
    21181705  };
    21191706
    … …  
    21321719  /// \see BackwardMap
    21331720  /// \author Balazs Dezso
    2134   template <typename Digraph>
     1721  template <typename Graph>
    21351722  class ForwardMap {
    21361723  public:
    21371724
    2138     typedef typename Digraph::Arc Value;
    2139     typedef typename Digraph::Edge Key;
     1725    typedef typename Graph::Arc Value;
     1726    typedef typename Graph::Edge Key;
    21401727
    21411728    /// \brief Constructor
    21421729    ///
    21431730    /// Constructor
    2144     /// \param _digraph The digraph that the map belongs to.
    2145     explicit ForwardMap(const Digraph& _digraph) : digraph(_digraph) {}
     1731    /// \param _graph The graph that the map belongs to.
     1732    explicit ForwardMap(const Graph& graph) : _graph(graph) {}
    21461733
    21471734    /// \brief The subscript operator.
    … …  
    21511738    /// \return The "forward" directed arc view of edge
    21521739    Value operator[](const Key& key) const {
    2153       return digraph.direct(key, true);
     1740      return _graph.direct(key, true);
    21541741    }
    21551742
    21561743  private:
    2157     const Digraph& digraph;
     1744    const Graph& _graph;
    21581745  };
    21591746
    … …  
    21621749  /// This function just returns an \ref ForwardMap class.
    21631750  /// \relates ForwardMap
    2164   template <typename Digraph>
    2165   inline ForwardMap<Digraph> forwardMap(const Digraph& digraph) {
    2166     return ForwardMap<Digraph>(digraph);
     1751  template <typename Graph>
     1752  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
     1753    return ForwardMap<Graph>(graph);
    21671754  }
    21681755
    … …  
    21721759  /// \see ForwardMap
    21731760  /// \author Balazs Dezso
    2174   template <typename Digraph>
     1761  template <typename Graph>
    21751762  class BackwardMap {
    21761763  public:
    21771764
    2178     typedef typename Digraph::Arc Value;
    2179     typedef typename Digraph::Edge Key;
     1765    typedef typename Graph::Arc Value;
     1766    typedef typename Graph::Edge Key;
    21801767
    21811768    /// \brief Constructor
    21821769    ///
    21831770    /// Constructor
    2184     /// \param _digraph The digraph that the map belongs to.
    2185     explicit BackwardMap(const Digraph& _digraph) : digraph(_digraph) {}
     1771    /// \param _graph The graph that the map belongs to.
     1772    explicit BackwardMap(const Graph& graph) : _graph(graph) {}
    21861773
    21871774    /// \brief The subscript operator.
    … …  
    21911778    /// \return The "backward" directed arc view of edge
    21921779    Value operator[](const Key& key) const {
    2193       return digraph.direct(key, false);
     1780      return _graph.direct(key, false);
    21941781    }
    21951782
    21961783  private:
    2197     const Digraph& digraph;
     1784    const Graph& _graph;
    21981785  };
    21991786
    … …  
    22021789  /// This function just returns a \ref BackwardMap class.
    22031790  /// \relates BackwardMap
    2204   template <typename Digraph>
    2205   inline BackwardMap<Digraph> backwardMap(const Digraph& digraph) {
    2206     return BackwardMap<Digraph>(digraph);
     1791  template <typename Graph>
     1792  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
     1793    return BackwardMap<Graph>(graph);
    22071794  }
    22081795
    … …  
    22211808    ///
    22221809    /// Contructor of the map
    2223     explicit PotentialDifferenceMap(const Digraph& _digraph,
    2224                                     const NodeMap& _potential)
    2225       : digraph(_digraph), potential(_potential) {}
     1810    explicit PotentialDifferenceMap(const Digraph& digraph,
     1811                                    const NodeMap& potential)
     1812      : _digraph(digraph), _potential(potential) {}
    22261813
    22271814    /// \brief Const subscription operator
    … …  
    22291816    /// Const subscription operator
    22301817    Value operator[](const Key& arc) const {
    2231       return potential[digraph.target(arc)] - potential[digraph.source(arc)];
     1818      return _potential[_digraph.target(arc)] -
     1819        _potential[_digraph.source(arc)];
    22321820    }
    22331821
    22341822  private:
    2235     const Digraph& digraph;
    2236     const NodeMap& potential;
     1823    const Digraph& _digraph;
     1824    const NodeMap& _potential;
    22371825  };
    22381826
    … …  
    22751863    typedef typename Digraph::Node Key;
    22761864
    2277     typedef typename ItemSetTraits<_Digraph, typename _Digraph::Arc>
     1865    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
    22781866    ::ItemNotifier::ObserverBase Parent;
    22791867
    22801868  private:
    22811869
    2282     class AutoNodeMap : public DefaultMap<_Digraph, Key, int> {
     1870    class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
    22831871    public:
    22841872
    2285       typedef DefaultMap<_Digraph, Key, int> Parent;
    2286       typedef typename Parent::Digraph Digraph;
     1873      typedef DefaultMap<Digraph, Key, int> Parent;
    22871874
    22881875      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
    … …  
    23151902    ///
    23161903    /// Constructor for creating in-degree map.
    2317     explicit InDegMap(const Digraph& _digraph) : digraph(_digraph), deg(_digraph) {
    2318       Parent::attach(digraph.notifier(typename _Digraph::Arc()));
     1904    explicit InDegMap(const Digraph& digraph)
     1905      : _digraph(digraph), _deg(digraph) {
     1906      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
    23191907     
    2320       for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
    2321         deg[it] = countInArcs(digraph, it);
     1908      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
     1909        _deg[it] = countInArcs(_digraph, it);
    23221910      }
    23231911    }
    … …  
    23251913    /// Gives back the in-degree of a Node.
    23261914    int operator[](const Key& key) const {
    2327       return deg[key];
     1915      return _deg[key];
    23281916    }
    23291917
    … …  
    23331921
    23341922    virtual void add(const Arc& arc) {
    2335       ++deg[digraph.target(arc)];
     1923      ++_deg[_digraph.target(arc)];
    23361924    }
    23371925
    23381926    virtual void add(const std::vector<Arc>& arcs) {
    23391927      for (int i = 0; i < int(arcs.size()); ++i) {
    2340         ++deg[digraph.target(arcs[i])];
     1928        ++_deg[_digraph.target(arcs[i])];
    23411929      }
    23421930    }
    23431931
    23441932    virtual void erase(const Arc& arc) {
    2345       --deg[digraph.target(arc)];
     1933      --_deg[_digraph.target(arc)];
    23461934    }
    23471935
    23481936    virtual void erase(const std::vector<Arc>& arcs) {
    23491937      for (int i = 0; i < int(arcs.size()); ++i) {
    2350         --deg[digraph.target(arcs[i])];
     1938        --_deg[_digraph.target(arcs[i])];
    23511939      }
    23521940    }
    23531941
    23541942    virtual void build() {
    2355       for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
    2356         deg[it] = countInArcs(digraph, it);
     1943      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
     1944        _deg[it] = countInArcs(_digraph, it);
    23571945      }     
    23581946    }
    23591947
    23601948    virtual void clear() {
    2361       for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
    2362         deg[it] = 0;
     1949      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
     1950        _deg[it] = 0;
    23631951      }
    23641952    }
    23651953  private:
    23661954   
    2367     const _Digraph& digraph;
    2368     AutoNodeMap deg;
     1955    const Digraph& _digraph;
     1956    AutoNodeMap _deg;
    23691957  };
    23701958
    … …  
    23921980
    23931981  public:
    2394 
    2395     typedef typename ItemSetTraits<_Digraph, typename _Digraph::Arc>
    2396     ::ItemNotifier::ObserverBase Parent;
    23971982   
    23981983    typedef _Digraph Digraph;
    … …  
    24001985    typedef typename Digraph::Node Key;
    24011986
     1987    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
     1988    ::ItemNotifier::ObserverBase Parent;
     1989
    24021990  private:
    24031991
    2404     class AutoNodeMap : public DefaultMap<_Digraph, Key, int> {
     1992    class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
    24051993    public:
    24061994
    2407       typedef DefaultMap<_Digraph, Key, int> Parent;
    2408       typedef typename Parent::Digraph Digraph;
     1995      typedef DefaultMap<Digraph, Key, int> Parent;
    24091996
    24101997      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
    … …  
    24352022    ///
    24362023    /// Constructor for creating out-degree map.
    2437     explicit OutDegMap(const Digraph& _digraph) : digraph(_digraph), deg(_digraph) {
    2438       Parent::attach(digraph.notifier(typename _Digraph::Arc()));
     2024    explicit OutDegMap(const Digraph& digraph)
     2025      : _digraph(digraph), _deg(digraph) {
     2026      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
    24392027     
    2440       for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
    2441         deg[it] = countOutArcs(digraph, it);
     2028      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
     2029        _deg[it] = countOutArcs(_digraph, it);
    24422030      }
    24432031    }
    … …  
    24452033    /// Gives back the out-degree of a Node.
    24462034    int operator[](const Key& key) const {
    2447       return deg[key];
     2035      return _deg[key];
    24482036    }
    24492037
    … …  
    24532041
    24542042    virtual void add(const Arc& arc) {
    2455       ++deg[digraph.source(arc)];
     2043      ++_deg[_digraph.source(arc)];
    24562044    }
    24572045
    24582046    virtual void add(const std::vector<Arc>& arcs) {
    24592047      for (int i = 0; i < int(arcs.size()); ++i) {
    2460         ++deg[digraph.source(arcs[i])];
     2048        ++_deg[_digraph.source(arcs[i])];
    24612049      }
    24622050    }
    24632051
    24642052    virtual void erase(const Arc& arc) {
    2465       --deg[digraph.source(arc)];
     2053      --_deg[_digraph.source(arc)];
    24662054    }
    24672055
    24682056    virtual void erase(const std::vector<Arc>& arcs) {
    24692057      for (int i = 0; i < int(arcs.size()); ++i) {
    2470         --deg[digraph.source(arcs[i])];
     2058        --_deg[_digraph.source(arcs[i])];
    24712059      }
    24722060    }
    24732061
    24742062    virtual void build() {
    2475       for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
    2476         deg[it] = countOutArcs(digraph, it);
     2063      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
     2064        _deg[it] = countOutArcs(_digraph, it);
    24772065      }     
    24782066    }
    24792067
    24802068    virtual void clear() {
    2481       for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
    2482         deg[it] = 0;
     2069      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
     2070        _deg[it] = 0;
    24832071      }
    24842072    }
    24852073  private:
    24862074   
    2487     const _Digraph& digraph;
    2488     AutoNodeMap deg;
     2075    const Digraph& _digraph;
     2076    AutoNodeMap _deg;
    24892077  };
    24902078
    … …  
    25012089  ///
    25022090  ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
    2503   ///digraph do not changed so frequently.
     2091  ///digraph is not changed so frequently.
    25042092  ///
    25052093  ///This class uses a self-adjusting binary search tree, Sleator's
    … …  
    25212109    ::ItemNotifier::ObserverBase Parent;
    25222110
    2523     GRAPH_TYPEDEFS(typename G);
     2111    TEMPLATE_DIGRAPH_TYPEDEFS(G);
    25242112    typedef G Digraph;
    25252113
    … …  
    28362424    Arc operator()(Node s, Node t) const
    28372425    {
    2838       Arc e = _head[s];
     2426      Arc a = _head[s];
    28392427      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);
     2428        if (_g.target(a) == t) {
     2429          const_cast<DynArcLookUp&>(*this).splay(a);
     2430          return a;
     2431        } else if (t < _g.target(a)) {
     2432          if (_left[a] == INVALID) {
     2433            const_cast<DynArcLookUp&>(*this).splay(a);
    28462434            return INVALID;
    28472435          } else {
    2848             e = _left[e];
     2436            a = _left[a];
    28492437          }
    28502438        } else  {
    2851           if (_right[e] == INVALID) {
    2852             const_cast<DynArcLookUp&>(*this).splay(e);
     2439          if (_right[a] == INVALID) {
     2440            const_cast<DynArcLookUp&>(*this).splay(a);
    28532441            return INVALID;
    28542442          } else {
    2855             e = _right[e];
     2443            a = _right[a];
    28562444          }
    28572445        }
    … …  
    28702458    Arc findFirst(Node s, Node t) const
    28712459    {
    2872       Arc e = _head[s];
     2460      Arc a = _head[s];
    28732461      Arc r = INVALID;
    28742462      while (true) {
    2875         if (_g.target(e) < t) {
    2876           if (_right[e] == INVALID) {
    2877             const_cast<DynArcLookUp&>(*this).splay(e);
     2463        if (_g.target(a) < t) {
     2464          if (_right[a] == INVALID) {
     2465            const_cast<DynArcLookUp&>(*this).splay(a);
    28782466            return r;
    28792467          } else {
    2880             e = _right[e];
     2468            a = _right[a];
    28812469          }
    28822470        } else {
    2883           if (_g.target(e) == t) {
    2884             r = e;
     2471          if (_g.target(a) == t) {
     2472            r = a;
    28852473          }
    2886           if (_left[e] == INVALID) {
    2887             const_cast<DynArcLookUp&>(*this).splay(e);
     2474          if (_left[a] == INVALID) {
     2475            const_cast<DynArcLookUp&>(*this).splay(a);
    28882476            return r;
    28892477          } else {
    2890             e = _left[e];
     2478            a = _left[a];
    28912479          }
    28922480        }
    … …  
    29072495    ///operation then the amorized time bound can not be guaranteed.
    29082496#ifdef DOXYGEN
    2909     Arc findNext(Node s, Node t, Arc e) const
     2497    Arc findNext(Node s, Node t, Arc a) const
    29102498#else
    2911     Arc findNext(Node, Node t, Arc e) const
     2499    Arc findNext(Node, Node t, Arc a) const
    29122500#endif
    29132501    {
    2914       if (_right[e] != INVALID) {
    2915         e = _right[e];
    2916         while (_left[e] != INVALID) {
    2917           e = _left[e];
     2502      if (_right[a] != INVALID) {
     2503        a = _right[a];
     2504        while (_left[a] != INVALID) {
     2505          a = _left[a];
    29182506        }
    2919         const_cast<DynArcLookUp&>(*this).splay(e);
     2507        const_cast<DynArcLookUp&>(*this).splay(a);
    29202508      } else {
    2921         while (_parent[e] != INVALID && _right[_parent[e]] ==  e) {
    2922           e = _parent[e];
     2509        while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
     2510          a = _parent[a];
    29232511        }
    2924         if (_parent[e] == INVALID) {
     2512        if (_parent[a] == INVALID) {
    29252513          return INVALID;
    29262514        } else {
    2927           e = _parent[e];
    2928           const_cast<DynArcLookUp&>(*this).splay(e);
     2515          a = _parent[a];
     2516          const_cast<DynArcLookUp&>(*this).splay(a);
    29292517        }
    29302518      }
    2931       if (_g.target(e) == t) return e;
     2519      if (_g.target(a) == t) return a;
    29322520      else return INVALID;   
    29332521    }
    … …  
    29582546  {
    29592547  public:
    2960     GRAPH_TYPEDEFS(typename G);
     2548    TEMPLATE_DIGRAPH_TYPEDEFS(G);
    29612549    typedef G Digraph;
    29622550
    … …  
    30752663    using ArcLookUp<G>::_head;
    30762664
    3077     GRAPH_TYPEDEFS(typename G);
     2665    TEMPLATE_DIGRAPH_TYPEDEFS(G);
    30782666    typedef G Digraph;
    30792667   

  • lemon/lgf_reader.h

    r127 r148  
    303303
    304304    typedef _Digraph Digraph;
    305     GRAPH_TYPEDEFS(typename Digraph);
     305    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    306306   
    307307  private:

  • lemon/lgf_writer.h

    r127 r148  
    238238
    239239    typedef _Digraph Digraph;
    240     GRAPH_TYPEDEFS(typename Digraph);
     240    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    241241   
    242242  private:

  • lemon/list_graph.h

    r73 r149  
    153153    static Arc arcFromId(int id) { return Arc(id);}
    154154
     155    bool valid(Node n) const {
     156      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
     157        nodes[n.id].prev != -2;
     158    }
     159
     160    bool valid(Arc a) const {
     161      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
     162        arcs[a.id].prev_in != -2;
     163    }
     164
    155165    Node addNode() {     
    156166      int n;
    … …  
    220230      nodes[n].next = first_free_node;
    221231      first_free_node = n;
     232      nodes[n].prev = -2;
    222233
    223234    }
    … …  
    248259     
    249260      arcs[n].next_in = first_free_arc;
    250       first_free_arc = n;     
    251 
     261      first_free_arc = n;
     262      arcs[n].prev_in = -2;
    252263    }
    253264
    … …  
    350361      return Parent::addArc(s, t);
    351362    }
     363
     364    /// Node validity check
     365
     366    /// This function gives back true if the given node is valid,
     367    /// ie. it is a real node of the graph. 
     368    ///
     369    /// \warning A Node pointing to a removed item
     370    /// could become valid again later if new nodes are
     371    /// added to the graph.
     372    bool valid(Node n) const { return Parent::valid(n); }
     373
     374    /// Arc validity check
     375
     376    /// This function gives back true if the given arc is valid,
     377    /// ie. it is a real arc of the graph. 
     378    ///
     379    /// \warning An Arc pointing to a removed item
     380    /// could become valid again later if new nodes are
     381    /// added to the graph.
     382    bool valid(Arc a) const { return Parent::valid(a); }
    352383
    353384    /// Change the target of \c e to \c n
    … …  
    946977    static Edge edgeFromId(int id) { return Edge(id);}
    947978
     979    bool valid(Node n) const {
     980      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
     981        nodes[n.id].prev != -2;
     982    }
     983
     984    bool valid(Arc a) const {
     985      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
     986        arcs[a.id].prev_out != -2;
     987    }
     988
     989    bool valid(Edge e) const {
     990      return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
     991        arcs[2 * e.id].prev_out != -2;
     992    }
     993
    948994    Node addNode() {     
    949995      int n;
    … …  
    10141060      nodes[n].next = first_free_node;
    10151061      first_free_node = n;
    1016 
     1062      nodes[n].prev = -2;
    10171063    }
    10181064   
    … …  
    10421088      arcs[n].next_out = first_free_arc;
    10431089      first_free_arc = n;     
     1090      arcs[n].prev_out = -2;
     1091      arcs[n | 1].prev_out = -2;
    10441092
    10451093    }
    … …  
    11581206      return Parent::addEdge(s, t);
    11591207    }
     1208    /// Node validity check
     1209
     1210    /// This function gives back true if the given node is valid,
     1211    /// ie. it is a real node of the graph. 
     1212    ///
     1213    /// \warning A Node pointing to a removed item
     1214    /// could become valid again later if new nodes are
     1215    /// added to the graph.
     1216    bool valid(Node n) const { return Parent::valid(n); }
     1217    /// Arc validity check
     1218
     1219    /// This function gives back true if the given arc is valid,
     1220    /// ie. it is a real arc of the graph. 
     1221    ///
     1222    /// \warning An Arc pointing to a removed item
     1223    /// could become valid again later if new edges are
     1224    /// added to the graph.
     1225    bool valid(Arc a) const { return Parent::valid(a); }
     1226    /// Edge validity check
     1227
     1228    /// This function gives back true if the given edge is valid,
     1229    /// ie. it is a real arc of the graph. 
     1230    ///
     1231    /// \warning A Edge pointing to a removed item
     1232    /// could become valid again later if new edges are
     1233    /// added to the graph.
     1234    bool valid(Edge e) const { return Parent::valid(e); }
    11601235    /// \brief Change the source of \c e to \c n
    11611236    ///

  • lemon/path.h

    r100 r144  
    904904
    905905    template <typename Path, typename Enable = void>
    906     struct RevTagIndicator {
     906    struct RevPathTagIndicator {
    907907      static const bool value = false;
    908908    };
    909909
    910     template <typename Digraph>
    911     struct RevTagIndicator<
    912       Digraph,
    913       typename enable_if<typename Digraph::RevTag, void>::type
     910    template <typename Path>
     911    struct RevPathTagIndicator<
     912      Path,
     913      typename enable_if<typename Path::RevPathTag, void>::type
     914      > {
     915      static const bool value = true;
     916    };
     917
     918    template <typename Path, typename Enable = void>
     919    struct BuildTagIndicator {
     920      static const bool value = false;
     921    };
     922
     923    template <typename Path>
     924    struct BuildTagIndicator<
     925      Path,
     926      typename enable_if<typename Path::BuildTag, void>::type
    914927    > {
    915928      static const bool value = true;
    … …  
    917930
    918931    template <typename Target, typename Source,
    919               typename BuildEnable = void, typename RevEnable = void>
     932              bool buildEnable = BuildTagIndicator<Target>::value,
     933              bool revEnable = RevPathTagIndicator<Source>::value>
    920934    struct PathCopySelector {
    921935      static void copy(Target& target, const Source& source) {
    … …  
    927941    };
    928942
    929     template <typename Target, typename Source, typename BuildEnable>
    930     struct PathCopySelector<
    931       Target, Source, BuildEnable,
    932       typename enable_if<typename Source::RevPathTag, void>::type> {
     943    template <typename Target, typename Source>
     944    struct PathCopySelector<Target, Source, false, true> {
    933945      static void copy(Target& target, const Source& source) {
    934946        target.clear();
    … …  
    939951    };
    940952
    941     template <typename Target, typename Source, typename RevEnable>
    942     struct PathCopySelector<
    943       Target, Source,
    944       typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
     953    template <typename Target, typename Source>
     954    struct PathCopySelector<Target, Source, true, false> {
    945955      static void copy(Target& target, const Source& source) {
    946956        target.clear();
    … …  
    950960
    951961    template <typename Target, typename Source>
    952     struct PathCopySelector<
    953       Target, Source,
    954       typename enable_if<typename Target::BuildTag, void>::type,
    955       typename enable_if<typename Source::RevPathTag, void>::type> {
     962    struct PathCopySelector<Target, Source, true, true> {
    956963      static void copy(Target& target, const Source& source) {
    957964        target.clear();

  • lemon/smart_graph.h

    r125 r149  
    7474   
    7575    typedef True NodeNumTag;
    76     typedef True ArcNumTag;
     76    typedef True EdgeNumTag;
    7777
    7878    int nodeNum() const { return nodes.size(); }
    … …  
    115115    static Node nodeFromId(int id) { return Node(id);}
    116116    static Arc arcFromId(int id) { return Arc(id);}
     117
     118    bool valid(Node n) const {
     119      return n._id >= 0 && n._id < static_cast<int>(nodes.size());
     120    }
     121    bool valid(Arc a) const {
     122      return a._id >= 0 && a._id < static_cast<int>(arcs.size());
     123    }
    117124
    118125    class Node {
    … …  
    261268    /// \sa reserveNode
    262269    void reserveArc(int m) { arcs.reserve(m); };
     270
     271    /// \brief Node validity check
     272    ///
     273    /// This function gives back true if the given node is valid,
     274    /// ie. it is a real node of the graph. 
     275    ///
     276    /// \warning A removed node (using Snapshot) could become valid again
     277    /// when new nodes are added to the graph.
     278    bool valid(Node n) const { return Parent::valid(n); }
     279
     280    /// \brief Arc validity check
     281    ///
     282    /// This function gives back true if the given arc is valid,
     283    /// ie. it is a real arc of the graph. 
     284    ///
     285    /// \warning A removed arc (using Snapshot) could become valid again
     286    /// when new arcs are added to the graph.
     287    bool valid(Arc a) const { return Parent::valid(a); }
    263288
    264289    ///Clear the digraph.
    … …  
    551576    static Edge edgeFromId(int id) { return Edge(id);}
    552577
     578    bool valid(Node n) const {
     579      return n._id >= 0 && n._id < static_cast<int>(nodes.size());
     580    }
     581    bool valid(Arc a) const {
     582      return a._id >= 0 && a._id < static_cast<int>(arcs.size());
     583    }
     584    bool valid(Edge e) const {
     585      return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
     586    }
     587
    553588    Node addNode() {     
    554589      int n = nodes.size();
    … …  
    559594    }
    560595   
    561     Edge addArc(Node u, Node v) {
     596    Edge addEdge(Node u, Node v) {
    562597      int n = arcs.size();
    563598      arcs.push_back(ArcT());
    … …  
    640675    ///\return the new edge.
    641676    Edge addEdge(const Node& s, const Node& t) {
    642       return Parent::addArc(s, t);
    643     }
     677      return Parent::addEdge(s, t);
     678    }
     679
     680    /// \brief Node validity check
     681    ///
     682    /// This function gives back true if the given node is valid,
     683    /// ie. it is a real node of the graph. 
     684    ///
     685    /// \warning A removed node (using Snapshot) could become valid again
     686    /// when new nodes are added to the graph.
     687    bool valid(Node n) const { return Parent::valid(n); }
     688
     689    /// \brief Arc validity check
     690    ///
     691    /// This function gives back true if the given arc is valid,
     692    /// ie. it is a real arc of the graph. 
     693    ///
     694    /// \warning A removed arc (using Snapshot) could become valid again
     695    /// when new edges are added to the graph.
     696    bool valid(Arc a) const { return Parent::valid(a); }
     697
     698    /// \brief Edge validity check
     699    ///
     700    /// This function gives back true if the given edge is valid,
     701    /// ie. it is a real edge of the graph. 
     702    ///
     703    /// \warning A removed edge (using Snapshot) could become valid again
     704    /// when new edges are added to the graph.
     705    bool valid(Edge e) const { return Parent::valid(e); }
    644706
    645707    ///Clear the graph.

  • lemon/time_measure.h

    r126 r143  
    2525
    2626#ifdef WIN32
     27#define WIN32_LEAN_AND_MEAN
     28#define NOMINMAX
    2729#include <windows.h>
    2830#include <cmath>
    … …  
    3234#endif
    3335
     36#include <string>
    3437#include <fstream>
    3538#include <iostream>

  • test/Makefile.am

    r119 r146  
    11EXTRA_DIST += \
    2         test/Makefile
     2        test/CMakeLists.txt
    33
    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

  • test/graph_test.cc

    r109 r149  
    2323// #include <lemon/grid_graph.h>
    2424
    25 //#include <lemon/graph_utils.h>
     25#include <lemon/graph_utils.h>
    2626
    2727#include "test_tools.h"
    … …  
    8383
    8484template <typename Graph>
    85 void print_items(Graph &g) {
    86 
    87   typedef typename Graph::NodeIt NodeIt;
    88   typedef typename Graph::EdgeIt EdgeIt;
    89   typedef typename Graph::ArcIt ArcIt;
    90 
    91   std::cout << "Nodes" << std::endl;
    92   int i=0;
    93   for(NodeIt it(g); it!=INVALID; ++it, ++i) {
    94     std::cout << "  " << i << ": " << g.id(it) << std::endl;
    95   }
    96 
    97   std::cout << "Edge" << std::endl;
    98   i=0;
    99   for(EdgeIt it(g); it!=INVALID; ++it, ++i) {
    100     std::cout << "  " << i << ": " << g.id(it)
    101          << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it))
    102          << ")" << std::endl;
    103   }
    104 
    105   std::cout << "Arc" << std::endl;
    106   i=0;
    107   for(ArcIt it(g); it!=INVALID; ++it, ++i) {
    108     std::cout << "  " << i << ": " << g.id(it)
    109          << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it))
    110          << ")" << std::endl;
    111   }
    112 
    113 }
    114 
    115 template <typename Graph>
    116 void check_graph() {
    117 
    118   typedef typename Graph::Node Node;
    119   typedef typename Graph::Edge Edge;
    120   typedef typename Graph::Arc Arc;
    121   typedef typename Graph::NodeIt NodeIt;
    122   typedef typename Graph::EdgeIt EdgeIt;
    123   typedef typename Graph::ArcIt ArcIt;
    124 
     85void check_graph_counts() {
     86
     87  TEMPLATE_GRAPH_TYPEDEFS(Graph);
    12588  Graph g;
    12689
    … …  
    13699    e2 = g.addEdge(n2, n3);
    137100
    138   // print_items(g);
    139 
    140101  check_item_counts(g,3,2);
    141102}
     103
     104template <typename Graph>
     105void check_graph_validity() {
     106
     107  TEMPLATE_GRAPH_TYPEDEFS(Graph);
     108  Graph g;
     109
     110  check_item_counts(g,0,0);
     111
     112  Node
     113    n1 = g.addNode(),
     114    n2 = g.addNode(),
     115    n3 = g.addNode();
     116
     117  Edge
     118    e1 = g.addEdge(n1, n2),
     119    e2 = g.addEdge(n2, n3);
     120
     121  check(g.valid(n1), "Validity check");
     122  check(g.valid(e1), "Validity check");
     123  check(g.valid(g.direct(e1, true)), "Validity check");
     124
     125  check(!g.valid(g.nodeFromId(-1)), "Validity check");
     126  check(!g.valid(g.edgeFromId(-1)), "Validity check");
     127  check(!g.valid(g.arcFromId(-1)), "Validity check");
     128   
     129}
     130
     131template <typename Graph>
     132void check_graph_validity_erase() {
     133
     134  TEMPLATE_GRAPH_TYPEDEFS(Graph);
     135  Graph g;
     136
     137  check_item_counts(g,0,0);
     138
     139  Node
     140    n1 = g.addNode(),
     141    n2 = g.addNode(),
     142    n3 = g.addNode();
     143
     144  Edge
     145    e1 = g.addEdge(n1, n2),
     146    e2 = g.addEdge(n2, n3);
     147
     148  check(g.valid(n1), "Validity check");
     149  check(g.valid(e1), "Validity check");
     150  check(g.valid(g.direct(e1, true)), "Validity check");
     151
     152  g.erase(n1);
     153
     154  check(!g.valid(n1), "Validity check");
     155  check(g.valid(n2), "Validity check");
     156  check(g.valid(n3), "Validity check");
     157  check(!g.valid(e1), "Validity check");
     158  check(g.valid(e2), "Validity check");
     159
     160  check(!g.valid(g.nodeFromId(-1)), "Validity check");
     161  check(!g.valid(g.edgeFromId(-1)), "Validity check");
     162  check(!g.valid(g.arcFromId(-1)), "Validity check");
     163   
     164}
     165
     166
    142167
    143168// void checkGridGraph(const GridGraph& g, int w, int h) {
    … …  
    188213  check_concepts();
    189214
    190   check_graph<ListGraph>();
    191   check_graph<SmartGraph>();
     215  check_graph_counts<ListGraph>();
     216  check_graph_counts<SmartGraph>();
     217
     218  check_graph_validity_erase<ListGraph>();
     219  check_graph_validity<SmartGraph>();
    192220
    193221//   {

  • tools/Makefile.am

    r1 r146  
    1 EXTRA_DIST += \
    2         tools/Makefile
    3 
    41if WANT_TOOLS
    52
Note: See TracChangeset for help on using the changeset viewer.