graph_to_eps mission accomplished.
- lemon/graph_to_eps.h header created
- lemon/bezier.h: Tools to compute with bezier curves (unclean and undocumented
interface, used internally by graph_to_eps.h)
- demo/graph_to_eps_demo.cc: a simple demo for lemon/graph_to_eps.h
2 * src/lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2004 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);
168 while(e!=INVALID && g.source(e)!=v) ++e;
174 ///\todo Please document.
176 template <typename Graph>
177 inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) {
178 return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
183 ///\todo Please document.
185 template <typename Graph>
186 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) {
187 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
193 typename DestinationGraph,
194 typename SourceGraph,
195 typename NodeBijection>
196 void copyNodes(DestinationGraph& _d, const SourceGraph& _s,
197 NodeBijection& _nb) {
198 for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) {
199 _nb[it] = _d.addNode();
204 typename DestinationGraph,
205 typename SourceGraph,
206 typename NodeBijection,
207 typename EdgeBijection>
208 void copyEdges(DestinationGraph& _d, const SourceGraph& _s,
209 const NodeBijection& _nb, EdgeBijection& _eb) {
210 for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) {
211 _eb[it] = _d.addEdge(_nb[_s.source(it)], _nb[_s.target(it)]);
216 typename DestinationGraph,
217 typename SourceGraph,
218 typename NodeBijection,
219 typename EdgeBijection>
220 void copyGraph(DestinationGraph& _d, const SourceGraph& _s,
221 NodeBijection& _nb, EdgeBijection& _eb) {
222 nodeCopy(_d, _s, _nb);
223 edgeCopy(_d, _s, _nb, _eb);
227 typename _DestinationGraph,
228 typename _SourceGraph,
229 typename _NodeBijection
230 =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>,
231 typename _EdgeBijection
232 =typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>
237 typedef _DestinationGraph DestinationGraph;
238 typedef _SourceGraph SourceGraph;
240 typedef _NodeBijection NodeBijection;
241 typedef _EdgeBijection EdgeBijection;
245 NodeBijection node_bijection;
246 EdgeBijection edge_bijection;
250 GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
251 copyGraph(_d, _s, node_bijection, edge_bijection);
254 const NodeBijection& getNodeBijection() const {
255 return node_bijection;
258 const EdgeBijection& getEdgeBijection() const {
259 return edge_bijection;
266 } //END OF NAMESPACE LEMON