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/dfs.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
22 ///\brief %DFS algorithm.
24 ///\todo Revise Manual.
26 #include <lemon/graph_utils.h>
27 #include <lemon/invalid.h>
31 /// \addtogroup flowalgs
34 ///%DFS algorithm class.
36 ///This class provides an efficient implementation of %DFS algorithm.
38 ///\param GR The graph type the algorithm runs on.
40 ///\author Alpar Juttner
43 template <typename GR>
45 template <typename GR>
49 ///The type of the underlying graph.
52 typedef typename Graph::Node Node;
54 typedef typename Graph::NodeIt NodeIt;
56 typedef typename Graph::Edge Edge;
58 typedef typename Graph::OutEdgeIt OutEdgeIt;
60 ///\brief The type of the map that stores the last
61 ///edges of the paths on the %DFS tree.
62 typedef typename Graph::template NodeMap<Edge> PredMap;
63 ///\brief The type of the map that stores the last but one
64 ///nodes of the paths on the %DFS tree.
65 typedef typename Graph::template NodeMap<Node> PredNodeMap;
66 ///The type of the map that stores the dists of the nodes on the %DFS tree.
67 typedef typename Graph::template NodeMap<int> DistMap;
70 /// Pointer to the underlying graph.
72 ///Pointer to the map of predecessors edges.
74 ///Indicates if \ref predecessor is locally allocated (\c true) or not.
75 bool local_predecessor;
76 ///Pointer to the map of predecessors nodes.
77 PredNodeMap *pred_node;
78 ///Indicates if \ref pred_node is locally allocated (\c true) or not.
80 ///Pointer to the map of distances.
82 ///Indicates if \ref distance is locally allocated (\c true) or not.
85 ///The source node of the last execution.
89 ///Initializes the maps.
93 local_predecessor = true;
94 predecessor = new PredMap(*G);
97 local_pred_node = true;
98 pred_node = new PredNodeMap(*G);
101 local_distance = true;
102 distance = new DistMap(*G);
109 ///\param _G the graph the algorithm will run on.
111 Dfs(const Graph& _G) :
113 predecessor(NULL), local_predecessor(false),
114 pred_node(NULL), local_pred_node(false),
115 distance(NULL), local_distance(false)
121 if(local_predecessor) delete predecessor;
122 if(local_pred_node) delete pred_node;
123 if(local_distance) delete distance;
126 ///Sets the map storing the predecessor edges.
128 ///Sets the map storing the predecessor edges.
129 ///If you don't use this function before calling \ref run(),
130 ///it will allocate one. The destuctor deallocates this
131 ///automatically allocated map, of course.
132 ///\return <tt> (*this) </tt>
133 Dfs &setPredMap(PredMap &m)
135 if(local_predecessor) {
137 local_predecessor=false;
143 ///Sets the map storing the predecessor nodes.
145 ///Sets the map storing the predecessor nodes.
146 ///If you don't use this function before calling \ref run(),
147 ///it will allocate one. The destuctor deallocates this
148 ///automatically allocated map, of course.
149 ///\return <tt> (*this) </tt>
150 Dfs &setPredNodeMap(PredNodeMap &m)
152 if(local_pred_node) {
154 local_pred_node=false;
160 ///Sets the map storing the distances calculated by the algorithm.
162 ///Sets the map storing the distances calculated by the algorithm.
163 ///If you don't use this function before calling \ref run(),
164 ///it will allocate one. The destuctor deallocates this
165 ///automatically allocated map, of course.
166 ///\return <tt> (*this) </tt>
167 Dfs &setDistMap(DistMap &m)
171 local_distance=false;
177 ///Runs %DFS algorithm from node \c s.
179 ///This method runs the %DFS algorithm from a root node \c s
183 ///- the distance of each node from the root on this tree.
191 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
192 predecessor->set(u,INVALID);
193 pred_node->set(u,INVALID);
196 int N = countNodes(*G);
197 std::vector<typename Graph::OutEdgeIt> Q(N);
201 Q[Qh] = OutEdgeIt(*G, s);
208 if((e=Q[Qh])!=INVALID)
209 if((m=G->target(e))!=s && (*predecessor)[m=G->target(e)]==INVALID) {
210 predecessor->set(m,e);
212 Q[++Qh] = OutEdgeIt(*G, m);
217 else if(--Qh>=0) n=G->source(Q[Qh]);
221 ///The distance of a node from the root on the %DFS tree.
223 ///Returns the distance of a node from the root on the %DFS tree.
224 ///\pre \ref run() must be called before using this function.
225 ///\warning If node \c v in unreachable from the root the return value
226 ///of this funcion is undefined.
227 int dist(Node v) const { return (*distance)[v]; }
229 ///Returns the 'previous edge' of the %DFS path tree.
231 ///For a node \c v it returns the last edge of the path on the %DFS tree
232 ///from the root to \c
233 ///v. It is \ref INVALID
234 ///if \c v is unreachable from the root or if \c v=s. The
235 ///%DFS tree used here is equal to the %DFS tree used in
236 ///\ref predNode(Node v). \pre \ref run() must be called before using
238 Edge pred(Node v) const { return (*predecessor)[v]; }
240 ///Returns the 'previous node' of the %DFS tree.
242 ///For a node \c v it returns the 'previous node' on the %DFS tree,
243 ///i.e. it returns the last but one node of the path from the
244 ///root to \c /v on the %DFS tree.
245 ///It is INVALID if \c v is unreachable from the root or if
247 ///\pre \ref run() must be called before
248 ///using this function.
249 Node predNode(Node v) const { return (*pred_node)[v]; }
251 ///Returns a reference to the NodeMap of distances on the %DFS tree.
253 ///Returns a reference to the NodeMap of distances on the %DFS tree.
254 ///\pre \ref run() must
255 ///be called before using this function.
256 const DistMap &distMap() const { return *distance;}
258 ///Returns a reference to the %DFS tree map.
260 ///Returns a reference to the NodeMap of the edges of the
262 ///\pre \ref run() must be called before using this function.
263 const PredMap &predMap() const { return *predecessor;}
265 ///Returns a reference to the map of last but one nodes of the %DFS tree.
267 ///Returns a reference to the NodeMap of the last but one nodes of the paths
270 ///\pre \ref run() must be called before using this function.
271 const PredNodeMap &predNodeMap() const { return *pred_node;}
273 ///Checks if a node is reachable from the root.
275 ///Returns \c true if \c v is reachable from the root.
276 ///\note The root node is reported to be reached!
278 ///\pre \ref run() must be called before using this function.
280 bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
286 } //END OF NAMESPACE LEMON