COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 1695:e6f99fe1723f

Last change on this file since 1695:e6f99fe1723f was 1695:e6f99fe1723f, checked in by Balazs Dezso, 14 years ago

Potential difference map
NodeMatrixMap? -- Matrix over the nodes
Indicators for common tags

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