COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_utils.h @ 1413:3f45d58969d4

Last change on this file since 1413:3f45d58969d4 was 1413:3f45d58969d4, checked in by Balazs Dezso, 16 years ago

Fixing invertable maps:

InvertableMap?
DescriptorMap?
IdMap?

File size: 20.2 KB
Line 
1/* -*- C++ -*-
2 * src/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 <map>
22
23#include <lemon/invalid.h>
24#include <lemon/utility.h>
25#include <lemon/maps.h>
26
27///\ingroup gutils
28///\file
29///\brief Graph utilities.
30///
31///\todo Please
32///revise the documentation.
33///
34
35
36namespace lemon {
37
38  /// \addtogroup gutils
39  /// @{
40
41  /// \brief Function to count the items in the graph.
42  ///
43  /// This function counts the items in the graph.
44  /// The complexity of the function is O(n) because
45  /// it iterates on all of the items.
46
47  template <typename Graph, typename ItemIt>
48  inline int countItems(const Graph& g) {
49    int num = 0;
50    for (ItemIt it(g); it != INVALID; ++it) {
51      ++num;
52    }
53    return num;
54  }
55
56  // Node counting:
57
58  template <typename Graph>
59  inline
60  typename enable_if<typename Graph::NodeNumTag, int>::type
61  _countNodes(const Graph &g) {
62    return g.nodeNum();
63  }
64
65  template <typename Graph>
66  inline int _countNodes(Wrap<Graph> w) {
67    return countItems<Graph, typename Graph::NodeIt>(w.value);
68  }
69
70  /// \brief Function to count the nodes in the graph.
71  ///
72  /// This function counts the nodes in the graph.
73  /// The complexity of the function is O(n) but for some
74  /// graph structure it is specialized to run in O(1).
75  ///
76  /// \todo refer how to specialize it
77
78  template <typename Graph>
79  inline int countNodes(const Graph& g) {
80    return _countNodes<Graph>(g);
81  }
82
83  // Edge counting:
84
85  template <typename Graph>
86  inline
87  typename enable_if<typename Graph::EdgeNumTag, int>::type
88  _countEdges(const Graph &g) {
89    return g.edgeNum();
90  }
91
92  template <typename Graph>
93  inline int _countEdges(Wrap<Graph> w) {
94    return countItems<Graph, typename Graph::EdgeIt>(w.value);
95  }
96
97  /// \brief Function to count the edges in the graph.
98  ///
99  /// This function counts the edges in the graph.
100  /// The complexity of the function is O(e) but for some
101  /// graph structure it is specialized to run in O(1).
102
103  template <typename Graph>
104  inline int countEdges(const Graph& g) {
105    return _countEdges<Graph>(g);
106  }
107
108  // Undirected edge counting:
109
110  template <typename Graph>
111  inline
112  typename enable_if<typename Graph::EdgeNumTag, int>::type
113  _countUndirEdges(const Graph &g) {
114    return g.undirEdgeNum();
115  }
116
117  template <typename Graph>
118  inline int _countUndirEdges(Wrap<Graph> w) {
119    return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
120  }
121
122  /// \brief Function to count the edges in the graph.
123  ///
124  /// This function counts the edges in the graph.
125  /// The complexity of the function is O(e) but for some
126  /// graph structure it is specialized to run in O(1).
127
128  template <typename Graph>
129  inline int countUndirEdges(const Graph& g) {
130    return _countUndirEdges<Graph>(g);
131  }
132
133
134
135  template <typename Graph, typename DegIt>
136  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
137    int num = 0;
138    for (DegIt it(_g, _n); it != INVALID; ++it) {
139      ++num;
140    }
141    return num;
142  }
143
144  /// Finds an edge between two nodes of a graph.
145
146  /// Finds an edge from node \c u to node \c v in graph \c g.
147  ///
148  /// If \c prev is \ref INVALID (this is the default value), then
149  /// it finds the first edge from \c u to \c v. Otherwise it looks for
150  /// the next edge from \c u to \c v after \c prev.
151  /// \return The found edge or \ref INVALID if there is no such an edge.
152  ///
153  /// Thus you can iterate through each edge from \c u to \c v as it follows.
154  /// \code
155  /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
156  ///   ...
157  /// }
158  /// \endcode
159  /// \todo We may want to use the \ref concept::GraphBase "GraphBase"
160  /// interface here...
161  /// \bug Untested ...
162  template <typename Graph>
163  typename Graph::Edge findEdge(const Graph &g,
164                                typename Graph::Node u, typename Graph::Node v,
165                                typename Graph::Edge prev = INVALID)
166  {
167    typename Graph::OutEdgeIt e(g,prev);
168    //    if(prev==INVALID) g.first(e,u);
169    if(prev==INVALID) e=typename Graph::OutEdgeIt(g,u);
170    else ++e;
171    while(e!=INVALID && g.target(e)!=v) ++e;
172    return e;
173  }
174 
175  ///\e
176
177  ///\todo Please document.
178  ///
179  template <typename Graph>
180  inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
181    return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
182  }
183
184  ///\e
185
186  ///\todo Please document.
187  ///
188  template <typename Graph>
189  inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
190    return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
191  }
192
193  // graph copy
194
195  template <
196    typename DestinationGraph,
197    typename SourceGraph,
198    typename NodeBijection>
199  void copyNodes(DestinationGraph& _d, const SourceGraph& _s,
200                 NodeBijection& _nb) {   
201    for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) {
202      _nb[it] = _d.addNode();
203    }
204  }
205
206  template <
207    typename DestinationGraph,
208    typename SourceGraph,
209    typename NodeBijection,
210    typename EdgeBijection>
211  void copyEdges(DestinationGraph& _d, const SourceGraph& _s,
212                 const NodeBijection& _nb, EdgeBijection& _eb) {   
213    for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) {
214      _eb[it] = _d.addEdge(_nb[_s.source(it)], _nb[_s.target(it)]);
215    }
216  }
217
218  template <
219    typename DestinationGraph,
220    typename SourceGraph,
221    typename NodeBijection,
222    typename EdgeBijection>
223  void copyGraph(DestinationGraph& _d, const SourceGraph& _s,
224                 NodeBijection& _nb, EdgeBijection& _eb) {
225    nodeCopy(_d, _s, _nb);
226    edgeCopy(_d, _s, _nb, _eb);
227  }
228 
229  template <
230    typename _DestinationGraph,
231    typename _SourceGraph,
232    typename _NodeBijection
233    =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>,
234    typename _EdgeBijection
235    = typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>
236  >
237  class GraphCopy {
238  public:
239   
240    typedef _DestinationGraph DestinationGraph;
241    typedef _SourceGraph SourceGraph;
242
243    typedef _NodeBijection NodeBijection;
244    typedef _EdgeBijection EdgeBijection;
245   
246  protected:         
247   
248    NodeBijection node_bijection;
249    EdgeBijection edge_bijection;     
250
251  public:
252     
253    GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
254      copyGraph(_d, _s, node_bijection, edge_bijection);
255    }
256   
257    const NodeBijection& getNodeBijection() const {
258      return node_bijection;
259    }
260
261    const EdgeBijection& getEdgeBijection() const {
262      return edge_bijection;
263    }
264     
265  };
266
267
268  template <typename _Graph, typename _Item>
269  class ItemSetTraits {
270  };
271 
272  template <typename _Graph>
273  class ItemSetTraits<_Graph, typename _Graph::Node> {
274  public:
275   
276    typedef _Graph Graph;
277
278    typedef typename Graph::Node Item;
279    typedef typename Graph::NodeIt ItemIt;
280
281    template <typename _Value>
282    class Map : public Graph::template NodeMap<_Value> {
283    public:
284      typedef typename Graph::template NodeMap<_Value> Parent;
285      typedef typename Parent::Value Value;
286
287      Map(const Graph& _graph) : Parent(_graph) {}
288      Map(const Graph& _graph, const Value& _value)
289        : Parent(_graph, _value) {}
290    };
291
292  };
293
294  template <typename _Graph>
295  class ItemSetTraits<_Graph, typename _Graph::Edge> {
296  public:
297   
298    typedef _Graph Graph;
299
300    typedef typename Graph::Edge Item;
301    typedef typename Graph::EdgeIt ItemIt;
302
303    template <typename _Value>
304    class Map : public Graph::template EdgeMap<_Value> {
305    public:
306      typedef typename Graph::template EdgeMap<_Value> Parent;
307      typedef typename Parent::Value Value;
308
309      Map(const Graph& _graph) : Parent(_graph) {}
310      Map(const Graph& _graph, const Value& _value)
311        : Parent(_graph, _value) {}
312    };
313
314  };
315
316  template <typename _Graph>
317  class ItemSetTraits<_Graph, typename _Graph::UndirEdge> {
318  public:
319   
320    typedef _Graph Graph;
321
322    typedef typename Graph::UndirEdge Item;
323    typedef typename Graph::UndirEdgeIt ItemIt;
324
325    template <typename _Value>
326    class Map : public Graph::template UndirEdgeMap<_Value> {
327    public:
328      typedef typename Graph::template UndirEdgeMap<_Value> Parent;
329      typedef typename Parent::Value Value;
330
331      Map(const Graph& _graph) : Parent(_graph) {}
332      Map(const Graph& _graph, const Value& _value)
333        : Parent(_graph, _value) {}
334    };
335
336  };
337
338  /// @}
339
340  /// \addtogroup graph_maps
341  /// @{
342
343  template <typename Map, typename Enable = void>
344  struct ReferenceMapTraits {
345    typedef typename Map::Value Value;
346    typedef typename Map::Value& Reference;
347    typedef const typename Map::Value& ConstReference;
348    typedef typename Map::Value* Pointer;
349    typedef const typename Map::Value* ConstPointer;
350  };
351
352  template <typename Map>
353  struct ReferenceMapTraits<
354    Map,
355    typename enable_if<typename Map::FullTypeTag, void>::type
356  > {
357    typedef typename Map::Value Value;
358    typedef typename Map::Reference Reference;
359    typedef typename Map::ConstReference ConstReference;
360    typedef typename Map::Pointer Pointer;
361    typedef typename Map::ConstPointer ConstPointer;
362  };
363
364
365  /// Provides an immutable and unique id for each item in the graph.
366
367  /// The IdMap class provides an unique and immutable mapping for each item
368  /// in the graph.
369  ///
370  template <typename _Graph, typename _Item>
371  class IdMap {
372  public:
373    typedef _Graph Graph;
374    typedef int Value;
375    typedef _Item Item;
376    typedef _Item Key;
377
378    /// \brief Constructor.
379    ///
380    /// Constructor for creating id map.
381    IdMap(const Graph& _graph) : graph(&_graph) {}
382
383    /// \brief Gives back the \e id of the item.
384    ///
385    /// Gives back the immutable and unique \e id of the map.
386    int operator[](const Item& item) const { return graph->id(item);}
387
388
389  private:
390    const Graph* graph;
391
392  public:
393
394    /// \brief The class represents the inverse of the map.
395    ///
396    /// The class represents the inverse of the map.
397    /// \see inverse()
398    class InverseMap {
399    public:
400      /// \brief Constructor.
401      ///
402      /// Constructor for creating an id-to-item map.
403      InverseMap(const Graph& _graph) : graph(&_graph) {}
404
405      /// \brief Constructor.
406      ///
407      /// Constructor for creating an id-to-item map.
408      InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
409
410      /// \brief Gives back the given item from its id.
411      ///
412      /// Gives back the given item from its id.
413      ///
414      Item operator[](int id) const { return graph->fromId(id, Item());}
415    private:
416      const Graph* graph;
417    };
418
419    /// \brief Gives back the inverse of the map.
420    ///
421    /// Gives back the inverse of the map.
422    InverseMap inverse() const { return InverseMap(*graph);}
423
424  };
425
426 
427  /// \brief General inversable graph-map type.
428
429  /// This type provides simple inversable map functions.
430  /// The InversableMap wraps an arbitrary ReadWriteMap
431  /// and if a key is setted to a new value then store it
432  /// in the inverse map.
433  /// \param _Graph The graph type.
434  /// \param _Map The map to extend with inversable functionality.
435  template <
436    typename _Graph,
437    typename _Item,
438    typename _Value,
439    typename _Map
440    = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent
441  >
442  class InvertableMap : protected _Map {
443
444  public:
445 
446    typedef _Map Map;
447    typedef _Graph Graph;
448
449    /// The key type of InvertableMap (Node, Edge, UndirEdge).
450    typedef typename _Map::Key Key;
451    /// The value type of the InvertableMap.
452    typedef typename _Map::Value Value;
453
454    /// \brief Constructor.
455    ///
456    /// Construct a new InvertableMap for the graph.
457    ///
458    InvertableMap(const Graph& graph) : Map(graph) {}
459   
460    /// \brief The setter function of the map.
461    ///
462    /// Sets the mapped value.
463    void set(const Key& key, const Value& val) {
464      Value oldval = Map::operator[](key);
465      typename Container::iterator it = invMap.find(oldval);
466      if (it != invMap.end() && it->second == key) {
467        invMap.erase(it);
468      }     
469      invMap.insert(make_pair(val, key));
470      Map::set(key, val);
471    }
472
473    /// \brief The getter function of the map.
474    ///
475    /// It gives back the value associated with the key.
476    const Value operator[](const Key& key) const {
477      return Map::operator[](key);
478    }
479
480    /// \brief Add a new key to the map.
481    ///
482    /// Add a new key to the map. It is called by the
483    /// \c AlterationNotifier.
484    virtual void add(const Key& key) {
485      Map::add(key);
486    }
487
488    /// \brief Erase the key from the map.
489    ///
490    /// Erase the key to the map. It is called by the
491    /// \c AlterationNotifier.
492    virtual void erase(const Key& key) {
493      Value val = Map::operator[](key);
494      typename Container::iterator it = invMap.find(val);
495      if (it != invMap.end() && it->second == key) {
496        invMap.erase(it);
497      }
498      Map::erase(key);
499    }
500
501    /// \brief Clear the keys from the map and inverse map.
502    ///
503    /// Clear the keys from the map and inverse map. It is called by the
504    /// \c AlterationNotifier.
505    virtual void clear() {
506      invMap.clear();
507      Map::clear();
508    }
509
510  private:
511   
512    typedef std::map<Value, Key> Container;
513    Container invMap;   
514
515  public:
516
517    /// \brief The inverse map type.
518    ///
519    /// The inverse of this map. The subscript operator of the map
520    /// gives back always the item what was last assigned to the value.
521    class InverseMap {
522    public:
523      /// \brief Constructor of the InverseMap.
524      ///
525      /// Constructor of the InverseMap.
526      InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
527
528      /// The value type of the InverseMap.
529      typedef typename InvertableMap::Key Value;
530      /// The key type of the InverseMap.
531      typedef typename InvertableMap::Value Key;
532
533      /// \brief Subscript operator.
534      ///
535      /// Subscript operator. It gives back always the item
536      /// what was last assigned to the value.
537      Value operator[](const Key& key) const {
538        typename Container::const_iterator it = inverted.invMap.find(key);
539        return it->second;
540      }
541     
542    private:
543      const InvertableMap& inverted;
544    };
545
546    /// \brief It gives back the just readeable inverse map.
547    ///
548    /// It gives back the just readeable inverse map.
549    InverseMap inverse() const {
550      return InverseMap(*this);
551    }
552
553
554   
555  };
556
557  /// \brief Provides a mutable, continuous and unique descriptor for each
558  /// item in the graph.
559  ///
560  /// The DescriptorMap class provides a mutable, continuous and immutable
561  /// mapping for each item in the graph. The value for an item may mutated
562  /// on each operation when the an item erased or added to graph.
563  ///
564  /// \param _Graph The graph class the \c DescriptorMap belongs to.
565  /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
566  /// UndirEdge.
567  /// \param _Map A ReadWriteMap mapping from the item type to integer.
568  template <
569    typename _Graph,   
570    typename _Item,
571    typename _Map
572    = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
573  >
574  class DescriptorMap : protected _Map {
575
576    typedef _Item Item;
577    typedef _Map Map;
578
579  public:
580    /// The graph class of DescriptorMap.
581    typedef _Graph Graph;
582
583    /// The key type of DescriptorMap (Node, Edge, UndirEdge).
584    typedef typename _Map::Key Key;
585    /// The value type of DescriptorMap.
586    typedef typename _Map::Value Value;
587
588    /// \brief Constructor.
589    ///
590    /// Constructor for descriptor map.
591    DescriptorMap(const Graph& _graph) : Map(_graph) {
592      build();
593    }
594
595    /// \brief Add a new key to the map.
596    ///
597    /// Add a new key to the map. It is called by the
598    /// \c AlterationNotifier.
599    virtual void add(const Item& item) {
600      Map::add(item);
601      Map::set(item, invMap.size());
602      invMap.push_back(item);
603    }
604
605    /// \brief Erase the key from the map.
606    ///
607    /// Erase the key to the map. It is called by the
608    /// \c AlterationNotifier.
609    virtual void erase(const Item& item) {
610      Map::set(invMap.back(), Map::operator[](item));
611      invMap[Map::operator[](item)] = invMap.back();
612      invMap.pop_back();
613      Map::erase(item);
614    }
615
616    /// \brief Build the unique map.
617    ///
618    /// Build the unique map. It is called by the
619    /// \c AlterationNotifier.
620    virtual void build() {
621      Map::build();
622      Item it;
623      const typename Map::Graph* graph = Map::getGraph();
624      for (graph->first(it); it != INVALID; graph->next(it)) {
625        Map::set(it, invMap.size());
626        invMap.push_back(it);   
627      }     
628    }
629   
630    /// \brief Clear the keys from the map.
631    ///
632    /// Clear the keys from the map. It is called by the
633    /// \c AlterationNotifier.
634    virtual void clear() {
635      invMap.clear();
636      Map::clear();
637    }
638
639    /// \brief Gives back the \e descriptor of the item.
640    ///
641    /// Gives back the mutable and unique \e descriptor of the map.
642    int operator[](const Item& item) const {
643      return Map::operator[](item);
644    }
645   
646  private:
647
648    typedef std::vector<Item> Container;
649    Container invMap;
650
651  public:
652    /// \brief The inverse map type.
653    ///
654    /// The inverse map type.
655    class InverseMap {
656    public:
657      /// \brief Constructor of the InverseMap.
658      ///
659      /// Constructor of the InverseMap.
660      InverseMap(const DescriptorMap& _inverted)
661        : inverted(_inverted) {}
662
663
664      /// The value type of the InverseMap.
665      typedef typename DescriptorMap::Key Value;
666      /// The key type of the InverseMap.
667      typedef typename DescriptorMap::Value Key;
668
669      /// \brief Subscript operator.
670      ///
671      /// Subscript operator. It gives back the item
672      /// that the descriptor belongs to currently.
673      Value operator[](const Key& key) const {
674        return inverted.invMap[key];
675      }
676     
677    private:
678      const DescriptorMap& inverted;
679    };
680
681    /// \brief Gives back the inverse of the map.
682    ///
683    /// Gives back the inverse of the map.
684    const InverseMap inverse() const {
685      return InverseMap(*this);
686    }
687  };
688
689  /// \brief Returns the source of the given edge.
690  ///
691  /// The SourceMap gives back the source Node of the given edge.
692  /// \author Balazs Dezso
693  template <typename Graph>
694  class SourceMap {
695  public:
696    typedef typename Graph::Node Value;
697    typedef typename Graph::Edge Key;
698
699    /// \brief Constructor
700    ///
701    /// Constructor
702    /// \param _graph The graph that the map belongs to.
703    SourceMap(const Graph& _graph) : graph(_graph) {}
704
705    /// \brief The subscript operator.
706    ///
707    /// The subscript operator.
708    /// \param edge The edge
709    /// \return The source of the edge
710    Value operator[](const Key& edge) {
711      return graph.source(edge);
712    }
713
714  private:
715    const Graph& graph;
716  };
717
718  /// \brief Returns a \ref SourceMap class
719  ///
720  /// This function just returns an \ref SourceMap class.
721  /// \relates SourceMap
722  template <typename Graph>
723  inline SourceMap<Graph> sourceMap(const Graph& graph) {
724    return SourceMap<Graph>(graph);
725  }
726
727  /// \brief Returns the target of the given edge.
728  ///
729  /// The TargetMap gives back the target Node of the given edge.
730  /// \author Balazs Dezso
731  template <typename Graph>
732  class TargetMap {
733  public:
734    typedef typename Graph::Node Value;
735    typedef typename Graph::Edge Key;
736
737    /// \brief Constructor
738    ///
739    /// Constructor
740    /// \param _graph The graph that the map belongs to.
741    TargetMap(const Graph& _graph) : graph(_graph) {}
742
743    /// \brief The subscript operator.
744    ///
745    /// The subscript operator.
746    /// \param edge The edge
747    /// \return The target of the edge
748    Value operator[](const Key& key) {
749      return graph.target(key);
750    }
751
752  private:
753    const Graph& graph;
754  };
755
756  /// \brief Returns a \ref TargetMap class
757
758  /// This function just returns an \ref TargetMap class.
759  /// \relates TargetMap
760  template <typename Graph>
761  inline TargetMap<Graph> targetMap(const Graph& graph) {
762    return TargetMap<Graph>(graph);
763  }
764
765
766  /// @}
767
768} //END OF NAMESPACE LEMON
769
770#endif
Note: See TracBrowser for help on using the repository browser.