COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_utils.h @ 986:e997802b855c

Last change on this file since 986:e997802b855c was 986:e997802b855c, checked in by Alpar Juttner, 19 years ago

Naming changes:

  • head -> target
  • tail -> source
File size: 6.6 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 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///
29///\todo Please
30///revise the documentation.
31///
32
33
34namespace lemon {
35
36/// \addtogroup gutils
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  /// \brief Function to count the symmetric edges in the graph.
107  ///
108  /// This function counts the symmetric edges in the graph.
109  /// The complexity of the function is O(e) but for some
110  /// graph structure it is specialized to run in O(1).
111  template <typename Graph>
112  inline int countSymEdges(const Graph& _g) {
113    return countItems<Graph, typename Graph::SymEdgeIt>(_g);
114  }
115
116
117  template <typename Graph, typename DegIt>
118  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
119    int num = 0;
120    for (DegIt it(_g, _n); it != INVALID; ++it) {
121      ++num;
122    }
123    return num;
124  }
125
126  /// Finds an edge between two nodes of a graph.
127
128  /// Finds an edge from node \c u to node \c v in graph \c g.
129  ///
130  /// If \c prev is \ref INVALID (this is the default value), then
131  /// it finds the first edge from \c u to \c v. Otherwise it looks for
132  /// the next edge from \c u to \c v after \c prev.
133  /// \return The found edge or \ref INVALID if there is no such an edge.
134  ///
135  /// Thus you can iterate through each edge from \c u to \c v as it follows.
136  /// \code
137  /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
138  ///   ...
139  /// }
140  /// \endcode
141  /// \todo We may want to use the \ref concept::GraphBase "GraphBase"
142  /// interface here...
143  /// \bug Untested ...
144  template <typename Graph>
145  typename Graph::Edge findEdge(const Graph &g,
146                typename Graph::Node u, typename Graph::Node v,
147                typename Graph::Edge prev = INVALID)
148  {
149    typename Graph::OutEdgeIt e(g,prev);
150    if(prev==INVALID) g.first(e,u);
151    else ++e;
152    while(e!=INVALID && g.source(e)!=v) ++e;
153    return e;
154  }
155 
156  ///\e
157
158  ///\todo Please document.
159  ///
160  template <typename Graph>
161  inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
162    return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
163  }
164
165  ///\e
166
167  ///\todo Please document.
168  ///
169  template <typename Graph>
170  inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
171    return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
172  }
173
174  // graph copy
175
176  template <
177    typename DestinationGraph,
178    typename SourceGraph,
179    typename NodeBijection>
180  void copyNodes(DestinationGraph& _d, const SourceGraph& _s,
181                 NodeBijection& _nb) {   
182    for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) {
183      _nb[it] = _d.addNode();
184    }
185  }
186
187  template <
188    typename DestinationGraph,
189    typename SourceGraph,
190    typename NodeBijection,
191    typename EdgeBijection>
192  void copyEdges(DestinationGraph& _d, const SourceGraph& _s,
193                 const NodeBijection& _nb, EdgeBijection& _eb) {   
194    for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) {
195      _eb[it] = _d.addEdge(_nb[_s.source(it)], _nb[_s.target(it)]);
196    }
197  }
198
199  template <
200    typename DestinationGraph,
201    typename SourceGraph,
202    typename NodeBijection,
203    typename EdgeBijection>
204  void copyGraph(DestinationGraph& _d, const SourceGraph& _s,
205                 NodeBijection& _nb, EdgeBijection& _eb) {
206    nodeCopy(_d, _s, _nb);
207    edgeCopy(_d, _s, _nb, _eb);
208  }
209 
210   template <
211    typename _DestinationGraph,
212    typename _SourceGraph,
213    typename _NodeBijection
214    =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>,
215    typename _EdgeBijection
216    =typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>
217   >
218   class GraphCopy {
219   public:
220
221     typedef _DestinationGraph DestinationGraph;
222     typedef _SourceGraph SourceGraph;
223
224     typedef _NodeBijection NodeBijection;
225     typedef _EdgeBijection EdgeBijection;
226
227   protected:         
228
229     NodeBijection node_bijection;
230     EdgeBijection edge_bijection;     
231
232   public:
233     
234     GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
235       copyGraph(_d, _s, node_bijection, edge_bijection);
236     }
237
238     const NodeBijection& getNodeBijection() const {
239       return node_bijection;
240     }
241
242     const EdgeBijection& getEdgeBijection() const {
243       return edge_bijection;
244     }
245     
246   };
247
248/// @}
249 
250} //END OF NAMESPACE LEMON
251
252#endif
Note: See TracBrowser for help on using the repository browser.