COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_utils.h @ 967:6563019430ba

Last change on this file since 967:6563019430ba was 967:6563019430ba, checked in by Alpar Juttner, 15 years ago

Several changes in doc.

File size: 6.0 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
24///\ingroup gutils
25///\file
26///\brief Graph utilities.
27///
28///\todo Please
29///revise the documentation.
30///
31
32
33namespace lemon {
34
35/// \addtogroup gutils
36/// @{
37
38  // counters in the graph
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  /// \brief Function to count the nodes in the graph.
55  ///
56  /// This function counts the nodes in the graph.
57  /// The complexity of the function is O(n) but for some
58  /// graph structure it is specialized to run in O(1).
59
60  template <typename Graph>
61  inline int countNodes(const Graph& _g) {
62    return countItems<Graph, typename Graph::NodeIt>(_g);
63  }
64
65  /// \brief Function to count the edges in the graph.
66  ///
67  /// This function counts the edges in the graph.
68  /// The complexity of the function is O(e) but for some
69  /// graph structure it is specialized to run in O(1).
70  template <typename Graph>
71  inline int countEdges(const Graph& _g) {
72    return countItems<Graph, typename Graph::EdgeIt>(_g);
73  }
74
75  /// \brief Function to count the symmetric edges in the graph.
76  ///
77  /// This function counts the symmetric edges in the graph.
78  /// The complexity of the function is O(e) but for some
79  /// graph structure it is specialized to run in O(1).
80  template <typename Graph>
81  inline int countSymEdges(const Graph& _g) {
82    return countItems<Graph, typename Graph::SymEdgeIt>(_g);
83  }
84
85  template <typename Graph, typename DegIt>
86  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
87    int num = 0;
88    for (DegIt it(_g, _n); it != INVALID; ++it) {
89      ++num;
90    }
91    return num;
92  }
93
94  /// Finds an edge between two nodes of a graph.
95
96  /// Finds an edge from node \c u to node \c v in graph \c g.
97  ///
98  /// If \c prev is \ref INVALID (this is the default value), then
99  /// it finds the first edge from \c u to \c v. Otherwise it looks for
100  /// the next edge from \c u to \c v after \c prev.
101  /// \return The found edge or \ref INVALID if there is no such an edge.
102  ///
103  /// Thus you can iterate through each edge from \c u to \c v as it follows.
104  /// \code
105  /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
106  ///   ...
107  /// }
108  /// \endcode
109  /// \todo We may want to use the \ref concept::GraphBase "GraphBase"
110  /// interface here...
111  /// \bug Untested ...
112  template <typename Graph>
113  typename Graph::Edge findEdge(const Graph &g,
114                typename Graph::Node u, typename Graph::Node v,
115                typename Graph::Edge prev = INVALID)
116  {
117    typename Graph::OutEdgeIt e(g,prev);
118    if(prev==INVALID) g.first(e,u);
119    else ++e;
120    while(e!=INVALID && g.tail(e)!=v) ++e;
121    return e;
122  }
123 
124  ///\e
125
126  ///\todo Please document.
127  ///
128  template <typename Graph>
129  inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
130    return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
131  }
132
133  ///\e
134
135  ///\todo Please document.
136  ///
137  template <typename Graph>
138  inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
139    return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
140  }
141
142  // graph copy
143
144  template <
145    typename DestinationGraph,
146    typename SourceGraph,
147    typename NodeBijection>
148  void copyNodes(DestinationGraph& _d, const SourceGraph& _s,
149                 NodeBijection& _nb) {   
150    for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) {
151      _nb[it] = _d.addNode();
152    }
153  }
154
155  template <
156    typename DestinationGraph,
157    typename SourceGraph,
158    typename NodeBijection,
159    typename EdgeBijection>
160  void copyEdges(DestinationGraph& _d, const SourceGraph& _s,
161                 const NodeBijection& _nb, EdgeBijection& _eb) {   
162    for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) {
163      _eb[it] = _d.addEdge(_nb[_s.tail(it)], _nb[_s.head(it)]);
164    }
165  }
166
167  template <
168    typename DestinationGraph,
169    typename SourceGraph,
170    typename NodeBijection,
171    typename EdgeBijection>
172  void copyGraph(DestinationGraph& _d, const SourceGraph& _s,
173                 NodeBijection& _nb, EdgeBijection& _eb) {
174    nodeCopy(_d, _s, _nb);
175    edgeCopy(_d, _s, _nb, _eb);
176  }
177 
178   template <
179    typename _DestinationGraph,
180    typename _SourceGraph,
181    typename _NodeBijection
182    =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>,
183    typename _EdgeBijection
184    =typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>
185   >
186   class GraphCopy {
187   public:
188
189     typedef _DestinationGraph DestinationGraph;
190     typedef _SourceGraph SourceGraph;
191
192     typedef _NodeBijection NodeBijection;
193     typedef _EdgeBijection EdgeBijection;
194
195   protected:         
196
197     NodeBijection node_bijection;
198     EdgeBijection edge_bijection;     
199
200   public:
201     
202     GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
203       copyGraph(_d, _s, node_bijection, edge_bijection);
204     }
205
206     const NodeBijection& getNodeBijection() const {
207       return node_bijection;
208     }
209
210     const EdgeBijection& getEdgeBijection() const {
211       return edge_bijection;
212     }
213     
214   };
215
216/// @}
217 
218} //END OF NAMESPACE LEMON
219
220#endif
Note: See TracBrowser for help on using the repository browser.