COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_utils.h @ 1192:aa4483befa56

Last change on this file since 1192:aa4483befa56 was 1192:aa4483befa56, checked in by Balazs Dezso, 15 years ago

Adding GraphEdgeSet? and GraphNodeSet? classes to graph_utils.h.

File size: 8.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 Combinatorial Optimization Research Group, 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
22#include <lemon/invalid.h>
23#include <lemon/utility.h>
24#include <lemon/map_utils.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  template <typename _Graph>
267  class GraphNodeSet {
268  public:
269   
270    typedef _Graph Graph;
271
272    typedef typename Graph::Node Item;
273    typedef typename Graph::NodeIt ItemIt;
274
275    template <typename _Value>
276    class Map : public Graph::template NodeMap<_Value> {
277    public:
278      typedef typename Graph::template NodeMap<_Value> Parent;
279      typedef typename Parent::Value Value;
280
281      Map(const Graph& _graph) : Parent(_graph) {}
282      Map(const Graph& _graph, const Value& _value)
283        : Parent(_graph, _value) {}
284    };
285
286    typedef IdMap<Graph, Item> IdMap;
287   
288  private:
289    Graph* graph;
290  };
291
292  template <typename _Graph>
293  class GraphEdgeSet {
294  public:
295   
296    typedef _Graph Graph;
297
298    typedef typename Graph::Edge Item;
299    typedef typename Graph::EdgeIt ItemIt;
300
301    template <typename _Value>
302    class Map : public Graph::template EdgeMap<_Value> {
303    public:
304      typedef typename Graph::template EdgeMap<_Value> Parent;
305      typedef typename Parent::Value Value;
306
307      Map(const Graph& _graph) : Parent(_graph) {}
308      Map(const Graph& _graph, const Value& _value)
309        : Parent(_graph, _value) {}
310    };
311
312    typedef IdMap<Graph, Item> IdMap;
313   
314  private:
315    Graph* graph;
316  };
317
318
319  /// @}
320 
321} //END OF NAMESPACE LEMON
322
323#endif
Note: See TracBrowser for help on using the repository browser.