COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_utils.h @ 1402:655d8e78454d

Last change on this file since 1402:655d8e78454d was 1402:655d8e78454d, checked in by Alpar Juttner, 16 years ago

Special maps' placement in the headers and in the doxigen modules
reorganized

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