lemon/graph_utils.h
author Balazs Dezso <deba@inf.elte.hu>
Wed, 23 Apr 2008 15:33:53 +0200
changeset 147 7c39a090cfc3
parent 140 356930927a71
child 148 4e2581021300
permissions -rw-r--r--
Fix missing semicolon in GRAPH_TYPEDEFS (ticket #89)
alpar@100
     1
/* -*- C++ -*-
alpar@100
     2
 *
alpar@100
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@100
     4
 *
alpar@100
     5
 * Copyright (C) 2003-2008
alpar@100
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@100
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@100
     8
 *
alpar@100
     9
 * Permission to use, modify and distribute this software is granted
alpar@100
    10
 * provided that this copyright notice appears in all copies. For
alpar@100
    11
 * precise terms see the accompanying LICENSE file.
alpar@100
    12
 *
alpar@100
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@100
    14
 * express or implied, and with no claim as to its suitability for any
alpar@100
    15
 * purpose.
alpar@100
    16
 *
alpar@100
    17
 */
alpar@100
    18
alpar@100
    19
#ifndef LEMON_GRAPH_UTILS_H
alpar@100
    20
#define LEMON_GRAPH_UTILS_H
alpar@100
    21
alpar@100
    22
#include <iterator>
alpar@100
    23
#include <vector>
alpar@100
    24
#include <map>
alpar@100
    25
#include <cmath>
alpar@100
    26
#include <algorithm>
alpar@100
    27
alpar@100
    28
#include <lemon/bits/invalid.h>
alpar@100
    29
#include <lemon/bits/utility.h>
alpar@100
    30
#include <lemon/maps.h>
alpar@100
    31
#include <lemon/bits/traits.h>
alpar@100
    32
alpar@100
    33
#include <lemon/bits/alteration_notifier.h>
alpar@100
    34
#include <lemon/bits/default_map.h>
alpar@100
    35
alpar@100
    36
///\ingroup gutils
alpar@100
    37
///\file
deba@139
    38
///\brief Graph utilities.
alpar@100
    39
alpar@100
    40
namespace lemon {
alpar@100
    41
alpar@100
    42
  /// \addtogroup gutils
alpar@100
    43
  /// @{
alpar@100
    44
deba@140
    45
  namespace _graph_utils_bits {
deba@140
    46
    template <typename Graph>
deba@140
    47
    struct Node { typedef typename Graph::Node type; };
deba@140
    48
deba@140
    49
    template <typename Graph>
deba@140
    50
    struct NodeIt { typedef typename Graph::NodeIt type; };
deba@140
    51
deba@140
    52
    template <typename Graph>
deba@140
    53
    struct Arc { typedef typename Graph::Arc type; };
deba@140
    54
deba@140
    55
    template <typename Graph>
deba@140
    56
    struct ArcIt { typedef typename Graph::ArcIt type; };
deba@140
    57
deba@140
    58
    template <typename Graph>
deba@140
    59
    struct Edge { typedef typename Graph::Edge type; };
deba@140
    60
deba@140
    61
    template <typename Graph>
deba@140
    62
    struct EdgeIt { typedef typename Graph::EdgeIt type; };
deba@140
    63
deba@140
    64
    template <typename Graph>
deba@140
    65
    struct OutArcIt { typedef typename Graph::OutArcIt type; };
deba@140
    66
deba@140
    67
    template <typename Graph>
deba@140
    68
    struct InArcIt { typedef typename Graph::InArcIt type; };
deba@140
    69
deba@140
    70
    template <typename Graph>
deba@140
    71
    struct IncEdgeIt { typedef typename Graph::IncEdgeIt type; };
deba@140
    72
deba@140
    73
    template <typename Graph>
deba@140
    74
    struct BoolNodeMap { 
deba@140
    75
      typedef typename Graph::template NodeMap<bool> type; 
deba@140
    76
    };
deba@140
    77
deba@140
    78
    template <typename Graph>
deba@140
    79
    struct IntNodeMap { 
deba@140
    80
      typedef typename Graph::template NodeMap<int> type; 
deba@140
    81
    };
deba@140
    82
deba@140
    83
    template <typename Graph>
deba@140
    84
    struct DoubleNodeMap { 
deba@140
    85
      typedef typename Graph::template NodeMap<double> type; 
deba@140
    86
    };
deba@140
    87
deba@140
    88
    template <typename Graph>
deba@140
    89
    struct BoolArcMap { 
deba@140
    90
      typedef typename Graph::template ArcMap<bool> type; 
deba@140
    91
    };
deba@140
    92
deba@140
    93
    template <typename Graph>
deba@140
    94
    struct IntArcMap { 
deba@140
    95
      typedef typename Graph::template ArcMap<int> type; 
deba@140
    96
    };
deba@140
    97
deba@140
    98
    template <typename Graph>
deba@140
    99
    struct DoubleArcMap { 
deba@140
   100
      typedef typename Graph::template ArcMap<double> type; 
deba@140
   101
    };
deba@140
   102
deba@140
   103
    template <typename Graph>
deba@140
   104
    struct BoolEdgeMap { 
deba@140
   105
      typedef typename Graph::template EdgeMap<bool> type; 
deba@140
   106
    };
deba@140
   107
deba@140
   108
    template <typename Graph>
deba@140
   109
    struct IntEdgeMap { 
deba@140
   110
      typedef typename Graph::template EdgeMap<int> type; 
deba@140
   111
    };
deba@140
   112
deba@140
   113
    template <typename Graph>
deba@140
   114
    struct DoubleEdgeMap { 
deba@140
   115
      typedef typename Graph::template EdgeMap<double> type; 
deba@140
   116
    };
deba@140
   117
deba@140
   118
    
deba@140
   119
  }
deba@140
   120
alpar@100
   121
  ///Creates convenience typedefs for the digraph types and iterators
alpar@100
   122
alpar@100
   123
  ///This \c \#define creates convenience typedefs for the following types
alpar@100
   124
  ///of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
deba@139
   125
  ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, 
deba@139
   126
  ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap. 
deba@139
   127
#define DIGRAPH_TYPEDEFS(Digraph)					\
deba@140
   128
  typedef typename ::lemon::_graph_utils_bits::				\
deba@140
   129
  Node<Digraph>::type Node;						\
deba@140
   130
  typedef typename ::lemon::_graph_utils_bits::				\
deba@140
   131
  NodeIt<Digraph>::type	NodeIt;						\
deba@140
   132
  typedef typename ::lemon::_graph_utils_bits::				\
deba@140
   133
  Arc<Digraph>::type Arc;						\
deba@140
   134
  typedef typename ::lemon::_graph_utils_bits::				\
deba@140
   135
  ArcIt<Digraph>::type ArcIt;						\
deba@140
   136
  typedef typename ::lemon::_graph_utils_bits::				\
deba@140
   137
  OutArcIt<Digraph>::type OutArcIt;					\
deba@140
   138
  typedef typename ::lemon::_graph_utils_bits::				\
deba@140
   139
  InArcIt<Digraph>::type InArcIt;					\
deba@140
   140
  typedef typename ::lemon::_graph_utils_bits::				\
deba@140
   141
  BoolNodeMap<Digraph>::type BoolNodeMap;				\
deba@140
   142
  typedef typename ::lemon::_graph_utils_bits::				\
deba@140
   143
  IntNodeMap<Digraph>::type IntNodeMap;					\
deba@140
   144
  typedef typename ::lemon::_graph_utils_bits::				\
deba@140
   145
  DoubleNodeMap<Digraph>::type DoubleNodeMap;				\
deba@140
   146
  typedef typename ::lemon::_graph_utils_bits::				\
deba@140
   147
  BoolArcMap<Digraph>::type BoolArcMap;					\
deba@140
   148
  typedef typename ::lemon::_graph_utils_bits::				\
deba@140
   149
  IntArcMap<Digraph>::type IntArcMap;					\
deba@140
   150
  typedef typename ::lemon::_graph_utils_bits::				\
deba@140
   151
  DoubleArcMap<Digraph>::type DoubleArcMap
deba@140
   152
alpar@100
   153
alpar@100
   154
  ///Creates convenience typedefs for the graph types and iterators
alpar@100
   155
deba@139
   156
  ///This \c \#define creates the same convenience typedefs as defined
deba@139
   157
  ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
deba@139
   158
  ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
deba@139
   159
  ///\c DoubleEdgeMap.
deba@139
   160
#define GRAPH_TYPEDEFS(Graph)						\
deba@139
   161
  DIGRAPH_TYPEDEFS(Graph);						\
deba@140
   162
  typedef typename ::lemon::_graph_utils_bits::				\
deba@140
   163
  Edge<Graph>::type Edge;						\
deba@140
   164
  typedef typename ::lemon::_graph_utils_bits::				\
deba@140
   165
  EdgeIt<Graph>::type EdgeIt;						\
deba@140
   166
  typedef typename ::lemon::_graph_utils_bits::				\
deba@147
   167
  IncEdgeIt<Graph>::type IncEdgeIt;					\
deba@140
   168
  typedef typename ::lemon::_graph_utils_bits::				\
deba@140
   169
  BoolEdgeMap<Graph>::type BoolEdgeMap;					\
deba@140
   170
  typedef typename ::lemon::_graph_utils_bits::				\
deba@140
   171
  IntEdgeMap<Graph>::type IntEdgeMap;					\
deba@140
   172
  typedef typename ::lemon::_graph_utils_bits::				\
deba@140
   173
  DoubleEdgeMap<Graph>::type DoubleEdgeMap
deba@140
   174
deba@139
   175
deba@139
   176
  /// \brief Function to count the items in the graph.
alpar@100
   177
  ///
deba@139
   178
  /// This function counts the items (nodes, arcs etc) in the graph.
alpar@100
   179
  /// The complexity of the function is O(n) because
alpar@100
   180
  /// it iterates on all of the items.
deba@139
   181
  template <typename Graph, typename Item>
deba@139
   182
  inline int countItems(const Graph& g) {
deba@139
   183
    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
alpar@100
   184
    int num = 0;
alpar@100
   185
    for (ItemIt it(g); it != INVALID; ++it) {
alpar@100
   186
      ++num;
alpar@100
   187
    }
alpar@100
   188
    return num;
alpar@100
   189
  }
alpar@100
   190
alpar@100
   191
  // Node counting:
alpar@100
   192
deba@139
   193
  namespace _graph_utils_bits {
alpar@100
   194
    
deba@139
   195
    template <typename Graph, typename Enable = void>
alpar@100
   196
    struct CountNodesSelector {
deba@139
   197
      static int count(const Graph &g) {
deba@139
   198
        return countItems<Graph, typename Graph::Node>(g);
alpar@100
   199
      }
alpar@100
   200
    };
alpar@100
   201
deba@139
   202
    template <typename Graph>
alpar@100
   203
    struct CountNodesSelector<
deba@139
   204
      Graph, typename 
deba@139
   205
      enable_if<typename Graph::NodeNumTag, void>::type> 
alpar@100
   206
    {
deba@139
   207
      static int count(const Graph &g) {
alpar@100
   208
        return g.nodeNum();
alpar@100
   209
      }
alpar@100
   210
    };    
alpar@100
   211
  }
alpar@100
   212
deba@139
   213
  /// \brief Function to count the nodes in the graph.
alpar@100
   214
  ///
deba@139
   215
  /// This function counts the nodes in the graph.
alpar@100
   216
  /// The complexity of the function is O(n) but for some
deba@139
   217
  /// graph structures it is specialized to run in O(1).
alpar@100
   218
  ///
deba@139
   219
  /// If the graph contains a \e nodeNum() member function and a 
alpar@100
   220
  /// \e NodeNumTag tag then this function calls directly the member
alpar@100
   221
  /// function to query the cardinality of the node set.
deba@139
   222
  template <typename Graph>
deba@139
   223
  inline int countNodes(const Graph& g) {
deba@139
   224
    return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
alpar@100
   225
  }
alpar@100
   226
deba@139
   227
  // Arc counting:
deba@139
   228
deba@139
   229
  namespace _graph_utils_bits {
alpar@100
   230
    
deba@139
   231
    template <typename Graph, typename Enable = void>
deba@139
   232
    struct CountArcsSelector {
deba@139
   233
      static int count(const Graph &g) {
deba@139
   234
        return countItems<Graph, typename Graph::Arc>(g);
alpar@100
   235
      }
alpar@100
   236
    };
alpar@100
   237
deba@139
   238
    template <typename Graph>
deba@139
   239
    struct CountArcsSelector<
deba@139
   240
      Graph, 
deba@139
   241
      typename enable_if<typename Graph::ArcNumTag, void>::type> 
alpar@100
   242
    {
deba@139
   243
      static int count(const Graph &g) {
alpar@100
   244
        return g.arcNum();
alpar@100
   245
      }
alpar@100
   246
    };    
alpar@100
   247
  }
alpar@100
   248
deba@139
   249
  /// \brief Function to count the arcs in the graph.
alpar@100
   250
  ///
deba@139
   251
  /// This function counts the arcs in the graph.
alpar@100
   252
  /// The complexity of the function is O(e) but for some
deba@139
   253
  /// graph structures it is specialized to run in O(1).
alpar@100
   254
  ///
deba@139
   255
  /// If the graph contains a \e arcNum() member function and a 
deba@139
   256
  /// \e EdgeNumTag tag then this function calls directly the member
alpar@100
   257
  /// function to query the cardinality of the arc set.
deba@139
   258
  template <typename Graph>
deba@139
   259
  inline int countArcs(const Graph& g) {
deba@139
   260
    return _graph_utils_bits::CountArcsSelector<Graph>::count(g);
alpar@100
   261
  }
alpar@100
   262
deba@139
   263
  // Edge counting:
deba@139
   264
  namespace _graph_utils_bits {
alpar@100
   265
    
deba@139
   266
    template <typename Graph, typename Enable = void>
alpar@100
   267
    struct CountEdgesSelector {
deba@139
   268
      static int count(const Graph &g) {
deba@139
   269
        return countItems<Graph, typename Graph::Edge>(g);
alpar@100
   270
      }
alpar@100
   271
    };
alpar@100
   272
deba@139
   273
    template <typename Graph>
alpar@100
   274
    struct CountEdgesSelector<
deba@139
   275
      Graph, 
deba@139
   276
      typename enable_if<typename Graph::EdgeNumTag, void>::type> 
alpar@100
   277
    {
deba@139
   278
      static int count(const Graph &g) {
alpar@100
   279
        return g.edgeNum();
alpar@100
   280
      }
alpar@100
   281
    };    
alpar@100
   282
  }
alpar@100
   283
deba@139
   284
  /// \brief Function to count the edges in the graph.
alpar@100
   285
  ///
deba@139
   286
  /// This function counts the edges in the graph.
deba@139
   287
  /// The complexity of the function is O(m) but for some
deba@139
   288
  /// graph structures it is specialized to run in O(1).
alpar@100
   289
  ///
deba@139
   290
  /// If the graph contains a \e edgeNum() member function and a 
deba@139
   291
  /// \e EdgeNumTag tag then this function calls directly the member
alpar@100
   292
  /// function to query the cardinality of the edge set.
deba@139
   293
  template <typename Graph>
deba@139
   294
  inline int countEdges(const Graph& g) {
deba@139
   295
    return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
alpar@100
   296
alpar@100
   297
  }
alpar@100
   298
alpar@100
   299
deba@139
   300
  template <typename Graph, typename DegIt>
deba@139
   301
  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
alpar@100
   302
    int num = 0;
alpar@100
   303
    for (DegIt it(_g, _n); it != INVALID; ++it) {
alpar@100
   304
      ++num;
alpar@100
   305
    }
alpar@100
   306
    return num;
alpar@100
   307
  }
alpar@100
   308
alpar@100
   309
  /// \brief Function to count the number of the out-arcs from node \c n.
alpar@100
   310
  ///
alpar@100
   311
  /// This function counts the number of the out-arcs from node \c n
deba@139
   312
  /// in the graph.  
deba@139
   313
  template <typename Graph>
deba@139
   314
  inline int countOutArcs(const Graph& _g,  const typename Graph::Node& _n) {
deba@139
   315
    return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);
alpar@100
   316
  }
alpar@100
   317
alpar@100
   318
  /// \brief Function to count the number of the in-arcs to node \c n.
alpar@100
   319
  ///
alpar@100
   320
  /// This function counts the number of the in-arcs to node \c n
deba@139
   321
  /// in the graph.  
deba@139
   322
  template <typename Graph>
deba@139
   323
  inline int countInArcs(const Graph& _g,  const typename Graph::Node& _n) {
deba@139
   324
    return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);
alpar@100
   325
  }
alpar@100
   326
deba@139
   327
  /// \brief Function to count the number of the inc-edges to node \c n.
alpar@100
   328
  ///
deba@139
   329
  /// This function counts the number of the inc-edges to node \c n
deba@139
   330
  /// in the graph.  
deba@139
   331
  template <typename Graph>
deba@139
   332
  inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) {
deba@139
   333
    return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
alpar@100
   334
  }
alpar@100
   335
deba@139
   336
  namespace _graph_utils_bits {
alpar@100
   337
    
deba@139
   338
    template <typename Graph, typename Enable = void>
alpar@100
   339
    struct FindArcSelector {
deba@139
   340
      typedef typename Graph::Node Node;
deba@139
   341
      typedef typename Graph::Arc Arc;
deba@139
   342
      static Arc find(const Graph &g, Node u, Node v, Arc e) {
alpar@100
   343
        if (e == INVALID) {
alpar@100
   344
          g.firstOut(e, u);
alpar@100
   345
        } else {
alpar@100
   346
          g.nextOut(e);
alpar@100
   347
        }
alpar@100
   348
        while (e != INVALID && g.target(e) != v) {
alpar@100
   349
          g.nextOut(e);
alpar@100
   350
        }
alpar@100
   351
        return e;
alpar@100
   352
      }
alpar@100
   353
    };
alpar@100
   354
deba@139
   355
    template <typename Graph>
alpar@100
   356
    struct FindArcSelector<
deba@139
   357
      Graph, 
deba@139
   358
      typename enable_if<typename Graph::FindEdgeTag, void>::type> 
alpar@100
   359
    {
deba@139
   360
      typedef typename Graph::Node Node;
deba@139
   361
      typedef typename Graph::Arc Arc;
deba@139
   362
      static Arc find(const Graph &g, Node u, Node v, Arc prev) {
alpar@100
   363
        return g.findArc(u, v, prev);
alpar@100
   364
      }
alpar@100
   365
    };    
alpar@100
   366
  }
alpar@100
   367
deba@139
   368
  /// \brief Finds an arc between two nodes of a graph.
alpar@100
   369
  ///
deba@139
   370
  /// Finds an arc from node \c u to node \c v in graph \c g.
alpar@100
   371
  ///
alpar@100
   372
  /// If \c prev is \ref INVALID (this is the default value), then
alpar@100
   373
  /// it finds the first arc from \c u to \c v. Otherwise it looks for
alpar@100
   374
  /// the next arc from \c u to \c v after \c prev.
alpar@100
   375
  /// \return The found arc or \ref INVALID if there is no such an arc.
alpar@100
   376
  ///
alpar@100
   377
  /// Thus you can iterate through each arc from \c u to \c v as it follows.
alpar@100
   378
  ///\code
alpar@100
   379
  /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) {
alpar@100
   380
  ///   ...
alpar@100
   381
  /// }
alpar@100
   382
  ///\endcode
alpar@100
   383
  ///
alpar@100
   384
  ///\sa ArcLookUp
alpar@100
   385
  ///\sa AllArcLookUp
alpar@100
   386
  ///\sa DynArcLookUp
alpar@100
   387
  ///\sa ConArcIt
deba@139
   388
  template <typename Graph>
deba@139
   389
  inline typename Graph::Arc 
deba@139
   390
  findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
deba@139
   391
           typename Graph::Arc prev = INVALID) {
deba@139
   392
    return _graph_utils_bits::FindArcSelector<Graph>::find(g, u, v, prev);
alpar@100
   393
  }
alpar@100
   394
alpar@100
   395
  /// \brief Iterator for iterating on arcs connected the same nodes.
alpar@100
   396
  ///
alpar@100
   397
  /// Iterator for iterating on arcs connected the same nodes. It is 
alpar@100
   398
  /// higher level interface for the findArc() function. You can
alpar@100
   399
  /// use it the following way:
alpar@100
   400
  ///\code
deba@139
   401
  /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
alpar@100
   402
  ///   ...
alpar@100
   403
  /// }
alpar@100
   404
  ///\endcode
alpar@100
   405
  /// 
alpar@100
   406
  ///\sa findArc()
alpar@100
   407
  ///\sa ArcLookUp
alpar@100
   408
  ///\sa AllArcLookUp
alpar@100
   409
  ///\sa DynArcLookUp
alpar@100
   410
  ///
alpar@100
   411
  /// \author Balazs Dezso 
deba@139
   412
  template <typename _Graph>
deba@139
   413
  class ConArcIt : public _Graph::Arc {
alpar@100
   414
  public:
alpar@100
   415
deba@139
   416
    typedef _Graph Graph;
deba@139
   417
    typedef typename Graph::Arc Parent;
alpar@100
   418
deba@139
   419
    typedef typename Graph::Arc Arc;
deba@139
   420
    typedef typename Graph::Node Node;
alpar@100
   421
alpar@100
   422
    /// \brief Constructor.
alpar@100
   423
    ///
alpar@100
   424
    /// Construct a new ConArcIt iterating on the arcs which
alpar@100
   425
    /// connects the \c u and \c v node.
deba@139
   426
    ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
deba@139
   427
      Parent::operator=(findArc(_graph, u, v));
alpar@100
   428
    }
alpar@100
   429
alpar@100
   430
    /// \brief Constructor.
alpar@100
   431
    ///
alpar@100
   432
    /// Construct a new ConArcIt which continues the iterating from 
alpar@100
   433
    /// the \c e arc.
deba@139
   434
    ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
alpar@100
   435
    
alpar@100
   436
    /// \brief Increment operator.
alpar@100
   437
    ///
alpar@100
   438
    /// It increments the iterator and gives back the next arc.
alpar@100
   439
    ConArcIt& operator++() {
deba@139
   440
      Parent::operator=(findArc(_graph, _graph.source(*this), 
deba@139
   441
				_graph.target(*this), *this));
alpar@100
   442
      return *this;
alpar@100
   443
    }
alpar@100
   444
  private:
deba@139
   445
    const Graph& _graph;
alpar@100
   446
  };
alpar@100
   447
deba@139
   448
  namespace _graph_utils_bits {
alpar@100
   449
    
deba@139
   450
    template <typename Graph, typename Enable = void>
alpar@100
   451
    struct FindEdgeSelector {
deba@139
   452
      typedef typename Graph::Node Node;
deba@139
   453
      typedef typename Graph::Edge Edge;
deba@139
   454
      static Edge find(const Graph &g, Node u, Node v, Edge e) {
alpar@100
   455
        bool b;
alpar@100
   456
        if (u != v) {
alpar@100
   457
          if (e == INVALID) {
alpar@100
   458
            g.firstInc(e, b, u);
alpar@100
   459
          } else {
alpar@100
   460
            b = g.source(e) == u;
alpar@100
   461
            g.nextInc(e, b);
alpar@100
   462
          }
alpar@100
   463
          while (e != INVALID && (b ? g.target(e) : g.source(e)) != v) {
alpar@100
   464
            g.nextInc(e, b);
alpar@100
   465
          }
alpar@100
   466
        } else {
alpar@100
   467
          if (e == INVALID) {
alpar@100
   468
            g.firstInc(e, b, u);
alpar@100
   469
          } else {
alpar@100
   470
            b = true;
alpar@100
   471
            g.nextInc(e, b);
alpar@100
   472
          }
alpar@100
   473
          while (e != INVALID && (!b || g.target(e) != v)) {
alpar@100
   474
            g.nextInc(e, b);
alpar@100
   475
          }
alpar@100
   476
        }
alpar@100
   477
        return e;
alpar@100
   478
      }
alpar@100
   479
    };
alpar@100
   480
deba@139
   481
    template <typename Graph>
alpar@100
   482
    struct FindEdgeSelector<
deba@139
   483
      Graph, 
deba@139
   484
      typename enable_if<typename Graph::FindEdgeTag, void>::type> 
alpar@100
   485
    {
deba@139
   486
      typedef typename Graph::Node Node;
deba@139
   487
      typedef typename Graph::Edge Edge;
deba@139
   488
      static Edge find(const Graph &g, Node u, Node v, Edge prev) {
alpar@100
   489
        return g.findEdge(u, v, prev);
alpar@100
   490
      }
alpar@100
   491
    };    
alpar@100
   492
  }
alpar@100
   493
deba@139
   494
  /// \brief Finds an edge between two nodes of a graph.
alpar@100
   495
  ///
deba@139
   496
  /// Finds an edge from node \c u to node \c v in graph \c g.
deba@139
   497
  /// If the node \c u and node \c v is equal then each loop edge
deba@139
   498
  /// will be enumerated once.
alpar@100
   499
  ///
alpar@100
   500
  /// If \c prev is \ref INVALID (this is the default value), then
alpar@100
   501
  /// it finds the first arc from \c u to \c v. Otherwise it looks for
alpar@100
   502
  /// the next arc from \c u to \c v after \c prev.
alpar@100
   503
  /// \return The found arc or \ref INVALID if there is no such an arc.
alpar@100
   504
  ///
alpar@100
   505
  /// Thus you can iterate through each arc from \c u to \c v as it follows.
alpar@100
   506
  ///\code
alpar@100
   507
  /// for(Edge e = findEdge(g,u,v); e != INVALID; 
alpar@100
   508
  ///     e = findEdge(g,u,v,e)) {
alpar@100
   509
  ///   ...
alpar@100
   510
  /// }
alpar@100
   511
  ///\endcode
alpar@100
   512
  ///
alpar@100
   513
  ///\sa ConArcIt
alpar@100
   514
deba@139
   515
  template <typename Graph>
deba@139
   516
  inline typename Graph::Edge 
deba@139
   517
  findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
deba@139
   518
            typename Graph::Edge p = INVALID) {
deba@139
   519
    return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
alpar@100
   520
  }
alpar@100
   521
alpar@100
   522
  /// \brief Iterator for iterating on edges connected the same nodes.
alpar@100
   523
  ///
alpar@100
   524
  /// Iterator for iterating on edges connected the same nodes. It is 
alpar@100
   525
  /// higher level interface for the findEdge() function. You can
alpar@100
   526
  /// use it the following way:
alpar@100
   527
  ///\code
deba@139
   528
  /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
alpar@100
   529
  ///   ...
alpar@100
   530
  /// }
alpar@100
   531
  ///\endcode
alpar@100
   532
  ///
alpar@100
   533
  ///\sa findEdge()
alpar@100
   534
  ///
alpar@100
   535
  /// \author Balazs Dezso 
deba@139
   536
  template <typename _Graph>
deba@139
   537
  class ConEdgeIt : public _Graph::Edge {
alpar@100
   538
  public:
alpar@100
   539
deba@139
   540
    typedef _Graph Graph;
deba@139
   541
    typedef typename Graph::Edge Parent;
alpar@100
   542
deba@139
   543
    typedef typename Graph::Edge Edge;
deba@139
   544
    typedef typename Graph::Node Node;
alpar@100
   545
alpar@100
   546
    /// \brief Constructor.
alpar@100
   547
    ///
deba@139
   548
    /// Construct a new ConEdgeIt iterating on the edges which
alpar@100
   549
    /// connects the \c u and \c v node.
deba@139
   550
    ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
deba@139
   551
      Parent::operator=(findEdge(_graph, u, v));
alpar@100
   552
    }
alpar@100
   553
alpar@100
   554
    /// \brief Constructor.
alpar@100
   555
    ///
alpar@100
   556
    /// Construct a new ConEdgeIt which continues the iterating from 
deba@139
   557
    /// the \c e edge.
deba@139
   558
    ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
alpar@100
   559
    
alpar@100
   560
    /// \brief Increment operator.
alpar@100
   561
    ///
deba@139
   562
    /// It increments the iterator and gives back the next edge.
alpar@100
   563
    ConEdgeIt& operator++() {
deba@139
   564
      Parent::operator=(findEdge(_graph, _graph.source(*this), 
deba@139
   565
				 _graph.target(*this), *this));
alpar@100
   566
      return *this;
alpar@100
   567
    }
alpar@100
   568
  private:
deba@139
   569
    const Graph& _graph;
alpar@100
   570
  };
alpar@100
   571
deba@139
   572
  namespace _graph_utils_bits {
alpar@100
   573
alpar@100
   574
    template <typename Digraph, typename Item, typename RefMap>
alpar@100
   575
    class MapCopyBase {
alpar@100
   576
    public:
alpar@100
   577
      virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
alpar@100
   578
      
alpar@100
   579
      virtual ~MapCopyBase() {}
alpar@100
   580
    };
alpar@100
   581
alpar@100
   582
    template <typename Digraph, typename Item, typename RefMap, 
alpar@100
   583
              typename ToMap, typename FromMap>
alpar@100
   584
    class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
alpar@100
   585
    public:
alpar@100
   586
alpar@100
   587
      MapCopy(ToMap& tmap, const FromMap& map) 
alpar@100
   588
        : _tmap(tmap), _map(map) {}
alpar@100
   589
      
alpar@100
   590
      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
alpar@100
   591
        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
alpar@100
   592
        for (ItemIt it(digraph); it != INVALID; ++it) {
alpar@100
   593
          _tmap.set(refMap[it], _map[it]);
alpar@100
   594
        }
alpar@100
   595
      }
alpar@100
   596
alpar@100
   597
    private:
alpar@100
   598
      ToMap& _tmap;
alpar@100
   599
      const FromMap& _map;
alpar@100
   600
    };
alpar@100
   601
alpar@100
   602
    template <typename Digraph, typename Item, typename RefMap, typename It>
alpar@100
   603
    class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
alpar@100
   604
    public:
alpar@100
   605
alpar@100
   606
      ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
alpar@100
   607
      
alpar@100
   608
      virtual void copy(const Digraph&, const RefMap& refMap) {
alpar@100
   609
        _it = refMap[_item];
alpar@100
   610
      }
alpar@100
   611
alpar@100
   612
    private:
alpar@100
   613
      It& _it;
alpar@100
   614
      Item _item;
alpar@100
   615
    };
alpar@100
   616
alpar@100
   617
    template <typename Digraph, typename Item, typename RefMap, typename Ref>
alpar@100
   618
    class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
alpar@100
   619
    public:
alpar@100
   620
alpar@100
   621
      RefCopy(Ref& map) : _map(map) {}
alpar@100
   622
      
alpar@100
   623
      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
alpar@100
   624
        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
alpar@100
   625
        for (ItemIt it(digraph); it != INVALID; ++it) {
alpar@100
   626
          _map.set(it, refMap[it]);
alpar@100
   627
        }
alpar@100
   628
      }
alpar@100
   629
alpar@100
   630
    private:
alpar@100
   631
      Ref& _map;
alpar@100
   632
    };
alpar@100
   633
alpar@100
   634
    template <typename Digraph, typename Item, typename RefMap, 
alpar@100
   635
              typename CrossRef>
alpar@100
   636
    class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
alpar@100
   637
    public:
alpar@100
   638
alpar@100
   639
      CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
alpar@100
   640
      
alpar@100
   641
      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
alpar@100
   642
        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
alpar@100
   643
        for (ItemIt it(digraph); it != INVALID; ++it) {
alpar@100
   644
          _cmap.set(refMap[it], it);
alpar@100
   645
        }
alpar@100
   646
      }
alpar@100
   647
alpar@100
   648
    private:
alpar@100
   649
      CrossRef& _cmap;
alpar@100
   650
    };
alpar@100
   651
alpar@100
   652
    template <typename Digraph, typename Enable = void>
alpar@100
   653
    struct DigraphCopySelector {
alpar@100
   654
      template <typename From, typename NodeRefMap, typename ArcRefMap>
alpar@100
   655
      static void copy(Digraph &to, const From& from,
alpar@100
   656
                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
alpar@100
   657
        for (typename From::NodeIt it(from); it != INVALID; ++it) {
alpar@100
   658
          nodeRefMap[it] = to.addNode();
alpar@100
   659
        }
alpar@100
   660
        for (typename From::ArcIt it(from); it != INVALID; ++it) {
alpar@100
   661
          arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)], 
alpar@100
   662
                                          nodeRefMap[from.target(it)]);
alpar@100
   663
        }
alpar@100
   664
      }
alpar@100
   665
    };
alpar@100
   666
alpar@100
   667
    template <typename Digraph>
alpar@100
   668
    struct DigraphCopySelector<
alpar@100
   669
      Digraph, 
alpar@100
   670
      typename enable_if<typename Digraph::BuildTag, void>::type> 
alpar@100
   671
    {
alpar@100
   672
      template <typename From, typename NodeRefMap, typename ArcRefMap>
alpar@100
   673
      static void copy(Digraph &to, const From& from,
alpar@100
   674
                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
alpar@100
   675
        to.build(from, nodeRefMap, arcRefMap);
alpar@100
   676
      }
alpar@100
   677
    };
alpar@100
   678
alpar@100
   679
    template <typename Graph, typename Enable = void>
alpar@100
   680
    struct GraphCopySelector {
alpar@100
   681
      template <typename From, typename NodeRefMap, typename EdgeRefMap>
alpar@100
   682
      static void copy(Graph &to, const From& from,
alpar@100
   683
                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
alpar@100
   684
        for (typename From::NodeIt it(from); it != INVALID; ++it) {
alpar@100
   685
          nodeRefMap[it] = to.addNode();
alpar@100
   686
        }
alpar@100
   687
        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
alpar@100
   688
          edgeRefMap[it] = to.addArc(nodeRefMap[from.source(it)], 
alpar@100
   689
				       nodeRefMap[from.target(it)]);
alpar@100
   690
        }
alpar@100
   691
      }
alpar@100
   692
    };
alpar@100
   693
alpar@100
   694
    template <typename Graph>
alpar@100
   695
    struct GraphCopySelector<
alpar@100
   696
      Graph, 
alpar@100
   697
      typename enable_if<typename Graph::BuildTag, void>::type> 
alpar@100
   698
    {
alpar@100
   699
      template <typename From, typename NodeRefMap, typename EdgeRefMap>
alpar@100
   700
      static void copy(Graph &to, const From& from,
alpar@100
   701
                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
alpar@100
   702
        to.build(from, nodeRefMap, edgeRefMap);
alpar@100
   703
      }
alpar@100
   704
    };
alpar@100
   705
alpar@100
   706
  }
alpar@100
   707
alpar@100
   708
  /// \brief Class to copy a digraph.
alpar@100
   709
  ///
alpar@100
   710
  /// Class to copy a digraph to another digraph (duplicate a digraph). The
alpar@100
   711
  /// simplest way of using it is through the \c copyDigraph() function.
deba@139
   712
  ///
deba@139
   713
  /// This class not just make a copy of a graph, but it can create
deba@139
   714
  /// references and cross references between the nodes and arcs of
deba@139
   715
  /// the two graphs, it can copy maps for use with the newly created
deba@139
   716
  /// graph and copy nodes and arcs.
deba@139
   717
  ///
deba@139
   718
  /// To make a copy from a graph, first an instance of DigraphCopy
deba@139
   719
  /// should be created, then the data belongs to the graph should
deba@139
   720
  /// assigned to copy. In the end, the \c run() member should be
deba@139
   721
  /// called.
deba@139
   722
  ///
deba@139
   723
  /// The next code copies a graph with several data:
deba@139
   724
  ///\code
deba@139
   725
  ///  DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
deba@139
   726
  ///  // create a reference for the nodes
deba@139
   727
  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
deba@139
   728
  ///  dc.nodeRef(nr);
deba@139
   729
  ///  // create a cross reference (inverse) for the arcs
deba@139
   730
  ///  NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
deba@139
   731
  ///  dc.arcCrossRef(acr);
deba@139
   732
  ///  // copy an arc map
deba@139
   733
  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
deba@139
   734
  ///  NewGraph::ArcMap<double> namap(new_graph);
deba@139
   735
  ///  dc.arcMap(namap, oamap);
deba@139
   736
  ///  // copy a node
deba@139
   737
  ///  OrigGraph::Node on;
deba@139
   738
  ///  NewGraph::Node nn;
deba@139
   739
  ///  dc.node(nn, on);
deba@139
   740
  ///  // Executions of copy
deba@139
   741
  ///  dc.run();
deba@139
   742
  ///\endcode
alpar@100
   743
  template <typename To, typename From>
alpar@100
   744
  class DigraphCopy {
alpar@100
   745
  private:
alpar@100
   746
alpar@100
   747
    typedef typename From::Node Node;
alpar@100
   748
    typedef typename From::NodeIt NodeIt;
alpar@100
   749
    typedef typename From::Arc Arc;
alpar@100
   750
    typedef typename From::ArcIt ArcIt;
alpar@100
   751
alpar@100
   752
    typedef typename To::Node TNode;
alpar@100
   753
    typedef typename To::Arc TArc;
alpar@100
   754
alpar@100
   755
    typedef typename From::template NodeMap<TNode> NodeRefMap;
alpar@100
   756
    typedef typename From::template ArcMap<TArc> ArcRefMap;
alpar@100
   757
    
alpar@100
   758
    
alpar@100
   759
  public: 
alpar@100
   760
alpar@100
   761
alpar@100
   762
    /// \brief Constructor for the DigraphCopy.
alpar@100
   763
    ///
alpar@100
   764
    /// It copies the content of the \c _from digraph into the
alpar@100
   765
    /// \c _to digraph.
deba@139
   766
    DigraphCopy(To& to, const From& from) 
deba@139
   767
      : _from(from), _to(to) {}
alpar@100
   768
alpar@100
   769
    /// \brief Destructor of the DigraphCopy
alpar@100
   770
    ///
alpar@100
   771
    /// Destructor of the DigraphCopy
alpar@100
   772
    ~DigraphCopy() {
deba@139
   773
      for (int i = 0; i < int(_node_maps.size()); ++i) {
deba@139
   774
        delete _node_maps[i];
alpar@100
   775
      }
deba@139
   776
      for (int i = 0; i < int(_arc_maps.size()); ++i) {
deba@139
   777
        delete _arc_maps[i];
alpar@100
   778
      }
alpar@100
   779
alpar@100
   780
    }
alpar@100
   781
alpar@100
   782
    /// \brief Copies the node references into the given map.
alpar@100
   783
    ///
deba@139
   784
    /// Copies the node references into the given map. The parameter
deba@139
   785
    /// should be a map, which key type is the Node type of the source
deba@139
   786
    /// graph, while the value type is the Node type of the
deba@139
   787
    /// destination graph.
alpar@100
   788
    template <typename NodeRef>
alpar@100
   789
    DigraphCopy& nodeRef(NodeRef& map) {
deba@139
   790
      _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node, 
deba@139
   791
			   NodeRefMap, NodeRef>(map));
alpar@100
   792
      return *this;
alpar@100
   793
    }
alpar@100
   794
alpar@100
   795
    /// \brief Copies the node cross references into the given map.
alpar@100
   796
    ///
alpar@100
   797
    ///  Copies the node cross references (reverse references) into
deba@139
   798
    ///  the given map. The parameter should be a map, which key type
deba@139
   799
    ///  is the Node type of the destination graph, while the value type is
deba@139
   800
    ///  the Node type of the source graph.
alpar@100
   801
    template <typename NodeCrossRef>
alpar@100
   802
    DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
deba@139
   803
      _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
deba@139
   804
			   NodeRefMap, NodeCrossRef>(map));
alpar@100
   805
      return *this;
alpar@100
   806
    }
alpar@100
   807
alpar@100
   808
    /// \brief Make copy of the given map.
alpar@100
   809
    ///
deba@139
   810
    /// Makes copy of the given map for the newly created digraph.
deba@139
   811
    /// The new map's key type is the destination graph's node type,
deba@139
   812
    /// and the copied map's key type is the source graph's node type.
alpar@100
   813
    template <typename ToMap, typename FromMap>
alpar@100
   814
    DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
deba@139
   815
      _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node, 
deba@139
   816
			   NodeRefMap, ToMap, FromMap>(tmap, map));
alpar@100
   817
      return *this;
alpar@100
   818
    }
alpar@100
   819
alpar@100
   820
    /// \brief Make a copy of the given node.
alpar@100
   821
    ///
alpar@100
   822
    /// Make a copy of the given node.
alpar@100
   823
    DigraphCopy& node(TNode& tnode, const Node& snode) {
deba@139
   824
      _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node, 
deba@139
   825
			   NodeRefMap, TNode>(tnode, snode));
alpar@100
   826
      return *this;
alpar@100
   827
    }
alpar@100
   828
alpar@100
   829
    /// \brief Copies the arc references into the given map.
alpar@100
   830
    ///
alpar@100
   831
    /// Copies the arc references into the given map.
alpar@100
   832
    template <typename ArcRef>
alpar@100
   833
    DigraphCopy& arcRef(ArcRef& map) {
deba@139
   834
      _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc, 
deba@139
   835
			  ArcRefMap, ArcRef>(map));
alpar@100
   836
      return *this;
alpar@100
   837
    }
alpar@100
   838
alpar@100
   839
    /// \brief Copies the arc cross references into the given map.
alpar@100
   840
    ///
alpar@100
   841
    ///  Copies the arc cross references (reverse references) into
alpar@100
   842
    ///  the given map.
alpar@100
   843
    template <typename ArcCrossRef>
alpar@100
   844
    DigraphCopy& arcCrossRef(ArcCrossRef& map) {
deba@139
   845
      _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
deba@139
   846
			  ArcRefMap, ArcCrossRef>(map));
alpar@100
   847
      return *this;
alpar@100
   848
    }
alpar@100
   849
alpar@100
   850
    /// \brief Make copy of the given map.
alpar@100
   851
    ///
alpar@100
   852
    /// Makes copy of the given map for the newly created digraph. 
alpar@100
   853
    /// The new map's key type is the to digraph's arc type,
alpar@100
   854
    /// and the copied map's key type is the from digraph's arc
alpar@100
   855
    /// type.  
alpar@100
   856
    template <typename ToMap, typename FromMap>
alpar@100
   857
    DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
deba@139
   858
      _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc, 
deba@139
   859
			  ArcRefMap, ToMap, FromMap>(tmap, map));
alpar@100
   860
      return *this;
alpar@100
   861
    }
alpar@100
   862
alpar@100
   863
    /// \brief Make a copy of the given arc.
alpar@100
   864
    ///
alpar@100
   865
    /// Make a copy of the given arc.
alpar@100
   866
    DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
deba@139
   867
      _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc, 
deba@139
   868
			  ArcRefMap, TArc>(tarc, sarc));
alpar@100
   869
      return *this;
alpar@100
   870
    }
alpar@100
   871
alpar@100
   872
    /// \brief Executes the copies.
alpar@100
   873
    ///
alpar@100
   874
    /// Executes the copies.
alpar@100
   875
    void run() {
deba@139
   876
      NodeRefMap nodeRefMap(_from);
deba@139
   877
      ArcRefMap arcRefMap(_from);
deba@139
   878
      _graph_utils_bits::DigraphCopySelector<To>::
deba@139
   879
        copy(_to, _from, nodeRefMap, arcRefMap);
deba@139
   880
      for (int i = 0; i < int(_node_maps.size()); ++i) {
deba@139
   881
        _node_maps[i]->copy(_from, nodeRefMap);
alpar@100
   882
      }
deba@139
   883
      for (int i = 0; i < int(_arc_maps.size()); ++i) {
deba@139
   884
        _arc_maps[i]->copy(_from, arcRefMap);
alpar@100
   885
      }      
alpar@100
   886
    }
alpar@100
   887
alpar@100
   888
  protected:
alpar@100
   889
alpar@100
   890
deba@139
   891
    const From& _from;
deba@139
   892
    To& _to;
alpar@100
   893
deba@139
   894
    std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* > 
deba@139
   895
    _node_maps;
alpar@100
   896
deba@139
   897
    std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* > 
deba@139
   898
    _arc_maps;
alpar@100
   899
alpar@100
   900
  };
alpar@100
   901
alpar@100
   902
  /// \brief Copy a digraph to another digraph.
alpar@100
   903
  ///
deba@139
   904
  /// Copy a digraph to another digraph. The complete usage of the
deba@139
   905
  /// function is detailed in the DigraphCopy class, but a short
deba@139
   906
  /// example shows a basic work:
alpar@100
   907
  ///\code
alpar@100
   908
  /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
alpar@100
   909
  ///\endcode
alpar@100
   910
  /// 
alpar@100
   911
  /// After the copy the \c nr map will contain the mapping from the
alpar@100
   912
  /// nodes of the \c from digraph to the nodes of the \c to digraph and
alpar@100
   913
  /// \c ecr will contain the mapping from the arcs of the \c to digraph
alpar@100
   914
  /// to the arcs of the \c from digraph.
alpar@100
   915
  ///
alpar@100
   916
  /// \see DigraphCopy 
alpar@100
   917
  template <typename To, typename From>
alpar@100
   918
  DigraphCopy<To, From> copyDigraph(To& to, const From& from) {
alpar@100
   919
    return DigraphCopy<To, From>(to, from);
alpar@100
   920
  }
alpar@100
   921
deba@139
   922
  /// \brief Class to copy a graph.
alpar@100
   923
  ///
deba@139
   924
  /// Class to copy a graph to another graph (duplicate a graph). The
deba@139
   925
  /// simplest way of using it is through the \c copyGraph() function.
deba@139
   926
  ///
deba@139
   927
  /// This class not just make a copy of a graph, but it can create
deba@139
   928
  /// references and cross references between the nodes, edges and arcs of
deba@139
   929
  /// the two graphs, it can copy maps for use with the newly created
deba@139
   930
  /// graph and copy nodes, edges and arcs.
deba@139
   931
  ///
deba@139
   932
  /// To make a copy from a graph, first an instance of GraphCopy
deba@139
   933
  /// should be created, then the data belongs to the graph should
deba@139
   934
  /// assigned to copy. In the end, the \c run() member should be
deba@139
   935
  /// called.
deba@139
   936
  ///
deba@139
   937
  /// The next code copies a graph with several data:
deba@139
   938
  ///\code
deba@139
   939
  ///  GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
deba@139
   940
  ///  // create a reference for the nodes
deba@139
   941
  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
deba@139
   942
  ///  dc.nodeRef(nr);
deba@139
   943
  ///  // create a cross reference (inverse) for the edges
deba@139
   944
  ///  NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph);
deba@139
   945
  ///  dc.edgeCrossRef(ecr);
deba@139
   946
  ///  // copy an arc map
deba@139
   947
  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
deba@139
   948
  ///  NewGraph::ArcMap<double> namap(new_graph);
deba@139
   949
  ///  dc.arcMap(namap, oamap);
deba@139
   950
  ///  // copy a node
deba@139
   951
  ///  OrigGraph::Node on;
deba@139
   952
  ///  NewGraph::Node nn;
deba@139
   953
  ///  dc.node(nn, on);
deba@139
   954
  ///  // Executions of copy
deba@139
   955
  ///  dc.run();
deba@139
   956
  ///\endcode
alpar@100
   957
  template <typename To, typename From>
alpar@100
   958
  class GraphCopy {
alpar@100
   959
  private:
alpar@100
   960
alpar@100
   961
    typedef typename From::Node Node;
alpar@100
   962
    typedef typename From::NodeIt NodeIt;
alpar@100
   963
    typedef typename From::Arc Arc;
alpar@100
   964
    typedef typename From::ArcIt ArcIt;
alpar@100
   965
    typedef typename From::Edge Edge;
alpar@100
   966
    typedef typename From::EdgeIt EdgeIt;
alpar@100
   967
alpar@100
   968
    typedef typename To::Node TNode;
alpar@100
   969
    typedef typename To::Arc TArc;
alpar@100
   970
    typedef typename To::Edge TEdge;
alpar@100
   971
alpar@100
   972
    typedef typename From::template NodeMap<TNode> NodeRefMap;
alpar@100
   973
    typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
alpar@100
   974
alpar@100
   975
    struct ArcRefMap {
deba@139
   976
      ArcRefMap(const To& to, const From& from,
deba@139
   977
		const EdgeRefMap& edge_ref, const NodeRefMap& node_ref) 
deba@139
   978
        : _to(to), _from(from), 
deba@139
   979
          _edge_ref(edge_ref), _node_ref(node_ref) {}
alpar@100
   980
alpar@100
   981
      typedef typename From::Arc Key;
alpar@100
   982
      typedef typename To::Arc Value;
alpar@100
   983
alpar@100
   984
      Value operator[](const Key& key) const {
alpar@100
   985
        bool forward = 
deba@139
   986
          (_from.direction(key) == 
deba@139
   987
	   (_node_ref[_from.source(key)] == _to.source(_edge_ref[key])));
deba@139
   988
	return _to.direct(_edge_ref[key], forward); 
alpar@100
   989
      }
alpar@100
   990
      
deba@139
   991
      const To& _to;
deba@139
   992
      const From& _from;
deba@139
   993
      const EdgeRefMap& _edge_ref;
deba@139
   994
      const NodeRefMap& _node_ref;
alpar@100
   995
    };
alpar@100
   996
alpar@100
   997
    
alpar@100
   998
  public: 
alpar@100
   999
alpar@100
  1000
deba@139
  1001
    /// \brief Constructor for the GraphCopy.
alpar@100
  1002
    ///
deba@139
  1003
    /// It copies the content of the \c _from graph into the
deba@139
  1004
    /// \c _to graph.
deba@139
  1005
    GraphCopy(To& to, const From& from) 
deba@139
  1006
      : _from(from), _to(to) {}
alpar@100
  1007
deba@139
  1008
    /// \brief Destructor of the GraphCopy
alpar@100
  1009
    ///
deba@139
  1010
    /// Destructor of the GraphCopy
alpar@100
  1011
    ~GraphCopy() {
deba@139
  1012
      for (int i = 0; i < int(_node_maps.size()); ++i) {
deba@139
  1013
        delete _node_maps[i];
alpar@100
  1014
      }
deba@139
  1015
      for (int i = 0; i < int(_arc_maps.size()); ++i) {
deba@139
  1016
        delete _arc_maps[i];
alpar@100
  1017
      }
deba@139
  1018
      for (int i = 0; i < int(_edge_maps.size()); ++i) {
deba@139
  1019
        delete _edge_maps[i];
alpar@100
  1020
      }
alpar@100
  1021
alpar@100
  1022
    }
alpar@100
  1023
alpar@100
  1024
    /// \brief Copies the node references into the given map.
alpar@100
  1025
    ///
alpar@100
  1026
    /// Copies the node references into the given map.
alpar@100
  1027
    template <typename NodeRef>
alpar@100
  1028
    GraphCopy& nodeRef(NodeRef& map) {
deba@139
  1029
      _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node, 
deba@139
  1030
			   NodeRefMap, NodeRef>(map));
alpar@100
  1031
      return *this;
alpar@100
  1032
    }
alpar@100
  1033
alpar@100
  1034
    /// \brief Copies the node cross references into the given map.
alpar@100
  1035
    ///
alpar@100
  1036
    ///  Copies the node cross references (reverse references) into
alpar@100
  1037
    ///  the given map.
alpar@100
  1038
    template <typename NodeCrossRef>
alpar@100
  1039
    GraphCopy& nodeCrossRef(NodeCrossRef& map) {
deba@139
  1040
      _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
deba@139
  1041
			   NodeRefMap, NodeCrossRef>(map));
alpar@100
  1042
      return *this;
alpar@100
  1043
    }
alpar@100
  1044
alpar@100
  1045
    /// \brief Make copy of the given map.
alpar@100
  1046
    ///
deba@139
  1047
    /// Makes copy of the given map for the newly created graph. 
deba@139
  1048
    /// The new map's key type is the to graph's node type,
deba@139
  1049
    /// and the copied map's key type is the from graph's node
alpar@100
  1050
    /// type.  
alpar@100
  1051
    template <typename ToMap, typename FromMap>
alpar@100
  1052
    GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
deba@139
  1053
      _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node, 
deba@139
  1054
			   NodeRefMap, ToMap, FromMap>(tmap, map));
alpar@100
  1055
      return *this;
alpar@100
  1056
    }
alpar@100
  1057
alpar@100
  1058
    /// \brief Make a copy of the given node.
alpar@100
  1059
    ///
alpar@100
  1060
    /// Make a copy of the given node.
alpar@100
  1061
    GraphCopy& node(TNode& tnode, const Node& snode) {
deba@139
  1062
      _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node, 
deba@139
  1063
			   NodeRefMap, TNode>(tnode, snode));
alpar@100
  1064
      return *this;
alpar@100
  1065
    }
alpar@100
  1066
alpar@100
  1067
    /// \brief Copies the arc references into the given map.
alpar@100
  1068
    ///
alpar@100
  1069
    /// Copies the arc references into the given map.
alpar@100
  1070
    template <typename ArcRef>
alpar@100
  1071
    GraphCopy& arcRef(ArcRef& map) {
deba@139
  1072
      _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc, 
deba@139
  1073
			  ArcRefMap, ArcRef>(map));
alpar@100
  1074
      return *this;
alpar@100
  1075
    }
alpar@100
  1076
alpar@100
  1077
    /// \brief Copies the arc cross references into the given map.
alpar@100
  1078
    ///
alpar@100
  1079
    ///  Copies the arc cross references (reverse references) into
alpar@100
  1080
    ///  the given map.
alpar@100
  1081
    template <typename ArcCrossRef>
alpar@100
  1082
    GraphCopy& arcCrossRef(ArcCrossRef& map) {
deba@139
  1083
      _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
deba@139
  1084
			  ArcRefMap, ArcCrossRef>(map));
alpar@100
  1085
      return *this;
alpar@100
  1086
    }
alpar@100
  1087
alpar@100
  1088
    /// \brief Make copy of the given map.
alpar@100
  1089
    ///
deba@139
  1090
    /// Makes copy of the given map for the newly created graph. 
deba@139
  1091
    /// The new map's key type is the to graph's arc type,
deba@139
  1092
    /// and the copied map's key type is the from graph's arc
alpar@100
  1093
    /// type.  
alpar@100
  1094
    template <typename ToMap, typename FromMap>
alpar@100
  1095
    GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
deba@139
  1096
      _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc, 
deba@139
  1097
			  ArcRefMap, ToMap, FromMap>(tmap, map));
alpar@100
  1098
      return *this;
alpar@100
  1099
    }
alpar@100
  1100
alpar@100
  1101
    /// \brief Make a copy of the given arc.
alpar@100
  1102
    ///
alpar@100
  1103
    /// Make a copy of the given arc.
alpar@100
  1104
    GraphCopy& arc(TArc& tarc, const Arc& sarc) {
deba@139
  1105
      _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc, 
deba@139
  1106
			  ArcRefMap, TArc>(tarc, sarc));
alpar@100
  1107
      return *this;
alpar@100
  1108
    }
alpar@100
  1109
alpar@100
  1110
    /// \brief Copies the edge references into the given map.
alpar@100
  1111
    ///
alpar@100
  1112
    /// Copies the edge references into the given map.
alpar@100
  1113
    template <typename EdgeRef>
alpar@100
  1114
    GraphCopy& edgeRef(EdgeRef& map) {
deba@139
  1115
      _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge, 
deba@139
  1116
			   EdgeRefMap, EdgeRef>(map));
alpar@100
  1117
      return *this;
alpar@100
  1118
    }
alpar@100
  1119
alpar@100
  1120
    /// \brief Copies the edge cross references into the given map.
alpar@100
  1121
    ///
alpar@100
  1122
    /// Copies the edge cross references (reverse
alpar@100
  1123
    /// references) into the given map.
alpar@100
  1124
    template <typename EdgeCrossRef>
alpar@100
  1125
    GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
deba@139
  1126
      _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, 
deba@139
  1127
			   Edge, EdgeRefMap, EdgeCrossRef>(map));
alpar@100
  1128
      return *this;
alpar@100
  1129
    }
alpar@100
  1130
alpar@100
  1131
    /// \brief Make copy of the given map.
alpar@100
  1132
    ///
deba@139
  1133
    /// Makes copy of the given map for the newly created graph. 
deba@139
  1134
    /// The new map's key type is the to graph's edge type,
deba@139
  1135
    /// and the copied map's key type is the from graph's edge
alpar@100
  1136
    /// type.  
alpar@100
  1137
    template <typename ToMap, typename FromMap>
alpar@100
  1138
    GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
deba@139
  1139
      _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge, 
deba@139
  1140
			   EdgeRefMap, ToMap, FromMap>(tmap, map));
alpar@100
  1141
      return *this;
alpar@100
  1142
    }
alpar@100
  1143
alpar@100
  1144
    /// \brief Make a copy of the given edge.
alpar@100
  1145
    ///
alpar@100
  1146
    /// Make a copy of the given edge.
alpar@100
  1147
    GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
deba@139
  1148
      _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge, 
deba@139
  1149
			   EdgeRefMap, TEdge>(tedge, sedge));
alpar@100
  1150
      return *this;
alpar@100
  1151
    }
alpar@100
  1152
alpar@100
  1153
    /// \brief Executes the copies.
alpar@100
  1154
    ///
alpar@100
  1155
    /// Executes the copies.
alpar@100
  1156
    void run() {
deba@139
  1157
      NodeRefMap nodeRefMap(_from);
deba@139
  1158
      EdgeRefMap edgeRefMap(_from);
deba@139
  1159
      ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
deba@139
  1160
      _graph_utils_bits::GraphCopySelector<To>::
deba@139
  1161
        copy(_to, _from, nodeRefMap, edgeRefMap);
deba@139
  1162
      for (int i = 0; i < int(_node_maps.size()); ++i) {
deba@139
  1163
        _node_maps[i]->copy(_from, nodeRefMap);
alpar@100
  1164
      }
deba@139
  1165
      for (int i = 0; i < int(_edge_maps.size()); ++i) {
deba@139
  1166
        _edge_maps[i]->copy(_from, edgeRefMap);
alpar@100
  1167
      }
deba@139
  1168
      for (int i = 0; i < int(_arc_maps.size()); ++i) {
deba@139
  1169
        _arc_maps[i]->copy(_from, arcRefMap);
alpar@100
  1170
      }
alpar@100
  1171
    }
alpar@100
  1172
alpar@100
  1173
  private:
alpar@100
  1174
    
deba@139
  1175
    const From& _from;
deba@139
  1176
    To& _to;
alpar@100
  1177
deba@139
  1178
    std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* > 
deba@139
  1179
    _node_maps;
alpar@100
  1180
deba@139
  1181
    std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* > 
deba@139
  1182
    _arc_maps;
alpar@100
  1183
deba@139
  1184
    std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* > 
deba@139
  1185
    _edge_maps;
alpar@100
  1186
alpar@100
  1187
  };
alpar@100
  1188
deba@139
  1189
  /// \brief Copy a graph to another graph.
alpar@100
  1190
  ///
deba@139
  1191
  /// Copy a graph to another graph. The complete usage of the
deba@139
  1192
  /// function is detailed in the GraphCopy class, but a short
deba@139
  1193
  /// example shows a basic work:
alpar@100
  1194
  ///\code
alpar@100
  1195
  /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
alpar@100
  1196
  ///\endcode
alpar@100
  1197
  /// 
alpar@100
  1198
  /// After the copy the \c nr map will contain the mapping from the
deba@139
  1199
  /// nodes of the \c from graph to the nodes of the \c to graph and
deba@139
  1200
  /// \c ecr will contain the mapping from the arcs of the \c to graph
deba@139
  1201
  /// to the arcs of the \c from graph.
alpar@100
  1202
  ///
alpar@100
  1203
  /// \see GraphCopy 
alpar@100
  1204
  template <typename To, typename From>
alpar@100
  1205
  GraphCopy<To, From> 
alpar@100
  1206
  copyGraph(To& to, const From& from) {
alpar@100
  1207
    return GraphCopy<To, From>(to, from);
alpar@100
  1208
  }
alpar@100
  1209
alpar@100
  1210
  /// @}
alpar@100
  1211
deba@139
  1212
  /// \addtogroup graph_maps
alpar@100
  1213
  /// @{
alpar@100
  1214
deba@139
  1215
  /// Provides an immutable and unique id for each item in the graph.
alpar@100
  1216
alpar@100
  1217
  /// The IdMap class provides a unique and immutable id for each item of the
deba@139
  1218
  /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
alpar@100
  1219
  /// different items (nodes) get different ids <li>\b immutable: the id of an
alpar@100
  1220
  /// item (node) does not change (even if you delete other nodes).  </ul>
alpar@100
  1221
  /// Through this map you get access (i.e. can read) the inner id values of
deba@139
  1222
  /// the items stored in the graph. This map can be inverted with its member
deba@139
  1223
  /// class \c InverseMap or with the \c operator() member.
alpar@100
  1224
  ///
deba@139
  1225
  template <typename _Graph, typename _Item>
alpar@100
  1226
  class IdMap {
alpar@100
  1227
  public:
deba@139
  1228
    typedef _Graph Graph;
alpar@100
  1229
    typedef int Value;
alpar@100
  1230
    typedef _Item Item;
alpar@100
  1231
    typedef _Item Key;
alpar@100
  1232
alpar@100
  1233
    /// \brief Constructor.
alpar@100
  1234
    ///
alpar@100
  1235
    /// Constructor of the map.
deba@139
  1236
    explicit IdMap(const Graph& graph) : _graph(&graph) {}
alpar@100
  1237
alpar@100
  1238
    /// \brief Gives back the \e id of the item.
alpar@100
  1239
    ///
alpar@100
  1240
    /// Gives back the immutable and unique \e id of the item.
deba@139
  1241
    int operator[](const Item& item) const { return _graph->id(item);}
alpar@100
  1242
alpar@100
  1243
    /// \brief Gives back the item by its id.
alpar@100
  1244
    ///
alpar@100
  1245
    /// Gives back the item by its id.
deba@139
  1246
    Item operator()(int id) { return _graph->fromId(id, Item()); }
alpar@100
  1247
alpar@100
  1248
  private:
deba@139
  1249
    const Graph* _graph;
alpar@100
  1250
alpar@100
  1251
  public:
alpar@100
  1252
alpar@100
  1253
    /// \brief The class represents the inverse of its owner (IdMap).
alpar@100
  1254
    ///
alpar@100
  1255
    /// The class represents the inverse of its owner (IdMap).
alpar@100
  1256
    /// \see inverse()
alpar@100
  1257
    class InverseMap {
alpar@100
  1258
    public:
alpar@100
  1259
alpar@100
  1260
      /// \brief Constructor.
alpar@100
  1261
      ///
alpar@100
  1262
      /// Constructor for creating an id-to-item map.
deba@139
  1263
      explicit InverseMap(const Graph& graph) : _graph(&graph) {}
alpar@100
  1264
alpar@100
  1265
      /// \brief Constructor.
alpar@100
  1266
      ///
alpar@100
  1267
      /// Constructor for creating an id-to-item map.
deba@139
  1268
      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
alpar@100
  1269
alpar@100
  1270
      /// \brief Gives back the given item from its id.
alpar@100
  1271
      ///
alpar@100
  1272
      /// Gives back the given item from its id.
alpar@100
  1273
      /// 
deba@139
  1274
      Item operator[](int id) const { return _graph->fromId(id, Item());}
alpar@100
  1275
alpar@100
  1276
    private:
deba@139
  1277
      const Graph* _graph;
alpar@100
  1278
    };
alpar@100
  1279
alpar@100
  1280
    /// \brief Gives back the inverse of the map.
alpar@100
  1281
    ///
alpar@100
  1282
    /// Gives back the inverse of the IdMap.
deba@139
  1283
    InverseMap inverse() const { return InverseMap(*_graph);} 
alpar@100
  1284
alpar@100
  1285
  };
alpar@100
  1286
alpar@100
  1287
  
deba@139
  1288
  /// \brief General invertable graph-map type.
alpar@100
  1289
deba@139
  1290
  /// This type provides simple invertable graph-maps. 
alpar@100
  1291
  /// The InvertableMap wraps an arbitrary ReadWriteMap 
alpar@100
  1292
  /// and if a key is set to a new value then store it
alpar@100
  1293
  /// in the inverse map.
alpar@100
  1294
  ///
alpar@100
  1295
  /// The values of the map can be accessed
alpar@100
  1296
  /// with stl compatible forward iterator.
alpar@100
  1297
  ///
deba@139
  1298
  /// \param _Graph The graph type.
deba@139
  1299
  /// \param _Item The item type of the graph.
alpar@100
  1300
  /// \param _Value The value type of the map.
alpar@100
  1301
  ///
alpar@100
  1302
  /// \see IterableValueMap
deba@139
  1303
  template <typename _Graph, typename _Item, typename _Value>
deba@139
  1304
  class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
alpar@100
  1305
  private:
alpar@100
  1306
    
deba@139
  1307
    typedef DefaultMap<_Graph, _Item, _Value> Map;
deba@139
  1308
    typedef _Graph Graph;
alpar@100
  1309
alpar@100
  1310
    typedef std::map<_Value, _Item> Container;
deba@139
  1311
    Container _inv_map;    
alpar@100
  1312
alpar@100
  1313
  public:
alpar@100
  1314
 
alpar@100
  1315
    /// The key type of InvertableMap (Node, Arc, Edge).
alpar@100
  1316
    typedef typename Map::Key Key;
alpar@100
  1317
    /// The value type of the InvertableMap.
alpar@100
  1318
    typedef typename Map::Value Value;
alpar@100
  1319
alpar@100
  1320
alpar@100
  1321
alpar@100
  1322
    /// \brief Constructor.
alpar@100
  1323
    ///
deba@139
  1324
    /// Construct a new InvertableMap for the graph.
alpar@100
  1325
    ///
deba@139
  1326
    explicit InvertableMap(const Graph& graph) : Map(graph) {} 
alpar@100
  1327
alpar@100
  1328
    /// \brief Forward iterator for values.
alpar@100
  1329
    ///
alpar@100
  1330
    /// This iterator is an stl compatible forward
alpar@100
  1331
    /// iterator on the values of the map. The values can
alpar@100
  1332
    /// be accessed in the [beginValue, endValue) range.
alpar@100
  1333
    ///
alpar@100
  1334
    class ValueIterator 
alpar@100
  1335
      : public std::iterator<std::forward_iterator_tag, Value> {
alpar@100
  1336
      friend class InvertableMap;
alpar@100
  1337
    private:
alpar@100
  1338
      ValueIterator(typename Container::const_iterator _it) 
alpar@100
  1339
        : it(_it) {}
alpar@100
  1340
    public:
alpar@100
  1341
      
alpar@100
  1342
      ValueIterator() {}
alpar@100
  1343
alpar@100
  1344
      ValueIterator& operator++() { ++it; return *this; }
alpar@100
  1345
      ValueIterator operator++(int) { 
alpar@100
  1346
        ValueIterator tmp(*this); 
alpar@100
  1347
        operator++();
alpar@100
  1348
        return tmp; 
alpar@100
  1349
      }
alpar@100
  1350
alpar@100
  1351
      const Value& operator*() const { return it->first; }
alpar@100
  1352
      const Value* operator->() const { return &(it->first); }
alpar@100
  1353
alpar@100
  1354
      bool operator==(ValueIterator jt) const { return it == jt.it; }
alpar@100
  1355
      bool operator!=(ValueIterator jt) const { return it != jt.it; }
alpar@100
  1356
      
alpar@100
  1357
    private:
alpar@100
  1358
      typename Container::const_iterator it;
alpar@100
  1359
    };
alpar@100
  1360
alpar@100
  1361
    /// \brief Returns an iterator to the first value.
alpar@100
  1362
    ///
alpar@100
  1363
    /// Returns an stl compatible iterator to the 
alpar@100
  1364
    /// first value of the map. The values of the
alpar@100
  1365
    /// map can be accessed in the [beginValue, endValue)
alpar@100
  1366
    /// range.
alpar@100
  1367
    ValueIterator beginValue() const {
deba@139
  1368
      return ValueIterator(_inv_map.begin());
alpar@100
  1369
    }
alpar@100
  1370
alpar@100
  1371
    /// \brief Returns an iterator after the last value.
alpar@100
  1372
    ///
alpar@100
  1373
    /// Returns an stl compatible iterator after the 
alpar@100
  1374
    /// last value of the map. The values of the
alpar@100
  1375
    /// map can be accessed in the [beginValue, endValue)
alpar@100
  1376
    /// range.
alpar@100
  1377
    ValueIterator endValue() const {
deba@139
  1378
      return ValueIterator(_inv_map.end());
alpar@100
  1379
    }
alpar@100
  1380
    
alpar@100
  1381
    /// \brief The setter function of the map.
alpar@100
  1382
    ///
alpar@100
  1383
    /// Sets the mapped value.
alpar@100
  1384
    void set(const Key& key, const Value& val) {
alpar@100
  1385
      Value oldval = Map::operator[](key);
deba@139
  1386
      typename Container::iterator it = _inv_map.find(oldval);
deba@139
  1387
      if (it != _inv_map.end() && it->second == key) {
deba@139
  1388
	_inv_map.erase(it);
alpar@100
  1389
      }      
deba@139
  1390
      _inv_map.insert(make_pair(val, key));
alpar@100
  1391
      Map::set(key, val);
alpar@100
  1392
    }
alpar@100
  1393
alpar@100
  1394
    /// \brief The getter function of the map.
alpar@100
  1395
    ///
alpar@100
  1396
    /// It gives back the value associated with the key.
alpar@100
  1397
    typename MapTraits<Map>::ConstReturnValue 
alpar@100
  1398
    operator[](const Key& key) const {
alpar@100
  1399
      return Map::operator[](key);
alpar@100
  1400
    }
alpar@100
  1401
alpar@100
  1402
    /// \brief Gives back the item by its value.
alpar@100
  1403
    ///
alpar@100
  1404
    /// Gives back the item by its value.
alpar@100
  1405
    Key operator()(const Value& key) const {
deba@139
  1406
      typename Container::const_iterator it = _inv_map.find(key);
deba@139
  1407
      return it != _inv_map.end() ? it->second : INVALID;
alpar@100
  1408
    }
alpar@100
  1409
alpar@100
  1410
  protected:
alpar@100
  1411
alpar@100
  1412
    /// \brief Erase the key from the map.
alpar@100
  1413
    ///
alpar@100
  1414
    /// Erase the key to the map. It is called by the
alpar@100
  1415
    /// \c AlterationNotifier.
alpar@100
  1416
    virtual void erase(const Key& key) {
alpar@100
  1417
      Value val = Map::operator[](key);
deba@139
  1418
      typename Container::iterator it = _inv_map.find(val);
deba@139
  1419
      if (it != _inv_map.end() && it->second == key) {
deba@139
  1420
	_inv_map.erase(it);
alpar@100
  1421
      }
alpar@100
  1422
      Map::erase(key);
alpar@100
  1423
    }
alpar@100
  1424
alpar@100
  1425
    /// \brief Erase more keys from the map.
alpar@100
  1426
    ///
alpar@100
  1427
    /// Erase more keys from the map. It is called by the
alpar@100
  1428
    /// \c AlterationNotifier.
alpar@100
  1429
    virtual void erase(const std::vector<Key>& keys) {
alpar@100
  1430
      for (int i = 0; i < int(keys.size()); ++i) {
alpar@100
  1431
	Value val = Map::operator[](keys[i]);
deba@139
  1432
	typename Container::iterator it = _inv_map.find(val);
deba@139
  1433
	if (it != _inv_map.end() && it->second == keys[i]) {
deba@139
  1434
	  _inv_map.erase(it);
alpar@100
  1435
	}
alpar@100
  1436
      }
alpar@100
  1437
      Map::erase(keys);
alpar@100
  1438
    }
alpar@100
  1439
alpar@100
  1440
    /// \brief Clear the keys from the map and inverse map.
alpar@100
  1441
    ///
alpar@100
  1442
    /// Clear the keys from the map and inverse map. It is called by the
alpar@100
  1443
    /// \c AlterationNotifier.
alpar@100
  1444
    virtual void clear() {
deba@139
  1445
      _inv_map.clear();
alpar@100
  1446
      Map::clear();
alpar@100
  1447
    }
alpar@100
  1448
alpar@100
  1449
  public:
alpar@100
  1450
alpar@100
  1451
    /// \brief The inverse map type.
alpar@100
  1452
    ///
alpar@100
  1453
    /// The inverse of this map. The subscript operator of the map
alpar@100
  1454
    /// gives back always the item what was last assigned to the value. 
alpar@100
  1455
    class InverseMap {
alpar@100
  1456
    public:
alpar@100
  1457
      /// \brief Constructor of the InverseMap.
alpar@100
  1458
      ///
alpar@100
  1459
      /// Constructor of the InverseMap.
deba@139
  1460
      explicit InverseMap(const InvertableMap& inverted) 
deba@139
  1461
        : _inverted(inverted) {}
alpar@100
  1462
alpar@100
  1463
      /// The value type of the InverseMap.
alpar@100
  1464
      typedef typename InvertableMap::Key Value;
alpar@100
  1465
      /// The key type of the InverseMap.
alpar@100
  1466
      typedef typename InvertableMap::Value Key; 
alpar@100
  1467
alpar@100
  1468
      /// \brief Subscript operator. 
alpar@100
  1469
      ///
alpar@100
  1470
      /// Subscript operator. It gives back always the item 
alpar@100
  1471
      /// what was last assigned to the value.
alpar@100
  1472
      Value operator[](const Key& key) const {
deba@139
  1473
	return _inverted(key);
alpar@100
  1474
      }
alpar@100
  1475
      
alpar@100
  1476
    private:
deba@139
  1477
      const InvertableMap& _inverted;
alpar@100
  1478
    };
alpar@100
  1479
alpar@100
  1480
    /// \brief It gives back the just readable inverse map.
alpar@100
  1481
    ///
alpar@100
  1482
    /// It gives back the just readable inverse map.
alpar@100
  1483
    InverseMap inverse() const {
alpar@100
  1484
      return InverseMap(*this);
alpar@100
  1485
    } 
alpar@100
  1486
alpar@100
  1487
alpar@100
  1488
    
alpar@100
  1489
  };
alpar@100
  1490
alpar@100
  1491
  /// \brief Provides a mutable, continuous and unique descriptor for each 
deba@139
  1492
  /// item in the graph.
alpar@100
  1493
  ///
alpar@100
  1494
  /// The DescriptorMap class provides a unique and continuous (but mutable)
alpar@100
  1495
  /// descriptor (id) for each item of the same type (e.g. node) in the
deba@139
  1496
  /// graph. This id is <ul><li>\b unique: different items (nodes) get
alpar@100
  1497
  /// different ids <li>\b continuous: the range of the ids is the set of
alpar@100
  1498
  /// integers between 0 and \c n-1, where \c n is the number of the items of
alpar@100
  1499
  /// this type (e.g. nodes) (so the id of a node can change if you delete an
alpar@100
  1500
  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
deba@139
  1501
  /// with its member class \c InverseMap, or with the \c operator() member.
alpar@100
  1502
  ///
deba@139
  1503
  /// \param _Graph The graph class the \c DescriptorMap belongs to.
alpar@100
  1504
  /// \param _Item The Item is the Key of the Map. It may be Node, Arc or 
alpar@100
  1505
  /// Edge.
deba@139
  1506
  template <typename _Graph, typename _Item>
deba@139
  1507
  class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
alpar@100
  1508
alpar@100
  1509
    typedef _Item Item;
deba@139
  1510
    typedef DefaultMap<_Graph, _Item, int> Map;
alpar@100
  1511
alpar@100
  1512
  public:
deba@139
  1513
    /// The graph class of DescriptorMap.
deba@139
  1514
    typedef _Graph Graph;
alpar@100
  1515
alpar@100
  1516
    /// The key type of DescriptorMap (Node, Arc, Edge).
alpar@100
  1517
    typedef typename Map::Key Key;
alpar@100
  1518
    /// The value type of DescriptorMap.
alpar@100
  1519
    typedef typename Map::Value Value;
alpar@100
  1520
alpar@100
  1521
    /// \brief Constructor.
alpar@100
  1522
    ///
alpar@100
  1523
    /// Constructor for descriptor map.
deba@139
  1524
    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
alpar@100
  1525
      Item it;
alpar@100
  1526
      const typename Map::Notifier* nf = Map::notifier(); 
alpar@100
  1527
      for (nf->first(it); it != INVALID; nf->next(it)) {
deba@139
  1528
	Map::set(it, _inv_map.size());
deba@139
  1529
	_inv_map.push_back(it);	
alpar@100
  1530
      }      
alpar@100
  1531
    }
alpar@100
  1532
alpar@100
  1533
  protected:
alpar@100
  1534
alpar@100
  1535
    /// \brief Add a new key to the map.
alpar@100
  1536
    ///
alpar@100
  1537
    /// Add a new key to the map. It is called by the
alpar@100
  1538
    /// \c AlterationNotifier.
alpar@100
  1539
    virtual void add(const Item& item) {
alpar@100
  1540
      Map::add(item);
deba@139
  1541
      Map::set(item, _inv_map.size());
deba@139
  1542
      _inv_map.push_back(item);
alpar@100
  1543
    }
alpar@100
  1544
alpar@100
  1545
    /// \brief Add more new keys to the map.
alpar@100
  1546
    ///
alpar@100
  1547
    /// Add more new keys to the map. It is called by the
alpar@100
  1548
    /// \c AlterationNotifier.
alpar@100
  1549
    virtual void add(const std::vector<Item>& items) {
alpar@100
  1550
      Map::add(items);
alpar@100
  1551
      for (int i = 0; i < int(items.size()); ++i) {
deba@139
  1552
	Map::set(items[i], _inv_map.size());
deba@139
  1553
	_inv_map.push_back(items[i]);
alpar@100
  1554
      }
alpar@100
  1555
    }
alpar@100
  1556
alpar@100
  1557
    /// \brief Erase the key from the map.
alpar@100
  1558
    ///
alpar@100
  1559
    /// Erase the key from the map. It is called by the
alpar@100
  1560
    /// \c AlterationNotifier.
alpar@100
  1561
    virtual void erase(const Item& item) {
deba@139
  1562
      Map::set(_inv_map.back(), Map::operator[](item));
deba@139
  1563
      _inv_map[Map::operator[](item)] = _inv_map.back();
deba@139
  1564
      _inv_map.pop_back();
alpar@100
  1565
      Map::erase(item);
alpar@100
  1566
    }
alpar@100
  1567
alpar@100
  1568
    /// \brief Erase more keys from the map.
alpar@100
  1569
    ///
alpar@100
  1570
    /// Erase more keys from the map. It is called by the
alpar@100
  1571
    /// \c AlterationNotifier.
alpar@100
  1572
    virtual void erase(const std::vector<Item>& items) {
alpar@100
  1573
      for (int i = 0; i < int(items.size()); ++i) {
deba@139
  1574
	Map::set(_inv_map.back(), Map::operator[](items[i]));
deba@139
  1575
	_inv_map[Map::operator[](items[i])] = _inv_map.back();
deba@139
  1576
	_inv_map.pop_back();
alpar@100
  1577
      }
alpar@100
  1578
      Map::erase(items);
alpar@100
  1579
    }
alpar@100
  1580
alpar@100
  1581
    /// \brief Build the unique map.
alpar@100
  1582
    ///
alpar@100
  1583
    /// Build the unique map. It is called by the
alpar@100
  1584
    /// \c AlterationNotifier.
alpar@100
  1585
    virtual void build() {
alpar@100
  1586
      Map::build();
alpar@100
  1587
      Item it;
alpar@100
  1588
      const typename Map::Notifier* nf = Map::notifier(); 
alpar@100
  1589
      for (nf->first(it); it != INVALID; nf->next(it)) {
deba@139
  1590
	Map::set(it, _inv_map.size());
deba@139
  1591
	_inv_map.push_back(it);	
alpar@100
  1592
      }      
alpar@100
  1593
    }
alpar@100
  1594
    
alpar@100
  1595
    /// \brief Clear the keys from the map.
alpar@100
  1596
    ///
alpar@100
  1597
    /// Clear the keys from the map. It is called by the
alpar@100
  1598
    /// \c AlterationNotifier.
alpar@100
  1599
    virtual void clear() {
deba@139
  1600
      _inv_map.clear();
alpar@100
  1601
      Map::clear();
alpar@100
  1602
    }
alpar@100
  1603
alpar@100
  1604
  public:
alpar@100
  1605
alpar@100
  1606
    /// \brief Returns the maximal value plus one.
alpar@100
  1607
    ///
alpar@100
  1608
    /// Returns the maximal value plus one in the map.
alpar@100
  1609
    unsigned int size() const {
deba@139
  1610
      return _inv_map.size();
alpar@100
  1611
    }
alpar@100
  1612
alpar@100
  1613
    /// \brief Swaps the position of the two items in the map.
alpar@100
  1614
    ///
alpar@100
  1615
    /// Swaps the position of the two items in the map.
alpar@100
  1616
    void swap(const Item& p, const Item& q) {
alpar@100
  1617
      int pi = Map::operator[](p);
alpar@100
  1618
      int qi = Map::operator[](q);
alpar@100
  1619
      Map::set(p, qi);
deba@139
  1620
      _inv_map[qi] = p;
alpar@100
  1621
      Map::set(q, pi);
deba@139
  1622
      _inv_map[pi] = q;
alpar@100
  1623
    }
alpar@100
  1624
alpar@100
  1625
    /// \brief Gives back the \e descriptor of the item.
alpar@100
  1626
    ///
alpar@100
  1627
    /// Gives back the mutable and unique \e descriptor of the map.
alpar@100
  1628
    int operator[](const Item& item) const {
alpar@100
  1629
      return Map::operator[](item);
alpar@100
  1630
    }
alpar@100
  1631
alpar@100
  1632
    /// \brief Gives back the item by its descriptor.
alpar@100
  1633
    ///
alpar@100
  1634
    /// Gives back th item by its descriptor.
alpar@100
  1635
    Item operator()(int id) const {
deba@139
  1636
      return _inv_map[id];
alpar@100
  1637
    }
alpar@100
  1638
    
alpar@100
  1639
  private:
alpar@100
  1640
alpar@100
  1641
    typedef std::vector<Item> Container;
deba@139
  1642
    Container _inv_map;
alpar@100
  1643
alpar@100
  1644
  public:
alpar@100
  1645
    /// \brief The inverse map type of DescriptorMap.
alpar@100
  1646
    ///
alpar@100
  1647
    /// The inverse map type of DescriptorMap.
alpar@100
  1648
    class InverseMap {
alpar@100
  1649
    public:
alpar@100
  1650
      /// \brief Constructor of the InverseMap.
alpar@100
  1651
      ///
alpar@100
  1652
      /// Constructor of the InverseMap.
deba@139
  1653
      explicit InverseMap(const DescriptorMap& inverted) 
deba@139
  1654
	: _inverted(inverted) {}
alpar@100
  1655
alpar@100
  1656
alpar@100
  1657
      /// The value type of the InverseMap.
alpar@100
  1658
      typedef typename DescriptorMap::Key Value;
alpar@100
  1659
      /// The key type of the InverseMap.
alpar@100
  1660
      typedef typename DescriptorMap::Value Key; 
alpar@100
  1661
alpar@100
  1662
      /// \brief Subscript operator. 
alpar@100
  1663
      ///
alpar@100
  1664
      /// Subscript operator. It gives back the item 
alpar@100
  1665
      /// that the descriptor belongs to currently.
alpar@100
  1666
      Value operator[](const Key& key) const {
deba@139
  1667
	return _inverted(key);
alpar@100
  1668
      }
alpar@100
  1669
alpar@100
  1670
      /// \brief Size of the map.
alpar@100
  1671
      ///
alpar@100
  1672
      /// Returns the size of the map.
alpar@100
  1673
      unsigned int size() const {
deba@139
  1674
	return _inverted.size();
alpar@100
  1675
      }
alpar@100
  1676
      
alpar@100
  1677
    private:
deba@139
  1678
      const DescriptorMap& _inverted;
alpar@100
  1679
    };
alpar@100
  1680
alpar@100
  1681
    /// \brief Gives back the inverse of the map.
alpar@100
  1682
    ///
alpar@100
  1683
    /// Gives back the inverse of the map.
alpar@100
  1684
    const InverseMap inverse() const {
alpar@100
  1685
      return InverseMap(*this);
alpar@100
  1686
    }
alpar@100
  1687
  };
alpar@100
  1688
alpar@100
  1689
  /// \brief Returns the source of the given arc.
alpar@100
  1690
  ///
alpar@100
  1691
  /// The SourceMap gives back the source Node of the given arc. 
alpar@100
  1692
  /// \see TargetMap
alpar@100
  1693
  /// \author Balazs Dezso
alpar@100
  1694
  template <typename Digraph>
alpar@100
  1695
  class SourceMap {
alpar@100
  1696
  public:
alpar@100
  1697
alpar@100
  1698
    typedef typename Digraph::Node Value;
alpar@100
  1699
    typedef typename Digraph::Arc Key;
alpar@100
  1700
alpar@100
  1701
    /// \brief Constructor
alpar@100
  1702
    ///
alpar@100
  1703
    /// Constructor
alpar@100
  1704
    /// \param _digraph The digraph that the map belongs to.
deba@139
  1705
    explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
alpar@100
  1706
alpar@100
  1707
    /// \brief The subscript operator.
alpar@100
  1708
    ///
alpar@100
  1709
    /// The subscript operator.
alpar@100
  1710
    /// \param arc The arc 
alpar@100
  1711
    /// \return The source of the arc 
alpar@100
  1712
    Value operator[](const Key& arc) const {
deba@139
  1713
      return _digraph.source(arc);
alpar@100
  1714
    }
alpar@100
  1715
alpar@100
  1716
  private:
deba@139
  1717
    const Digraph& _digraph;
alpar@100
  1718
  };
alpar@100
  1719
alpar@100
  1720
  /// \brief Returns a \ref SourceMap class.
alpar@100
  1721
  ///
alpar@100
  1722
  /// This function just returns an \ref SourceMap class.
alpar@100
  1723
  /// \relates SourceMap
alpar@100
  1724
  template <typename Digraph>
alpar@100
  1725
  inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
alpar@100
  1726
    return SourceMap<Digraph>(digraph);
alpar@100
  1727
  } 
alpar@100
  1728
alpar@100
  1729
  /// \brief Returns the target of the given arc.
alpar@100
  1730
  ///
alpar@100
  1731
  /// The TargetMap gives back the target Node of the given arc. 
alpar@100
  1732
  /// \see SourceMap
alpar@100
  1733
  /// \author Balazs Dezso
alpar@100
  1734
  template <typename Digraph>
alpar@100
  1735
  class TargetMap {
alpar@100
  1736
  public:
alpar@100
  1737
alpar@100
  1738
    typedef typename Digraph::Node Value;
alpar@100
  1739
    typedef typename Digraph::Arc Key;
alpar@100
  1740
alpar@100
  1741
    /// \brief Constructor
alpar@100
  1742
    ///
alpar@100
  1743
    /// Constructor
alpar@100
  1744
    /// \param _digraph The digraph that the map belongs to.
deba@139
  1745
    explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
alpar@100
  1746
alpar@100
  1747
    /// \brief The subscript operator.
alpar@100
  1748
    ///
alpar@100
  1749
    /// The subscript operator.
alpar@100
  1750
    /// \param e The arc 
alpar@100
  1751
    /// \return The target of the arc 
alpar@100
  1752
    Value operator[](const Key& e) const {
deba@139
  1753
      return _digraph.target(e);
alpar@100
  1754
    }
alpar@100
  1755
alpar@100
  1756
  private:
deba@139
  1757
    const Digraph& _digraph;
alpar@100
  1758
  };
alpar@100
  1759
alpar@100
  1760
  /// \brief Returns a \ref TargetMap class.
alpar@100
  1761
  ///
alpar@100
  1762
  /// This function just returns a \ref TargetMap class.
alpar@100
  1763
  /// \relates TargetMap
alpar@100
  1764
  template <typename Digraph>
alpar@100
  1765
  inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
alpar@100
  1766
    return TargetMap<Digraph>(digraph);
alpar@100
  1767
  }
alpar@100
  1768
alpar@100
  1769
  /// \brief Returns the "forward" directed arc view of an edge.
alpar@100
  1770
  ///
alpar@100
  1771
  /// Returns the "forward" directed arc view of an edge.
alpar@100
  1772
  /// \see BackwardMap
alpar@100
  1773
  /// \author Balazs Dezso
deba@139
  1774
  template <typename Graph>
alpar@100
  1775
  class ForwardMap {
alpar@100
  1776
  public:
alpar@100
  1777
deba@139
  1778
    typedef typename Graph::Arc Value;
deba@139
  1779
    typedef typename Graph::Edge Key;
alpar@100
  1780
alpar@100
  1781
    /// \brief Constructor
alpar@100
  1782
    ///
alpar@100
  1783
    /// Constructor
deba@139
  1784
    /// \param _graph The graph that the map belongs to.
deba@139
  1785
    explicit ForwardMap(const Graph& graph) : _graph(graph) {}
alpar@100
  1786
alpar@100
  1787
    /// \brief The subscript operator.
alpar@100
  1788
    ///
alpar@100
  1789
    /// The subscript operator.
alpar@100
  1790
    /// \param key An edge 
alpar@100
  1791
    /// \return The "forward" directed arc view of edge 
alpar@100
  1792
    Value operator[](const Key& key) const {
deba@139
  1793
      return _graph.direct(key, true);
alpar@100
  1794
    }
alpar@100
  1795
alpar@100
  1796
  private:
deba@139
  1797
    const Graph& _graph;
alpar@100
  1798
  };
alpar@100
  1799
alpar@100
  1800
  /// \brief Returns a \ref ForwardMap class.
alpar@100
  1801
  ///
alpar@100
  1802
  /// This function just returns an \ref ForwardMap class.
alpar@100
  1803
  /// \relates ForwardMap
deba@139
  1804
  template <typename Graph>
deba@139
  1805
  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
deba@139
  1806
    return ForwardMap<Graph>(graph);
alpar@100
  1807
  }
alpar@100
  1808
alpar@100
  1809
  /// \brief Returns the "backward" directed arc view of an edge.
alpar@100
  1810
  ///
alpar@100
  1811
  /// Returns the "backward" directed arc view of an edge.
alpar@100
  1812
  /// \see ForwardMap
alpar@100
  1813
  /// \author Balazs Dezso
deba@139
  1814
  template <typename Graph>
alpar@100
  1815
  class BackwardMap {
alpar@100
  1816
  public:
alpar@100
  1817
deba@139
  1818
    typedef typename Graph::Arc Value;
deba@139
  1819
    typedef typename Graph::Edge Key;
alpar@100
  1820
alpar@100
  1821
    /// \brief Constructor
alpar@100
  1822
    ///
alpar@100
  1823
    /// Constructor
deba@139
  1824
    /// \param _graph The graph that the map belongs to.
deba@139
  1825
    explicit BackwardMap(const Graph& graph) : _graph(graph) {}
alpar@100
  1826
alpar@100
  1827
    /// \brief The subscript operator.
alpar@100
  1828
    ///
alpar@100
  1829
    /// The subscript operator.
alpar@100
  1830
    /// \param key An edge 
alpar@100
  1831
    /// \return The "backward" directed arc view of edge 
alpar@100
  1832
    Value operator[](const Key& key) const {
deba@139
  1833
      return _graph.direct(key, false);
alpar@100
  1834
    }
alpar@100
  1835
alpar@100
  1836
  private:
deba@139
  1837
    const Graph& _graph;
alpar@100
  1838
  };
alpar@100
  1839
alpar@100
  1840
  /// \brief Returns a \ref BackwardMap class
alpar@100
  1841
alpar@100
  1842
  /// This function just returns a \ref BackwardMap class.
alpar@100
  1843
  /// \relates BackwardMap
deba@139
  1844
  template <typename Graph>
deba@139
  1845
  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
deba@139
  1846
    return BackwardMap<Graph>(graph);
alpar@100
  1847
  }
alpar@100
  1848
alpar@100
  1849
  /// \brief Potential difference map
alpar@100
  1850
  ///
alpar@100
  1851
  /// If there is an potential map on the nodes then we
alpar@100
  1852
  /// can get an arc map as we get the substraction of the
alpar@100
  1853
  /// values of the target and source.
alpar@100
  1854
  template <typename Digraph, typename NodeMap>
alpar@100
  1855
  class PotentialDifferenceMap {
alpar@100
  1856
  public:
alpar@100
  1857
    typedef typename Digraph::Arc Key;
alpar@100
  1858
    typedef typename NodeMap::Value Value;
alpar@100
  1859
alpar@100
  1860
    /// \brief Constructor
alpar@100
  1861
    ///
alpar@100
  1862
    /// Contructor of the map
deba@139
  1863
    explicit PotentialDifferenceMap(const Digraph& digraph, 
deba@139
  1864
                                    const NodeMap& potential) 
deba@139
  1865
      : _digraph(digraph), _potential(potential) {}
alpar@100
  1866
alpar@100
  1867
    /// \brief Const subscription operator
alpar@100
  1868
    ///
alpar@100
  1869
    /// Const subscription operator
alpar@100
  1870
    Value operator[](const Key& arc) const {
deba@139
  1871
      return _potential[_digraph.target(arc)] - 
deba@139
  1872
	_potential[_digraph.source(arc)];
alpar@100
  1873
    }
alpar@100
  1874
alpar@100
  1875
  private:
deba@139
  1876
    const Digraph& _digraph;
deba@139
  1877
    const NodeMap& _potential;
alpar@100
  1878
  };
alpar@100
  1879
alpar@100
  1880
  /// \brief Returns a PotentialDifferenceMap.
alpar@100
  1881
  ///
alpar@100
  1882
  /// This function just returns a PotentialDifferenceMap.
alpar@100
  1883
  /// \relates PotentialDifferenceMap
alpar@100
  1884
  template <typename Digraph, typename NodeMap>
alpar@100
  1885
  PotentialDifferenceMap<Digraph, NodeMap> 
alpar@100
  1886
  potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
alpar@100
  1887
    return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
alpar@100
  1888
  }
alpar@100
  1889
alpar@100
  1890
  /// \brief Map of the node in-degrees.
alpar@100
  1891
  ///
alpar@100
  1892
  /// This map returns the in-degree of a node. Once it is constructed,
alpar@100
  1893
  /// the degrees are stored in a standard NodeMap, so each query is done
alpar@100
  1894
  /// in constant time. On the other hand, the values are updated automatically
alpar@100
  1895
  /// whenever the digraph changes.
alpar@100
  1896
  ///
alpar@100
  1897
  /// \warning Besides addNode() and addArc(), a digraph structure may provide
alpar@100
  1898
  /// alternative ways to modify the digraph. The correct behavior of InDegMap
alpar@100
  1899
  /// is not guarantied if these additional features are used. For example
alpar@100
  1900
  /// the functions \ref ListDigraph::changeSource() "changeSource()",
alpar@100
  1901
  /// \ref ListDigraph::changeTarget() "changeTarget()" and
alpar@100
  1902
  /// \ref ListDigraph::reverseArc() "reverseArc()"
alpar@100
  1903
  /// of \ref ListDigraph will \e not update the degree values correctly.
alpar@100
  1904
  ///
alpar@100
  1905
  /// \sa OutDegMap
alpar@100
  1906
alpar@100
  1907
  template <typename _Digraph>
alpar@100
  1908
  class InDegMap  
alpar@100
  1909
    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
alpar@100
  1910
      ::ItemNotifier::ObserverBase {
alpar@100
  1911
alpar@100
  1912
  public:
alpar@100
  1913
    
alpar@100
  1914
    typedef _Digraph Digraph;
alpar@100
  1915
    typedef int Value;
alpar@100
  1916
    typedef typename Digraph::Node Key;
alpar@100
  1917
deba@139
  1918
    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
alpar@100
  1919
    ::ItemNotifier::ObserverBase Parent;
alpar@100
  1920
alpar@100
  1921
  private:
alpar@100
  1922
deba@139
  1923
    class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
alpar@100
  1924
    public:
alpar@100
  1925
deba@139
  1926
      typedef DefaultMap<Digraph, Key, int> Parent;
alpar@100
  1927
alpar@100
  1928
      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
alpar@100
  1929
      
alpar@100
  1930
      virtual void add(const Key& key) {
alpar@100
  1931
	Parent::add(key);
alpar@100
  1932
	Parent::set(key, 0);
alpar@100
  1933
      }
alpar@100
  1934
alpar@100
  1935
      virtual void add(const std::vector<Key>& keys) {
alpar@100
  1936
	Parent::add(keys);
alpar@100
  1937
	for (int i = 0; i < int(keys.size()); ++i) {
alpar@100
  1938
	  Parent::set(keys[i], 0);
alpar@100
  1939
	}
alpar@100
  1940
      }
alpar@100
  1941
alpar@100
  1942
      virtual void build() {
alpar@100
  1943
	Parent::build();
alpar@100
  1944
	Key it;
alpar@100
  1945
	typename Parent::Notifier* nf = Parent::notifier();
alpar@100
  1946
	for (nf->first(it); it != INVALID; nf->next(it)) {
alpar@100
  1947
	  Parent::set(it, 0);
alpar@100
  1948
	}
alpar@100
  1949
      }
alpar@100
  1950
    };
alpar@100
  1951
alpar@100
  1952
  public:
alpar@100
  1953
alpar@100
  1954
    /// \brief Constructor.
alpar@100
  1955
    ///
alpar@100
  1956
    /// Constructor for creating in-degree map.
deba@139
  1957
    explicit InDegMap(const Digraph& digraph) 
deba@139
  1958
      : _digraph(digraph), _deg(digraph) {
deba@139
  1959
      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
alpar@100
  1960
      
deba@139
  1961
      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@139
  1962
	_deg[it] = countInArcs(_digraph, it);
alpar@100
  1963
      }
alpar@100
  1964
    }
alpar@100
  1965
    
alpar@100
  1966
    /// Gives back the in-degree of a Node.
alpar@100
  1967
    int operator[](const Key& key) const {
deba@139
  1968
      return _deg[key];
alpar@100
  1969
    }
alpar@100
  1970
alpar@100
  1971
  protected:
alpar@100
  1972
    
alpar@100
  1973
    typedef typename Digraph::Arc Arc;
alpar@100
  1974
alpar@100
  1975
    virtual void add(const Arc& arc) {
deba@139
  1976
      ++_deg[_digraph.target(arc)];
alpar@100
  1977
    }
alpar@100
  1978
alpar@100
  1979
    virtual void add(const std::vector<Arc>& arcs) {
alpar@100
  1980
      for (int i = 0; i < int(arcs.size()); ++i) {
deba@139
  1981
        ++_deg[_digraph.target(arcs[i])];
alpar@100
  1982
      }
alpar@100
  1983
    }
alpar@100
  1984
alpar@100
  1985
    virtual void erase(const Arc& arc) {
deba@139
  1986
      --_deg[_digraph.target(arc)];
alpar@100
  1987
    }
alpar@100
  1988
alpar@100
  1989
    virtual void erase(const std::vector<Arc>& arcs) {
alpar@100
  1990
      for (int i = 0; i < int(arcs.size()); ++i) {
deba@139
  1991
        --_deg[_digraph.target(arcs[i])];
alpar@100
  1992
      }
alpar@100
  1993
    }
alpar@100
  1994
alpar@100
  1995
    virtual void build() {
deba@139
  1996
      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@139
  1997
	_deg[it] = countInArcs(_digraph, it);
alpar@100
  1998
      }      
alpar@100
  1999
    }
alpar@100
  2000
alpar@100
  2001
    virtual void clear() {
deba@139
  2002
      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@139
  2003
	_deg[it] = 0;
alpar@100
  2004
      }
alpar@100
  2005
    }
alpar@100
  2006
  private:
alpar@100
  2007
    
deba@139
  2008
    const Digraph& _digraph;
deba@139
  2009
    AutoNodeMap _deg;
alpar@100
  2010
  };
alpar@100
  2011
alpar@100
  2012
  /// \brief Map of the node out-degrees.
alpar@100
  2013
  ///
alpar@100
  2014
  /// This map returns the out-degree of a node. Once it is constructed,
alpar@100
  2015
  /// the degrees are stored in a standard NodeMap, so each query is done
alpar@100
  2016
  /// in constant time. On the other hand, the values are updated automatically
alpar@100
  2017
  /// whenever the digraph changes.
alpar@100
  2018
  ///
alpar@100
  2019
  /// \warning Besides addNode() and addArc(), a digraph structure may provide
alpar@100
  2020
  /// alternative ways to modify the digraph. The correct behavior of OutDegMap
alpar@100
  2021
  /// is not guarantied if these additional features are used. For example
alpar@100
  2022
  /// the functions \ref ListDigraph::changeSource() "changeSource()",
alpar@100
  2023
  /// \ref ListDigraph::changeTarget() "changeTarget()" and
alpar@100
  2024
  /// \ref ListDigraph::reverseArc() "reverseArc()"
alpar@100
  2025
  /// of \ref ListDigraph will \e not update the degree values correctly.
alpar@100
  2026
  ///
alpar@100
  2027
  /// \sa InDegMap
alpar@100
  2028
alpar@100
  2029
  template <typename _Digraph>
alpar@100
  2030
  class OutDegMap  
alpar@100
  2031
    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
alpar@100
  2032
      ::ItemNotifier::ObserverBase {
alpar@100
  2033
alpar@100
  2034
  public:
alpar@100
  2035
    
alpar@100
  2036
    typedef _Digraph Digraph;
alpar@100
  2037
    typedef int Value;
alpar@100
  2038
    typedef typename Digraph::Node Key;
alpar@100
  2039
deba@139
  2040
    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
deba@139
  2041
    ::ItemNotifier::ObserverBase Parent;
deba@139
  2042
alpar@100
  2043
  private:
alpar@100
  2044
deba@139
  2045
    class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
alpar@100
  2046
    public:
alpar@100
  2047
deba@139
  2048
      typedef DefaultMap<Digraph, Key, int> Parent;
alpar@100
  2049
alpar@100
  2050
      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
alpar@100
  2051
      
alpar@100
  2052
      virtual void add(const Key& key) {
alpar@100
  2053
	Parent::add(key);
alpar@100
  2054
	Parent::set(key, 0);
alpar@100
  2055
      }
alpar@100
  2056
      virtual void add(const std::vector<Key>& keys) {
alpar@100
  2057
	Parent::add(keys);
alpar@100
  2058
	for (int i = 0; i < int(keys.size()); ++i) {
alpar@100
  2059
	  Parent::set(keys[i], 0);
alpar@100
  2060
	}
alpar@100
  2061
      }
alpar@100
  2062
      virtual void build() {
alpar@100
  2063
	Parent::build();
alpar@100
  2064
	Key it;
alpar@100
  2065
	typename Parent::Notifier* nf = Parent::notifier();
alpar@100
  2066
	for (nf->first(it); it != INVALID; nf->next(it)) {
alpar@100
  2067
	  Parent::set(it, 0);
alpar@100
  2068
	}
alpar@100
  2069
      }
alpar@100
  2070
    };
alpar@100
  2071
alpar@100
  2072
  public:
alpar@100
  2073
alpar@100
  2074
    /// \brief Constructor.
alpar@100
  2075
    ///
alpar@100
  2076
    /// Constructor for creating out-degree map.
deba@139
  2077
    explicit OutDegMap(const Digraph& digraph) 
deba@139
  2078
      : _digraph(digraph), _deg(digraph) {
deba@139
  2079
      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
alpar@100
  2080
      
deba@139
  2081
      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@139
  2082
	_deg[it] = countOutArcs(_digraph, it);
alpar@100
  2083
      }
alpar@100
  2084
    }
alpar@100
  2085
alpar@100
  2086
    /// Gives back the out-degree of a Node.
alpar@100
  2087
    int operator[](const Key& key) const {
deba@139
  2088
      return _deg[key];
alpar@100
  2089
    }
alpar@100
  2090
alpar@100
  2091
  protected:
alpar@100
  2092
    
alpar@100
  2093
    typedef typename Digraph::Arc Arc;
alpar@100
  2094
alpar@100
  2095
    virtual void add(const Arc& arc) {
deba@139
  2096
      ++_deg[_digraph.source(arc)];
alpar@100
  2097
    }
alpar@100
  2098
alpar@100
  2099
    virtual void add(const std::vector<Arc>& arcs) {
alpar@100
  2100
      for (int i = 0; i < int(arcs.size()); ++i) {
deba@139
  2101
        ++_deg[_digraph.source(arcs[i])];
alpar@100
  2102
      }
alpar@100
  2103
    }
alpar@100
  2104
alpar@100
  2105
    virtual void erase(const Arc& arc) {
deba@139
  2106
      --_deg[_digraph.source(arc)];
alpar@100
  2107
    }
alpar@100
  2108
alpar@100
  2109
    virtual void erase(const std::vector<Arc>& arcs) {
alpar@100
  2110
      for (int i = 0; i < int(arcs.size()); ++i) {
deba@139
  2111
        --_deg[_digraph.source(arcs[i])];
alpar@100
  2112
      }
alpar@100
  2113
    }
alpar@100
  2114
alpar@100
  2115
    virtual void build() {
deba@139
  2116
      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@139
  2117
	_deg[it] = countOutArcs(_digraph, it);
alpar@100
  2118
      }      
alpar@100
  2119
    }
alpar@100
  2120
alpar@100
  2121
    virtual void clear() {
deba@139
  2122
      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@139
  2123
	_deg[it] = 0;
alpar@100
  2124
      }
alpar@100
  2125
    }
alpar@100
  2126
  private:
alpar@100
  2127
    
deba@139
  2128
    const Digraph& _digraph;
deba@139
  2129
    AutoNodeMap _deg;
alpar@100
  2130
  };
alpar@100
  2131
alpar@100
  2132
alpar@100
  2133
  ///Dynamic arc look up between given endpoints.
alpar@100
  2134
  
alpar@100
  2135
  ///\ingroup gutils
alpar@100
  2136
  ///Using this class, you can find an arc in a digraph from a given
alpar@100
  2137
  ///source to a given target in amortized time <em>O(log d)</em>,
alpar@100
  2138
  ///where <em>d</em> is the out-degree of the source node.
alpar@100
  2139
  ///
alpar@100
  2140
  ///It is possible to find \e all parallel arcs between two nodes with
alpar@100
  2141
  ///the \c findFirst() and \c findNext() members.
alpar@100
  2142
  ///
alpar@100
  2143
  ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
deba@139
  2144
  ///digraph is not changed so frequently.
alpar@100
  2145
  ///
alpar@100
  2146
  ///This class uses a self-adjusting binary search tree, Sleator's
alpar@100
  2147
  ///and Tarjan's Splay tree for guarantee the logarithmic amortized
alpar@100
  2148
  ///time bound for arc lookups. This class also guarantees the
alpar@100
  2149
  ///optimal time bound in a constant factor for any distribution of
alpar@100
  2150
  ///queries.
alpar@100
  2151
  ///
alpar@100
  2152
  ///\param G The type of the underlying digraph.  
alpar@100
  2153
  ///
alpar@100
  2154
  ///\sa ArcLookUp  
alpar@100
  2155
  ///\sa AllArcLookUp  
alpar@100
  2156
  template<class G>
alpar@100
  2157
  class DynArcLookUp 
alpar@100
  2158
    : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
alpar@100
  2159
  {
alpar@100
  2160
  public:
alpar@100
  2161
    typedef typename ItemSetTraits<G, typename G::Arc>
alpar@100
  2162
    ::ItemNotifier::ObserverBase Parent;
alpar@100
  2163
deba@140
  2164
    DIGRAPH_TYPEDEFS(G);
alpar@100
  2165
    typedef G Digraph;
alpar@100
  2166
alpar@100
  2167
  protected:
alpar@100
  2168
alpar@100
  2169
    class AutoNodeMap : public DefaultMap<G, Node, Arc> {
alpar@100
  2170
    public:
alpar@100
  2171
alpar@100
  2172
      typedef DefaultMap<G, Node, Arc> Parent;
alpar@100
  2173
alpar@100
  2174
      AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
alpar@100
  2175
      
alpar@100
  2176
      virtual void add(const Node& node) {
alpar@100
  2177
	Parent::add(node);
alpar@100
  2178
	Parent::set(node, INVALID);
alpar@100
  2179
      }
alpar@100
  2180
alpar@100
  2181
      virtual void add(const std::vector<Node>& nodes) {
alpar@100
  2182
	Parent::add(nodes);
alpar@100
  2183
	for (int i = 0; i < int(nodes.size()); ++i) {
alpar@100
  2184
	  Parent::set(nodes[i], INVALID);
alpar@100
  2185
	}
alpar@100
  2186
      }
alpar@100
  2187
alpar@100
  2188
      virtual void build() {
alpar@100
  2189
	Parent::build();
alpar@100
  2190
	Node it;
alpar@100
  2191
	typename Parent::Notifier* nf = Parent::notifier();
alpar@100
  2192
	for (nf->first(it); it != INVALID; nf->next(it)) {
alpar@100
  2193
	  Parent::set(it, INVALID);
alpar@100
  2194
	}
alpar@100
  2195
      }
alpar@100
  2196
    };
alpar@100
  2197
alpar@100
  2198
    const Digraph &_g;
alpar@100
  2199
    AutoNodeMap _head;
alpar@100
  2200
    typename Digraph::template ArcMap<Arc> _parent;
alpar@100
  2201
    typename Digraph::template ArcMap<Arc> _left;
alpar@100
  2202
    typename Digraph::template ArcMap<Arc> _right;
alpar@100
  2203
    
alpar@100
  2204
    class ArcLess {
alpar@100
  2205
      const Digraph &g;
alpar@100
  2206
    public:
alpar@100
  2207
      ArcLess(const Digraph &_g) : g(_g) {}
alpar@100
  2208
      bool operator()(Arc a,Arc b) const 
alpar@100
  2209
      {
alpar@100
  2210
	return g.target(a)<g.target(b);
alpar@100
  2211
      }
alpar@100
  2212
    };
alpar@100
  2213
    
alpar@100
  2214
  public:
alpar@100
  2215
    
alpar@100
  2216
    ///Constructor
alpar@100
  2217
alpar@100
  2218
    ///Constructor.
alpar@100
  2219
    ///
alpar@100
  2220
    ///It builds up the search database.
alpar@100
  2221
    DynArcLookUp(const Digraph &g) 
alpar@100
  2222
      : _g(g),_head(g),_parent(g),_left(g),_right(g) 
alpar@100
  2223
    { 
alpar@100
  2224
      Parent::attach(_g.notifier(typename Digraph::Arc()));
alpar@100
  2225
      refresh(); 
alpar@100
  2226
    }
alpar@100
  2227
    
alpar@100
  2228
  protected:
alpar@100
  2229
alpar@100
  2230
    virtual void add(const Arc& arc) {
alpar@100
  2231
      insert(arc);
alpar@100
  2232
    }
alpar@100
  2233
alpar@100
  2234
    virtual void add(const std::vector<Arc>& arcs) {
alpar@100
  2235
      for (int i = 0; i < int(arcs.size()); ++i) {
alpar@100
  2236
	insert(arcs[i]);
alpar@100
  2237
      }
alpar@100
  2238
    }
alpar@100
  2239
alpar@100
  2240
    virtual void erase(const Arc& arc) {
alpar@100
  2241
      remove(arc);
alpar@100
  2242
    }
alpar@100
  2243
alpar@100
  2244
    virtual void erase(const std::vector<Arc>& arcs) {
alpar@100
  2245
      for (int i = 0; i < int(arcs.size()); ++i) {
alpar@100
  2246
	remove(arcs[i]);
alpar@100
  2247
      }     
alpar@100
  2248
    }
alpar@100
  2249
alpar@100
  2250
    virtual void build() {
alpar@100
  2251
      refresh();
alpar@100
  2252
    }
alpar@100
  2253
alpar@100
  2254
    virtual void clear() {
alpar@100
  2255
      for(NodeIt n(_g);n!=INVALID;++n) {
alpar@100
  2256
	_head.set(n, INVALID);
alpar@100
  2257
      }
alpar@100
  2258
    }
alpar@100
  2259
alpar@100
  2260
    void insert(Arc arc) {
alpar@100
  2261
      Node s = _g.source(arc);
alpar@100
  2262
      Node t = _g.target(arc);
alpar@100
  2263
      _left.set(arc, INVALID);
alpar@100
  2264
      _right.set(arc, INVALID);
alpar@100
  2265
      
alpar@100
  2266
      Arc e = _head[s];
alpar@100
  2267
      if (e == INVALID) {
alpar@100
  2268
	_head.set(s, arc);
alpar@100
  2269
	_parent.set(arc, INVALID);
alpar@100
  2270
	return;
alpar@100
  2271
      }
alpar@100
  2272
      while (true) {
alpar@100
  2273
	if (t < _g.target(e)) {
alpar@100
  2274
	  if (_left[e] == INVALID) {
alpar@100
  2275
	    _left.set(e, arc);
alpar@100
  2276
	    _parent.set(arc, e);
alpar@100
  2277
	    splay(arc);
alpar@100
  2278
	    return;
alpar@100
  2279
	  } else {
alpar@100
  2280
	    e = _left[e];
alpar@100
  2281
	  }
alpar@100
  2282
	} else {
alpar@100
  2283
	  if (_right[e] == INVALID) {
alpar@100
  2284
	    _right.set(e, arc);
alpar@100
  2285
	    _parent.set(arc, e);
alpar@100
  2286
	    splay(arc);
alpar@100
  2287
	    return;
alpar@100
  2288
	  } else {
alpar@100
  2289
	    e = _right[e];
alpar@100
  2290
	  }
alpar@100
  2291
	}
alpar@100
  2292
      }
alpar@100
  2293
    }
alpar@100
  2294
alpar@100
  2295
    void remove(Arc arc) {
alpar@100
  2296
      if (_left[arc] == INVALID) {
alpar@100
  2297
	if (_right[arc] != INVALID) {
alpar@100
  2298
	  _parent.set(_right[arc], _parent[arc]);
alpar@100
  2299
	}
alpar@100
  2300
	if (_parent[arc] != INVALID) {
alpar@100
  2301
	  if (_left[_parent[arc]] == arc) {
alpar@100
  2302
	    _left.set(_parent[arc], _right[arc]);
alpar@100
  2303
	  } else {
alpar@100
  2304
	    _right.set(_parent[arc], _right[arc]);
alpar@100
  2305
	  }
alpar@100
  2306
	} else {
alpar@100
  2307
	  _head.set(_g.source(arc), _right[arc]);
alpar@100
  2308
	}
alpar@100
  2309
      } else if (_right[arc] == INVALID) {
alpar@100
  2310
	_parent.set(_left[arc], _parent[arc]);
alpar@100
  2311
	if (_parent[arc] != INVALID) {
alpar@100
  2312
	  if (_left[_parent[arc]] == arc) {
alpar@100
  2313
	    _left.set(_parent[arc], _left[arc]);
alpar@100
  2314
	  } else {
alpar@100
  2315
	    _right.set(_parent[arc], _left[arc]);
alpar@100
  2316
	  }
alpar@100
  2317
	} else {
alpar@100
  2318
	  _head.set(_g.source(arc), _left[arc]);
alpar@100
  2319
	}
alpar@100
  2320
      } else {
alpar@100
  2321
	Arc e = _left[arc];
alpar@100
  2322
	if (_right[e] != INVALID) {
alpar@100
  2323
	  e = _right[e];	  
alpar@100
  2324
	  while (_right[e] != INVALID) {
alpar@100
  2325
	    e = _right[e];
alpar@100
  2326
	  }
alpar@100
  2327
	  Arc s = _parent[e];
alpar@100
  2328
	  _right.set(_parent[e], _left[e]);
alpar@100
  2329
	  if (_left[e] != INVALID) {
alpar@100
  2330
	    _parent.set(_left[e], _parent[e]);
alpar@100
  2331
	  }
alpar@100
  2332
	  
alpar@100
  2333
	  _left.set(e, _left[arc]);
alpar@100
  2334
	  _parent.set(_left[arc], e);
alpar@100
  2335
	  _right.set(e, _right[arc]);
alpar@100
  2336
	  _parent.set(_right[arc], e);
alpar@100
  2337
alpar@100
  2338
	  _parent.set(e, _parent[arc]);
alpar@100
  2339
	  if (_parent[arc] != INVALID) {
alpar@100
  2340
	    if (_left[_parent[arc]] == arc) {
alpar@100
  2341
	      _left.set(_parent[arc], e);
alpar@100
  2342
	    } else {
alpar@100
  2343
	      _right.set(_parent[arc], e);
alpar@100
  2344
	    }
alpar@100
  2345
	  }
alpar@100
  2346
	  splay(s);
alpar@100
  2347
	} else {
alpar@100
  2348
	  _right.set(e, _right[arc]);
alpar@100
  2349
	  _parent.set(_right[arc], e);
alpar@100
  2350
alpar@100
  2351
	  if (_parent[arc] != INVALID) {
alpar@100
  2352
	    if (_left[_parent[arc]] == arc) {
alpar@100
  2353
	      _left.set(_parent[arc], e);
alpar@100
  2354
	    } else {
alpar@100
  2355
	      _right.set(_parent[arc], e);
alpar@100
  2356
	    }
alpar@100
  2357
	  } else {
alpar@100
  2358
	    _head.set(_g.source(arc), e);
alpar@100
  2359
	  }
alpar@100
  2360
	}
alpar@100
  2361
      }
alpar@100
  2362
    }
alpar@100
  2363
alpar@100
  2364
    Arc refreshRec(std::vector<Arc> &v,int a,int b) 
alpar@100
  2365
    {
alpar@100
  2366
      int m=(a+b)/2;
alpar@100
  2367
      Arc me=v[m];
alpar@100
  2368
      if (a < m) {
alpar@100
  2369
	Arc left = refreshRec(v,a,m-1);
alpar@100
  2370
	_left.set(me, left);
alpar@100
  2371
	_parent.set(left, me);
alpar@100
  2372
      } else {
alpar@100
  2373
	_left.set(me, INVALID);
alpar@100
  2374
      }
alpar@100
  2375
      if (m < b) {
alpar@100
  2376
	Arc right = refreshRec(v,m+1,b);
alpar@100
  2377
	_right.set(me, right);
alpar@100
  2378
	_parent.set(right, me);
alpar@100
  2379
      } else {
alpar@100
  2380
	_right.set(me, INVALID);
alpar@100
  2381
      }
alpar@100
  2382
      return me;
alpar@100
  2383
    }
alpar@100
  2384
alpar@100
  2385
    void refresh() {
alpar@100
  2386
      for(NodeIt n(_g);n!=INVALID;++n) {
alpar@100
  2387
	std::vector<Arc> v;
alpar@100
  2388
	for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
alpar@100
  2389
	if(v.size()) {
alpar@100
  2390
	  std::sort(v.begin(),v.end(),ArcLess(_g));
alpar@100
  2391
	  Arc head = refreshRec(v,0,v.size()-1);
alpar@100
  2392
	  _head.set(n, head);
alpar@100
  2393
	  _parent.set(head, INVALID);
alpar@100
  2394
	}
alpar@100
  2395
	else _head.set(n, INVALID);
alpar@100
  2396
      }
alpar@100
  2397
    }
alpar@100
  2398
alpar@100
  2399
    void zig(Arc v) {        
alpar@100
  2400
      Arc w = _parent[v];
alpar@100
  2401
      _parent.set(v, _parent[w]);
alpar@100
  2402
      _parent.set(w, v);
alpar@100
  2403
      _left.set(w, _right[v]);
alpar@100
  2404
      _right.set(v, w);
alpar@100
  2405
      if (_parent[v] != INVALID) {
alpar@100
  2406
	if (_right[_parent[v]] == w) {
alpar@100
  2407
	  _right.set(_parent[v], v);
alpar@100
  2408
	} else {
alpar@100
  2409
	  _left.set(_parent[v], v);
alpar@100
  2410
	}
alpar@100
  2411
      }
alpar@100
  2412
      if (_left[w] != INVALID){
alpar@100
  2413
	_parent.set(_left[w], w);
alpar@100
  2414
      }
alpar@100
  2415
    }
alpar@100
  2416
alpar@100
  2417
    void zag(Arc v) {        
alpar@100
  2418
      Arc w = _parent[v];
alpar@100
  2419
      _parent.set(v, _parent[w]);
alpar@100
  2420
      _parent.set(w, v);
alpar@100
  2421
      _right.set(w, _left[v]);
alpar@100
  2422
      _left.set(v, w);
alpar@100
  2423
      if (_parent[v] != INVALID){
alpar@100
  2424
	if (_left[_parent[v]] == w) {
alpar@100
  2425
	  _left.set(_parent[v], v);
alpar@100
  2426
	} else {
alpar@100
  2427
	  _right.set(_parent[v], v);
alpar@100
  2428
	}
alpar@100
  2429
      }
alpar@100
  2430
      if (_right[w] != INVALID){
alpar@100
  2431
	_parent.set(_right[w], w);
alpar@100
  2432
      }
alpar@100
  2433
    }
alpar@100
  2434
alpar@100
  2435
    void splay(Arc v) {
alpar@100
  2436
      while (_parent[v] != INVALID) {
alpar@100
  2437
	if (v == _left[_parent[v]]) {
alpar@100
  2438
	  if (_parent[_parent[v]] == INVALID) {
alpar@100
  2439
	    zig(v);
alpar@100
  2440
	  } else {
alpar@100
  2441
	    if (_parent[v] == _left[_parent[_parent[v]]]) {
alpar@100
  2442
	      zig(_parent[v]);
alpar@100
  2443
	      zig(v);
alpar@100
  2444
	    } else {
alpar@100
  2445
	      zig(v);
alpar@100
  2446
	      zag(v);
alpar@100
  2447
	    }
alpar@100
  2448
	  }
alpar@100
  2449
	} else {
alpar@100
  2450
	  if (_parent[_parent[v]] == INVALID) {
alpar@100
  2451
	    zag(v);
alpar@100
  2452
	  } else {
alpar@100
  2453
	    if (_parent[v] == _left[_parent[_parent[v]]]) {
alpar@100
  2454
	      zag(v);
alpar@100
  2455
	      zig(v);
alpar@100
  2456
	    } else {
alpar@100
  2457
	      zag(_parent[v]);
alpar@100
  2458
	      zag(v);
alpar@100
  2459
	    }
alpar@100
  2460
	  }
alpar@100
  2461
	}
alpar@100
  2462
      }
alpar@100
  2463
      _head[_g.source(v)] = v;
alpar@100
  2464
    }
alpar@100
  2465
alpar@100
  2466
alpar@100
  2467
  public:
alpar@100
  2468
    
alpar@100
  2469
    ///Find an arc between two nodes.
alpar@100
  2470
    
alpar@100
  2471
    ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
alpar@100
  2472
    /// <em>d</em> is the number of outgoing arcs of \c s.
alpar@100
  2473
    ///\param s The source node
alpar@100
  2474
    ///\param t The target node
alpar@100
  2475
    ///\return An arc from \c s to \c t if there exists,
alpar@100
  2476
    ///\ref INVALID otherwise.
alpar@100
  2477
    Arc operator()(Node s, Node t) const
alpar@100
  2478
    {
deba@139
  2479
      Arc a = _head[s];
alpar@100
  2480
      while (true) {
deba@139
  2481
	if (_g.target(a) == t) {
deba@139
  2482
	  const_cast<DynArcLookUp&>(*this).splay(a);
deba@139
  2483
	  return a;
deba@139
  2484
	} else if (t < _g.target(a)) {
deba@139
  2485
	  if (_left[a] == INVALID) {
deba@139
  2486
	    const_cast<DynArcLookUp&>(*this).splay(a);
alpar@100
  2487
	    return INVALID;
alpar@100
  2488
	  } else {
deba@139
  2489
	    a = _left[a];
alpar@100
  2490
	  }
alpar@100
  2491
	} else  {
deba@139
  2492
	  if (_right[a] == INVALID) {
deba@139
  2493
	    const_cast<DynArcLookUp&>(*this).splay(a);
alpar@100
  2494
	    return INVALID;
alpar@100
  2495
	  } else {
deba@139
  2496
	    a = _right[a];
alpar@100
  2497
	  }
alpar@100
  2498
	}
alpar@100
  2499
      }
alpar@100
  2500
    }
alpar@100
  2501
alpar@100
  2502
    ///Find the first arc between two nodes.
alpar@100
  2503
    
alpar@100
  2504
    ///Find the first arc between two nodes in time
alpar@100
  2505
    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
alpar@100
  2506
    /// outgoing arcs of \c s.  
alpar@100
  2507
    ///\param s The source node 
alpar@100
  2508
    ///\param t The target node
alpar@100
  2509
    ///\return An arc from \c s to \c t if there exists, \ref INVALID
alpar@100
  2510
    /// otherwise.
alpar@100
  2511
    Arc findFirst(Node s, Node t) const
alpar@100
  2512
    {
deba@139
  2513
      Arc a = _head[s];
alpar@100
  2514
      Arc r = INVALID;
alpar@100
  2515
      while (true) {
deba@139
  2516
	if (_g.target(a) < t) {
deba@139
  2517
	  if (_right[a] == INVALID) {
deba@139
  2518
	    const_cast<DynArcLookUp&>(*this).splay(a);
alpar@100
  2519
	    return r;
alpar@100
  2520
	  } else {
deba@139
  2521
	    a = _right[a];
alpar@100
  2522
	  }
alpar@100
  2523
	} else {
deba@139
  2524
	  if (_g.target(a) == t) {
deba@139
  2525
	    r = a;
alpar@100
  2526
	  }
deba@139
  2527
	  if (_left[a] == INVALID) {
deba@139
  2528
	    const_cast<DynArcLookUp&>(*this).splay(a);
alpar@100
  2529
	    return r;
alpar@100
  2530
	  } else {
deba@139
  2531
	    a = _left[a];
alpar@100
  2532
	  }
alpar@100
  2533
	}
alpar@100
  2534
      }
alpar@100
  2535
    }
alpar@100
  2536
alpar@100
  2537
    ///Find the next arc between two nodes.
alpar@100
  2538
    
alpar@100
  2539
    ///Find the next arc between two nodes in time
alpar@100
  2540
    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
alpar@100
  2541
    /// outgoing arcs of \c s.  
alpar@100
  2542
    ///\param s The source node 
alpar@100
  2543
    ///\param t The target node
alpar@100
  2544
    ///\return An arc from \c s to \c t if there exists, \ref INVALID
alpar@100
  2545
    /// otherwise.
alpar@100
  2546
alpar@100
  2547
    ///\note If \c e is not the result of the previous \c findFirst()
alpar@100
  2548
    ///operation then the amorized time bound can not be guaranteed.
alpar@100
  2549
#ifdef DOXYGEN
deba@139
  2550
    Arc findNext(Node s, Node t, Arc a) const
alpar@100
  2551
#else
deba@139
  2552
    Arc findNext(Node, Node t, Arc a) const
alpar@100
  2553
#endif
alpar@100
  2554
    {
deba@139
  2555
      if (_right[a] != INVALID) {
deba@139
  2556
	a = _right[a];
deba@139
  2557
	while (_left[a] != INVALID) {
deba@139
  2558
	  a = _left[a];
alpar@100
  2559
	}
deba@139
  2560
	const_cast<DynArcLookUp&>(*this).splay(a);
alpar@100
  2561
      } else {
deba@139
  2562
	while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
deba@139
  2563
	  a = _parent[a];
alpar@100
  2564
	}
deba@139
  2565
	if (_parent[a] == INVALID) {
alpar@100
  2566
	  return INVALID;
alpar@100
  2567
	} else {
deba@139
  2568
	  a = _parent[a];
deba@139
  2569
	  const_cast<DynArcLookUp&>(*this).splay(a);
alpar@100
  2570
	}
alpar@100
  2571
      }
deba@139
  2572
      if (_g.target(a) == t) return a;
alpar@100
  2573
      else return INVALID;    
alpar@100
  2574
    }
alpar@100
  2575
alpar@100
  2576
  };
alpar@100
  2577
alpar@100
  2578
  ///Fast arc look up between given endpoints.
alpar@100
  2579
  
alpar@100
  2580
  ///\ingroup gutils
alpar@100
  2581
  ///Using this class, you can find an arc in a digraph from a given
alpar@100
  2582
  ///source to a given target in time <em>O(log d)</em>,
alpar@100
  2583
  ///where <em>d</em> is the out-degree of the source node.
alpar@100
  2584
  ///
alpar@100
  2585
  ///It is not possible to find \e all parallel arcs between two nodes.
alpar@100
  2586
  ///Use \ref AllArcLookUp for this purpose.
alpar@100
  2587
  ///
alpar@100
  2588
  ///\warning This class is static, so you should refresh() (or at least
alpar@100
  2589
  ///refresh(Node)) this data structure
alpar@100
  2590
  ///whenever the digraph changes. This is a time consuming (superlinearly
alpar@100
  2591
  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
alpar@100
  2592
  ///
alpar@100
  2593
  ///\param G The type of the underlying digraph.
alpar@100
  2594
  ///
alpar@100
  2595
  ///\sa DynArcLookUp
alpar@100
  2596
  ///\sa AllArcLookUp  
alpar@100
  2597
  template<class G>
alpar@100
  2598
  class ArcLookUp 
alpar@100
  2599
  {
alpar@100