graphwrapper dox. everybody is asked to read doxygen.log
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>
27 ///\brief Graph utilities.
30 ///revise the documentation.
36 /// \addtogroup gutils
39 /// \brief Function to count the items in the graph.
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.
45 template <typename Graph, typename ItemIt>
46 inline int countItems(const Graph& g) {
48 for (ItemIt it(g); it != INVALID; ++it) {
56 template <typename Graph>
58 typename enable_if<typename Graph::NodeNumTag, int>::type
59 _countNodes(const Graph &g) {
63 template <typename Graph>
64 inline int _countNodes(Wrap<Graph> w) {
65 return countItems<Graph, typename Graph::NodeIt>(w.value);
68 /// \brief Function to count the nodes in the graph.
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).
74 /// \todo refer how to specialize it
76 template <typename Graph>
77 inline int countNodes(const Graph& g) {
78 return _countNodes<Graph>(g);
83 template <typename Graph>
85 typename enable_if<typename Graph::EdgeNumTag, int>::type
86 _countEdges(const Graph &g) {
90 template <typename Graph>
91 inline int _countEdges(Wrap<Graph> w) {
92 return countItems<Graph, typename Graph::EdgeIt>(w.value);
95 /// \brief Function to count the edges in the graph.
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).
101 template <typename Graph>
102 inline int countEdges(const Graph& g) {
103 return _countEdges<Graph>(g);
106 // Undirected edge counting:
108 template <typename Graph>
110 typename enable_if<typename Graph::EdgeNumTag, int>::type
111 _countUndirEdges(const Graph &g) {
112 return g.undirEdgeNum();
115 template <typename Graph>
116 inline int _countUndirEdges(Wrap<Graph> w) {
117 return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
120 /// \brief Function to count the edges in the graph.
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).
126 template <typename Graph>
127 inline int countUndirEdges(const Graph& g) {
128 return _countUndirEdges<Graph>(g);
133 template <typename Graph, typename DegIt>
134 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
136 for (DegIt it(_g, _n); it != INVALID; ++it) {
142 /// Finds an edge between two nodes of a graph.
144 /// Finds an edge from node \c u to node \c v in graph \c g.
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.
151 /// Thus you can iterate through each edge from \c u to \c v as it follows.
153 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
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)
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);
169 while(e!=INVALID && g.target(e)!=v) ++e;
175 ///\todo Please document.
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);
184 ///\todo Please document.
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);
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) {
200 _nb[it] = _d.addNode();
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) {
212 _eb[it] = _d.addEdge(_nb[_s.source(it)], _nb[_s.target(it)]);
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);
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>
238 typedef _DestinationGraph DestinationGraph;
239 typedef _SourceGraph SourceGraph;
241 typedef _NodeBijection NodeBijection;
242 typedef _EdgeBijection EdgeBijection;
246 NodeBijection node_bijection;
247 EdgeBijection edge_bijection;
251 GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
252 copyGraph(_d, _s, node_bijection, edge_bijection);
255 const NodeBijection& getNodeBijection() const {
256 return node_bijection;
259 const EdgeBijection& getEdgeBijection() const {
260 return edge_bijection;
267 } //END OF NAMESPACE LEMON