# source:lemon-0.x/src/lemon/graph_utils.h@1311:b810a07248a0

Last change on this file since 1311:b810a07248a0 was 1267:a93f94dbe3d3, checked in by Balazs Dezso, 15 years ago

First version of iterable maps.

File size: 8.7 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
25///\ingroup gutils
26///\file
27///\brief Graph utilities.
28///
30///revise the documentation.
31///
32
33
34namespace lemon {
35
37  /// @{
38
39  /// \brief Function to count the items in the graph.
40  ///
41  /// This function counts the items in the graph.
42  /// The complexity of the function is O(n) because
43  /// it iterates on all of the items.
44
45  template <typename Graph, typename ItemIt>
46  inline int countItems(const Graph& g) {
47    int num = 0;
48    for (ItemIt it(g); it != INVALID; ++it) {
49      ++num;
50    }
51    return num;
52  }
53
54  // Node counting:
55
56  template <typename Graph>
57  inline
58  typename enable_if<typename Graph::NodeNumTag, int>::type
59  _countNodes(const Graph &g) {
60    return g.nodeNum();
61  }
62
63  template <typename Graph>
64  inline int _countNodes(Wrap<Graph> w) {
65    return countItems<Graph, typename Graph::NodeIt>(w.value);
66  }
67
68  /// \brief Function to count the nodes in the graph.
69  ///
70  /// This function counts the nodes in the graph.
71  /// The complexity of the function is O(n) but for some
72  /// graph structure it is specialized to run in O(1).
73  ///
74  /// \todo refer how to specialize it
75
76  template <typename Graph>
77  inline int countNodes(const Graph& g) {
78    return _countNodes<Graph>(g);
79  }
80
81  // Edge counting:
82
83  template <typename Graph>
84  inline
85  typename enable_if<typename Graph::EdgeNumTag, int>::type
86  _countEdges(const Graph &g) {
87    return g.edgeNum();
88  }
89
90  template <typename Graph>
91  inline int _countEdges(Wrap<Graph> w) {
92    return countItems<Graph, typename Graph::EdgeIt>(w.value);
93  }
94
95  /// \brief Function to count the edges in the graph.
96  ///
97  /// This function counts the edges in the graph.
98  /// The complexity of the function is O(e) but for some
99  /// graph structure it is specialized to run in O(1).
100
101  template <typename Graph>
102  inline int countEdges(const Graph& g) {
103    return _countEdges<Graph>(g);
104  }
105
106  // Undirected edge counting:
107
108  template <typename Graph>
109  inline
110  typename enable_if<typename Graph::EdgeNumTag, int>::type
111  _countUndirEdges(const Graph &g) {
112    return g.undirEdgeNum();
113  }
114
115  template <typename Graph>
116  inline int _countUndirEdges(Wrap<Graph> w) {
117    return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
118  }
119
120  /// \brief Function to count the edges in the graph.
121  ///
122  /// This function counts the edges in the graph.
123  /// The complexity of the function is O(e) but for some
124  /// graph structure it is specialized to run in O(1).
125
126  template <typename Graph>
127  inline int countUndirEdges(const Graph& g) {
128    return _countUndirEdges<Graph>(g);
129  }
130
131
132
133  template <typename Graph, typename DegIt>
134  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
135    int num = 0;
136    for (DegIt it(_g, _n); it != INVALID; ++it) {
137      ++num;
138    }
139    return num;
140  }
141
142  /// Finds an edge between two nodes of a graph.
143
144  /// Finds an edge from node \c u to node \c v in graph \c g.
145  ///
146  /// If \c prev is \ref INVALID (this is the default value), then
147  /// it finds the first edge from \c u to \c v. Otherwise it looks for
148  /// the next edge from \c u to \c v after \c prev.
149  /// \return The found edge or \ref INVALID if there is no such an edge.
150  ///
151  /// Thus you can iterate through each edge from \c u to \c v as it follows.
152  /// \code
153  /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
154  ///   ...
155  /// }
156  /// \endcode
157  /// \todo We may want to use the \ref concept::GraphBase "GraphBase"
158  /// interface here...
159  /// \bug Untested ...
160  template <typename Graph>
161  typename Graph::Edge findEdge(const Graph &g,
162                                typename Graph::Node u, typename Graph::Node v,
163                                typename Graph::Edge prev = INVALID)
164  {
165    typename Graph::OutEdgeIt e(g,prev);
166    //    if(prev==INVALID) g.first(e,u);
167    if(prev==INVALID) e=typename Graph::OutEdgeIt(g,u);
168    else ++e;
169    while(e!=INVALID && g.target(e)!=v) ++e;
170    return e;
171  }
172
173  ///\e
174
176  ///
177  template <typename Graph>
178  inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
179    return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
180  }
181
182  ///\e
183
185  ///
186  template <typename Graph>
187  inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
188    return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
189  }
190
191  // graph copy
192
193  template <
194    typename DestinationGraph,
195    typename SourceGraph,
196    typename NodeBijection>
197  void copyNodes(DestinationGraph& _d, const SourceGraph& _s,
198                 NodeBijection& _nb) {
199    for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) {
201    }
202  }
203
204  template <
205    typename DestinationGraph,
206    typename SourceGraph,
207    typename NodeBijection,
208    typename EdgeBijection>
209  void copyEdges(DestinationGraph& _d, const SourceGraph& _s,
210                 const NodeBijection& _nb, EdgeBijection& _eb) {
211    for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) {
213    }
214  }
215
216  template <
217    typename DestinationGraph,
218    typename SourceGraph,
219    typename NodeBijection,
220    typename EdgeBijection>
221  void copyGraph(DestinationGraph& _d, const SourceGraph& _s,
222                 NodeBijection& _nb, EdgeBijection& _eb) {
223    nodeCopy(_d, _s, _nb);
224    edgeCopy(_d, _s, _nb, _eb);
225  }
226
227  template <
228    typename _DestinationGraph,
229    typename _SourceGraph,
230    typename _NodeBijection
231    =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>,
232    typename _EdgeBijection
233    = typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>
234  >
235  class GraphCopy {
236  public:
237
238    typedef _DestinationGraph DestinationGraph;
239    typedef _SourceGraph SourceGraph;
240
241    typedef _NodeBijection NodeBijection;
242    typedef _EdgeBijection EdgeBijection;
243
244  protected:
245
246    NodeBijection node_bijection;
247    EdgeBijection edge_bijection;
248
249  public:
250
251    GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
252      copyGraph(_d, _s, node_bijection, edge_bijection);
253    }
254
255    const NodeBijection& getNodeBijection() const {
256      return node_bijection;
257    }
258
259    const EdgeBijection& getEdgeBijection() const {
260      return edge_bijection;
261    }
262
263  };
264
265
266  template <typename _Graph, typename _Item>
267  class ItemSetTraits {
268  };
269
270  template <typename _Graph>
271  class ItemSetTraits<_Graph, typename _Graph::Node> {
272  public:
273
274    typedef _Graph Graph;
275
276    typedef typename Graph::Node Item;
277    typedef typename Graph::NodeIt ItemIt;
278
279    template <typename _Value>
280    class Map : public Graph::template NodeMap<_Value> {
281    public:
282      typedef typename Graph::template NodeMap<_Value> Parent;
283      typedef typename Parent::Value Value;
284
285      Map(const Graph& _graph) : Parent(_graph) {}
286      Map(const Graph& _graph, const Value& _value)
287        : Parent(_graph, _value) {}
288    };
289
290  };
291
292  template <typename _Graph>
293  class ItemSetTraits<_Graph, typename _Graph::Edge> {
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  };
313
314  template <typename _Graph>
315  class ItemSetTraits<_Graph, typename _Graph::UndirEdge> {
316  public:
317
318    typedef _Graph Graph;
319
320    typedef typename Graph::UndirEdge Item;
321    typedef typename Graph::UndirEdgeIt ItemIt;
322
323    template <typename _Value>
324    class Map : public Graph::template UndirEdgeMap<_Value> {
325    public:
326      typedef typename Graph::template UndirEdgeMap<_Value> Parent;
327      typedef typename Parent::Value Value;
328
329      Map(const Graph& _graph) : Parent(_graph) {}
330      Map(const Graph& _graph, const Value& _value)
331        : Parent(_graph, _value) {}
332    };
333
334  };
335
336  /// @}
337
338} //END OF NAMESPACE LEMON
339
340#endif
Note: See TracBrowser for help on using the repository browser.