lemon/graph_utils.h
author alpar
Fri, 18 Nov 2005 11:17:08 +0000
changeset 1817 dc3516405f8f
parent 1809 029cc4f638d1
child 1829 183b4cbf9733
permissions -rw-r--r--
- Spellcheck (pathes->paths)
klao@946
     1
/* -*- C++ -*-
ladanyi@1435
     2
 * lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library
klao@946
     3
 *
alpar@1164
     4
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359
     5
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
klao@946
     6
 *
klao@946
     7
 * Permission to use, modify and distribute this software is granted
klao@946
     8
 * provided that this copyright notice appears in all copies. For
klao@946
     9
 * precise terms see the accompanying LICENSE file.
klao@946
    10
 *
klao@946
    11
 * This software is provided "AS IS" with no warranty of any kind,
klao@946
    12
 * express or implied, and with no claim as to its suitability for any
klao@946
    13
 * purpose.
klao@946
    14
 *
klao@946
    15
 */
klao@946
    16
klao@946
    17
#ifndef LEMON_GRAPH_UTILS_H
klao@946
    18
#define LEMON_GRAPH_UTILS_H
klao@946
    19
klao@946
    20
#include <iterator>
deba@1419
    21
#include <vector>
alpar@1402
    22
#include <map>
deba@1695
    23
#include <cmath>
klao@946
    24
klao@946
    25
#include <lemon/invalid.h>
klao@977
    26
#include <lemon/utility.h>
deba@1413
    27
#include <lemon/maps.h>
deba@1720
    28
#include <lemon/traits.h>
alpar@1459
    29
#include <lemon/bits/alteration_notifier.h>
klao@946
    30
alpar@947
    31
///\ingroup gutils
klao@946
    32
///\file
alpar@947
    33
///\brief Graph utilities.
klao@946
    34
///
alpar@964
    35
///
klao@946
    36
klao@946
    37
klao@946
    38
namespace lemon {
klao@946
    39
deba@1267
    40
  /// \addtogroup gutils
deba@1267
    41
  /// @{
alpar@947
    42
alpar@1756
    43
  ///Creates convenience typedefs for the graph types and iterators
alpar@1756
    44
alpar@1756
    45
  ///This \c \#define creates convenience typedefs for the following types
alpar@1756
    46
  ///of \c Graph: \c Node,  \c NodeIt, \c Edge, \c EdgeIt, \c InEdgeIt,
alpar@1804
    47
  ///\c OutEdgeIt,  \c BoolNodeMap,  \c IntNodeMap,  \c DoubleNodeMap,
alpar@1804
    48
  ///\c BoolEdgeMap, \c IntEdgeMap,  \c DoubleEdgeMap.  
alpar@1756
    49
  ///\note If \c G it a template parameter, it should be used in this way.
alpar@1756
    50
  ///\code
alpar@1756
    51
  ///  GRAPH_TYPEDEFS(typename G)
alpar@1756
    52
  ///\endcode
alpar@1756
    53
  ///
alpar@1756
    54
  ///\warning There are no typedefs for the graph maps because of the lack of
alpar@1756
    55
  ///template typedefs in C++.
alpar@1804
    56
#define GRAPH_TYPEDEFS(Graph)				\
alpar@1804
    57
  typedef Graph::     Node      Node;			\
alpar@1804
    58
    typedef Graph::   NodeIt    NodeIt;			\
alpar@1804
    59
    typedef Graph::   Edge      Edge;			\
alpar@1804
    60
    typedef Graph::   EdgeIt    EdgeIt;			\
alpar@1804
    61
    typedef Graph:: InEdgeIt  InEdgeIt;			\
alpar@1811
    62
    typedef Graph::OutEdgeIt OutEdgeIt;			
alpar@1811
    63
//     typedef Graph::template NodeMap<bool> BoolNodeMap;	       
alpar@1811
    64
//     typedef Graph::template NodeMap<int> IntNodeMap;	       
alpar@1811
    65
//     typedef Graph::template NodeMap<double> DoubleNodeMap;  
alpar@1811
    66
//     typedef Graph::template EdgeMap<bool> BoolEdgeMap;	       
alpar@1811
    67
//     typedef Graph::template EdgeMap<int> IntEdgeMap;	       
alpar@1811
    68
//     typedef Graph::template EdgeMap<double> DoubleEdgeMap;
alpar@1756
    69
  
alpar@1756
    70
  ///Creates convenience typedefs for the undirected graph types and iterators
alpar@1756
    71
alpar@1756
    72
  ///This \c \#define creates the same convenience typedefs as defined by
alpar@1756
    73
  ///\ref GRAPH_TYPEDEFS(Graph) and three more, namely it creates
alpar@1756
    74
  ///\c UndirEdge, \c UndirEdgeIt, \c IncEdgeIt,
alpar@1804
    75
  ///\c BoolUndirEdgeMap, \c IntUndirEdgeMap,  \c DoubleUndirEdgeMap.  
alpar@1756
    76
  ///
alpar@1756
    77
  ///\note If \c G it a template parameter, it should be used in this way.
alpar@1756
    78
  ///\code
alpar@1756
    79
  ///  UNDIRGRAPH_TYPEDEFS(typename G)
alpar@1756
    80
  ///\endcode
alpar@1756
    81
  ///
alpar@1756
    82
  ///\warning There are no typedefs for the graph maps because of the lack of
alpar@1756
    83
  ///template typedefs in C++.
alpar@1804
    84
#define UNDIRGRAPH_TYPEDEFS(Graph)				\
alpar@1804
    85
  GRAPH_TYPEDEFS(Graph)						\
alpar@1804
    86
    typedef Graph:: UndirEdge   UndirEdge;			\
alpar@1804
    87
    typedef Graph:: UndirEdgeIt UndirEdgeIt;			\
alpar@1811
    88
    typedef Graph:: IncEdgeIt   IncEdgeIt;		       
alpar@1811
    89
//     typedef Graph::template UndirEdgeMap<bool> BoolUndirEdgeMap;	 
alpar@1811
    90
//     typedef Graph::template UndirEdgeMap<int> IntUndirEdgeMap;
alpar@1811
    91
//     typedef Graph::template UndirEdgeMap<double> DoubleUndirEdgeMap;
alpar@1804
    92
  
alpar@1756
    93
alpar@1756
    94
klao@946
    95
  /// \brief Function to count the items in the graph.
klao@946
    96
  ///
athos@1540
    97
  /// This function counts the items (nodes, edges etc) in the graph.
klao@946
    98
  /// The complexity of the function is O(n) because
klao@946
    99
  /// it iterates on all of the items.
klao@946
   100
klao@946
   101
  template <typename Graph, typename ItemIt>
klao@977
   102
  inline int countItems(const Graph& g) {
klao@946
   103
    int num = 0;
klao@977
   104
    for (ItemIt it(g); it != INVALID; ++it) {
klao@946
   105
      ++num;
klao@946
   106
    }
klao@946
   107
    return num;
klao@946
   108
  }
klao@946
   109
klao@977
   110
  // Node counting:
klao@977
   111
klao@977
   112
  template <typename Graph>
klao@977
   113
  inline
klao@977
   114
  typename enable_if<typename Graph::NodeNumTag, int>::type
klao@977
   115
  _countNodes(const Graph &g) {
klao@977
   116
    return g.nodeNum();
klao@977
   117
  }
klao@977
   118
klao@977
   119
  template <typename Graph>
klao@977
   120
  inline int _countNodes(Wrap<Graph> w) {
klao@977
   121
    return countItems<Graph, typename Graph::NodeIt>(w.value);
klao@977
   122
  }
klao@977
   123
klao@946
   124
  /// \brief Function to count the nodes in the graph.
klao@946
   125
  ///
klao@946
   126
  /// This function counts the nodes in the graph.
klao@946
   127
  /// The complexity of the function is O(n) but for some
athos@1526
   128
  /// graph structures it is specialized to run in O(1).
klao@977
   129
  ///
klao@977
   130
  /// \todo refer how to specialize it
klao@946
   131
klao@946
   132
  template <typename Graph>
klao@977
   133
  inline int countNodes(const Graph& g) {
klao@977
   134
    return _countNodes<Graph>(g);
klao@977
   135
  }
klao@977
   136
klao@977
   137
  // Edge counting:
klao@977
   138
klao@977
   139
  template <typename Graph>
klao@977
   140
  inline
klao@977
   141
  typename enable_if<typename Graph::EdgeNumTag, int>::type
klao@977
   142
  _countEdges(const Graph &g) {
klao@977
   143
    return g.edgeNum();
klao@977
   144
  }
klao@977
   145
klao@977
   146
  template <typename Graph>
klao@977
   147
  inline int _countEdges(Wrap<Graph> w) {
klao@977
   148
    return countItems<Graph, typename Graph::EdgeIt>(w.value);
klao@946
   149
  }
klao@946
   150
klao@946
   151
  /// \brief Function to count the edges in the graph.
klao@946
   152
  ///
klao@946
   153
  /// This function counts the edges in the graph.
klao@946
   154
  /// The complexity of the function is O(e) but for some
athos@1526
   155
  /// graph structures it is specialized to run in O(1).
klao@977
   156
klao@946
   157
  template <typename Graph>
klao@977
   158
  inline int countEdges(const Graph& g) {
klao@977
   159
    return _countEdges<Graph>(g);
klao@946
   160
  }
klao@946
   161
klao@1053
   162
  // Undirected edge counting:
klao@1053
   163
klao@1053
   164
  template <typename Graph>
klao@1053
   165
  inline
klao@1053
   166
  typename enable_if<typename Graph::EdgeNumTag, int>::type
klao@1053
   167
  _countUndirEdges(const Graph &g) {
klao@1053
   168
    return g.undirEdgeNum();
klao@1053
   169
  }
klao@1053
   170
klao@1053
   171
  template <typename Graph>
klao@1053
   172
  inline int _countUndirEdges(Wrap<Graph> w) {
klao@1053
   173
    return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
klao@1053
   174
  }
klao@1053
   175
athos@1526
   176
  /// \brief Function to count the undirected edges in the graph.
klao@946
   177
  ///
athos@1526
   178
  /// This function counts the undirected edges in the graph.
klao@946
   179
  /// The complexity of the function is O(e) but for some
athos@1540
   180
  /// graph structures it is specialized to run in O(1).
klao@1053
   181
klao@946
   182
  template <typename Graph>
klao@1053
   183
  inline int countUndirEdges(const Graph& g) {
klao@1053
   184
    return _countUndirEdges<Graph>(g);
klao@946
   185
  }
klao@946
   186
klao@977
   187
klao@1053
   188
klao@946
   189
  template <typename Graph, typename DegIt>
klao@946
   190
  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
klao@946
   191
    int num = 0;
klao@946
   192
    for (DegIt it(_g, _n); it != INVALID; ++it) {
klao@946
   193
      ++num;
klao@946
   194
    }
klao@946
   195
    return num;
klao@946
   196
  }
alpar@967
   197
deba@1531
   198
  /// \brief Function to count the number of the out-edges from node \c n.
deba@1531
   199
  ///
deba@1531
   200
  /// This function counts the number of the out-edges from node \c n
deba@1531
   201
  /// in the graph.  
deba@1531
   202
  template <typename Graph>
deba@1531
   203
  inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
deba@1531
   204
    return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
deba@1531
   205
  }
deba@1531
   206
deba@1531
   207
  /// \brief Function to count the number of the in-edges to node \c n.
deba@1531
   208
  ///
deba@1531
   209
  /// This function counts the number of the in-edges to node \c n
deba@1531
   210
  /// in the graph.  
deba@1531
   211
  template <typename Graph>
deba@1531
   212
  inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
deba@1531
   213
    return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
deba@1531
   214
  }
deba@1531
   215
deba@1704
   216
  /// \brief Function to count the number of the inc-edges to node \c n.
deba@1679
   217
  ///
deba@1704
   218
  /// This function counts the number of the inc-edges to node \c n
deba@1679
   219
  /// in the graph.  
deba@1679
   220
  template <typename Graph>
deba@1679
   221
  inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) {
deba@1679
   222
    return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
deba@1679
   223
  }
deba@1679
   224
deba@1531
   225
deba@1565
   226
  template <typename Graph>
deba@1565
   227
  inline
deba@1565
   228
  typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type 
deba@1565
   229
  _findEdge(const Graph &g,
deba@1565
   230
	    typename Graph::Node u, typename Graph::Node v,
deba@1565
   231
	    typename Graph::Edge prev = INVALID) {
deba@1565
   232
    return g.findEdge(u, v, prev);
deba@1565
   233
  }
alpar@967
   234
deba@1565
   235
  template <typename Graph>
deba@1565
   236
  inline typename Graph::Edge 
deba@1565
   237
  _findEdge(Wrap<Graph> w,
deba@1565
   238
	    typename Graph::Node u, 
deba@1565
   239
	    typename Graph::Node v,
deba@1565
   240
	    typename Graph::Edge prev = INVALID) {
deba@1565
   241
    const Graph& g = w.value;
deba@1565
   242
    if (prev == INVALID) {
deba@1565
   243
      typename Graph::OutEdgeIt e(g, u);
deba@1565
   244
      while (e != INVALID && g.target(e) != v) ++e;
deba@1565
   245
      return e;
deba@1565
   246
    } else {
deba@1565
   247
      typename Graph::OutEdgeIt e(g, prev); ++e;
deba@1565
   248
      while (e != INVALID && g.target(e) != v) ++e;
deba@1565
   249
      return e;
deba@1565
   250
    }
deba@1565
   251
  }
deba@1565
   252
deba@1565
   253
  /// \brief Finds an edge between two nodes of a graph.
deba@1565
   254
  ///
alpar@967
   255
  /// Finds an edge from node \c u to node \c v in graph \c g.
alpar@967
   256
  ///
alpar@967
   257
  /// If \c prev is \ref INVALID (this is the default value), then
alpar@967
   258
  /// it finds the first edge from \c u to \c v. Otherwise it looks for
alpar@967
   259
  /// the next edge from \c u to \c v after \c prev.
alpar@967
   260
  /// \return The found edge or \ref INVALID if there is no such an edge.
alpar@967
   261
  ///
alpar@967
   262
  /// Thus you can iterate through each edge from \c u to \c v as it follows.
alpar@967
   263
  /// \code
alpar@967
   264
  /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
alpar@967
   265
  ///   ...
alpar@967
   266
  /// }
alpar@967
   267
  /// \endcode
deba@1565
   268
  // /// \todo We may want to use the "GraphBase" 
deba@1565
   269
  // /// interface here...
alpar@967
   270
  template <typename Graph>
deba@1565
   271
  inline typename Graph::Edge findEdge(const Graph &g,
deba@1565
   272
				       typename Graph::Node u, 
deba@1565
   273
				       typename Graph::Node v,
deba@1565
   274
				       typename Graph::Edge prev = INVALID) {
deba@1565
   275
    return _findEdge<Graph>(g, u, v, prev);
alpar@967
   276
  }
deba@1531
   277
deba@1565
   278
  /// \brief Iterator for iterating on edges connected the same nodes.
deba@1565
   279
  ///
deba@1565
   280
  /// Iterator for iterating on edges connected the same nodes. It is 
deba@1565
   281
  /// higher level interface for the findEdge() function. You can
alpar@1591
   282
  /// use it the following way:
deba@1565
   283
  /// \code
deba@1565
   284
  /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
deba@1565
   285
  ///   ...
deba@1565
   286
  /// }
deba@1565
   287
  /// \endcode
deba@1565
   288
  ///
deba@1565
   289
  /// \author Balazs Dezso 
deba@1565
   290
  template <typename _Graph>
deba@1565
   291
  class ConEdgeIt : public _Graph::Edge {
deba@1565
   292
  public:
deba@1565
   293
deba@1565
   294
    typedef _Graph Graph;
deba@1565
   295
    typedef typename Graph::Edge Parent;
deba@1565
   296
deba@1565
   297
    typedef typename Graph::Edge Edge;
deba@1565
   298
    typedef typename Graph::Node Node;
deba@1565
   299
deba@1565
   300
    /// \brief Constructor.
deba@1565
   301
    ///
deba@1565
   302
    /// Construct a new ConEdgeIt iterating on the edges which
deba@1565
   303
    /// connects the \c u and \c v node.
deba@1565
   304
    ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
deba@1565
   305
      Parent::operator=(findEdge(graph, u, v));
deba@1565
   306
    }
deba@1565
   307
deba@1565
   308
    /// \brief Constructor.
deba@1565
   309
    ///
deba@1565
   310
    /// Construct a new ConEdgeIt which continues the iterating from 
deba@1565
   311
    /// the \c e edge.
deba@1565
   312
    ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {}
deba@1565
   313
    
deba@1565
   314
    /// \brief Increment operator.
deba@1565
   315
    ///
deba@1565
   316
    /// It increments the iterator and gives back the next edge.
deba@1565
   317
    ConEdgeIt& operator++() {
deba@1565
   318
      Parent::operator=(findEdge(graph, graph.source(*this), 
deba@1565
   319
				 graph.target(*this), *this));
deba@1565
   320
      return *this;
deba@1565
   321
    }
deba@1565
   322
  private:
deba@1565
   323
    const Graph& graph;
deba@1565
   324
  };
deba@1565
   325
deba@1704
   326
  template <typename Graph>
deba@1704
   327
  inline
deba@1704
   328
  typename enable_if<
deba@1704
   329
    typename Graph::FindEdgeTag, 
deba@1704
   330
    typename Graph::UndirEdge>::type 
deba@1704
   331
  _findUndirEdge(const Graph &g,
deba@1704
   332
	    typename Graph::Node u, typename Graph::Node v,
deba@1704
   333
	    typename Graph::UndirEdge prev = INVALID) {
deba@1704
   334
    return g.findUndirEdge(u, v, prev);
deba@1704
   335
  }
deba@1704
   336
deba@1704
   337
  template <typename Graph>
deba@1704
   338
  inline typename Graph::UndirEdge 
deba@1704
   339
  _findUndirEdge(Wrap<Graph> w,
deba@1704
   340
	    typename Graph::Node u, 
deba@1704
   341
	    typename Graph::Node v,
deba@1704
   342
	    typename Graph::UndirEdge prev = INVALID) {
deba@1704
   343
    const Graph& g = w.value;
deba@1704
   344
    if (prev == INVALID) {
deba@1704
   345
      typename Graph::OutEdgeIt e(g, u);
deba@1704
   346
      while (e != INVALID && g.target(e) != v) ++e;
deba@1704
   347
      return e;
deba@1704
   348
    } else {
deba@1704
   349
      typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e;
deba@1704
   350
      while (e != INVALID && g.target(e) != v) ++e;
deba@1704
   351
      return e;
deba@1704
   352
    }
deba@1704
   353
  }
deba@1704
   354
deba@1704
   355
  /// \brief Finds an undir edge between two nodes of a graph.
deba@1704
   356
  ///
deba@1704
   357
  /// Finds an undir edge from node \c u to node \c v in graph \c g.
deba@1704
   358
  ///
deba@1704
   359
  /// If \c prev is \ref INVALID (this is the default value), then
deba@1704
   360
  /// it finds the first edge from \c u to \c v. Otherwise it looks for
deba@1704
   361
  /// the next edge from \c u to \c v after \c prev.
deba@1704
   362
  /// \return The found edge or \ref INVALID if there is no such an edge.
deba@1704
   363
  ///
deba@1704
   364
  /// Thus you can iterate through each edge from \c u to \c v as it follows.
deba@1704
   365
  /// \code
deba@1704
   366
  /// for(UndirEdge e = findUndirEdge(g,u,v); e != INVALID; 
deba@1704
   367
  ///     e = findUndirEdge(g,u,v,e)) {
deba@1704
   368
  ///   ...
deba@1704
   369
  /// }
deba@1704
   370
  /// \endcode
deba@1704
   371
  // /// \todo We may want to use the "GraphBase" 
deba@1704
   372
  // /// interface here...
deba@1704
   373
  template <typename Graph>
deba@1704
   374
  inline typename Graph::UndirEdge 
deba@1704
   375
  findUndirEdge(const Graph &g,
deba@1704
   376
		typename Graph::Node u, 
deba@1704
   377
		typename Graph::Node v,
deba@1704
   378
		typename Graph::UndirEdge prev = INVALID) {
deba@1704
   379
    return _findUndirEdge<Graph>(g, u, v, prev);
deba@1704
   380
  }
deba@1704
   381
deba@1704
   382
  /// \brief Iterator for iterating on undir edges connected the same nodes.
deba@1704
   383
  ///
deba@1704
   384
  /// Iterator for iterating on undir edges connected the same nodes. It is 
deba@1704
   385
  /// higher level interface for the findUndirEdge() function. You can
deba@1704
   386
  /// use it the following way:
deba@1704
   387
  /// \code
deba@1704
   388
  /// for (ConUndirEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
deba@1704
   389
  ///   ...
deba@1704
   390
  /// }
deba@1704
   391
  /// \endcode
deba@1704
   392
  ///
deba@1704
   393
  /// \author Balazs Dezso 
deba@1704
   394
  template <typename _Graph>
deba@1704
   395
  class ConUndirEdgeIt : public _Graph::UndirEdge {
deba@1704
   396
  public:
deba@1704
   397
deba@1704
   398
    typedef _Graph Graph;
deba@1704
   399
    typedef typename Graph::UndirEdge Parent;
deba@1704
   400
deba@1704
   401
    typedef typename Graph::UndirEdge UndirEdge;
deba@1704
   402
    typedef typename Graph::Node Node;
deba@1704
   403
deba@1704
   404
    /// \brief Constructor.
deba@1704
   405
    ///
deba@1704
   406
    /// Construct a new ConUndirEdgeIt iterating on the edges which
deba@1704
   407
    /// connects the \c u and \c v node.
deba@1704
   408
    ConUndirEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
deba@1704
   409
      Parent::operator=(findUndirEdge(graph, u, v));
deba@1704
   410
    }
deba@1704
   411
deba@1704
   412
    /// \brief Constructor.
deba@1704
   413
    ///
deba@1704
   414
    /// Construct a new ConUndirEdgeIt which continues the iterating from 
deba@1704
   415
    /// the \c e edge.
deba@1704
   416
    ConUndirEdgeIt(const Graph& g, UndirEdge e) : Parent(e), graph(g) {}
deba@1704
   417
    
deba@1704
   418
    /// \brief Increment operator.
deba@1704
   419
    ///
deba@1704
   420
    /// It increments the iterator and gives back the next edge.
deba@1704
   421
    ConUndirEdgeIt& operator++() {
deba@1704
   422
      Parent::operator=(findUndirEdge(graph, graph.source(*this), 
deba@1704
   423
				 graph.target(*this), *this));
deba@1704
   424
      return *this;
deba@1704
   425
    }
deba@1704
   426
  private:
deba@1704
   427
    const Graph& graph;
deba@1704
   428
  };
deba@1704
   429
athos@1540
   430
  /// \brief Copy a map.
alpar@964
   431
  ///
alpar@1547
   432
  /// This function copies the \c source map to the \c target map. It uses the
athos@1540
   433
  /// given iterator to iterate on the data structure and it uses the \c ref
athos@1540
   434
  /// mapping to convert the source's keys to the target's keys.
deba@1531
   435
  template <typename Target, typename Source, 
deba@1531
   436
	    typename ItemIt, typename Ref>	    
deba@1531
   437
  void copyMap(Target& target, const Source& source, 
deba@1531
   438
	       ItemIt it, const Ref& ref) {
deba@1531
   439
    for (; it != INVALID; ++it) {
deba@1531
   440
      target[ref[it]] = source[it];
klao@946
   441
    }
klao@946
   442
  }
klao@946
   443
deba@1531
   444
  /// \brief Copy the source map to the target map.
deba@1531
   445
  ///
deba@1531
   446
  /// Copy the \c source map to the \c target map. It uses the given iterator
deba@1531
   447
  /// to iterate on the data structure.
deba@1531
   448
  template <typename Target, typename Source, 
deba@1531
   449
	    typename ItemIt>	    
deba@1531
   450
  void copyMap(Target& target, const Source& source, ItemIt it) {
deba@1531
   451
    for (; it != INVALID; ++it) {
deba@1531
   452
      target[it] = source[it];
klao@946
   453
    }
klao@946
   454
  }
klao@946
   455
athos@1540
   456
  /// \brief Class to copy a graph.
deba@1531
   457
  ///
athos@1540
   458
  /// Class to copy a graph to an other graph (duplicate a graph). The
athos@1540
   459
  /// simplest way of using it is through the \c copyGraph() function.
deba@1531
   460
  template <typename Target, typename Source>
deba@1267
   461
  class GraphCopy {
deba@1531
   462
  public: 
deba@1531
   463
    typedef typename Source::Node Node;
deba@1531
   464
    typedef typename Source::NodeIt NodeIt;
deba@1531
   465
    typedef typename Source::Edge Edge;
deba@1531
   466
    typedef typename Source::EdgeIt EdgeIt;
klao@946
   467
deba@1531
   468
    typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
deba@1531
   469
    typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
klao@946
   470
deba@1531
   471
    /// \brief Constructor for the GraphCopy.
deba@1531
   472
    ///
deba@1531
   473
    /// It copies the content of the \c _source graph into the
deba@1531
   474
    /// \c _target graph. It creates also two references, one beetween
deba@1531
   475
    /// the two nodeset and one beetween the two edgesets.
deba@1531
   476
    GraphCopy(Target& _target, const Source& _source) 
deba@1531
   477
      : source(_source), target(_target), 
deba@1531
   478
	nodeRefMap(_source), edgeRefMap(_source) {
deba@1531
   479
      for (NodeIt it(source); it != INVALID; ++it) {
deba@1531
   480
	nodeRefMap[it] = target.addNode();
deba@1531
   481
      }
deba@1531
   482
      for (EdgeIt it(source); it != INVALID; ++it) {
deba@1531
   483
	edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], 
deba@1531
   484
					nodeRefMap[source.target(it)]);
deba@1531
   485
      }
deba@1267
   486
    }
klao@946
   487
deba@1531
   488
    /// \brief Copies the node references into the given map.
deba@1531
   489
    ///
deba@1531
   490
    /// Copies the node references into the given map.
deba@1531
   491
    template <typename NodeRef>
deba@1531
   492
    const GraphCopy& nodeRef(NodeRef& map) const {
deba@1531
   493
      for (NodeIt it(source); it != INVALID; ++it) {
deba@1531
   494
	map.set(it, nodeRefMap[it]);
deba@1531
   495
      }
deba@1531
   496
      return *this;
deba@1267
   497
    }
deba@1531
   498
deba@1531
   499
    /// \brief Reverse and copies the node references into the given map.
deba@1531
   500
    ///
deba@1531
   501
    /// Reverse and copies the node references into the given map.
deba@1531
   502
    template <typename NodeRef>
deba@1531
   503
    const GraphCopy& nodeCrossRef(NodeRef& map) const {
deba@1531
   504
      for (NodeIt it(source); it != INVALID; ++it) {
deba@1531
   505
	map.set(nodeRefMap[it], it);
deba@1531
   506
      }
deba@1531
   507
      return *this;
deba@1531
   508
    }
deba@1531
   509
deba@1531
   510
    /// \brief Copies the edge references into the given map.
deba@1531
   511
    ///
deba@1531
   512
    /// Copies the edge references into the given map.
deba@1531
   513
    template <typename EdgeRef>
deba@1531
   514
    const GraphCopy& edgeRef(EdgeRef& map) const {
deba@1531
   515
      for (EdgeIt it(source); it != INVALID; ++it) {
deba@1531
   516
	map.set(it, edgeRefMap[it]);
deba@1531
   517
      }
deba@1531
   518
      return *this;
deba@1531
   519
    }
deba@1531
   520
deba@1531
   521
    /// \brief Reverse and copies the edge references into the given map.
deba@1531
   522
    ///
deba@1531
   523
    /// Reverse and copies the edge references into the given map.
deba@1531
   524
    template <typename EdgeRef>
deba@1531
   525
    const GraphCopy& edgeCrossRef(EdgeRef& map) const {
deba@1531
   526
      for (EdgeIt it(source); it != INVALID; ++it) {
deba@1531
   527
	map.set(edgeRefMap[it], it);
deba@1531
   528
      }
deba@1531
   529
      return *this;
deba@1531
   530
    }
deba@1531
   531
deba@1531
   532
    /// \brief Make copy of the given map.
deba@1531
   533
    ///
deba@1531
   534
    /// Makes copy of the given map for the newly created graph. 
deba@1531
   535
    /// The new map's key type is the target graph's node type,
deba@1531
   536
    /// and the copied map's key type is the source graph's node
deba@1531
   537
    /// type.  
deba@1531
   538
    template <typename TargetMap, typename SourceMap>
deba@1531
   539
    const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
deba@1531
   540
      copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
deba@1531
   541
      return *this;
deba@1531
   542
    }
deba@1531
   543
deba@1531
   544
    /// \brief Make copy of the given map.
deba@1531
   545
    ///
deba@1531
   546
    /// Makes copy of the given map for the newly created graph. 
deba@1531
   547
    /// The new map's key type is the target graph's edge type,
deba@1531
   548
    /// and the copied map's key type is the source graph's edge
deba@1531
   549
    /// type.  
deba@1531
   550
    template <typename TargetMap, typename SourceMap>
deba@1531
   551
    const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
deba@1531
   552
      copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
deba@1531
   553
      return *this;
deba@1531
   554
    }
deba@1531
   555
deba@1531
   556
    /// \brief Gives back the stored node references.
deba@1531
   557
    ///
deba@1531
   558
    /// Gives back the stored node references.
deba@1531
   559
    const NodeRefMap& nodeRef() const {
deba@1531
   560
      return nodeRefMap;
deba@1531
   561
    }
deba@1531
   562
deba@1531
   563
    /// \brief Gives back the stored edge references.
deba@1531
   564
    ///
deba@1531
   565
    /// Gives back the stored edge references.
deba@1531
   566
    const EdgeRefMap& edgeRef() const {
deba@1531
   567
      return edgeRefMap;
deba@1531
   568
    }
deba@1531
   569
deba@1720
   570
    void run() {}
deba@1720
   571
deba@1531
   572
  private:
deba@1531
   573
    
deba@1531
   574
    const Source& source;
deba@1531
   575
    Target& target;
deba@1531
   576
deba@1531
   577
    NodeRefMap nodeRefMap;
deba@1531
   578
    EdgeRefMap edgeRefMap;
deba@1267
   579
  };
klao@946
   580
deba@1531
   581
  /// \brief Copy a graph to an other graph.
deba@1531
   582
  ///
deba@1531
   583
  /// Copy a graph to an other graph.
deba@1531
   584
  /// The usage of the function:
deba@1531
   585
  /// 
deba@1531
   586
  /// \code
deba@1531
   587
  /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
deba@1531
   588
  /// \endcode
deba@1531
   589
  /// 
deba@1531
   590
  /// After the copy the \c nr map will contain the mapping from the
deba@1531
   591
  /// source graph's nodes to the target graph's nodes and the \c ecr will
athos@1540
   592
  /// contain the mapping from the target graph's edges to the source's
deba@1531
   593
  /// edges.
deba@1531
   594
  template <typename Target, typename Source>
deba@1531
   595
  GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
deba@1531
   596
    return GraphCopy<Target, Source>(target, source);
deba@1531
   597
  }
klao@946
   598
deba@1720
   599
  /// \brief Class to copy an undirected graph.
deba@1720
   600
  ///
deba@1720
   601
  /// Class to copy an undirected graph to an other graph (duplicate a graph).
deba@1720
   602
  /// The simplest way of using it is through the \c copyUndirGraph() function.
deba@1720
   603
  template <typename Target, typename Source>
deba@1720
   604
  class UndirGraphCopy {
deba@1720
   605
  public: 
deba@1720
   606
    typedef typename Source::Node Node;
deba@1720
   607
    typedef typename Source::NodeIt NodeIt;
deba@1720
   608
    typedef typename Source::Edge Edge;
deba@1720
   609
    typedef typename Source::EdgeIt EdgeIt;
deba@1720
   610
    typedef typename Source::UndirEdge UndirEdge;
deba@1720
   611
    typedef typename Source::UndirEdgeIt UndirEdgeIt;
deba@1720
   612
deba@1720
   613
    typedef typename Source::
deba@1720
   614
    template NodeMap<typename Target::Node> NodeRefMap;
deba@1720
   615
    
deba@1720
   616
    typedef typename Source::
deba@1720
   617
    template UndirEdgeMap<typename Target::UndirEdge> UndirEdgeRefMap;
deba@1720
   618
deba@1720
   619
  private:
deba@1720
   620
deba@1720
   621
    struct EdgeRefMap {
deba@1720
   622
      EdgeRefMap(UndirGraphCopy& _gc) : gc(_gc) {}
deba@1720
   623
      typedef typename Source::Edge Key;
deba@1720
   624
      typedef typename Target::Edge Value;
deba@1720
   625
deba@1720
   626
      Value operator[](const Key& key) {
deba@1720
   627
	return gc.target.direct(gc.undirEdgeRef[key], 
deba@1720
   628
				gc.target.direction(key));
deba@1720
   629
      }
deba@1720
   630
      
deba@1720
   631
      UndirGraphCopy& gc;
deba@1720
   632
    };
deba@1720
   633
    
deba@1192
   634
  public:
deba@1720
   635
deba@1720
   636
    /// \brief Constructor for the UndirGraphCopy.
deba@1720
   637
    ///
deba@1720
   638
    /// It copies the content of the \c _source graph into the
deba@1720
   639
    /// \c _target graph. It creates also two references, one beetween
deba@1720
   640
    /// the two nodeset and one beetween the two edgesets.
deba@1720
   641
    UndirGraphCopy(Target& _target, const Source& _source) 
deba@1720
   642
      : source(_source), target(_target), 
deba@1720
   643
	nodeRefMap(_source), edgeRefMap(*this), undirEdgeRefMap(_source) {
deba@1720
   644
      for (NodeIt it(source); it != INVALID; ++it) {
deba@1720
   645
	nodeRefMap[it] = target.addNode();
deba@1720
   646
      }
deba@1720
   647
      for (UndirEdgeIt it(source); it != INVALID; ++it) {
deba@1720
   648
	undirEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], 
deba@1720
   649
					nodeRefMap[source.target(it)]);
deba@1720
   650
      }
deba@1720
   651
    }
deba@1720
   652
deba@1720
   653
    /// \brief Copies the node references into the given map.
deba@1720
   654
    ///
deba@1720
   655
    /// Copies the node references into the given map.
deba@1720
   656
    template <typename NodeRef>
deba@1720
   657
    const UndirGraphCopy& nodeRef(NodeRef& map) const {
deba@1720
   658
      for (NodeIt it(source); it != INVALID; ++it) {
deba@1720
   659
	map.set(it, nodeRefMap[it]);
deba@1720
   660
      }
deba@1720
   661
      return *this;
deba@1720
   662
    }
deba@1720
   663
deba@1720
   664
    /// \brief Reverse and copies the node references into the given map.
deba@1720
   665
    ///
deba@1720
   666
    /// Reverse and copies the node references into the given map.
deba@1720
   667
    template <typename NodeRef>
deba@1720
   668
    const UndirGraphCopy& nodeCrossRef(NodeRef& map) const {
deba@1720
   669
      for (NodeIt it(source); it != INVALID; ++it) {
deba@1720
   670
	map.set(nodeRefMap[it], it);
deba@1720
   671
      }
deba@1720
   672
      return *this;
deba@1720
   673
    }
deba@1720
   674
deba@1720
   675
    /// \brief Copies the edge references into the given map.
deba@1720
   676
    ///
deba@1720
   677
    /// Copies the edge references into the given map.
deba@1720
   678
    template <typename EdgeRef>
deba@1720
   679
    const UndirGraphCopy& edgeRef(EdgeRef& map) const {
deba@1720
   680
      for (EdgeIt it(source); it != INVALID; ++it) {
deba@1720
   681
	map.set(edgeRefMap[it], it);
deba@1720
   682
      }
deba@1720
   683
      return *this;
deba@1720
   684
    }
deba@1720
   685
deba@1720
   686
    /// \brief Reverse and copies the undirected edge references into the 
deba@1720
   687
    /// given map.
deba@1720
   688
    ///
deba@1720
   689
    /// Reverse and copies the undirected edge references into the given map.
deba@1720
   690
    template <typename EdgeRef>
deba@1720
   691
    const UndirGraphCopy& edgeCrossRef(EdgeRef& map) const {
deba@1720
   692
      for (EdgeIt it(source); it != INVALID; ++it) {
deba@1720
   693
	map.set(it, edgeRefMap[it]);
deba@1720
   694
      }
deba@1720
   695
      return *this;
deba@1720
   696
    }
deba@1720
   697
deba@1720
   698
    /// \brief Copies the undirected edge references into the given map.
deba@1720
   699
    ///
deba@1720
   700
    /// Copies the undirected edge references into the given map.
deba@1720
   701
    template <typename EdgeRef>
deba@1720
   702
    const UndirGraphCopy& undirEdgeRef(EdgeRef& map) const {
deba@1720
   703
      for (UndirEdgeIt it(source); it != INVALID; ++it) {
deba@1720
   704
	map.set(it, undirEdgeRefMap[it]);
deba@1720
   705
      }
deba@1720
   706
      return *this;
deba@1720
   707
    }
deba@1720
   708
deba@1720
   709
    /// \brief Reverse and copies the undirected edge references into the 
deba@1720
   710
    /// given map.
deba@1720
   711
    ///
deba@1720
   712
    /// Reverse and copies the undirected edge references into the given map.
deba@1720
   713
    template <typename EdgeRef>
deba@1720
   714
    const UndirGraphCopy& undirEdgeCrossRef(EdgeRef& map) const {
deba@1720
   715
      for (UndirEdgeIt it(source); it != INVALID; ++it) {
deba@1720
   716
	map.set(undirEdgeRefMap[it], it);
deba@1720
   717
      }
deba@1720
   718
      return *this;
deba@1720
   719
    }
deba@1720
   720
deba@1720
   721
    /// \brief Make copy of the given map.
deba@1720
   722
    ///
deba@1720
   723
    /// Makes copy of the given map for the newly created graph. 
deba@1720
   724
    /// The new map's key type is the target graph's node type,
deba@1720
   725
    /// and the copied map's key type is the source graph's node
deba@1720
   726
    /// type.  
deba@1720
   727
    template <typename TargetMap, typename SourceMap>
deba@1720
   728
    const UndirGraphCopy& nodeMap(TargetMap& tMap, 
deba@1720
   729
				  const SourceMap& sMap) const {
deba@1720
   730
      copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
deba@1720
   731
      return *this;
deba@1720
   732
    }
deba@1720
   733
deba@1720
   734
    /// \brief Make copy of the given map.
deba@1720
   735
    ///
deba@1720
   736
    /// Makes copy of the given map for the newly created graph. 
deba@1720
   737
    /// The new map's key type is the target graph's edge type,
deba@1720
   738
    /// and the copied map's key type is the source graph's edge
deba@1720
   739
    /// type.  
deba@1720
   740
    template <typename TargetMap, typename SourceMap>
deba@1720
   741
    const UndirGraphCopy& edgeMap(TargetMap& tMap, 
deba@1720
   742
				  const SourceMap& sMap) const {
deba@1720
   743
      copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
deba@1720
   744
      return *this;
deba@1720
   745
    }
deba@1720
   746
deba@1720
   747
    /// \brief Make copy of the given map.
deba@1720
   748
    ///
deba@1720
   749
    /// Makes copy of the given map for the newly created graph. 
deba@1720
   750
    /// The new map's key type is the target graph's edge type,
deba@1720
   751
    /// and the copied map's key type is the source graph's edge
deba@1720
   752
    /// type.  
deba@1720
   753
    template <typename TargetMap, typename SourceMap>
deba@1720
   754
    const UndirGraphCopy& undirEdgeMap(TargetMap& tMap, 
deba@1720
   755
				  const SourceMap& sMap) const {
deba@1720
   756
      copyMap(tMap, sMap, UndirEdgeIt(source), undirEdgeRefMap);
deba@1720
   757
      return *this;
deba@1720
   758
    }
deba@1720
   759
deba@1720
   760
    /// \brief Gives back the stored node references.
deba@1720
   761
    ///
deba@1720
   762
    /// Gives back the stored node references.
deba@1720
   763
    const NodeRefMap& nodeRef() const {
deba@1720
   764
      return nodeRefMap;
deba@1720
   765
    }
deba@1720
   766
deba@1720
   767
    /// \brief Gives back the stored edge references.
deba@1720
   768
    ///
deba@1720
   769
    /// Gives back the stored edge references.
deba@1720
   770
    const EdgeRefMap& edgeRef() const {
deba@1720
   771
      return edgeRefMap;
deba@1720
   772
    }
deba@1720
   773
deba@1720
   774
    /// \brief Gives back the stored undir edge references.
deba@1720
   775
    ///
deba@1720
   776
    /// Gives back the stored undir edge references.
deba@1720
   777
    const UndirEdgeRefMap& undirEdgeRef() const {
deba@1720
   778
      return undirEdgeRefMap;
deba@1720
   779
    }
deba@1720
   780
deba@1720
   781
    void run() {}
deba@1720
   782
deba@1720
   783
  private:
deba@1192
   784
    
deba@1720
   785
    const Source& source;
deba@1720
   786
    Target& target;
alpar@947
   787
deba@1720
   788
    NodeRefMap nodeRefMap;
deba@1720
   789
    EdgeRefMap edgeRefMap;
deba@1720
   790
    UndirEdgeRefMap undirEdgeRefMap;
deba@1192
   791
  };
deba@1192
   792
deba@1720
   793
  /// \brief Copy a graph to an other graph.
deba@1720
   794
  ///
deba@1720
   795
  /// Copy a graph to an other graph.
deba@1720
   796
  /// The usage of the function:
deba@1720
   797
  /// 
deba@1720
   798
  /// \code
deba@1720
   799
  /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
deba@1720
   800
  /// \endcode
deba@1720
   801
  /// 
deba@1720
   802
  /// After the copy the \c nr map will contain the mapping from the
deba@1720
   803
  /// source graph's nodes to the target graph's nodes and the \c ecr will
deba@1720
   804
  /// contain the mapping from the target graph's edges to the source's
deba@1720
   805
  /// edges.
deba@1720
   806
  template <typename Target, typename Source>
deba@1720
   807
  UndirGraphCopy<Target, Source> 
deba@1720
   808
  copyUndirGraph(Target& target, const Source& source) {
deba@1720
   809
    return UndirGraphCopy<Target, Source>(target, source);
deba@1720
   810
  }
deba@1192
   811
deba@1192
   812
deba@1192
   813
  /// @}
alpar@1402
   814
alpar@1402
   815
  /// \addtogroup graph_maps
alpar@1402
   816
  /// @{
alpar@1402
   817
deba@1413
   818
  /// Provides an immutable and unique id for each item in the graph.
deba@1413
   819
athos@1540
   820
  /// The IdMap class provides a unique and immutable id for each item of the
athos@1540
   821
  /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
athos@1540
   822
  /// different items (nodes) get different ids <li>\b immutable: the id of an
athos@1540
   823
  /// item (node) does not change (even if you delete other nodes).  </ul>
athos@1540
   824
  /// Through this map you get access (i.e. can read) the inner id values of
athos@1540
   825
  /// the items stored in the graph. This map can be inverted with its member
athos@1540
   826
  /// class \c InverseMap.
deba@1413
   827
  ///
deba@1413
   828
  template <typename _Graph, typename _Item>
deba@1413
   829
  class IdMap {
deba@1413
   830
  public:
deba@1413
   831
    typedef _Graph Graph;
deba@1413
   832
    typedef int Value;
deba@1413
   833
    typedef _Item Item;
deba@1413
   834
    typedef _Item Key;
deba@1413
   835
deba@1413
   836
    /// \brief Constructor.
deba@1413
   837
    ///
deba@1413
   838
    /// Constructor for creating id map.
deba@1413
   839
    IdMap(const Graph& _graph) : graph(&_graph) {}
deba@1413
   840
deba@1413
   841
    /// \brief Gives back the \e id of the item.
deba@1413
   842
    ///
deba@1413
   843
    /// Gives back the immutable and unique \e id of the map.
deba@1413
   844
    int operator[](const Item& item) const { return graph->id(item);}
deba@1413
   845
deba@1413
   846
deba@1413
   847
  private:
deba@1413
   848
    const Graph* graph;
deba@1413
   849
deba@1413
   850
  public:
deba@1413
   851
athos@1540
   852
    /// \brief The class represents the inverse of its owner (IdMap).
deba@1413
   853
    ///
athos@1540
   854
    /// The class represents the inverse of its owner (IdMap).
deba@1413
   855
    /// \see inverse()
deba@1413
   856
    class InverseMap {
deba@1413
   857
    public:
deba@1419
   858
deba@1413
   859
      /// \brief Constructor.
deba@1413
   860
      ///
deba@1413
   861
      /// Constructor for creating an id-to-item map.
deba@1413
   862
      InverseMap(const Graph& _graph) : graph(&_graph) {}
deba@1413
   863
deba@1413
   864
      /// \brief Constructor.
deba@1413
   865
      ///
deba@1413
   866
      /// Constructor for creating an id-to-item map.
deba@1413
   867
      InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
deba@1413
   868
deba@1413
   869
      /// \brief Gives back the given item from its id.
deba@1413
   870
      ///
deba@1413
   871
      /// Gives back the given item from its id.
deba@1413
   872
      /// 
deba@1413
   873
      Item operator[](int id) const { return graph->fromId(id, Item());}
deba@1413
   874
    private:
deba@1413
   875
      const Graph* graph;
deba@1413
   876
    };
deba@1413
   877
deba@1413
   878
    /// \brief Gives back the inverse of the map.
deba@1413
   879
    ///
athos@1540
   880
    /// Gives back the inverse of the IdMap.
deba@1413
   881
    InverseMap inverse() const { return InverseMap(*graph);} 
deba@1413
   882
deba@1413
   883
  };
deba@1413
   884
deba@1413
   885
  
athos@1526
   886
  /// \brief General invertable graph-map type.
alpar@1402
   887
athos@1540
   888
  /// This type provides simple invertable graph-maps. 
athos@1526
   889
  /// The InvertableMap wraps an arbitrary ReadWriteMap 
athos@1526
   890
  /// and if a key is set to a new value then store it
alpar@1402
   891
  /// in the inverse map.
alpar@1402
   892
  /// \param _Graph The graph type.
athos@1526
   893
  /// \param _Map The map to extend with invertable functionality. 
alpar@1402
   894
  template <
alpar@1402
   895
    typename _Graph,
alpar@1402
   896
    typename _Item, 
alpar@1402
   897
    typename _Value,
alpar@1402
   898
    typename _Map 
deba@1413
   899
    = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent 
alpar@1402
   900
  >
deba@1413
   901
  class InvertableMap : protected _Map {
alpar@1402
   902
alpar@1402
   903
  public:
alpar@1402
   904
 
alpar@1402
   905
    typedef _Map Map;
alpar@1402
   906
    typedef _Graph Graph;
deba@1413
   907
deba@1413
   908
    /// The key type of InvertableMap (Node, Edge, UndirEdge).
alpar@1402
   909
    typedef typename _Map::Key Key;
deba@1413
   910
    /// The value type of the InvertableMap.
alpar@1402
   911
    typedef typename _Map::Value Value;
alpar@1402
   912
alpar@1402
   913
    /// \brief Constructor.
alpar@1402
   914
    ///
deba@1413
   915
    /// Construct a new InvertableMap for the graph.
alpar@1402
   916
    ///
deba@1413
   917
    InvertableMap(const Graph& graph) : Map(graph) {} 
alpar@1402
   918
    
alpar@1402
   919
    /// \brief The setter function of the map.
alpar@1402
   920
    ///
deba@1413
   921
    /// Sets the mapped value.
alpar@1402
   922
    void set(const Key& key, const Value& val) {
alpar@1402
   923
      Value oldval = Map::operator[](key);
deba@1413
   924
      typename Container::iterator it = invMap.find(oldval);
alpar@1402
   925
      if (it != invMap.end() && it->second == key) {
alpar@1402
   926
	invMap.erase(it);
alpar@1402
   927
      }      
alpar@1402
   928
      invMap.insert(make_pair(val, key));
alpar@1402
   929
      Map::set(key, val);
alpar@1402
   930
    }
alpar@1402
   931
alpar@1402
   932
    /// \brief The getter function of the map.
alpar@1402
   933
    ///
alpar@1402
   934
    /// It gives back the value associated with the key.
deba@1720
   935
    Value operator[](const Key& key) const {
alpar@1402
   936
      return Map::operator[](key);
alpar@1402
   937
    }
alpar@1402
   938
deba@1515
   939
  protected:
deba@1515
   940
alpar@1402
   941
    /// \brief Add a new key to the map.
alpar@1402
   942
    ///
alpar@1402
   943
    /// Add a new key to the map. It is called by the
alpar@1402
   944
    /// \c AlterationNotifier.
alpar@1402
   945
    virtual void add(const Key& key) {
alpar@1402
   946
      Map::add(key);
alpar@1402
   947
    }
alpar@1402
   948
alpar@1402
   949
    /// \brief Erase the key from the map.
alpar@1402
   950
    ///
alpar@1402
   951
    /// Erase the key to the map. It is called by the
alpar@1402
   952
    /// \c AlterationNotifier.
alpar@1402
   953
    virtual void erase(const Key& key) {
alpar@1402
   954
      Value val = Map::operator[](key);
deba@1413
   955
      typename Container::iterator it = invMap.find(val);
alpar@1402
   956
      if (it != invMap.end() && it->second == key) {
alpar@1402
   957
	invMap.erase(it);
alpar@1402
   958
      }
alpar@1402
   959
      Map::erase(key);
alpar@1402
   960
    }
alpar@1402
   961
alpar@1402
   962
    /// \brief Clear the keys from the map and inverse map.
alpar@1402
   963
    ///
alpar@1402
   964
    /// Clear the keys from the map and inverse map. It is called by the
alpar@1402
   965
    /// \c AlterationNotifier.
alpar@1402
   966
    virtual void clear() {
alpar@1402
   967
      invMap.clear();
alpar@1402
   968
      Map::clear();
alpar@1402
   969
    }
alpar@1402
   970
deba@1413
   971
  private:
deba@1413
   972
    
deba@1413
   973
    typedef std::map<Value, Key> Container;
deba@1413
   974
    Container invMap;    
deba@1413
   975
deba@1413
   976
  public:
deba@1413
   977
deba@1413
   978
    /// \brief The inverse map type.
deba@1413
   979
    ///
deba@1413
   980
    /// The inverse of this map. The subscript operator of the map
deba@1413
   981
    /// gives back always the item what was last assigned to the value. 
deba@1413
   982
    class InverseMap {
deba@1413
   983
    public:
deba@1413
   984
      /// \brief Constructor of the InverseMap.
deba@1413
   985
      ///
deba@1413
   986
      /// Constructor of the InverseMap.
deba@1413
   987
      InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
deba@1413
   988
deba@1413
   989
      /// The value type of the InverseMap.
deba@1413
   990
      typedef typename InvertableMap::Key Value;
deba@1413
   991
      /// The key type of the InverseMap.
deba@1413
   992
      typedef typename InvertableMap::Value Key; 
deba@1413
   993
deba@1413
   994
      /// \brief Subscript operator. 
deba@1413
   995
      ///
deba@1413
   996
      /// Subscript operator. It gives back always the item 
deba@1413
   997
      /// what was last assigned to the value.
deba@1413
   998
      Value operator[](const Key& key) const {
deba@1413
   999
	typename Container::const_iterator it = inverted.invMap.find(key);
deba@1413
  1000
	return it->second;
deba@1413
  1001
      }
deba@1413
  1002
      
deba@1413
  1003
    private:
deba@1413
  1004
      const InvertableMap& inverted;
deba@1413
  1005
    };
deba@1413
  1006
alpar@1402
  1007
    /// \brief It gives back the just readeable inverse map.
alpar@1402
  1008
    ///
alpar@1402
  1009
    /// It gives back the just readeable inverse map.
deba@1413
  1010
    InverseMap inverse() const {
deba@1413
  1011
      return InverseMap(*this);
alpar@1402
  1012
    } 
alpar@1402
  1013
alpar@1402
  1014
deba@1413
  1015
    
alpar@1402
  1016
  };
alpar@1402
  1017
alpar@1402
  1018
  /// \brief Provides a mutable, continuous and unique descriptor for each 
alpar@1402
  1019
  /// item in the graph.
alpar@1402
  1020
  ///
athos@1540
  1021
  /// The DescriptorMap class provides a unique and continuous (but mutable)
athos@1540
  1022
  /// descriptor (id) for each item of the same type (e.g. node) in the
athos@1540
  1023
  /// graph. This id is <ul><li>\b unique: different items (nodes) get
athos@1540
  1024
  /// different ids <li>\b continuous: the range of the ids is the set of
athos@1540
  1025
  /// integers between 0 and \c n-1, where \c n is the number of the items of
athos@1540
  1026
  /// this type (e.g. nodes) (so the id of a node can change if you delete an
athos@1540
  1027
  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
athos@1540
  1028
  /// with its member class \c InverseMap.
alpar@1402
  1029
  ///
alpar@1402
  1030
  /// \param _Graph The graph class the \c DescriptorMap belongs to.
alpar@1402
  1031
  /// \param _Item The Item is the Key of the Map. It may be Node, Edge or 
alpar@1402
  1032
  /// UndirEdge.
alpar@1402
  1033
  /// \param _Map A ReadWriteMap mapping from the item type to integer.
alpar@1402
  1034
  template <
alpar@1402
  1035
    typename _Graph,   
alpar@1402
  1036
    typename _Item,
deba@1413
  1037
    typename _Map 
deba@1413
  1038
    = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
alpar@1402
  1039
  >
alpar@1402
  1040
  class DescriptorMap : protected _Map {
alpar@1402
  1041
alpar@1402
  1042
    typedef _Item Item;
alpar@1402
  1043
    typedef _Map Map;
alpar@1402
  1044
alpar@1402
  1045
  public:
alpar@1402
  1046
    /// The graph class of DescriptorMap.
alpar@1402
  1047
    typedef _Graph Graph;
alpar@1402
  1048
alpar@1402
  1049
    /// The key type of DescriptorMap (Node, Edge, UndirEdge).
alpar@1402
  1050
    typedef typename _Map::Key Key;
alpar@1402
  1051
    /// The value type of DescriptorMap.
alpar@1402
  1052
    typedef typename _Map::Value Value;
alpar@1402
  1053
alpar@1402
  1054
    /// \brief Constructor.
alpar@1402
  1055
    ///
deba@1413
  1056
    /// Constructor for descriptor map.
alpar@1402
  1057
    DescriptorMap(const Graph& _graph) : Map(_graph) {
alpar@1402
  1058
      build();
alpar@1402
  1059
    }
alpar@1402
  1060
deba@1515
  1061
  protected:
deba@1515
  1062
alpar@1402
  1063
    /// \brief Add a new key to the map.
alpar@1402
  1064
    ///
alpar@1402
  1065
    /// Add a new key to the map. It is called by the
alpar@1402
  1066
    /// \c AlterationNotifier.
alpar@1402
  1067
    virtual void add(const Item& item) {
alpar@1402
  1068
      Map::add(item);
alpar@1402
  1069
      Map::set(item, invMap.size());
alpar@1402
  1070
      invMap.push_back(item);
alpar@1402
  1071
    }
alpar@1402
  1072
alpar@1402
  1073
    /// \brief Erase the key from the map.
alpar@1402
  1074
    ///
alpar@1402
  1075
    /// Erase the key to the map. It is called by the
alpar@1402
  1076
    /// \c AlterationNotifier.
alpar@1402
  1077
    virtual void erase(const Item& item) {
alpar@1402
  1078
      Map::set(invMap.back(), Map::operator[](item));
alpar@1402
  1079
      invMap[Map::operator[](item)] = invMap.back();
deba@1413
  1080
      invMap.pop_back();
alpar@1402
  1081
      Map::erase(item);
alpar@1402
  1082
    }
alpar@1402
  1083
alpar@1402
  1084
    /// \brief Build the unique map.
alpar@1402
  1085
    ///
alpar@1402
  1086
    /// Build the unique map. It is called by the
alpar@1402
  1087
    /// \c AlterationNotifier.
alpar@1402
  1088
    virtual void build() {
alpar@1402
  1089
      Map::build();
alpar@1402
  1090
      Item it;
alpar@1402
  1091
      const typename Map::Graph* graph = Map::getGraph(); 
alpar@1402
  1092
      for (graph->first(it); it != INVALID; graph->next(it)) {
alpar@1402
  1093
	Map::set(it, invMap.size());
alpar@1402
  1094
	invMap.push_back(it);	
alpar@1402
  1095
      }      
alpar@1402
  1096
    }
alpar@1402
  1097
    
alpar@1402
  1098
    /// \brief Clear the keys from the map.
alpar@1402
  1099
    ///
alpar@1402
  1100
    /// Clear the keys from the map. It is called by the
alpar@1402
  1101
    /// \c AlterationNotifier.
alpar@1402
  1102
    virtual void clear() {
alpar@1402
  1103
      invMap.clear();
alpar@1402
  1104
      Map::clear();
alpar@1402
  1105
    }
alpar@1402
  1106
deba@1538
  1107
  public:
deba@1538
  1108
deba@1552
  1109
    /// \brief Swaps the position of the two items in the map.
deba@1552
  1110
    ///
deba@1552
  1111
    /// Swaps the position of the two items in the map.
deba@1552
  1112
    void swap(const Item& p, const Item& q) {
deba@1552
  1113
      int pi = Map::operator[](p);
deba@1552
  1114
      int qi = Map::operator[](q);
deba@1552
  1115
      Map::set(p, qi);
deba@1552
  1116
      invMap[qi] = p;
deba@1552
  1117
      Map::set(q, pi);
deba@1552
  1118
      invMap[pi] = q;
deba@1552
  1119
    }
deba@1552
  1120
alpar@1402
  1121
    /// \brief Gives back the \e descriptor of the item.
alpar@1402
  1122
    ///
alpar@1402
  1123
    /// Gives back the mutable and unique \e descriptor of the map.
alpar@1402
  1124
    int operator[](const Item& item) const {
alpar@1402
  1125
      return Map::operator[](item);
alpar@1402
  1126
    }
alpar@1402
  1127
    
deba@1413
  1128
  private:
deba@1413
  1129
deba@1413
  1130
    typedef std::vector<Item> Container;
deba@1413
  1131
    Container invMap;
deba@1413
  1132
deba@1413
  1133
  public:
athos@1540
  1134
    /// \brief The inverse map type of DescriptorMap.
deba@1413
  1135
    ///
athos@1540
  1136
    /// The inverse map type of DescriptorMap.
deba@1413
  1137
    class InverseMap {
deba@1413
  1138
    public:
deba@1413
  1139
      /// \brief Constructor of the InverseMap.
deba@1413
  1140
      ///
deba@1413
  1141
      /// Constructor of the InverseMap.
deba@1413
  1142
      InverseMap(const DescriptorMap& _inverted) 
deba@1413
  1143
	: inverted(_inverted) {}
deba@1413
  1144
deba@1413
  1145
deba@1413
  1146
      /// The value type of the InverseMap.
deba@1413
  1147
      typedef typename DescriptorMap::Key Value;
deba@1413
  1148
      /// The key type of the InverseMap.
deba@1413
  1149
      typedef typename DescriptorMap::Value Key; 
deba@1413
  1150
deba@1413
  1151
      /// \brief Subscript operator. 
deba@1413
  1152
      ///
deba@1413
  1153
      /// Subscript operator. It gives back the item 
deba@1413
  1154
      /// that the descriptor belongs to currently.
deba@1413
  1155
      Value operator[](const Key& key) const {
deba@1413
  1156
	return inverted.invMap[key];
deba@1413
  1157
      }
deba@1470
  1158
deba@1470
  1159
      /// \brief Size of the map.
deba@1470
  1160
      ///
deba@1470
  1161
      /// Returns the size of the map.
deba@1552
  1162
      int size() const {
deba@1470
  1163
	return inverted.invMap.size();
deba@1470
  1164
      }
deba@1413
  1165
      
deba@1413
  1166
    private:
deba@1413
  1167
      const DescriptorMap& inverted;
deba@1413
  1168
    };
deba@1413
  1169
alpar@1402
  1170
    /// \brief Gives back the inverse of the map.
alpar@1402
  1171
    ///
alpar@1402
  1172
    /// Gives back the inverse of the map.
alpar@1402
  1173
    const InverseMap inverse() const {
deba@1413
  1174
      return InverseMap(*this);
alpar@1402
  1175
    }
alpar@1402
  1176
  };
alpar@1402
  1177
alpar@1402
  1178
  /// \brief Returns the source of the given edge.
alpar@1402
  1179
  ///
alpar@1402
  1180
  /// The SourceMap gives back the source Node of the given edge. 
alpar@1402
  1181
  /// \author Balazs Dezso
alpar@1402
  1182
  template <typename Graph>
alpar@1402
  1183
  class SourceMap {
alpar@1402
  1184
  public:
deba@1419
  1185
alpar@1402
  1186
    typedef typename Graph::Node Value;
alpar@1402
  1187
    typedef typename Graph::Edge Key;
alpar@1402
  1188
alpar@1402
  1189
    /// \brief Constructor
alpar@1402
  1190
    ///
alpar@1402
  1191
    /// Constructor
alpar@1402
  1192
    /// \param _graph The graph that the map belongs to.
alpar@1402
  1193
    SourceMap(const Graph& _graph) : graph(_graph) {}
alpar@1402
  1194
alpar@1402
  1195
    /// \brief The subscript operator.
alpar@1402
  1196
    ///
alpar@1402
  1197
    /// The subscript operator.
alpar@1402
  1198
    /// \param edge The edge 
alpar@1402
  1199
    /// \return The source of the edge 
deba@1679
  1200
    Value operator[](const Key& edge) const {
alpar@1402
  1201
      return graph.source(edge);
alpar@1402
  1202
    }
alpar@1402
  1203
alpar@1402
  1204
  private:
alpar@1402
  1205
    const Graph& graph;
alpar@1402
  1206
  };
alpar@1402
  1207
alpar@1402
  1208
  /// \brief Returns a \ref SourceMap class
alpar@1402
  1209
  ///
alpar@1402
  1210
  /// This function just returns an \ref SourceMap class.
alpar@1402
  1211
  /// \relates SourceMap
alpar@1402
  1212
  template <typename Graph>
alpar@1402
  1213
  inline SourceMap<Graph> sourceMap(const Graph& graph) {
alpar@1402
  1214
    return SourceMap<Graph>(graph);
alpar@1402
  1215
  } 
alpar@1402
  1216
alpar@1402
  1217
  /// \brief Returns the target of the given edge.
alpar@1402
  1218
  ///
alpar@1402
  1219
  /// The TargetMap gives back the target Node of the given edge. 
alpar@1402
  1220
  /// \author Balazs Dezso
alpar@1402
  1221
  template <typename Graph>
alpar@1402
  1222
  class TargetMap {
alpar@1402
  1223
  public:
deba@1419
  1224
alpar@1402
  1225
    typedef typename Graph::Node Value;
alpar@1402
  1226
    typedef typename Graph::Edge Key;
alpar@1402
  1227
alpar@1402
  1228
    /// \brief Constructor
alpar@1402
  1229
    ///
alpar@1402
  1230
    /// Constructor
alpar@1402
  1231
    /// \param _graph The graph that the map belongs to.
alpar@1402
  1232
    TargetMap(const Graph& _graph) : graph(_graph) {}
alpar@1402
  1233
alpar@1402
  1234
    /// \brief The subscript operator.
alpar@1402
  1235
    ///
alpar@1402
  1236
    /// The subscript operator.
alpar@1536
  1237
    /// \param e The edge 
alpar@1402
  1238
    /// \return The target of the edge 
deba@1679
  1239
    Value operator[](const Key& e) const {
alpar@1536
  1240
      return graph.target(e);
alpar@1402
  1241
    }
alpar@1402
  1242
alpar@1402
  1243
  private:
alpar@1402
  1244
    const Graph& graph;
alpar@1402
  1245
  };
alpar@1402
  1246
alpar@1402
  1247
  /// \brief Returns a \ref TargetMap class
deba@1515
  1248
  ///
athos@1540
  1249
  /// This function just returns a \ref TargetMap class.
alpar@1402
  1250
  /// \relates TargetMap
alpar@1402
  1251
  template <typename Graph>
alpar@1402
  1252
  inline TargetMap<Graph> targetMap(const Graph& graph) {
alpar@1402
  1253
    return TargetMap<Graph>(graph);
alpar@1402
  1254
  }
alpar@1402
  1255
athos@1540
  1256
  /// \brief Returns the "forward" directed edge view of an undirected edge.
deba@1419
  1257
  ///
athos@1540
  1258
  /// Returns the "forward" directed edge view of an undirected edge.
deba@1419
  1259
  /// \author Balazs Dezso
deba@1419
  1260
  template <typename Graph>
deba@1419
  1261
  class ForwardMap {
deba@1419
  1262
  public:
deba@1419
  1263
deba@1419
  1264
    typedef typename Graph::Edge Value;
deba@1419
  1265
    typedef typename Graph::UndirEdge Key;
deba@1419
  1266
deba@1419
  1267
    /// \brief Constructor
deba@1419
  1268
    ///
deba@1419
  1269
    /// Constructor
deba@1419
  1270
    /// \param _graph The graph that the map belongs to.
deba@1419
  1271
    ForwardMap(const Graph& _graph) : graph(_graph) {}
deba@1419
  1272
deba@1419
  1273
    /// \brief The subscript operator.
deba@1419
  1274
    ///
deba@1419
  1275
    /// The subscript operator.
deba@1419
  1276
    /// \param key An undirected edge 
deba@1419
  1277
    /// \return The "forward" directed edge view of undirected edge 
deba@1419
  1278
    Value operator[](const Key& key) const {
deba@1627
  1279
      return graph.direct(key, true);
deba@1419
  1280
    }
deba@1419
  1281
deba@1419
  1282
  private:
deba@1419
  1283
    const Graph& graph;
deba@1419
  1284
  };
deba@1419
  1285
deba@1419
  1286
  /// \brief Returns a \ref ForwardMap class
deba@1515
  1287
  ///
deba@1419
  1288
  /// This function just returns an \ref ForwardMap class.
deba@1419
  1289
  /// \relates ForwardMap
deba@1419
  1290
  template <typename Graph>
deba@1419
  1291
  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
deba@1419
  1292
    return ForwardMap<Graph>(graph);
deba@1419
  1293
  }
deba@1419
  1294
athos@1540
  1295
  /// \brief Returns the "backward" directed edge view of an undirected edge.
deba@1419
  1296
  ///
athos@1540
  1297
  /// Returns the "backward" directed edge view of an undirected edge.
deba@1419
  1298
  /// \author Balazs Dezso
deba@1419
  1299
  template <typename Graph>
deba@1419
  1300
  class BackwardMap {
deba@1419
  1301
  public:
deba@1419
  1302
deba@1419
  1303
    typedef typename Graph::Edge Value;
deba@1419
  1304
    typedef typename Graph::UndirEdge Key;
deba@1419
  1305
deba@1419
  1306
    /// \brief Constructor
deba@1419
  1307
    ///
deba@1419
  1308
    /// Constructor
deba@1419
  1309
    /// \param _graph The graph that the map belongs to.
deba@1419
  1310
    BackwardMap(const Graph& _graph) : graph(_graph) {}
deba@1419
  1311
deba@1419
  1312
    /// \brief The subscript operator.
deba@1419
  1313
    ///
deba@1419
  1314
    /// The subscript operator.
deba@1419
  1315
    /// \param key An undirected edge 
deba@1419
  1316
    /// \return The "backward" directed edge view of undirected edge 
deba@1419
  1317
    Value operator[](const Key& key) const {
deba@1627
  1318
      return graph.direct(key, false);
deba@1419
  1319
    }
deba@1419
  1320
deba@1419
  1321
  private:
deba@1419
  1322
    const Graph& graph;
deba@1419
  1323
  };
deba@1419
  1324
deba@1419
  1325
  /// \brief Returns a \ref BackwardMap class
deba@1419
  1326
athos@1540
  1327
  /// This function just returns a \ref BackwardMap class.
deba@1419
  1328
  /// \relates BackwardMap
deba@1419
  1329
  template <typename Graph>
deba@1419
  1330
  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
deba@1419
  1331
    return BackwardMap<Graph>(graph);
deba@1419
  1332
  }
deba@1419
  1333
deba@1695
  1334
  /// \brief Potential difference map
deba@1695
  1335
  ///
deba@1695
  1336
  /// If there is an potential map on the nodes then we
deba@1695
  1337
  /// can get an edge map as we get the substraction of the
deba@1695
  1338
  /// values of the target and source.
deba@1695
  1339
  template <typename Graph, typename NodeMap>
deba@1695
  1340
  class PotentialDifferenceMap {
deba@1515
  1341
  public:
deba@1695
  1342
    typedef typename Graph::Edge Key;
deba@1695
  1343
    typedef typename NodeMap::Value Value;
deba@1695
  1344
deba@1695
  1345
    /// \brief Constructor
deba@1695
  1346
    ///
deba@1695
  1347
    /// Contructor of the map
deba@1695
  1348
    PotentialDifferenceMap(const Graph& _graph, const NodeMap& _potential) 
deba@1695
  1349
      : graph(_graph), potential(_potential) {}
deba@1695
  1350
deba@1695
  1351
    /// \brief Const subscription operator
deba@1695
  1352
    ///
deba@1695
  1353
    /// Const subscription operator
deba@1695
  1354
    Value operator[](const Key& edge) const {
deba@1695
  1355
      return potential[graph.target(edge)] - potential[graph.source(edge)];
deba@1695
  1356
    }
deba@1695
  1357
deba@1695
  1358
  private:
deba@1695
  1359
    const Graph& graph;
deba@1695
  1360
    const NodeMap& potential;
deba@1695
  1361
  };
deba@1695
  1362
deba@1695
  1363
  /// \brief Just returns a PotentialDifferenceMap
deba@1695
  1364
  ///
deba@1695
  1365
  /// Just returns a PotentialDifferenceMap
deba@1695
  1366
  /// \relates PotentialDifferenceMap
deba@1695
  1367
  template <typename Graph, typename NodeMap>
deba@1695
  1368
  PotentialDifferenceMap<Graph, NodeMap> 
deba@1695
  1369
  potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
deba@1695
  1370
    return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
deba@1695
  1371
  }
deba@1695
  1372
deba@1515
  1373
  /// \brief Map of the node in-degrees.
alpar@1453
  1374
  ///
athos@1540
  1375
  /// This map returns the in-degree of a node. Once it is constructed,
deba@1515
  1376
  /// the degrees are stored in a standard NodeMap, so each query is done
athos@1540
  1377
  /// in constant time. On the other hand, the values are updated automatically
deba@1515
  1378
  /// whenever the graph changes.
deba@1515
  1379
  ///
deba@1729
  1380
  /// \warning Besides addNode() and addEdge(), a graph structure may provide
deba@1730
  1381
  /// alternative ways to modify the graph. The correct behavior of InDegMap
deba@1729
  1382
  /// is not guarantied if these additional featureas are used. For example
deba@1729
  1383
  /// the funstions \ref ListGraph::changeSource() "changeSource()",
deba@1729
  1384
  /// \ref ListGraph::changeTarget() "changeTarget()" and
deba@1729
  1385
  /// \ref ListGraph::reverseEdge() "reverseEdge()"
deba@1729
  1386
  /// of \ref ListGraph will \e not update the degree values correctly.
deba@1729
  1387
  ///
deba@1515
  1388
  /// \sa OutDegMap
deba@1515
  1389
alpar@1453
  1390
  template <typename _Graph>
deba@1515
  1391
  class InDegMap  
deba@1515
  1392
    : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
deba@1515
  1393
alpar@1453
  1394
  public:
deba@1515
  1395
    
deba@1515
  1396
    typedef _Graph Graph;
alpar@1453
  1397
    typedef int Value;
deba@1515
  1398
    typedef typename Graph::Node Key;
deba@1515
  1399
deba@1515
  1400
  private:
deba@1515
  1401
deba@1515
  1402
    class AutoNodeMap : public Graph::template NodeMap<int> {
deba@1515
  1403
    public:
deba@1515
  1404
deba@1515
  1405
      typedef typename Graph::template NodeMap<int> Parent;
deba@1515
  1406
deba@1515
  1407
      typedef typename Parent::Key Key;
deba@1515
  1408
      typedef typename Parent::Value Value;
deba@1515
  1409
      
deba@1515
  1410
      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
deba@1515
  1411
      
deba@1515
  1412
      void add(const Key& key) {
deba@1515
  1413
	Parent::add(key);
deba@1515
  1414
	Parent::set(key, 0);
deba@1515
  1415
      }
deba@1515
  1416
    };
deba@1515
  1417
deba@1515
  1418
  public:
alpar@1453
  1419
alpar@1453
  1420
    /// \brief Constructor.
alpar@1453
  1421
    ///
alpar@1453
  1422
    /// Constructor for creating in-degree map.
deba@1515
  1423
    InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
alpar@1459
  1424
      AlterationNotifier<typename _Graph::Edge>
alpar@1459
  1425
	::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
deba@1515
  1426
      
deba@1515
  1427
      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
deba@1515
  1428
	deg[it] = countInEdges(graph, it);
deba@1515
  1429
      }
alpar@1453
  1430
    }
alpar@1453
  1431
deba@1515
  1432
    virtual ~InDegMap() {
alpar@1459
  1433
      AlterationNotifier<typename _Graph::Edge>::
alpar@1453
  1434
	ObserverBase::detach();
alpar@1453
  1435
    }
alpar@1453
  1436
    
alpar@1459
  1437
    /// Gives back the in-degree of a Node.
deba@1515
  1438
    int operator[](const Key& key) const {
deba@1515
  1439
      return deg[key];
alpar@1459
  1440
    }
alpar@1453
  1441
alpar@1453
  1442
  protected:
deba@1515
  1443
    
deba@1515
  1444
    typedef typename Graph::Edge Edge;
deba@1515
  1445
deba@1515
  1446
    virtual void add(const Edge& edge) {
deba@1515
  1447
      ++deg[graph.target(edge)];
alpar@1453
  1448
    }
alpar@1453
  1449
deba@1515
  1450
    virtual void erase(const Edge& edge) {
deba@1515
  1451
      --deg[graph.target(edge)];
deba@1515
  1452
    }
deba@1515
  1453
deba@1720
  1454
    virtual void signalChange(const Edge& edge) {
deba@1720
  1455
      erase(edge);
deba@1720
  1456
    }
deba@1720
  1457
deba@1720
  1458
    virtual void commitChange(const Edge& edge) {
deba@1720
  1459
      add(edge);
deba@1720
  1460
    }
deba@1515
  1461
deba@1515
  1462
    virtual void build() {
deba@1515
  1463
      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
deba@1515
  1464
	deg[it] = countInEdges(graph, it);
deba@1515
  1465
      }      
deba@1515
  1466
    }
deba@1515
  1467
deba@1515
  1468
    virtual void clear() {
deba@1515
  1469
      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
deba@1515
  1470
	deg[it] = 0;
deba@1515
  1471
      }
deba@1515
  1472
    }
deba@1515
  1473
  private:
alpar@1506
  1474
    
deba@1515
  1475
    const _Graph& graph;
deba@1515
  1476
    AutoNodeMap deg;
alpar@1459
  1477
  };
alpar@1459
  1478
deba@1515
  1479
  /// \brief Map of the node out-degrees.
deba@1515
  1480
  ///
athos@1540
  1481
  /// This map returns the out-degree of a node. Once it is constructed,
deba@1515
  1482
  /// the degrees are stored in a standard NodeMap, so each query is done
athos@1540
  1483
  /// in constant time. On the other hand, the values are updated automatically
deba@1515
  1484
  /// whenever the graph changes.
deba@1515
  1485
  ///
deba@1729
  1486
  /// \warning Besides addNode() and addEdge(), a graph structure may provide
deba@1730
  1487
  /// alternative ways to modify the graph. The correct behavior of OutDegMap
deba@1729
  1488
  /// is not guarantied if these additional featureas are used. For example
deba@1729
  1489
  /// the funstions \ref ListGraph::changeSource() "changeSource()",
deba@1729
  1490
  /// \ref ListGraph::changeTarget() "changeTarget()" and
deba@1729
  1491
  /// \ref ListGraph::reverseEdge() "reverseEdge()"
deba@1729
  1492
  /// of \ref ListGraph will \e not update the degree values correctly.
deba@1729
  1493
  ///
alpar@1555
  1494
  /// \sa InDegMap
alpar@1459
  1495
alpar@1459
  1496
  template <typename _Graph>
deba@1515
  1497
  class OutDegMap  
deba@1515
  1498
    : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
deba@1515
  1499
alpar@1459
  1500
  public:
deba@1515
  1501
    
deba@1515
  1502
    typedef _Graph Graph;
alpar@1459
  1503
    typedef int Value;
deba@1515
  1504
    typedef typename Graph::Node Key;
deba@1515
  1505
deba@1515
  1506
  private:
deba@1515
  1507
deba@1515
  1508
    class AutoNodeMap : public Graph::template NodeMap<int> {
deba@1515
  1509
    public:
deba@1515
  1510
deba@1515
  1511
      typedef typename Graph::template NodeMap<int> Parent;
deba@1515
  1512
deba@1515
  1513
      typedef typename Parent::Key Key;
deba@1515
  1514
      typedef typename Parent::Value Value;
deba@1515
  1515
      
deba@1515
  1516
      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
deba@1515
  1517
      
deba@1515
  1518
      void add(const Key& key) {
deba@1515
  1519
	Parent::add(key);
deba@1515
  1520
	Parent::set(key, 0);
deba@1515
  1521
      }
deba@1515
  1522
    };
deba@1515
  1523
deba@1515
  1524
  public:
alpar@1459
  1525
alpar@1459
  1526
    /// \brief Constructor.
alpar@1459
  1527
    ///
alpar@1459
  1528
    /// Constructor for creating out-degree map.
deba@1515
  1529
    OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
alpar@1459
  1530
      AlterationNotifier<typename _Graph::Edge>
alpar@1459
  1531
	::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
deba@1515
  1532
      
deba@1515
  1533
      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
deba@1515
  1534
	deg[it] = countOutEdges(graph, it);
deba@1515
  1535
      }
alpar@1459
  1536
    }
alpar@1459
  1537
deba@1515
  1538
    virtual ~OutDegMap() {
alpar@1459
  1539
      AlterationNotifier<typename _Graph::Edge>::
alpar@1459
  1540
	ObserverBase::detach();
alpar@1459
  1541
    }
alpar@1459
  1542
    
alpar@1459
  1543
    /// Gives back the in-degree of a Node.
deba@1515
  1544
    int operator[](const Key& key) const {
deba@1515
  1545
      return deg[key];
alpar@1459
  1546
    }
alpar@1459
  1547
alpar@1459
  1548
  protected:
deba@1515
  1549
    
deba@1515
  1550
    typedef typename Graph::Edge Edge;
deba@1515
  1551
deba@1515
  1552
    virtual void add(const Edge& edge) {
deba@1515
  1553
      ++deg[graph.source(edge)];
alpar@1459
  1554
    }
alpar@1459
  1555
deba@1515
  1556
    virtual void erase(const Edge& edge) {
deba@1515
  1557
      --deg[graph.source(edge)];
deba@1515
  1558
    }
deba@1515
  1559
deba@1720
  1560
    virtual void signalChange(const Edge& edge) {
deba@1720
  1561
      erase(edge);
deba@1720
  1562
    }
deba@1720
  1563
deba@1720
  1564
    virtual void commitChange(const Edge& edge) {
deba@1720
  1565
      add(edge);
deba@1720
  1566
    }
deba@1720
  1567
deba@1515
  1568
deba@1515
  1569
    virtual void build() {
deba@1515
  1570
      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
deba@1515
  1571
	deg[it] = countOutEdges(graph, it);
deba@1515
  1572
      }      
deba@1515
  1573
    }
deba@1515
  1574
deba@1515
  1575
    virtual void clear() {
deba@1515
  1576
      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
deba@1515
  1577
	deg[it] = 0;
deba@1515
  1578
      }
deba@1515
  1579
    }
deba@1515
  1580
  private:
alpar@1506
  1581
    
deba@1515
  1582
    const _Graph& graph;
deba@1515
  1583
    AutoNodeMap deg;
alpar@1453
  1584
  };
alpar@1453
  1585
deba@1695
  1586
alpar@1402
  1587
  /// @}
alpar@1402
  1588
alpar@947
  1589
} //END OF NAMESPACE LEMON
klao@946
  1590
klao@946
  1591
#endif