Changing exception names.
Compile sentry fix.
2 * src/lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
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.
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
17 #ifndef LEMON_GRAPH_UTILS_H
18 #define LEMON_GRAPH_UTILS_H
22 #include <lemon/invalid.h>
23 #include <lemon/utility.h>
24 #include <lemon/map_utils.h>
28 ///\brief Graph utilities.
31 ///revise the documentation.
37 /// \addtogroup gutils
40 /// \brief Function to count the items in the graph.
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.
46 template <typename Graph, typename ItemIt>
47 inline int countItems(const Graph& g) {
49 for (ItemIt it(g); it != INVALID; ++it) {
57 template <typename Graph>
59 typename enable_if<typename Graph::NodeNumTag, int>::type
60 _countNodes(const Graph &g) {
64 template <typename Graph>
65 inline int _countNodes(Wrap<Graph> w) {
66 return countItems<Graph, typename Graph::NodeIt>(w.value);
69 /// \brief Function to count the nodes in the graph.
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).
75 /// \todo refer how to specialize it
77 template <typename Graph>
78 inline int countNodes(const Graph& g) {
79 return _countNodes<Graph>(g);
84 template <typename Graph>
86 typename enable_if<typename Graph::EdgeNumTag, int>::type
87 _countEdges(const Graph &g) {
91 template <typename Graph>
92 inline int _countEdges(Wrap<Graph> w) {
93 return countItems<Graph, typename Graph::EdgeIt>(w.value);
96 /// \brief Function to count the edges in the graph.
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).
102 template <typename Graph>
103 inline int countEdges(const Graph& g) {
104 return _countEdges<Graph>(g);
107 // Undirected edge counting:
109 template <typename Graph>
111 typename enable_if<typename Graph::EdgeNumTag, int>::type
112 _countUndirEdges(const Graph &g) {
113 return g.undirEdgeNum();
116 template <typename Graph>
117 inline int _countUndirEdges(Wrap<Graph> w) {
118 return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
121 /// \brief Function to count the edges in the graph.
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).
127 template <typename Graph>
128 inline int countUndirEdges(const Graph& g) {
129 return _countUndirEdges<Graph>(g);
134 template <typename Graph, typename DegIt>
135 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
137 for (DegIt it(_g, _n); it != INVALID; ++it) {
143 /// Finds an edge between two nodes of a graph.
145 /// Finds an edge from node \c u to node \c v in graph \c g.
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.
152 /// Thus you can iterate through each edge from \c u to \c v as it follows.
154 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
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)
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);
170 while(e!=INVALID && g.target(e)!=v) ++e;
176 ///\todo Please document.
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);
185 ///\todo Please document.
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);
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();
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)]);
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);
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>
239 typedef _DestinationGraph DestinationGraph;
240 typedef _SourceGraph SourceGraph;
242 typedef _NodeBijection NodeBijection;
243 typedef _EdgeBijection EdgeBijection;
247 NodeBijection node_bijection;
248 EdgeBijection edge_bijection;
252 GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
253 copyGraph(_d, _s, node_bijection, edge_bijection);
256 const NodeBijection& getNodeBijection() const {
257 return node_bijection;
260 const EdgeBijection& getEdgeBijection() const {
261 return edge_bijection;
266 template <typename _Graph>
270 typedef _Graph Graph;
272 typedef typename Graph::Node Item;
273 typedef typename Graph::NodeIt ItemIt;
275 template <typename _Value>
276 class Map : public Graph::template NodeMap<_Value> {
278 typedef typename Graph::template NodeMap<_Value> Parent;
279 typedef typename Parent::Value Value;
281 Map(const Graph& _graph) : Parent(_graph) {}
282 Map(const Graph& _graph, const Value& _value)
283 : Parent(_graph, _value) {}
286 typedef IdMap<Graph, Item> IdMap;
292 template <typename _Graph>
296 typedef _Graph Graph;
298 typedef typename Graph::Edge Item;
299 typedef typename Graph::EdgeIt ItemIt;
301 template <typename _Value>
302 class Map : public Graph::template EdgeMap<_Value> {
304 typedef typename Graph::template EdgeMap<_Value> Parent;
305 typedef typename Parent::Value Value;
307 Map(const Graph& _graph) : Parent(_graph) {}
308 Map(const Graph& _graph, const Value& _value)
309 : Parent(_graph, _value) {}
312 typedef IdMap<Graph, Item> IdMap;
321 } //END OF NAMESPACE LEMON