COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
6 added
6 deleted
20 edited

Legend:

Unmodified
Added
Removed

  • .hgignore

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

  • Makefile.am

    r146 r70  
    88        m4/lx_check_cplex.m4 \
    99        m4/lx_check_glpk.m4 \
    10         m4/lx_check_soplex.m4 \
    11         CMakeLists.txt
     10        m4/lx_check_soplex.m4
    1211
    1312pkgconfigdir = $(libdir)/pkgconfig
    … …  
    4645        build-aux/ltmain.sh \
    4746        build-aux/missing \
    48         doc/doxygen.log
     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
    4954
    5055mrproper:

  • benchmark/Makefile.am

    r146 r1  
     1EXTRA_DIST += \
     2        benchmark/Makefile
     3
    14if WANT_BENCHMARK
    25

  • demo/Makefile.am

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

    r143 r127  
    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 * std::log(double(n)));
     40  const int e = argc > 2 ? std::atoi(argv[2]) : static_cast<int>(n * log(n));
    4141  const int m = argc > 3 ? std::atoi(argv[3]) : 100;
    4242

  • doc/Makefile.am

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

  • lemon/Makefile.am

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

  • lemon/assert.h

    r142 r118  
    104104
    105105#ifndef LEMON_FUNCTION_NAME
    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
     106#  define LEMON_FUNCTION_NAME (__PRETTY_FUNCTION__)
    113107#endif
    114108

  • lemon/bits/traits.h

    r139 r107  
    217217
    218218  template <typename Graph, typename Enable = void>
    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
     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
    240240  > {
    241241    static const bool value = true;

  • lemon/graph_to_eps.h

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

  • lemon/graph_utils.h

    r148 r100  
    3636///\ingroup gutils
    3737///\file
    38 ///\brief Graph utilities.
     38///\brief Digraph 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, \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  
     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
    8965  ///Creates convenience typedefs for the graph types and iterators
    9066
    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.
     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.
    126108  /// The complexity of the function is O(n) because
    127109  /// it iterates on all of the items.
    128   template <typename Graph, typename Item>
    129   inline int countItems(const Graph& g) {
    130     typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
     110
     111  template <typename Digraph, typename Item>
     112  inline int countItems(const Digraph& g) {
     113    typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
    131114    int num = 0;
    132115    for (ItemIt it(g); it != INVALID; ++it) {
    … …  
    138121  // Node counting:
    139122
    140   namespace _graph_utils_bits {
    141    
    142     template <typename Graph, typename Enable = void>
     123  namespace _digraph_utils_bits {
     124   
     125    template <typename Digraph, typename Enable = void>
    143126    struct CountNodesSelector {
    144       static int count(const Graph &g) {
    145         return countItems<Graph, typename Graph::Node>(g);
     127      static int count(const Digraph &g) {
     128        return countItems<Digraph, typename Digraph::Node>(g);
    146129      }
    147130    };
    148131
    149     template <typename Graph>
     132    template <typename Digraph>
    150133    struct CountNodesSelector<
    151       Graph, typename
    152       enable_if<typename Graph::NodeNumTag, void>::type>
     134      Digraph, typename
     135      enable_if<typename Digraph::NodeNumTag, void>::type>
    153136    {
    154       static int count(const Graph &g) {
     137      static int count(const Digraph &g) {
    155138        return g.nodeNum();
    156139      }
    … …  
    158141  }
    159142
    160   /// \brief Function to count the nodes in the graph.
    161   ///
    162   /// This function counts the nodes in the graph.
     143  /// \brief Function to count the nodes in the digraph.
     144  ///
     145  /// This function counts the nodes in the digraph.
    163146  /// The complexity of the function is O(n) but for some
    164   /// graph structures it is specialized to run in O(1).
    165   ///
    166   /// If the graph contains a \e nodeNum() member function and a
     147  /// digraph structures it is specialized to run in O(1).
     148  ///
     149  /// If the digraph contains a \e nodeNum() member function and a
    167150  /// \e NodeNumTag tag then this function calls directly the member
    168151  /// function to query the cardinality of the node set.
    169   template <typename Graph>
    170   inline int countNodes(const Graph& g) {
    171     return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
     152  template <typename Digraph>
     153  inline int countNodes(const Digraph& g) {
     154    return _digraph_utils_bits::CountNodesSelector<Digraph>::count(g);
    172155  }
    173156
    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);
     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);
    182163      }
    183164    };
    184165
    185     template <typename Graph>
    186     struct CountArcsSelector<
    187       Graph,
    188       typename enable_if<typename Graph::ArcNumTag, void>::type>
     166    template <typename Digraph>
     167    struct CountRedsSelector<
     168      Digraph, typename
     169      enable_if<typename Digraph::NodeNumTag, void>::type>
    189170    {
    190       static int count(const Graph &g) {
    191         return g.arcNum();
     171      static int count(const Digraph &g) {
     172        return g.redNum();
    192173      }
    193174    };   
    194175  }
    195176
    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);
     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);
    208189  }
    209190
    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);
     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);
    217197      }
    218198    };
    219199
    220     template <typename Graph>
    221     struct CountEdgesSelector<
    222       Graph,
    223       typename enable_if<typename Graph::EdgeNumTag, void>::type>
     200    template <typename Digraph>
     201    struct CountBluesSelector<
     202      Digraph, typename
     203      enable_if<typename Digraph::NodeNumTag, void>::type>
    224204    {
    225       static int count(const Graph &g) {
    226         return g.edgeNum();
     205      static int count(const Digraph &g) {
     206        return g.blueNum();
    227207      }
    228208    };   
    229209  }
    230210
    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
     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);
     223  }
     224
     225
     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
    239291  /// 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);
     292  template <typename Digraph>
     293  inline int countEdges(const Digraph& g) {
     294    return _digraph_utils_bits::CountEdgesSelector<Digraph>::count(g);
    243295
    244296  }
    245297
    246298
    247   template <typename Graph, typename DegIt>
    248   inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
     299  template <typename Digraph, typename DegIt>
     300  inline int countNodeDegree(const Digraph& _g, const typename Digraph::Node& _n) {
    249301    int num = 0;
    250302    for (DegIt it(_g, _n); it != INVALID; ++it) {
    … …  
    257309  ///
    258310  /// This function counts the number of the out-arcs from node \c 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);
     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);
    263315  }
    264316
    … …  
    266318  ///
    267319  /// This function counts the number of the in-arcs to node \c 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);
     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);
    272324  }
    273325
    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);
     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);
    281333  }
    282334
    283   namespace _graph_utils_bits {
    284    
    285     template <typename Graph, typename Enable = void>
     335  namespace _digraph_utils_bits {
     336   
     337    template <typename Digraph, typename Enable = void>
    286338    struct FindArcSelector {
    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) {
     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) {
    290342        if (e == INVALID) {
    291343          g.firstOut(e, u);
    … …  
    300352    };
    301353
    302     template <typename Graph>
     354    template <typename Digraph>
    303355    struct FindArcSelector<
    304       Graph,
    305       typename enable_if<typename Graph::FindEdgeTag, void>::type>
     356      Digraph,
     357      typename enable_if<typename Digraph::FindArcTag, void>::type>
    306358    {
    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) {
     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) {
    310362        return g.findArc(u, v, prev);
    311363      }
    … …  
    313365  }
    314366
    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.
     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.
    318370  ///
    319371  /// If \c prev is \ref INVALID (this is the default value), then
    … …  
    333385  ///\sa DynArcLookUp
    334386  ///\sa ConArcIt
    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);
     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);
    340392  }
    341393
    … …  
    346398  /// use it the following way:
    347399  ///\code
    348   /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
     400  /// for (ConArcIt<Digraph> it(g, src, trg); it != INVALID; ++it) {
    349401  ///   ...
    350402  /// }
    … …  
    357409  ///
    358410  /// \author Balazs Dezso
    359   template <typename _Graph>
    360   class ConArcIt : public _Graph::Arc {
     411  template <typename _Digraph>
     412  class ConArcIt : public _Digraph::Arc {
    361413  public:
    362414
    363     typedef _Graph Graph;
    364     typedef typename Graph::Arc Parent;
    365 
    366     typedef typename Graph::Arc Arc;
    367     typedef typename Graph::Node Node;
     415    typedef _Digraph Digraph;
     416    typedef typename Digraph::Arc Parent;
     417
     418    typedef typename Digraph::Arc Arc;
     419    typedef typename Digraph::Node Node;
    368420
    369421    /// \brief Constructor.
    … …  
    371423    /// Construct a new ConArcIt iterating on the arcs which
    372424    /// connects the \c u and \c v node.
    373     ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
    374       Parent::operator=(findArc(_graph, u, v));
     425    ConArcIt(const Digraph& g, Node u, Node v) : digraph(g) {
     426      Parent::operator=(findArc(digraph, u, v));
    375427    }
    376428
    … …  
    379431    /// Construct a new ConArcIt which continues the iterating from
    380432    /// the \c e arc.
    381     ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
     433    ConArcIt(const Digraph& g, Arc e) : Parent(e), digraph(g) {}
    382434   
    383435    /// \brief Increment operator.
    … …  
    385437    /// It increments the iterator and gives back the next arc.
    386438    ConArcIt& operator++() {
    387       Parent::operator=(findArc(_graph, _graph.source(*this),
    388                                 _graph.target(*this), *this));
     439      Parent::operator=(findArc(digraph, digraph.source(*this),
     440                                 digraph.target(*this), *this));
    389441      return *this;
    390442    }
    391443  private:
    392     const Graph& _graph;
     444    const Digraph& digraph;
    393445  };
    394446
    395   namespace _graph_utils_bits {
    396    
    397     template <typename Graph, typename Enable = void>
     447  namespace _digraph_utils_bits {
     448   
     449    template <typename Digraph, typename Enable = void>
    398450    struct FindEdgeSelector {
    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) {
     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) {
    402454        bool b;
    403455        if (u != v) {
    … …  
    426478    };
    427479
    428     template <typename Graph>
     480    template <typename Digraph>
    429481    struct FindEdgeSelector<
    430       Graph,
    431       typename enable_if<typename Graph::FindEdgeTag, void>::type>
     482      Digraph,
     483      typename enable_if<typename Digraph::FindArcTag, void>::type>
    432484    {
    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) {
     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) {
    436488        return g.findEdge(u, v, prev);
    437489      }
    … …  
    439491  }
    440492
    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.
     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.
    446498  ///
    447499  /// If \c prev is \ref INVALID (this is the default value), then
    … …  
    460512  ///\sa ConArcIt
    461513
    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);
     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);
    467519  }
    468520
    … …  
    473525  /// use it the following way:
    474526  ///\code
    475   /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
     527  /// for (ConEdgeIt<Digraph> it(g, src, trg); it != INVALID; ++it) {
    476528  ///   ...
    477529  /// }
    … …  
    481533  ///
    482534  /// \author Balazs Dezso
    483   template <typename _Graph>
    484   class ConEdgeIt : public _Graph::Edge {
     535  template <typename _Digraph>
     536  class ConEdgeIt : public _Digraph::Edge {
    485537  public:
    486538
    487     typedef _Graph Graph;
    488     typedef typename Graph::Edge Parent;
    489 
    490     typedef typename Graph::Edge Edge;
    491     typedef typename Graph::Node Node;
     539    typedef _Digraph Digraph;
     540    typedef typename Digraph::Edge Parent;
     541
     542    typedef typename Digraph::Edge Edge;
     543    typedef typename Digraph::Node Node;
    492544
    493545    /// \brief Constructor.
    494546    ///
    495     /// Construct a new ConEdgeIt iterating on the edges which
     547    /// Construct a new ConEdgeIt iterating on the arcs which
    496548    /// connects the \c u and \c v node.
    497     ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
    498       Parent::operator=(findEdge(_graph, u, v));
     549    ConEdgeIt(const Digraph& g, Node u, Node v) : digraph(g) {
     550      Parent::operator=(findEdge(digraph, u, v));
    499551    }
    500552
    … …  
    502554    ///
    503555    /// Construct a new ConEdgeIt which continues the iterating from
    504     /// the \c e edge.
    505     ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
     556    /// the \c e arc.
     557    ConEdgeIt(const Digraph& g, Edge e) : Parent(e), digraph(g) {}
    506558   
    507559    /// \brief Increment operator.
    508560    ///
    509     /// It increments the iterator and gives back the next edge.
     561    /// It increments the iterator and gives back the next arc.
    510562    ConEdgeIt& operator++() {
    511       Parent::operator=(findEdge(_graph, _graph.source(*this),
    512                                  _graph.target(*this), *this));
     563      Parent::operator=(findEdge(digraph, digraph.source(*this),
     564                                      digraph.target(*this), *this));
    513565      return *this;
    514566    }
    515567  private:
    516     const Graph& _graph;
     568    const Digraph& digraph;
    517569  };
    518570
    519   namespace _graph_utils_bits {
     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 {
    520597
    521598    template <typename Digraph, typename Item, typename RefMap>
    … …  
    651728    };
    652729
     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
    653765  }
    654766
    … …  
    657769  /// Class to copy a digraph to another digraph (duplicate a digraph). The
    658770  /// 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
    690771  template <typename To, typename From>
    691772  class DigraphCopy {
    … …  
    711792    /// It copies the content of the \c _from digraph into the
    712793    /// \c _to digraph.
    713     DigraphCopy(To& to, const From& from)
    714       : _from(from), _to(to) {}
     794    DigraphCopy(To& _to, const From& _from)
     795      : from(_from), to(_to) {}
    715796
    716797    /// \brief Destructor of the DigraphCopy
    … …  
    718799    /// Destructor of the DigraphCopy
    719800    ~DigraphCopy() {
    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];
     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];
    725806      }
    726807
    … …  
    729810    /// \brief Copies the node references into the given map.
    730811    ///
    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.
     812    /// Copies the node references into the given map.
    735813    template <typename NodeRef>
    736814    DigraphCopy& nodeRef(NodeRef& map) {
    737       _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
    738                            NodeRefMap, NodeRef>(map));
     815      nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node,
     816                              NodeRefMap, NodeRef>(map));
    739817      return *this;
    740818    }
    … …  
    743821    ///
    744822    ///  Copies the node cross references (reverse references) into
    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.
     823    ///  the given map.
    748824    template <typename NodeCrossRef>
    749825    DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
    750       _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
    751                            NodeRefMap, NodeCrossRef>(map));
     826      nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,
     827                              NodeRefMap, NodeCrossRef>(map));
    752828      return *this;
    753829    }
    … …  
    755831    /// \brief Make copy of the given map.
    756832    ///
    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.
     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. 
    760837    template <typename ToMap, typename FromMap>
    761838    DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
    762       _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
    763                            NodeRefMap, ToMap, FromMap>(tmap, map));
     839      nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node,
     840                              NodeRefMap, ToMap, FromMap>(tmap, map));
    764841      return *this;
    765842    }
    … …  
    769846    /// Make a copy of the given node.
    770847    DigraphCopy& node(TNode& tnode, const Node& snode) {
    771       _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
    772                            NodeRefMap, TNode>(tnode, snode));
     848      nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,
     849                              NodeRefMap, TNode>(tnode, snode));
    773850      return *this;
    774851    }
    … …  
    779856    template <typename ArcRef>
    780857    DigraphCopy& arcRef(ArcRef& map) {
    781       _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
    782                           ArcRefMap, ArcRef>(map));
     858      arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,
     859                              ArcRefMap, ArcRef>(map));
    783860      return *this;
    784861    }
    … …  
    790867    template <typename ArcCrossRef>
    791868    DigraphCopy& arcCrossRef(ArcCrossRef& map) {
    792       _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
    793                           ArcRefMap, ArcCrossRef>(map));
     869      arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,
     870                              ArcRefMap, ArcCrossRef>(map));
    794871      return *this;
    795872    }
    … …  
    803880    template <typename ToMap, typename FromMap>
    804881    DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
    805       _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
    806                           ArcRefMap, ToMap, FromMap>(tmap, map));
     882      arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,
     883                              ArcRefMap, ToMap, FromMap>(tmap, map));
    807884      return *this;
    808885    }
    … …  
    812889    /// Make a copy of the given arc.
    813890    DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
    814       _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
    815                           ArcRefMap, TArc>(tarc, sarc));
     891      arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,
     892                              ArcRefMap, TArc>(tarc, sarc));
    816893      return *this;
    817894    }
    … …  
    821898    /// Executes the copies.
    822899    void run() {
    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);
     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);
    832909      }     
    833910    }
    … …  
    836913
    837914
    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;
     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;
    846923
    847924  };
    … …  
    849926  /// \brief Copy a digraph to another digraph.
    850927  ///
    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:
     928  /// Copy a digraph to another digraph.
     929  /// The usage of the function:
     930  ///
    854931  ///\code
    855932  /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
    … …  
    867944  }
    868945
    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
     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.
    904950  template <typename To, typename From>
    905951  class GraphCopy {
    … …  
    921967
    922968    struct ArcRefMap {
    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) {}
     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) {}
    927973
    928974      typedef typename From::Arc Key;
    … …  
    931977      Value operator[](const Key& key) const {
    932978        bool forward =
    933           (_from.direction(key) ==
    934            (_node_ref[_from.source(key)] == _to.source(_edge_ref[key])));
    935         return _to.direct(_edge_ref[key], 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);
    936983      }
    937984     
    938       const To& _to;
    939       const From& _from;
    940       const EdgeRefMap& _edge_ref;
    941       const NodeRefMap& _node_ref;
     985      const To& to;
     986      const From& from;
     987      const EdgeRefMap& edge_ref;
     988      const NodeRefMap& node_ref;
    942989    };
    943990
    … …  
    946993
    947994
    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
     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
    9581005    ~GraphCopy() {
    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];
     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];
    9671014      }
    9681015
    … …  
    9741021    template <typename NodeRef>
    9751022    GraphCopy& nodeRef(NodeRef& map) {
    976       _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
    977                            NodeRefMap, NodeRef>(map));
     1023      nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node,
     1024                              NodeRefMap, NodeRef>(map));
    9781025      return *this;
    9791026    }
    … …  
    9851032    template <typename NodeCrossRef>
    9861033    GraphCopy& nodeCrossRef(NodeCrossRef& map) {
    987       _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
    988                            NodeRefMap, NodeCrossRef>(map));
     1034      nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,
     1035                              NodeRefMap, NodeCrossRef>(map));
    9891036      return *this;
    9901037    }
    … …  
    9921039    /// \brief Make copy of the given map.
    9931040    ///
    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
     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
    9971044    /// type. 
    9981045    template <typename ToMap, typename FromMap>
    9991046    GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
    1000       _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
    1001                            NodeRefMap, ToMap, FromMap>(tmap, map));
     1047      nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node,
     1048                              NodeRefMap, ToMap, FromMap>(tmap, map));
    10021049      return *this;
    10031050    }
    … …  
    10071054    /// Make a copy of the given node.
    10081055    GraphCopy& node(TNode& tnode, const Node& snode) {
    1009       _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
    1010                            NodeRefMap, TNode>(tnode, snode));
     1056      nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,
     1057                              NodeRefMap, TNode>(tnode, snode));
    10111058      return *this;
    10121059    }
    … …  
    10171064    template <typename ArcRef>
    10181065    GraphCopy& arcRef(ArcRef& map) {
    1019       _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
    1020                           ArcRefMap, ArcRef>(map));
     1066      arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,
     1067                              ArcRefMap, ArcRef>(map));
    10211068      return *this;
    10221069    }
    … …  
    10281075    template <typename ArcCrossRef>
    10291076    GraphCopy& arcCrossRef(ArcCrossRef& map) {
    1030       _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
    1031                           ArcRefMap, ArcCrossRef>(map));
     1077      arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,
     1078                              ArcRefMap, ArcCrossRef>(map));
    10321079      return *this;
    10331080    }
    … …  
    10351082    /// \brief Make copy of the given map.
    10361083    ///
    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
     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
    10401087    /// type. 
    10411088    template <typename ToMap, typename FromMap>
    10421089    GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
    1043       _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
    1044                           ArcRefMap, ToMap, FromMap>(tmap, map));
     1090      arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,
     1091                              ArcRefMap, ToMap, FromMap>(tmap, map));
    10451092      return *this;
    10461093    }
    … …  
    10501097    /// Make a copy of the given arc.
    10511098    GraphCopy& arc(TArc& tarc, const Arc& sarc) {
    1052       _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
    1053                           ArcRefMap, TArc>(tarc, sarc));
     1099      arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,
     1100                              ArcRefMap, TArc>(tarc, sarc));
    10541101      return *this;
    10551102    }
    … …  
    10601107    template <typename EdgeRef>
    10611108    GraphCopy& edgeRef(EdgeRef& map) {
    1062       _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge,
    1063                            EdgeRefMap, EdgeRef>(map));
     1109      edgeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Edge,
     1110                               EdgeRefMap, EdgeRef>(map));
    10641111      return *this;
    10651112    }
    … …  
    10711118    template <typename EdgeCrossRef>
    10721119    GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
    1073       _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From,
    1074                            Edge, EdgeRefMap, EdgeCrossRef>(map));
     1120      edgeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,
     1121                               Edge, EdgeRefMap, EdgeCrossRef>(map));
    10751122      return *this;
    10761123    }
    … …  
    10781125    /// \brief Make copy of the given map.
    10791126    ///
    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
     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
    10831130    /// type. 
    10841131    template <typename ToMap, typename FromMap>
    10851132    GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
    1086       _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge,
    1087                            EdgeRefMap, ToMap, FromMap>(tmap, map));
     1133      edgeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Edge,
     1134                               EdgeRefMap, ToMap, FromMap>(tmap, map));
    10881135      return *this;
    10891136    }
    … …  
    10931140    /// Make a copy of the given edge.
    10941141    GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
    1095       _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
    1096                            EdgeRefMap, TEdge>(tedge, sedge));
     1142      edgeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Edge,
     1143                               EdgeRefMap, TEdge>(tedge, sedge));
    10971144      return *this;
    10981145    }
    … …  
    11021149    /// Executes the copies.
    11031150    void run() {
    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);
     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);
    11171164      }
    11181165    }
    … …  
    11201167  private:
    11211168   
    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;
     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;
    11331180
    11341181  };
    11351182
    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:
     1183  /// \brief Copy an graph to another digraph.
     1184  ///
     1185  /// Copy an graph to another digraph.
     1186  /// The usage of the function:
     1187  ///
    11411188  ///\code
    11421189  /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
    … …  
    11441191  ///
    11451192  /// After the copy the \c nr map will contain the mapping from the
    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.
     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.
    11491196  ///
    11501197  /// \see GraphCopy
    … …  
    11551202  }
    11561203
     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
    11571570  /// @}
    11581571
    1159   /// \addtogroup graph_maps
     1572  /// \addtogroup digraph_maps
    11601573  /// @{
    11611574
    1162   /// Provides an immutable and unique id for each item in the graph.
     1575  /// Provides an immutable and unique id for each item in the digraph.
    11631576
    11641577  /// The IdMap class provides a unique and immutable id for each item of the
    1165   /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
     1578  /// same type (e.g. node) in the digraph. This id is <ul><li>\b unique:
    11661579  /// different items (nodes) get different ids <li>\b immutable: the id of an
    11671580  /// item (node) does not change (even if you delete other nodes).  </ul>
    11681581  /// Through this map you get access (i.e. can read) the inner id values of
    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>
     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>
    11731586  class IdMap {
    11741587  public:
    1175     typedef _Graph Graph;
     1588    typedef _Digraph Digraph;
    11761589    typedef int Value;
    11771590    typedef _Item Item;
    … …  
    11811594    ///
    11821595    /// Constructor of the map.
    1183     explicit IdMap(const Graph& graph) : _graph(&graph) {}
     1596    explicit IdMap(const Digraph& _digraph) : digraph(&_digraph) {}
    11841597
    11851598    /// \brief Gives back the \e id of the item.
    11861599    ///
    11871600    /// Gives back the immutable and unique \e id of the item.
    1188     int operator[](const Item& item) const { return _graph->id(item);}
     1601    int operator[](const Item& item) const { return digraph->id(item);}
    11891602
    11901603    /// \brief Gives back the item by its id.
    11911604    ///
    11921605    /// Gives back the item by its id.
    1193     Item operator()(int id) { return _graph->fromId(id, Item()); }
     1606    Item operator()(int id) { return digraph->fromId(id, Item()); }
    11941607
    11951608  private:
    1196     const Graph* _graph;
     1609    const Digraph* digraph;
    11971610
    11981611  public:
    … …  
    12081621      ///
    12091622      /// Constructor for creating an id-to-item map.
    1210       explicit InverseMap(const Graph& graph) : _graph(&graph) {}
     1623      explicit InverseMap(const Digraph& _digraph) : digraph(&_digraph) {}
    12111624
    12121625      /// \brief Constructor.
    12131626      ///
    12141627      /// Constructor for creating an id-to-item map.
    1215       explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
     1628      explicit InverseMap(const IdMap& idMap) : digraph(idMap.digraph) {}
    12161629
    12171630      /// \brief Gives back the given item from its id.
    … …  
    12191632      /// Gives back the given item from its id.
    12201633      ///
    1221       Item operator[](int id) const { return _graph->fromId(id, Item());}
     1634      Item operator[](int id) const { return digraph->fromId(id, Item());}
    12221635
    12231636    private:
    1224       const Graph* _graph;
     1637      const Digraph* digraph;
    12251638    };
    12261639
    … …  
    12281641    ///
    12291642    /// Gives back the inverse of the IdMap.
    1230     InverseMap inverse() const { return InverseMap(*_graph);}
     1643    InverseMap inverse() const { return InverseMap(*digraph);}
    12311644
    12321645  };
    12331646
    12341647 
    1235   /// \brief General invertable graph-map type.
    1236 
    1237   /// This type provides simple invertable graph-maps.
     1648  /// \brief General invertable digraph-map type.
     1649
     1650  /// This type provides simple invertable digraph-maps.
    12381651  /// The InvertableMap wraps an arbitrary ReadWriteMap
    12391652  /// and if a key is set to a new value then store it
    … …  
    12431656  /// with stl compatible forward iterator.
    12441657  ///
    1245   /// \param _Graph The graph type.
    1246   /// \param _Item The item type of the graph.
     1658  /// \param _Digraph The digraph type.
     1659  /// \param _Item The item type of the digraph.
    12471660  /// \param _Value The value type of the map.
    12481661  ///
    12491662  /// \see IterableValueMap
    1250   template <typename _Graph, typename _Item, typename _Value>
    1251   class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
     1663  template <typename _Digraph, typename _Item, typename _Value>
     1664  class InvertableMap : protected DefaultMap<_Digraph, _Item, _Value> {
    12521665  private:
    12531666   
    1254     typedef DefaultMap<_Graph, _Item, _Value> Map;
    1255     typedef _Graph Graph;
     1667    typedef DefaultMap<_Digraph, _Item, _Value> Map;
     1668    typedef _Digraph Digraph;
    12561669
    12571670    typedef std::map<_Value, _Item> Container;
    1258     Container _inv_map;   
     1671    Container invMap;   
    12591672
    12601673  public:
    … …  
    12691682    /// \brief Constructor.
    12701683    ///
    1271     /// Construct a new InvertableMap for the graph.
    1272     ///
    1273     explicit InvertableMap(const Graph& graph) : Map(graph) {}
     1684    /// Construct a new InvertableMap for the digraph.
     1685    ///
     1686    explicit InvertableMap(const Digraph& digraph) : Map(digraph) {}
    12741687
    12751688    /// \brief Forward iterator for values.
    … …  
    13131726    /// range.
    13141727    ValueIterator beginValue() const {
    1315       return ValueIterator(_inv_map.begin());
     1728      return ValueIterator(invMap.begin());
    13161729    }
    13171730
    … …  
    13231736    /// range.
    13241737    ValueIterator endValue() const {
    1325       return ValueIterator(_inv_map.end());
     1738      return ValueIterator(invMap.end());
    13261739    }
    13271740   
    … …  
    13311744    void set(const Key& key, const Value& val) {
    13321745      Value oldval = Map::operator[](key);
    1333       typename Container::iterator it = _inv_map.find(oldval);
    1334       if (it != _inv_map.end() && it->second == key) {
    1335         _inv_map.erase(it);
     1746      typename Container::iterator it = invMap.find(oldval);
     1747      if (it != invMap.end() && it->second == key) {
     1748        invMap.erase(it);
    13361749      }     
    1337       _inv_map.insert(make_pair(val, key));
     1750      invMap.insert(make_pair(val, key));
    13381751      Map::set(key, val);
    13391752    }
    … …  
    13511764    /// Gives back the item by its value.
    13521765    Key operator()(const Value& key) const {
    1353       typename Container::const_iterator it = _inv_map.find(key);
    1354       return it != _inv_map.end() ? it->second : INVALID;
     1766      typename Container::const_iterator it = invMap.find(key);
     1767      return it != invMap.end() ? it->second : INVALID;
    13551768    }
    13561769
    … …  
    13631776    virtual void erase(const Key& key) {
    13641777      Value val = Map::operator[](key);
    1365       typename Container::iterator it = _inv_map.find(val);
    1366       if (it != _inv_map.end() && it->second == key) {
    1367         _inv_map.erase(it);
     1778      typename Container::iterator it = invMap.find(val);
     1779      if (it != invMap.end() && it->second == key) {
     1780        invMap.erase(it);
    13681781      }
    13691782      Map::erase(key);
    … …  
    13771790      for (int i = 0; i < int(keys.size()); ++i) {
    13781791        Value val = Map::operator[](keys[i]);
    1379         typename Container::iterator it = _inv_map.find(val);
    1380         if (it != _inv_map.end() && it->second == keys[i]) {
    1381           _inv_map.erase(it);
     1792        typename Container::iterator it = invMap.find(val);
     1793        if (it != invMap.end() && it->second == keys[i]) {
     1794          invMap.erase(it);
    13821795        }
    13831796      }
    … …  
    13901803    /// \c AlterationNotifier.
    13911804    virtual void clear() {
    1392       _inv_map.clear();
     1805      invMap.clear();
    13931806      Map::clear();
    13941807    }
    … …  
    14051818      ///
    14061819      /// Constructor of the InverseMap.
    1407       explicit InverseMap(const InvertableMap& inverted)
    1408         : _inverted(inverted) {}
     1820      explicit InverseMap(const InvertableMap& _inverted)
     1821        : inverted(_inverted) {}
    14091822
    14101823      /// The value type of the InverseMap.
    … …  
    14181831      /// what was last assigned to the value.
    14191832      Value operator[](const Key& key) const {
    1420         return _inverted(key);
     1833        return inverted(key);
    14211834      }
    14221835     
    14231836    private:
    1424       const InvertableMap& _inverted;
     1837      const InvertableMap& inverted;
    14251838    };
    14261839
    … …  
    14371850
    14381851  /// \brief Provides a mutable, continuous and unique descriptor for each
    1439   /// item in the graph.
     1852  /// item in the digraph.
    14401853  ///
    14411854  /// The DescriptorMap class provides a unique and continuous (but mutable)
    14421855  /// descriptor (id) for each item of the same type (e.g. node) in the
    1443   /// graph. This id is <ul><li>\b unique: different items (nodes) get
     1856  /// digraph. This id is <ul><li>\b unique: different items (nodes) get
    14441857  /// different ids <li>\b continuous: the range of the ids is the set of
    14451858  /// integers between 0 and \c n-1, where \c n is the number of the items of
    14461859  /// this type (e.g. nodes) (so the id of a node can change if you delete an
    14471860  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
    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.
     1861  /// with its member class \c InverseMap.
     1862  ///
     1863  /// \param _Digraph The digraph class the \c DescriptorMap belongs to.
    14511864  /// \param _Item The Item is the Key of the Map. It may be Node, Arc or
    14521865  /// Edge.
    1453   template <typename _Graph, typename _Item>
    1454   class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
     1866  template <typename _Digraph, typename _Item>
     1867  class DescriptorMap : protected DefaultMap<_Digraph, _Item, int> {
    14551868
    14561869    typedef _Item Item;
    1457     typedef DefaultMap<_Graph, _Item, int> Map;
     1870    typedef DefaultMap<_Digraph, _Item, int> Map;
    14581871
    14591872  public:
    1460     /// The graph class of DescriptorMap.
    1461     typedef _Graph Graph;
     1873    /// The digraph class of DescriptorMap.
     1874    typedef _Digraph Digraph;
    14621875
    14631876    /// The key type of DescriptorMap (Node, Arc, Edge).
    … …  
    14691882    ///
    14701883    /// Constructor for descriptor map.
    1471     explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
     1884    explicit DescriptorMap(const Digraph& _digraph) : Map(_digraph) {
    14721885      Item it;
    14731886      const typename Map::Notifier* nf = Map::notifier();
    14741887      for (nf->first(it); it != INVALID; nf->next(it)) {
    1475         Map::set(it, _inv_map.size());
    1476         _inv_map.push_back(it);
     1888        Map::set(it, invMap.size());
     1889        invMap.push_back(it);   
    14771890      }     
    14781891    }
    … …  
    14861899    virtual void add(const Item& item) {
    14871900      Map::add(item);
    1488       Map::set(item, _inv_map.size());
    1489       _inv_map.push_back(item);
     1901      Map::set(item, invMap.size());
     1902      invMap.push_back(item);
    14901903    }
    14911904
    … …  
    14971910      Map::add(items);
    14981911      for (int i = 0; i < int(items.size()); ++i) {
    1499         Map::set(items[i], _inv_map.size());
    1500         _inv_map.push_back(items[i]);
     1912        Map::set(items[i], invMap.size());
     1913        invMap.push_back(items[i]);
    15011914      }
    15021915    }
    … …  
    15071920    /// \c AlterationNotifier.
    15081921    virtual void erase(const Item& item) {
    1509       Map::set(_inv_map.back(), Map::operator[](item));
    1510       _inv_map[Map::operator[](item)] = _inv_map.back();
    1511       _inv_map.pop_back();
     1922      Map::set(invMap.back(), Map::operator[](item));
     1923      invMap[Map::operator[](item)] = invMap.back();
     1924      invMap.pop_back();
    15121925      Map::erase(item);
    15131926    }
    … …  
    15191932    virtual void erase(const std::vector<Item>& items) {
    15201933      for (int i = 0; i < int(items.size()); ++i) {
    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();
     1934        Map::set(invMap.back(), Map::operator[](items[i]));
     1935        invMap[Map::operator[](items[i])] = invMap.back();
     1936        invMap.pop_back();
    15241937      }
    15251938      Map::erase(items);
    … …  
    15351948      const typename Map::Notifier* nf = Map::notifier();
    15361949      for (nf->first(it); it != INVALID; nf->next(it)) {
    1537         Map::set(it, _inv_map.size());
    1538         _inv_map.push_back(it);
     1950        Map::set(it, invMap.size());
     1951        invMap.push_back(it);   
    15391952      }     
    15401953    }
    … …  
    15451958    /// \c AlterationNotifier.
    15461959    virtual void clear() {
    1547       _inv_map.clear();
     1960      invMap.clear();
    15481961      Map::clear();
    15491962    }
    … …  
    15551968    /// Returns the maximal value plus one in the map.
    15561969    unsigned int size() const {
    1557       return _inv_map.size();
     1970      return invMap.size();
    15581971    }
    15591972
    … …  
    15651978      int qi = Map::operator[](q);
    15661979      Map::set(p, qi);
    1567       _inv_map[qi] = p;
     1980      invMap[qi] = p;
    15681981      Map::set(q, pi);
    1569       _inv_map[pi] = q;
     1982      invMap[pi] = q;
    15701983    }
    15711984
    … …  
    15811994    /// Gives back th item by its descriptor.
    15821995    Item operator()(int id) const {
    1583       return _inv_map[id];
     1996      return invMap[id];
    15841997    }
    15851998   
    … …  
    15872000
    15882001    typedef std::vector<Item> Container;
    1589     Container _inv_map;
     2002    Container invMap;
    15902003
    15912004  public:
    … …  
    15982011      ///
    15992012      /// Constructor of the InverseMap.
    1600       explicit InverseMap(const DescriptorMap& inverted)
    1601         : _inverted(inverted) {}
     2013      explicit InverseMap(const DescriptorMap& _inverted)
     2014        : inverted(_inverted) {}
    16022015
    16032016
    … …  
    16122025      /// that the descriptor belongs to currently.
    16132026      Value operator[](const Key& key) const {
    1614         return _inverted(key);
     2027        return inverted(key);
    16152028      }
    16162029
    … …  
    16192032      /// Returns the size of the map.
    16202033      unsigned int size() const {
    1621         return _inverted.size();
     2034        return inverted.size();
    16222035      }
    16232036     
    16242037    private:
    1625       const DescriptorMap& _inverted;
     2038      const DescriptorMap& inverted;
    16262039    };
    16272040
    … …  
    16502063    /// Constructor
    16512064    /// \param _digraph The digraph that the map belongs to.
    1652     explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
     2065    explicit SourceMap(const Digraph& _digraph) : digraph(_digraph) {}
    16532066
    16542067    /// \brief The subscript operator.
    … …  
    16582071    /// \return The source of the arc
    16592072    Value operator[](const Key& arc) const {
    1660       return _digraph.source(arc);
     2073      return digraph.source(arc);
    16612074    }
    16622075
    16632076  private:
    1664     const Digraph& _digraph;
     2077    const Digraph& digraph;
    16652078  };
    16662079
    … …  
    16902103    /// Constructor
    16912104    /// \param _digraph The digraph that the map belongs to.
    1692     explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
     2105    explicit TargetMap(const Digraph& _digraph) : digraph(_digraph) {}
    16932106
    16942107    /// \brief The subscript operator.
    … …  
    16982111    /// \return The target of the arc
    16992112    Value operator[](const Key& e) const {
    1700       return _digraph.target(e);
     2113      return digraph.target(e);
    17012114    }
    17022115
    17032116  private:
    1704     const Digraph& _digraph;
     2117    const Digraph& digraph;
    17052118  };
    17062119
    … …  
    17192132  /// \see BackwardMap
    17202133  /// \author Balazs Dezso
    1721   template <typename Graph>
     2134  template <typename Digraph>
    17222135  class ForwardMap {
    17232136  public:
    17242137
    1725     typedef typename Graph::Arc Value;
    1726     typedef typename Graph::Edge Key;
     2138    typedef typename Digraph::Arc Value;
     2139    typedef typename Digraph::Edge Key;
    17272140
    17282141    /// \brief Constructor
    17292142    ///
    17302143    /// Constructor
    1731     /// \param _graph The graph that the map belongs to.
    1732     explicit ForwardMap(const Graph& graph) : _graph(graph) {}
     2144    /// \param _digraph The digraph that the map belongs to.
     2145    explicit ForwardMap(const Digraph& _digraph) : digraph(_digraph) {}
    17332146
    17342147    /// \brief The subscript operator.
    … …  
    17382151    /// \return The "forward" directed arc view of edge
    17392152    Value operator[](const Key& key) const {
    1740       return _graph.direct(key, true);
     2153      return digraph.direct(key, true);
    17412154    }
    17422155
    17432156  private:
    1744     const Graph& _graph;
     2157    const Digraph& digraph;
    17452158  };
    17462159
    … …  
    17492162  /// This function just returns an \ref ForwardMap class.
    17502163  /// \relates ForwardMap
    1751   template <typename Graph>
    1752   inline ForwardMap<Graph> forwardMap(const Graph& graph) {
    1753     return ForwardMap<Graph>(graph);
     2164  template <typename Digraph>
     2165  inline ForwardMap<Digraph> forwardMap(const Digraph& digraph) {
     2166    return ForwardMap<Digraph>(digraph);
    17542167  }
    17552168
    … …  
    17592172  /// \see ForwardMap
    17602173  /// \author Balazs Dezso
    1761   template <typename Graph>
     2174  template <typename Digraph>
    17622175  class BackwardMap {
    17632176  public:
    17642177
    1765     typedef typename Graph::Arc Value;
    1766     typedef typename Graph::Edge Key;
     2178    typedef typename Digraph::Arc Value;
     2179    typedef typename Digraph::Edge Key;
    17672180
    17682181    /// \brief Constructor
    17692182    ///
    17702183    /// Constructor
    1771     /// \param _graph The graph that the map belongs to.
    1772     explicit BackwardMap(const Graph& graph) : _graph(graph) {}
     2184    /// \param _digraph The digraph that the map belongs to.
     2185    explicit BackwardMap(const Digraph& _digraph) : digraph(_digraph) {}
    17732186
    17742187    /// \brief The subscript operator.
    … …  
    17782191    /// \return The "backward" directed arc view of edge
    17792192    Value operator[](const Key& key) const {
    1780       return _graph.direct(key, false);
     2193      return digraph.direct(key, false);
    17812194    }
    17822195
    17832196  private:
    1784     const Graph& _graph;
     2197    const Digraph& digraph;
    17852198  };
    17862199
    … …  
    17892202  /// This function just returns a \ref BackwardMap class.
    17902203  /// \relates BackwardMap
    1791   template <typename Graph>
    1792   inline BackwardMap<Graph> backwardMap(const Graph& graph) {
    1793     return BackwardMap<Graph>(graph);
     2204  template <typename Digraph>
     2205  inline BackwardMap<Digraph> backwardMap(const Digraph& digraph) {
     2206    return BackwardMap<Digraph>(digraph);
    17942207  }
    17952208
    … …  
    18082221    ///
    18092222    /// Contructor of the map
    1810     explicit PotentialDifferenceMap(const Digraph& digraph,
    1811                                     const NodeMap& potential)
    1812       : _digraph(digraph), _potential(potential) {}
     2223    explicit PotentialDifferenceMap(const Digraph& _digraph,
     2224                                    const NodeMap& _potential)
     2225      : digraph(_digraph), potential(_potential) {}
    18132226
    18142227    /// \brief Const subscription operator
    … …  
    18162229    /// Const subscription operator
    18172230    Value operator[](const Key& arc) const {
    1818       return _potential[_digraph.target(arc)] -
    1819         _potential[_digraph.source(arc)];
     2231      return potential[digraph.target(arc)] - potential[digraph.source(arc)];
    18202232    }
    18212233
    18222234  private:
    1823     const Digraph& _digraph;
    1824     const NodeMap& _potential;
     2235    const Digraph& digraph;
     2236    const NodeMap& potential;
    18252237  };
    18262238
    … …  
    18632275    typedef typename Digraph::Node Key;
    18642276
    1865     typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
     2277    typedef typename ItemSetTraits<_Digraph, typename _Digraph::Arc>
    18662278    ::ItemNotifier::ObserverBase Parent;
    18672279
    18682280  private:
    18692281
    1870     class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
     2282    class AutoNodeMap : public DefaultMap<_Digraph, Key, int> {
    18712283    public:
    18722284
    1873       typedef DefaultMap<Digraph, Key, int> Parent;
     2285      typedef DefaultMap<_Digraph, Key, int> Parent;
     2286      typedef typename Parent::Digraph Digraph;
    18742287
    18752288      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
    … …  
    19022315    ///
    19032316    /// Constructor for creating in-degree map.
    1904     explicit InDegMap(const Digraph& digraph)
    1905       : _digraph(digraph), _deg(digraph) {
    1906       Parent::attach(_digraph.notifier(typename Digraph::Arc()));
     2317    explicit InDegMap(const Digraph& _digraph) : digraph(_digraph), deg(_digraph) {
     2318      Parent::attach(digraph.notifier(typename _Digraph::Arc()));
    19072319     
    1908       for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
    1909         _deg[it] = countInArcs(_digraph, it);
     2320      for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
     2321        deg[it] = countInArcs(digraph, it);
    19102322      }
    19112323    }
    … …  
    19132325    /// Gives back the in-degree of a Node.
    19142326    int operator[](const Key& key) const {
    1915       return _deg[key];
     2327      return deg[key];
    19162328    }
    19172329
    … …  
    19212333
    19222334    virtual void add(const Arc& arc) {
    1923       ++_deg[_digraph.target(arc)];
     2335      ++deg[digraph.target(arc)];
    19242336    }
    19252337
    19262338    virtual void add(const std::vector<Arc>& arcs) {
    19272339      for (int i = 0; i < int(arcs.size()); ++i) {
    1928         ++_deg[_digraph.target(arcs[i])];
     2340        ++deg[digraph.target(arcs[i])];
    19292341      }
    19302342    }
    19312343
    19322344    virtual void erase(const Arc& arc) {
    1933       --_deg[_digraph.target(arc)];
     2345      --deg[digraph.target(arc)];
    19342346    }
    19352347
    19362348    virtual void erase(const std::vector<Arc>& arcs) {
    19372349      for (int i = 0; i < int(arcs.size()); ++i) {
    1938         --_deg[_digraph.target(arcs[i])];
     2350        --deg[digraph.target(arcs[i])];
    19392351      }
    19402352    }
    19412353
    19422354    virtual void build() {
    1943       for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
    1944         _deg[it] = countInArcs(_digraph, it);
     2355      for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
     2356        deg[it] = countInArcs(digraph, it);
    19452357      }     
    19462358    }
    19472359
    19482360    virtual void clear() {
    1949       for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
    1950         _deg[it] = 0;
     2361      for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
     2362        deg[it] = 0;
    19512363      }
    19522364    }
    19532365  private:
    19542366   
    1955     const Digraph& _digraph;
    1956     AutoNodeMap _deg;
     2367    const _Digraph& digraph;
     2368    AutoNodeMap deg;
    19572369  };
    19582370
    … …  
    19802392
    19812393  public:
     2394
     2395    typedef typename ItemSetTraits<_Digraph, typename _Digraph::Arc>
     2396    ::ItemNotifier::ObserverBase Parent;
    19822397   
    19832398    typedef _Digraph Digraph;
    … …  
    19852400    typedef typename Digraph::Node Key;
    19862401
    1987     typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
    1988     ::ItemNotifier::ObserverBase Parent;
    1989 
    19902402  private:
    19912403
    1992     class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
     2404    class AutoNodeMap : public DefaultMap<_Digraph, Key, int> {
    19932405    public:
    19942406
    1995       typedef DefaultMap<Digraph, Key, int> Parent;
     2407      typedef DefaultMap<_Digraph, Key, int> Parent;
     2408      typedef typename Parent::Digraph Digraph;
    19962409
    19972410      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
    … …  
    20222435    ///
    20232436    /// Constructor for creating out-degree map.
    2024     explicit OutDegMap(const Digraph& digraph)
    2025       : _digraph(digraph), _deg(digraph) {
    2026       Parent::attach(_digraph.notifier(typename Digraph::Arc()));
     2437    explicit OutDegMap(const Digraph& _digraph) : digraph(_digraph), deg(_digraph) {
     2438      Parent::attach(digraph.notifier(typename _Digraph::Arc()));
    20272439     
    2028       for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
    2029         _deg[it] = countOutArcs(_digraph, it);
     2440      for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
     2441        deg[it] = countOutArcs(digraph, it);
    20302442      }
    20312443    }
    … …  
    20332445    /// Gives back the out-degree of a Node.
    20342446    int operator[](const Key& key) const {
    2035       return _deg[key];
     2447      return deg[key];
    20362448    }
    20372449
    … …  
    20412453
    20422454    virtual void add(const Arc& arc) {
    2043       ++_deg[_digraph.source(arc)];
     2455      ++deg[digraph.source(arc)];
    20442456    }
    20452457
    20462458    virtual void add(const std::vector<Arc>& arcs) {
    20472459      for (int i = 0; i < int(arcs.size()); ++i) {
    2048         ++_deg[_digraph.source(arcs[i])];
     2460        ++deg[digraph.source(arcs[i])];
    20492461      }
    20502462    }
    20512463
    20522464    virtual void erase(const Arc& arc) {
    2053       --_deg[_digraph.source(arc)];
     2465      --deg[digraph.source(arc)];
    20542466    }
    20552467
    20562468    virtual void erase(const std::vector<Arc>& arcs) {
    20572469      for (int i = 0; i < int(arcs.size()); ++i) {
    2058         --_deg[_digraph.source(arcs[i])];
     2470        --deg[digraph.source(arcs[i])];
    20592471      }
    20602472    }
    20612473
    20622474    virtual void build() {
    2063       for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
    2064         _deg[it] = countOutArcs(_digraph, it);
     2475      for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
     2476        deg[it] = countOutArcs(digraph, it);
    20652477      }     
    20662478    }
    20672479
    20682480    virtual void clear() {
    2069       for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
    2070         _deg[it] = 0;
     2481      for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
     2482        deg[it] = 0;
    20712483      }
    20722484    }
    20732485  private:
    20742486   
    2075     const Digraph& _digraph;
    2076     AutoNodeMap _deg;
     2487    const _Digraph& digraph;
     2488    AutoNodeMap deg;
    20772489  };
    20782490
    … …  
    20892501  ///
    20902502  ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
    2091   ///digraph is not changed so frequently.
     2503  ///digraph do not changed so frequently.
    20922504  ///
    20932505  ///This class uses a self-adjusting binary search tree, Sleator's
    … …  
    21092521    ::ItemNotifier::ObserverBase Parent;
    21102522
    2111     TEMPLATE_DIGRAPH_TYPEDEFS(G);
     2523    GRAPH_TYPEDEFS(typename G);
    21122524    typedef G Digraph;
    21132525
    … …  
    24242836    Arc operator()(Node s, Node t) const
    24252837    {
    2426       Arc a = _head[s];
     2838      Arc e = _head[s];
    24272839      while (true) {
    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);
     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);
    24342846            return INVALID;
    24352847          } else {
    2436             a = _left[a];
     2848            e = _left[e];
    24372849          }
    24382850        } else  {
    2439           if (_right[a] == INVALID) {
    2440             const_cast<DynArcLookUp&>(*this).splay(a);
     2851          if (_right[e] == INVALID) {
     2852            const_cast<DynArcLookUp&>(*this).splay(e);
    24412853            return INVALID;
    24422854          } else {
    2443             a = _right[a];
     2855            e = _right[e];
    24442856          }
    24452857        }
    … …  
    24582870    Arc findFirst(Node s, Node t) const
    24592871    {
    2460       Arc a = _head[s];
     2872      Arc e = _head[s];
    24612873      Arc r = INVALID;
    24622874      while (true) {
    2463         if (_g.target(a) < t) {
    2464           if (_right[a] == INVALID) {
    2465             const_cast<DynArcLookUp&>(*this).splay(a);
     2875        if (_g.target(e) < t) {
     2876          if (_right[e] == INVALID) {
     2877            const_cast<DynArcLookUp&>(*this).splay(e);
    24662878            return r;
    24672879          } else {
    2468             a = _right[a];
     2880            e = _right[e];
    24692881          }
    24702882        } else {
    2471           if (_g.target(a) == t) {
    2472             r = a;
     2883          if (_g.target(e) == t) {
     2884            r = e;
    24732885          }
    2474           if (_left[a] == INVALID) {
    2475             const_cast<DynArcLookUp&>(*this).splay(a);
     2886          if (_left[e] == INVALID) {
     2887            const_cast<DynArcLookUp&>(*this).splay(e);
    24762888            return r;
    24772889          } else {
    2478             a = _left[a];
     2890            e = _left[e];
    24792891          }
    24802892        }
    … …  
    24952907    ///operation then the amorized time bound can not be guaranteed.
    24962908#ifdef DOXYGEN
    2497     Arc findNext(Node s, Node t, Arc a) const
     2909    Arc findNext(Node s, Node t, Arc e) const
    24982910#else
    2499     Arc findNext(Node, Node t, Arc a) const
     2911    Arc findNext(Node, Node t, Arc e) const
    25002912#endif
    25012913    {
    2502       if (_right[a] != INVALID) {
    2503         a = _right[a];
    2504         while (_left[a] != INVALID) {
    2505           a = _left[a];
     2914      if (_right[e] != INVALID) {
     2915        e = _right[e];
     2916        while (_left[e] != INVALID) {
     2917          e = _left[e];
    25062918        }
    2507         const_cast<DynArcLookUp&>(*this).splay(a);
     2919        const_cast<DynArcLookUp&>(*this).splay(e);
    25082920      } else {
    2509         while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
    2510           a = _parent[a];
     2921        while (_parent[e] != INVALID && _right[_parent[e]] ==  e) {
     2922          e = _parent[e];
    25112923        }
    2512         if (_parent[a] == INVALID) {
     2924        if (_parent[e] == INVALID) {
    25132925          return INVALID;
    25142926        } else {
    2515           a = _parent[a];
    2516           const_cast<DynArcLookUp&>(*this).splay(a);
     2927          e = _parent[e];
     2928          const_cast<DynArcLookUp&>(*this).splay(e);
    25172929        }
    25182930      }
    2519       if (_g.target(a) == t) return a;
     2931      if (_g.target(e) == t) return e;
    25202932      else return INVALID;   
    25212933    }
    … …  
    25462958  {
    25472959  public:
    2548     TEMPLATE_DIGRAPH_TYPEDEFS(G);
     2960    GRAPH_TYPEDEFS(typename G);
    25492961    typedef G Digraph;
    25502962
    … …  
    26633075    using ArcLookUp<G>::_head;
    26643076
    2665     TEMPLATE_DIGRAPH_TYPEDEFS(G);
     3077    GRAPH_TYPEDEFS(typename G);
    26663078    typedef G Digraph;
    26673079   

  • lemon/lgf_reader.h

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

  • lemon/lgf_writer.h

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

  • lemon/list_graph.h

    r149 r73  
    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 
    165155    Node addNode() {     
    166156      int n;
    … …  
    230220      nodes[n].next = first_free_node;
    231221      first_free_node = n;
    232       nodes[n].prev = -2;
    233222
    234223    }
    … …  
    259248     
    260249      arcs[n].next_in = first_free_arc;
    261       first_free_arc = n;
    262       arcs[n].prev_in = -2;
     250      first_free_arc = n;     
     251
    263252    }
    264253
    … …  
    361350      return Parent::addArc(s, t);
    362351    }
    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); }
    383352
    384353    /// Change the target of \c e to \c n
    … …  
    977946    static Edge edgeFromId(int id) { return Edge(id);}
    978947
    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 
    994948    Node addNode() {     
    995949      int n;
    … …  
    10601014      nodes[n].next = first_free_node;
    10611015      first_free_node = n;
    1062       nodes[n].prev = -2;
     1016
    10631017    }
    10641018   
    … …  
    10881042      arcs[n].next_out = first_free_arc;
    10891043      first_free_arc = n;     
    1090       arcs[n].prev_out = -2;
    1091       arcs[n | 1].prev_out = -2;
    10921044
    10931045    }
    … …  
    12061158      return Parent::addEdge(s, t);
    12071159    }
    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); }
    12351160    /// \brief Change the source of \c e to \c n
    12361161    ///

  • lemon/path.h

    r144 r100  
    904904
    905905    template <typename Path, typename Enable = void>
    906     struct RevPathTagIndicator {
     906    struct RevTagIndicator {
    907907      static const bool value = false;
    908908    };
    909909
    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
     910    template <typename Digraph>
     911    struct RevTagIndicator<
     912      Digraph,
     913      typename enable_if<typename Digraph::RevTag, void>::type
    927914    > {
    928915      static const bool value = true;
    … …  
    930917
    931918    template <typename Target, typename Source,
    932               bool buildEnable = BuildTagIndicator<Target>::value,
    933               bool revEnable = RevPathTagIndicator<Source>::value>
     919              typename BuildEnable = void, typename RevEnable = void>
    934920    struct PathCopySelector {
    935921      static void copy(Target& target, const Source& source) {
    … …  
    941927    };
    942928
    943     template <typename Target, typename Source>
    944     struct PathCopySelector<Target, Source, false, true> {
     929    template <typename Target, typename Source, typename BuildEnable>
     930    struct PathCopySelector<
     931      Target, Source, BuildEnable,
     932      typename enable_if<typename Source::RevPathTag, void>::type> {
    945933      static void copy(Target& target, const Source& source) {
    946934        target.clear();
    … …  
    951939    };
    952940
    953     template <typename Target, typename Source>
    954     struct PathCopySelector<Target, Source, true, false> {
     941    template <typename Target, typename Source, typename RevEnable>
     942    struct PathCopySelector<
     943      Target, Source,
     944      typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
    955945      static void copy(Target& target, const Source& source) {
    956946        target.clear();
    … …  
    960950
    961951    template <typename Target, typename Source>
    962     struct PathCopySelector<Target, Source, true, true> {
     952    struct PathCopySelector<
     953      Target, Source,
     954      typename enable_if<typename Target::BuildTag, void>::type,
     955      typename enable_if<typename Source::RevPathTag, void>::type> {
    963956      static void copy(Target& target, const Source& source) {
    964957        target.clear();

  • lemon/smart_graph.h

    r149 r125  
    7474   
    7575    typedef True NodeNumTag;
    76     typedef True EdgeNumTag;
     76    typedef True ArcNumTag;
    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     }
    124117
    125118    class Node {
    … …  
    268261    /// \sa reserveNode
    269262    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); }
    288263
    289264    ///Clear the digraph.
    … …  
    576551    static Edge edgeFromId(int id) { return Edge(id);}
    577552
    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 
    588553    Node addNode() {     
    589554      int n = nodes.size();
    … …  
    594559    }
    595560   
    596     Edge addEdge(Node u, Node v) {
     561    Edge addArc(Node u, Node v) {
    597562      int n = arcs.size();
    598563      arcs.push_back(ArcT());
    … …  
    675640    ///\return the new edge.
    676641    Edge addEdge(const Node& s, const Node& t) {
    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); }
     642      return Parent::addArc(s, t);
     643    }
    706644
    707645    ///Clear the graph.

  • lemon/time_measure.h

    r143 r126  
    2525
    2626#ifdef WIN32
    27 #define WIN32_LEAN_AND_MEAN
    28 #define NOMINMAX
    2927#include <windows.h>
    3028#include <cmath>
    … …  
    3432#endif
    3533
    36 #include <string>
    3734#include <fstream>
    3835#include <iostream>

  • test/Makefile.am

    r146 r119  
    11EXTRA_DIST += \
    2         test/CMakeLists.txt
     2        test/Makefile
    33
    44noinst_HEADERS += \
    55        test/digraph_test.h \
    6         test/graph_utils_test.h \
    76        test/heap_test.h \
    87        test/map_test.h \
    … …  
    1716        test/error_test \
    1817        test/graph_test \
    19         test/graph_utils_test \
    2018        test/kruskal_test \
    2119        test/maps_test \
    … …  
    3735test_error_test_SOURCES = test/error_test.cc
    3836test_graph_test_SOURCES = test/graph_test.cc
    39 test_graph_utils_test_SOURCES = test/graph_utils_test.cc
    4037# test_heap_test_SOURCES = test/heap_test.cc
    4138test_kruskal_test_SOURCES = test/kruskal_test.cc

  • test/graph_test.cc

    r149 r109  
    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 check_graph_counts() {
    86 
    87   TEMPLATE_GRAPH_TYPEDEFS(Graph);
     85void 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
     115template <typename Graph>
     116void 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
    88125  Graph g;
    89126
    … …  
    99136    e2 = g.addEdge(n2, n3);
    100137
     138  // print_items(g);
     139
    101140  check_item_counts(g,3,2);
    102141}
    103 
    104 template <typename Graph>
    105 void 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 
    131 template <typename Graph>
    132 void 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 
    167142
    168143// void checkGridGraph(const GridGraph& g, int w, int h) {
    … …  
    213188  check_concepts();
    214189
    215   check_graph_counts<ListGraph>();
    216   check_graph_counts<SmartGraph>();
    217 
    218   check_graph_validity_erase<ListGraph>();
    219   check_graph_validity<SmartGraph>();
     190  check_graph<ListGraph>();
     191  check_graph<SmartGraph>();
    220192
    221193//   {

  • tools/Makefile.am

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