1.1 --- a/lemon/Makefile.am Thu Jan 26 17:18:12 2006 +0000
1.2 +++ b/lemon/Makefile.am Fri Jan 27 08:17:25 2006 +0000
1.3 @@ -30,10 +30,12 @@
1.4 counter.h \
1.5 dijkstra.h \
1.6 dimacs.h \
1.7 + dag_shortest_path.h \
1.8 edge_set.h \
1.9 error.h \
1.10 fib_heap.h \
1.11 floyd_warshall.h \
1.12 + fredman_tarjan.h \
1.13 full_graph.h \
1.14 grid_graph.h \
1.15 graph_adaptor.h \
1.16 @@ -59,6 +61,7 @@
1.17 suurballe.h \
1.18 preflow.h \
1.19 path.h \
1.20 + prim.h \
1.21 radix_heap.h \
1.22 radix_sort.h \
1.23 smart_graph.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/dag_shortest_path.h Fri Jan 27 08:17:25 2006 +0000
2.3 @@ -0,0 +1,1082 @@
2.4 +/* -*- C++ -*-
2.5 + * lemon/dag_shortest_path.h - Part of LEMON, a generic C++ optimization library
2.6 + *
2.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.9 + *
2.10 + * Permission to use, modify and distribute this software is granted
2.11 + * provided that this copyright notice appears in all copies. For
2.12 + * precise terms see the accompanying LICENSE file.
2.13 + *
2.14 + * This software is provided "AS IS" with no warranty of any kind,
2.15 + * express or implied, and with no claim as to its suitability for any
2.16 + * purpose.
2.17 + *
2.18 + */
2.19 +
2.20 +#ifndef LEMON_DAG_SHORTEST_PATH_H
2.21 +#define LEMON_DAG_SHORTEST_PATH_H
2.22 +
2.23 +///\ingroup flowalgs
2.24 +/// \file
2.25 +/// \brief DagShortestPath algorithm.
2.26 +///
2.27 +
2.28 +#include <lemon/list_graph.h>
2.29 +#include <lemon/invalid.h>
2.30 +#include <lemon/error.h>
2.31 +#include <lemon/maps.h>
2.32 +#include <lemon/topology.h>
2.33 +
2.34 +#include <limits>
2.35 +
2.36 +namespace lemon {
2.37 +
2.38 + /// \brief Default OperationTraits for the DagShortestPath algorithm class.
2.39 + ///
2.40 + /// It defines all computational operations and constants which are
2.41 + /// used in the dag shortest path algorithm. The default implementation
2.42 + /// is based on the numeric_limits class. If the numeric type does not
2.43 + /// have infinity value then the maximum value is used as extremal
2.44 + /// infinity value.
2.45 + template <
2.46 + typename Value,
2.47 + bool has_infinity = std::numeric_limits<Value>::has_infinity>
2.48 + struct DagShortestPathDefaultOperationTraits {
2.49 + /// \brief Gives back the zero value of the type.
2.50 + static Value zero() {
2.51 + return static_cast<Value>(0);
2.52 + }
2.53 + /// \brief Gives back the positive infinity value of the type.
2.54 + static Value infinity() {
2.55 + return std::numeric_limits<Value>::infinity();
2.56 + }
2.57 + /// \brief Gives back the sum of the given two elements.
2.58 + static Value plus(const Value& left, const Value& right) {
2.59 + return left + right;
2.60 + }
2.61 + /// \brief Gives back true only if the first value less than the second.
2.62 + static bool less(const Value& left, const Value& right) {
2.63 + return left < right;
2.64 + }
2.65 + };
2.66 +
2.67 + template <typename Value>
2.68 + struct DagShortestPathDefaultOperationTraits<Value, false> {
2.69 + static Value zero() {
2.70 + return static_cast<Value>(0);
2.71 + }
2.72 + static Value infinity() {
2.73 + return std::numeric_limits<Value>::max();
2.74 + }
2.75 + static Value plus(const Value& left, const Value& right) {
2.76 + if (left == infinity() || right == infinity()) return infinity();
2.77 + return left + right;
2.78 + }
2.79 + static bool less(const Value& left, const Value& right) {
2.80 + return left < right;
2.81 + }
2.82 + };
2.83 +
2.84 + /// \brief Default traits class of DagShortestPath class.
2.85 + ///
2.86 + /// Default traits class of DagShortestPath class.
2.87 + /// \param _Graph Graph type.
2.88 + /// \param _LegthMap Type of length map.
2.89 + template<class _Graph, class _LengthMap>
2.90 + struct DagShortestPathDefaultTraits {
2.91 + /// The graph type the algorithm runs on.
2.92 + typedef _Graph Graph;
2.93 +
2.94 + /// \brief The type of the map that stores the edge lengths.
2.95 + ///
2.96 + /// The type of the map that stores the edge lengths.
2.97 + /// It must meet the \ref concept::ReadMap "ReadMap" concept.
2.98 + typedef _LengthMap LengthMap;
2.99 +
2.100 + // The type of the length of the edges.
2.101 + typedef typename _LengthMap::Value Value;
2.102 +
2.103 + /// \brief Operation traits for dag shortest path algorithm.
2.104 + ///
2.105 + /// It defines the infinity type on the given Value type
2.106 + /// and the used operation.
2.107 + /// \see DagShortestPathDefaultOperationTraits
2.108 + typedef DagShortestPathDefaultOperationTraits<Value> OperationTraits;
2.109 +
2.110 + /// \brief The type of the map that stores the last edges of the
2.111 + /// shortest paths.
2.112 + ///
2.113 + /// The type of the map that stores the last
2.114 + /// edges of the shortest paths.
2.115 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
2.116 + ///
2.117 + typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap;
2.118 +
2.119 + /// \brief Instantiates a PredMap.
2.120 + ///
2.121 + /// This function instantiates a \ref PredMap.
2.122 + /// \param G is the graph, to which we would like to define the PredMap.
2.123 + /// \todo The graph alone may be insufficient for the initialization
2.124 + static PredMap *createPredMap(const _Graph& graph) {
2.125 + return new PredMap(graph);
2.126 + }
2.127 +
2.128 + /// \brief The type of the map that stores the dists of the nodes.
2.129 + ///
2.130 + /// The type of the map that stores the dists of the nodes.
2.131 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
2.132 + ///
2.133 + typedef typename Graph::template NodeMap<typename _LengthMap::Value>
2.134 + DistMap;
2.135 +
2.136 + /// \brief Instantiates a DistMap.
2.137 + ///
2.138 + /// This function instantiates a \ref DistMap.
2.139 + /// \param G is the graph, to which we would like to define the
2.140 + /// \ref DistMap
2.141 + static DistMap *createDistMap(const _Graph& graph) {
2.142 + return new DistMap(graph);
2.143 + }
2.144 +
2.145 + };
2.146 +
2.147 + /// \brief Inverse OperationTraits for the DagShortestPath algorithm class.
2.148 + ///
2.149 + /// It defines all computational operations and constants which are
2.150 + /// used in the dag shortest path algorithm. It is the inverse of
2.151 + /// \ref DagShortestPathDefaultOperationTraits, so it can be used to
2.152 + /// calculate the longest path. The default implementation
2.153 + /// is based on the numeric_limits class. If the numeric type does not
2.154 + /// have infinity value then the minimum value is used as extremal
2.155 + /// infinity value.
2.156 + template <
2.157 + typename Value,
2.158 + bool has_infinity = std::numeric_limits<Value>::has_infinity>
2.159 + struct DagLongestPathOperationTraits {
2.160 + /// \brief Gives back the zero value of the type.
2.161 + static Value zero() {
2.162 + return static_cast<Value>(0);
2.163 + }
2.164 + /// \brief Gives back the negative infinity value of the type.
2.165 + static Value infinity() {
2.166 + return -(std::numeric_limits<Value>::infinity());
2.167 + }
2.168 + /// \brief Gives back the sum of the given two elements.
2.169 + static Value plus(const Value& left, const Value& right) {
2.170 + return left + right;
2.171 + }
2.172 + /// \brief Gives back true only if the first value less than the second.
2.173 + static bool less(const Value& left, const Value& right) {
2.174 + return left > right;
2.175 + }
2.176 + };
2.177 +
2.178 + template <typename Value>
2.179 + struct DagLongestPathOperationTraits<Value, false> {
2.180 + static Value zero() {
2.181 + return static_cast<Value>(0);
2.182 + }
2.183 + static Value infinity() {
2.184 + return std::numeric_limits<Value>::min();
2.185 + }
2.186 + static Value plus(const Value& left, const Value& right) {
2.187 + if (left == infinity() || right == infinity()) return infinity();
2.188 + return left + right;
2.189 + }
2.190 + static bool less(const Value& left, const Value& right) {
2.191 + return left > right;
2.192 + }
2.193 + };
2.194 +
2.195 + /// \brief Inverse traits class of DagShortestPath class.
2.196 + ///
2.197 + /// Inverse traits class of DagShortestPath class.
2.198 + /// \param _Graph Graph type.
2.199 + /// \param _LegthMap Type of length map.
2.200 + template<class _Graph, class _LengthMap>
2.201 + struct DagLongestPathTraits {
2.202 + /// The graph type the algorithm runs on.
2.203 + typedef _Graph Graph;
2.204 +
2.205 + /// \brief The type of the map that stores the edge lengths.
2.206 + ///
2.207 + /// The type of the map that stores the edge lengths.
2.208 + /// It must meet the \ref concept::ReadMap "ReadMap" concept.
2.209 + typedef _LengthMap LengthMap;
2.210 +
2.211 + // The type of the length of the edges.
2.212 + typedef typename _LengthMap::Value Value;
2.213 +
2.214 + /// \brief Inverse operation traits for dag shortest path algorithm.
2.215 + ///
2.216 + /// It defines the infinity type on the given Value type
2.217 + /// and the used operation.
2.218 + /// \see DagLongestPathOperationTraits
2.219 + typedef DagLongestPathOperationTraits<Value> OperationTraits;
2.220 +
2.221 + /// \brief The type of the map that stores the last edges of the
2.222 + /// longest paths.
2.223 + ///
2.224 + /// The type of the map that stores the last
2.225 + /// edges of the longest paths.
2.226 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
2.227 + ///
2.228 + typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap;
2.229 +
2.230 + /// \brief Instantiates a PredMap.
2.231 + ///
2.232 + /// This function instantiates a \ref PredMap.
2.233 + /// \param G is the graph, to which we would like to define the PredMap.
2.234 + /// \todo The graph alone may be insufficient for the initialization
2.235 + static PredMap *createPredMap(const _Graph& graph) {
2.236 + return new PredMap(graph);
2.237 + }
2.238 +
2.239 + /// \brief The type of the map that stores the dists of the nodes.
2.240 + ///
2.241 + /// The type of the map that stores the dists of the nodes.
2.242 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
2.243 + ///
2.244 + typedef typename Graph::template NodeMap<typename _LengthMap::Value>
2.245 + DistMap;
2.246 +
2.247 + /// \brief Instantiates a DistMap.
2.248 + ///
2.249 + /// This function instantiates a \ref DistMap.
2.250 + /// \param G is the graph, to which we would like to define the
2.251 + /// \ref DistMap
2.252 + static DistMap *createDistMap(const _Graph& graph) {
2.253 + return new DistMap(graph);
2.254 + }
2.255 +
2.256 + };
2.257 +
2.258 +
2.259 + /// \brief %DagShortestPath algorithm class.
2.260 + ///
2.261 + /// \ingroup flowalgs
2.262 + /// This class provides an efficient implementation of a Dag sortest path
2.263 + /// searching algorithm. The edge lengths are passed to the algorithm
2.264 + /// using a \ref concept::ReadMap "ReadMap", so it is easy to change it
2.265 + /// to any kind of length.
2.266 + ///
2.267 + /// The complexity of the algorithm is O(n + e).
2.268 + ///
2.269 + /// The type of the length is determined by the
2.270 + /// \ref concept::ReadMap::Value "Value" of the length map.
2.271 + ///
2.272 + /// \param _Graph The graph type the algorithm runs on. The default value
2.273 + /// is \ref ListGraph. The value of _Graph is not used directly by
2.274 + /// DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits.
2.275 + /// \param _LengthMap This read-only EdgeMap determines the lengths of the
2.276 + /// edges. The default map type is \ref concept::StaticGraph::EdgeMap
2.277 + /// "Graph::EdgeMap<int>". The value of _LengthMap is not used directly
2.278 + /// by DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits.
2.279 + /// \param _Traits Traits class to set various data types used by the
2.280 + /// algorithm. The default traits class is \ref DagShortestPathDefaultTraits
2.281 + /// "DagShortestPathDefaultTraits<_Graph,_LengthMap>". See \ref
2.282 + /// DagShortestPathDefaultTraits for the documentation of a DagShortestPath traits
2.283 + /// class.
2.284 + ///
2.285 + /// \author Balazs Attila Mihaly (based on Balazs Dezso's work)
2.286 +
2.287 +#ifdef DOXYGEN
2.288 + template <typename _Graph, typename _LengthMap, typename _Traits>
2.289 +#else
2.290 + template <typename _Graph=ListGraph,
2.291 + typename _LengthMap=typename _Graph::template EdgeMap<int>,
2.292 + typename _Traits=DagShortestPathDefaultTraits<_Graph,_LengthMap> >
2.293 +#endif
2.294 + class DagShortestPath {
2.295 + public:
2.296 +
2.297 + /// \brief \ref Exception for uninitialized parameters.
2.298 + ///
2.299 + /// This error represents problems in the initialization
2.300 + /// of the parameters of the algorithms.
2.301 +
2.302 + class UninitializedParameter : public lemon::UninitializedParameter {
2.303 + public:
2.304 + virtual const char* exceptionName() const {
2.305 + return "lemon::DagShortestPath::UninitializedParameter";
2.306 + }
2.307 + };
2.308 +
2.309 + typedef _Traits Traits;
2.310 + ///The type of the underlying graph.
2.311 + typedef typename _Traits::Graph Graph;
2.312 +
2.313 + typedef typename Graph::Node Node;
2.314 + typedef typename Graph::NodeIt NodeIt;
2.315 + typedef typename Graph::Edge Edge;
2.316 + typedef typename Graph::EdgeIt EdgeIt;
2.317 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.318 +
2.319 + /// \brief The type of the length of the edges.
2.320 + typedef typename _Traits::LengthMap::Value Value;
2.321 + /// \brief The type of the map that stores the edge lengths.
2.322 + typedef typename _Traits::LengthMap LengthMap;
2.323 + /// \brief The type of the map that stores the last
2.324 + /// edges of the shortest paths.
2.325 + typedef typename _Traits::PredMap PredMap;
2.326 + /// \brief The type of the map that stores the dists of the nodes.
2.327 + typedef typename _Traits::DistMap DistMap;
2.328 + /// \brief The operation traits.
2.329 + typedef typename _Traits::OperationTraits OperationTraits;
2.330 + /// \brief The Node weight map.
2.331 + typedef typename Graph::NodeMap<Value> WeightMap;
2.332 + private:
2.333 + /// Pointer to the underlying graph
2.334 + const Graph *graph;
2.335 + /// Pointer to the length map
2.336 + const LengthMap *length;
2.337 + ///Pointer to the map of predecessors edges
2.338 + PredMap *_pred;
2.339 + ///Indicates if \ref _pred is locally allocated (\c true) or not
2.340 + bool local_pred;
2.341 + ///Pointer to the map of distances
2.342 + DistMap *_dist;
2.343 + ///Indicates if \ref _dist is locally allocated (\c true) or not
2.344 + bool local_dist;
2.345 + ///Process step counter
2.346 + unsigned int _process_step;
2.347 +
2.348 + std::vector<Node> _node_order;
2.349 +
2.350 + /// Creates the maps if necessary.
2.351 + void create_maps() {
2.352 + if(!_pred) {
2.353 + local_pred = true;
2.354 + _pred = Traits::createPredMap(*graph);
2.355 + }
2.356 + if(!_dist) {
2.357 + local_dist = true;
2.358 + _dist = Traits::createDistMap(*graph);
2.359 + }
2.360 + }
2.361 +
2.362 + public :
2.363 +
2.364 + typedef DagShortestPath Create;
2.365 +
2.366 + /// \name Named template parameters
2.367 +
2.368 + ///@{
2.369 +
2.370 + template <class T>
2.371 + struct DefPredMapTraits : public Traits {
2.372 + typedef T PredMap;
2.373 + static PredMap *createPredMap(const Graph&) {
2.374 + throw UninitializedParameter();
2.375 + }
2.376 + };
2.377 +
2.378 + /// \brief \ref named-templ-param "Named parameter" for setting PredMap
2.379 + /// type
2.380 + /// \ref named-templ-param "Named parameter" for setting PredMap type
2.381 + ///
2.382 + template <class T>
2.383 + struct DefPredMap {
2.384 + typedef DagShortestPath< Graph, LengthMap, DefPredMapTraits<T> > Create;
2.385 + };
2.386 +
2.387 + template <class T>
2.388 + struct DefDistMapTraits : public Traits {
2.389 + typedef T DistMap;
2.390 + static DistMap *createDistMap(const Graph& graph) {
2.391 + throw UninitializedParameter();
2.392 + }
2.393 + };
2.394 +
2.395 + /// \brief \ref named-templ-param "Named parameter" for setting DistMap
2.396 + /// type
2.397 + ///
2.398 + /// \ref named-templ-param "Named parameter" for setting DistMap type
2.399 + ///
2.400 + template <class T>
2.401 + struct DefDistMap
2.402 + : public DagShortestPath< Graph, LengthMap, DefDistMapTraits<T> > {
2.403 + typedef DagShortestPath< Graph, LengthMap, DefDistMapTraits<T> > Create;
2.404 + };
2.405 +
2.406 + template <class T>
2.407 + struct DefOperationTraitsTraits : public Traits {
2.408 + typedef T OperationTraits;
2.409 + };
2.410 +
2.411 + /// \brief \ref named-templ-param "Named parameter" for setting
2.412 + /// OperationTraits type
2.413 + ///
2.414 + /// \ref named-templ-param "Named parameter" for setting OperationTraits
2.415 + /// type
2.416 + template <class T>
2.417 + struct DefOperationTraits
2.418 + : public DagShortestPath< Graph, LengthMap, DefOperationTraitsTraits<T> > {
2.419 + typedef DagShortestPath< Graph, LengthMap, DefOperationTraitsTraits<T> >
2.420 + Create;
2.421 + };
2.422 +
2.423 + ///@}
2.424 +
2.425 + protected:
2.426 +
2.427 + DagShortestPath() {}
2.428 +
2.429 + public:
2.430 +
2.431 + /// \brief Constructor.
2.432 + ///
2.433 + /// \param _graph the graph the algorithm will run on.
2.434 + /// \param _length the length map used by the algorithm.
2.435 + DagShortestPath(const Graph& _graph, const LengthMap& _length) :
2.436 + graph(&_graph), length(&_length),
2.437 + _pred(0), local_pred(false),
2.438 + _dist(0), local_dist(false){}
2.439 +
2.440 + /// \brief Constructor with node weight map.
2.441 + ///
2.442 + /// \param _graph the graph the algorithm will run on.
2.443 + /// \param _length the length map used by the algorithm.
2.444 + /// The NodeMap _length will be used as the weight map.
2.445 + /// Each edge will have the weight of its target node.
2.446 + DagShortestPath(const Graph& _graph, const WeightMap& _length) :
2.447 + graph(&_graph),
2.448 + _pred(0), local_pred(false),
2.449 + _dist(0), local_dist(false){
2.450 + length=new LengthMap(_graph);
2.451 + _dist=new DistMap(_graph);
2.452 + for(EdgeIt eit(_graph);eit!=INVALID;++eit)
2.453 + (const_cast<LengthMap*>(length))->set(eit,_length[_graph.target(eit)]);
2.454 + }
2.455 +
2.456 + ///Destructor.
2.457 + ~DagShortestPath() {
2.458 + if(local_pred) delete _pred;
2.459 + if(local_dist) delete _dist;
2.460 + }
2.461 +
2.462 + /// \brief Sets the length map.
2.463 + ///
2.464 + /// Sets the length map.
2.465 + /// \return \c (*this)
2.466 + DagShortestPath &lengthMap(const LengthMap &m) {
2.467 + length = &m;
2.468 + return *this;
2.469 + }
2.470 +
2.471 + /// \brief Sets the map storing the predecessor edges.
2.472 + ///
2.473 + /// Sets the map storing the predecessor edges.
2.474 + /// If you don't use this function before calling \ref run(),
2.475 + /// it will allocate one. The destuctor deallocates this
2.476 + /// automatically allocated map, of course.
2.477 + /// \return \c (*this)
2.478 + DagShortestPath &predMap(PredMap &m) {
2.479 + if(local_pred) {
2.480 + delete _pred;
2.481 + local_pred=false;
2.482 + }
2.483 + _pred = &m;
2.484 + return *this;
2.485 + }
2.486 +
2.487 + /// \brief Sets the map storing the distances calculated by the algorithm.
2.488 + ///
2.489 + /// Sets the map storing the distances calculated by the algorithm.
2.490 + /// If you don't use this function before calling \ref run(),
2.491 + /// it will allocate one. The destuctor deallocates this
2.492 + /// automatically allocated map, of course.
2.493 + /// \return \c (*this)
2.494 + DagShortestPath &distMap(DistMap &m) {
2.495 + if(local_dist) {
2.496 + delete _dist;
2.497 + local_dist=false;
2.498 + }
2.499 + _dist = &m;
2.500 + return *this;
2.501 + }
2.502 +
2.503 + /// \name Execution control
2.504 + /// The simplest way to execute the algorithm is to use
2.505 + /// one of the member functions called \c run(...)
2.506 + /// \n
2.507 + /// If you need more control on the execution,
2.508 + /// first you must call \ref init(...), then you can add several source
2.509 + /// nodes with \ref addSource().
2.510 + /// Finally \ref start() will perform the actual path computation.
2.511 + /// Some functions have an alternative form (\ref checkedInit(...),
2.512 + /// \ref checkedRun(...)) which also verifies if the graph given in the
2.513 + /// constructor is a dag.
2.514 +
2.515 + ///@{
2.516 +
2.517 + /// \brief Initializes the internal data structures.
2.518 + ///
2.519 + /// Initializes the internal data structures.
2.520 + void init(const Value value = OperationTraits::infinity()) {
2.521 + typedef typename Graph::template NodeMap<int> NodeOrderMap;
2.522 + _process_step=0;
2.523 + NodeOrderMap node_order(*graph);
2.524 + topologicalSort(*graph,node_order);
2.525 + _node_order.resize(countNodes(*graph),INVALID);
2.526 + create_maps();
2.527 + for (NodeIt it(*graph); it != INVALID; ++it) {
2.528 + _node_order[node_order[it]]=it;
2.529 + _pred->set(it, INVALID);
2.530 + _dist->set(it, value);
2.531 + }
2.532 + }
2.533 +
2.534 + /// \brief Initializes the internal data structures
2.535 + /// with a given topological sort (NodeMap).
2.536 + ///
2.537 + /// Initializes the internal data structures
2.538 + /// with a given topological sort (NodeMap).
2.539 + void init(const typename Graph::template NodeMap<int>& node_order,
2.540 + const Value value = OperationTraits::infinity()) {
2.541 + _process_step=0;
2.542 + _node_order.resize(countNodes(*graph),INVALID);
2.543 + create_maps();
2.544 + for (NodeIt it(*graph); it != INVALID; ++it) {
2.545 + _node_order[node_order[it]]=it;
2.546 + _pred->set(it, INVALID);
2.547 + _dist->set(it, value);
2.548 + }
2.549 + }
2.550 +
2.551 + /// \brief Initializes the internal data structures
2.552 + /// with a given topological sort (std::vector).
2.553 + ///
2.554 + /// Initializes the internal data structures
2.555 + /// with a given topological sort (std::vector).
2.556 + void init(const std::vector<Node>& node_order,
2.557 + const Value value = OperationTraits::infinity()) {
2.558 + _process_step=0;
2.559 + _node_order=node_order;
2.560 + create_maps();
2.561 + for (NodeIt it(*graph); it != INVALID; ++it) {
2.562 + _pred->set(it, INVALID);
2.563 + _dist->set(it, value);
2.564 + }
2.565 + }
2.566 +
2.567 + /// \brief Initializes the internal data structures. It also checks if the graph is dag.
2.568 + ///
2.569 + /// Initializes the internal data structures. It also checks if the graph is dag.
2.570 + /// \return true if the graph (given in the constructor) is dag, false otherwise.
2.571 + bool checkedInit(const Value value = OperationTraits::infinity()) {
2.572 + typedef typename Graph::template NodeMap<int> NodeOrderMap;
2.573 + NodeOrderMap node_order(*graph);
2.574 + if(!checkedTopologicalSort(*graph,node_order))return false;
2.575 + init(node_order,value);
2.576 + return true;
2.577 + }
2.578 +
2.579 + /// \brief Initializes the internal data structures with a given
2.580 + /// topological sort (NodeMap). It also checks if the graph is dag.
2.581 + ///
2.582 + /// Initializes the internal data structures with a given
2.583 + /// topological sort (NodeMap). It also checks if the graph is dag.
2.584 + /// \return true if the graph (given in the constructor) is dag, false otherwise.
2.585 + bool checkedInit(const typename Graph::template NodeMap<int>& node_order,
2.586 + const Value value = OperationTraits::infinity()) {
2.587 + for(NodeIt it(*graph);it!=INVALID;++it){
2.588 + for(OutEdgeIt oeit(*graph,it);oeit!=INVALID;++oeit){
2.589 + if(node_order[graph->target(oeit)]<node_order[it])return false;
2.590 + }
2.591 + }
2.592 + init(node_order,value);
2.593 + return true;
2.594 + }
2.595 +
2.596 + /// \brief Initializes the internal data structures with a given
2.597 + /// topological sort (std::vector). It also checks if the graph is dag.
2.598 + ///
2.599 + /// Initializes the internal data structures with a given
2.600 + /// topological sort (std::vector). It also checks if the graph is dag.
2.601 + /// \return true if the graph (given in the constructor) is dag, false otherwise.
2.602 + bool checkedInit(const std::vector<Node>& node_order,
2.603 + const Value value = OperationTraits::infinity()) {
2.604 + typedef typename Graph::template NodeMap<bool> BoolNodeMap;
2.605 + BoolNodeMap _processed(*graph,false);
2.606 + for(unsigned int i=0;i<_node_order.size();++i){
2.607 + _processed[node_order[i]]=true;
2.608 + for(OutEdgeIt oeit(*graph,node_order[i]);oeit!=INVALID;++oeit){
2.609 + if(_processed[graph->target(oeit)])return false;
2.610 + }
2.611 + }
2.612 + init(node_order,value);
2.613 + return true;
2.614 + }
2.615 +
2.616 + /// \brief Adds a new source node.
2.617 + ///
2.618 + /// The optional second parameter is the initial distance of the node.
2.619 + /// It just sets the distance of the node to the given value.
2.620 + void addSource(Node source, Value dst = OperationTraits::zero()) {
2.621 + if((*_dist)[source] != dst){
2.622 + _dist->set(source, dst);
2.623 + }
2.624 + }
2.625 +
2.626 + /// \brief Executes one step from the dag shortest path algorithm.
2.627 + ///
2.628 + /// If the algoritm calculated the distances in the previous step
2.629 + /// strictly for all at most k length paths then it will calculate the
2.630 + /// distances strictly for all at most k + 1 length paths. With k
2.631 + /// iteration this function calculates the at most k length paths.
2.632 + ///\pre the queue is not empty
2.633 + ///\return the currently processed node
2.634 + Node processNextNode() {
2.635 + if(reached(_node_order[_process_step])){
2.636 + for (OutEdgeIt it(*graph, _node_order[_process_step]); it != INVALID; ++it) {
2.637 + Node target = graph->target(it);
2.638 + Value relaxed =
2.639 + OperationTraits::plus((*_dist)[_node_order[_process_step]], (*length)[it]);
2.640 + if (OperationTraits::less(relaxed, (*_dist)[target])) {
2.641 + _pred->set(target, it);
2.642 + _dist->set(target, relaxed);
2.643 + }
2.644 + }
2.645 + }
2.646 + ++_process_step;
2.647 + return _node_order[_process_step-1];
2.648 + }
2.649 +
2.650 + ///\brief Returns \c false if there are nodes
2.651 + ///to be processed in the queue
2.652 + ///
2.653 + ///Returns \c false if there are nodes
2.654 + ///to be processed in the queue
2.655 + bool emptyQueue() { return _node_order.size()-1==_process_step; }
2.656 +
2.657 + ///\brief Returns the number of the nodes to be processed.
2.658 + ///
2.659 + ///Returns the number of the nodes to be processed in the queue.
2.660 + int queueSize() { return _node_order.size()-1-_process_step; }
2.661 +
2.662 + /// \brief Executes the algorithm.
2.663 + ///
2.664 + /// \pre init() must be called and at least one node should be added
2.665 + /// with addSource() before using this function.
2.666 + ///
2.667 + /// This method runs the %DagShortestPath algorithm from the root node(s)
2.668 + /// in order to compute the shortest path to each node. The algorithm
2.669 + /// computes
2.670 + /// - The shortest path tree.
2.671 + /// - The distance of each node from the root(s).
2.672 + void start() {
2.673 + while(!emptyQueue()) {
2.674 + processNextNode();
2.675 + }
2.676 + }
2.677 +
2.678 + /// \brief Runs %DagShortestPath algorithm from node \c s.
2.679 + ///
2.680 + /// This method runs the %DagShortestPath algorithm from a root node \c s
2.681 + /// in order to compute the shortest path to each node. The algorithm
2.682 + /// computes
2.683 + /// - The shortest path tree.
2.684 + /// - The distance of each node from the root.
2.685 + ///
2.686 + /// \note d.run(s) is just a shortcut of the following code.
2.687 + /// \code
2.688 + /// d.init();
2.689 + /// d.addSource(s);
2.690 + /// d.start();
2.691 + /// \endcode
2.692 + void run(Node s) {
2.693 + init();
2.694 + addSource(s);
2.695 + start();
2.696 + }
2.697 +
2.698 + /// \brief Runs %DagShortestPath algorithm from node \c s.
2.699 + /// It also checks if the graph is a dag.
2.700 + ///
2.701 + /// This method runs the %DagShortestPath algorithm from a root node \c s
2.702 + /// in order to compute the shortest path to each node. The algorithm
2.703 + /// computes
2.704 + /// - The shortest path tree.
2.705 + /// - The distance of each node from the root.
2.706 + /// The algorithm checks if the graph given int the constructor is a dag.
2.707 + bool checkedRun(Node s) {
2.708 + if(!checkedInit())return false;
2.709 + addSource(s);
2.710 + start();
2.711 + return true;
2.712 + }
2.713 +
2.714 + ///@}
2.715 +
2.716 + /// \name Query Functions
2.717 + /// The result of the %DagShortestPath algorithm can be obtained using these
2.718 + /// functions.\n
2.719 + /// Before the use of these functions,
2.720 + /// either run() or start() must be called.
2.721 +
2.722 + ///@{
2.723 +
2.724 + /// \brief Copies the shortest path to \c t into \c p
2.725 + ///
2.726 + /// This function copies the shortest path to \c t into \c p.
2.727 + /// If it \c t is a source itself or unreachable, then it does not
2.728 + /// alter \c p.
2.729 + ///
2.730 + /// \return Returns \c true if a path to \c t was actually copied to \c p,
2.731 + /// \c false otherwise.
2.732 + /// \sa DirPath
2.733 + template <typename Path>
2.734 + bool getPath(Path &p, Node t) {
2.735 + if(reached(t)) {
2.736 + p.clear();
2.737 + typename Path::Builder b(p);
2.738 + for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
2.739 + b.pushFront(predEdge(t));
2.740 + b.commit();
2.741 + return true;
2.742 + }
2.743 + return false;
2.744 + }
2.745 +
2.746 + /// \brief The distance of a node from the root.
2.747 + ///
2.748 + /// Returns the distance of a node from the root.
2.749 + /// \pre \ref run() must be called before using this function.
2.750 + /// \warning If node \c v in unreachable from the root the return value
2.751 + /// of this funcion is undefined.
2.752 + Value dist(Node v) const { return (*_dist)[v]; }
2.753 +
2.754 + /// \brief Returns the 'previous edge' of the shortest path tree.
2.755 + ///
2.756 + /// For a node \c v it returns the 'previous edge' of the shortest path
2.757 + /// tree, i.e. it returns the last edge of a shortest path from the root
2.758 + /// to \c v. It is \ref INVALID if \c v is unreachable from the root or
2.759 + /// if \c v=s. The shortest path tree used here is equal to the shortest
2.760 + /// path tree used in \ref predNode().
2.761 + /// \pre \ref run() must be called before using
2.762 + /// this function.
2.763 + Edge predEdge(Node v) const { return (*_pred)[v]; }
2.764 +
2.765 + /// \brief Returns the 'previous node' of the shortest path tree.
2.766 + ///
2.767 + /// For a node \c v it returns the 'previous node' of the shortest path
2.768 + /// tree, i.e. it returns the last but one node from a shortest path from
2.769 + /// the root to \c /v. It is INVALID if \c v is unreachable from the root
2.770 + /// or if \c v=s. The shortest path tree used here is equal to the
2.771 + /// shortest path tree used in \ref predEdge(). \pre \ref run() must be
2.772 + /// called before using this function.
2.773 + Node predNode(Node v) const {
2.774 + return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]);
2.775 + }
2.776 +
2.777 + /// \brief Returns a reference to the NodeMap of distances.
2.778 + ///
2.779 + /// Returns a reference to the NodeMap of distances. \pre \ref run() must
2.780 + /// be called before using this function.
2.781 + const DistMap &distMap() const { return *_dist;}
2.782 +
2.783 + /// \brief Returns a reference to the shortest path tree map.
2.784 + ///
2.785 + /// Returns a reference to the NodeMap of the edges of the
2.786 + /// shortest path tree.
2.787 + /// \pre \ref run() must be called before using this function.
2.788 + const PredMap &predMap() const { return *_pred; }
2.789 +
2.790 + /// \brief Checks if a node is reachable from the root.
2.791 + ///
2.792 + /// Returns \c true if \c v is reachable from the root.
2.793 + /// \pre \ref run() must be called before using this function.
2.794 + ///
2.795 + bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
2.796 +
2.797 + ///@}
2.798 + };
2.799 +
2.800 + /// \brief Default traits class of DagShortestPath function.
2.801 + ///
2.802 + /// Default traits class of DagShortestPath function.
2.803 + /// \param _Graph Graph type.
2.804 + /// \param _LengthMap Type of length map.
2.805 + template <typename _Graph, typename _LengthMap>
2.806 + struct DagShortestPathWizardDefaultTraits {
2.807 + /// \brief The graph type the algorithm runs on.
2.808 + typedef _Graph Graph;
2.809 +
2.810 + /// \brief The type of the map that stores the edge lengths.
2.811 + ///
2.812 + /// The type of the map that stores the edge lengths.
2.813 + /// It must meet the \ref concept::ReadMap "ReadMap" concept.
2.814 + typedef _LengthMap LengthMap;
2.815 +
2.816 + /// \brief The value type of the length map.
2.817 + typedef typename _LengthMap::Value Value;
2.818 +
2.819 + /// \brief Operation traits for dag shortest path algorithm.
2.820 + ///
2.821 + /// It defines the infinity type on the given Value type
2.822 + /// and the used operation.
2.823 + /// \see DagShortestPathDefaultOperationTraits
2.824 + typedef DagShortestPathDefaultOperationTraits<Value> OperationTraits;
2.825 +
2.826 + /// \brief The type of the map that stores the last
2.827 + /// edges of the shortest paths.
2.828 + ///
2.829 + /// The type of the map that stores the last
2.830 + /// edges of the shortest paths.
2.831 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
2.832 + typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap;
2.833 +
2.834 + /// \brief Instantiates a PredMap.
2.835 + ///
2.836 + /// This function instantiates a \ref PredMap.
2.837 + static PredMap *createPredMap(const _Graph &) {
2.838 + return new PredMap();
2.839 + }
2.840 + /// \brief The type of the map that stores the dists of the nodes.
2.841 + ///
2.842 + /// The type of the map that stores the dists of the nodes.
2.843 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
2.844 + typedef NullMap<typename Graph::Node, Value> DistMap;
2.845 + /// \brief Instantiates a DistMap.
2.846 + ///
2.847 + /// This function instantiates a \ref DistMap.
2.848 + static DistMap *createDistMap(const _Graph &) {
2.849 + return new DistMap();
2.850 + }
2.851 + };
2.852 +
2.853 + /// \brief Default traits used by \ref DagShortestPathWizard
2.854 + ///
2.855 + /// To make it easier to use DagShortestPath algorithm
2.856 + /// we have created a wizard class.
2.857 + /// This \ref DagShortestPathWizard class needs default traits,
2.858 + /// as well as the \ref DagShortestPath class.
2.859 + /// The \ref DagShortestPathWizardBase is a class to be the default traits of the
2.860 + /// \ref DagShortestPathWizard class.
2.861 + /// \todo More named parameters are required...
2.862 + template<class _Graph,class _LengthMap>
2.863 + class DagShortestPathWizardBase
2.864 + : public DagShortestPathWizardDefaultTraits<_Graph,_LengthMap> {
2.865 +
2.866 + typedef DagShortestPathWizardDefaultTraits<_Graph,_LengthMap> Base;
2.867 + protected:
2.868 + /// Type of the nodes in the graph.
2.869 + typedef typename Base::Graph::Node Node;
2.870 +
2.871 + /// Pointer to the underlying graph.
2.872 + void *_graph;
2.873 + /// Pointer to the length map
2.874 + void *_length;
2.875 + ///Pointer to the map of predecessors edges.
2.876 + void *_pred;
2.877 + ///Pointer to the map of distances.
2.878 + void *_dist;
2.879 + ///Pointer to the source node.
2.880 + Node _source;
2.881 +
2.882 + public:
2.883 + /// Constructor.
2.884 +
2.885 + /// This constructor does not require parameters, therefore it initiates
2.886 + /// all of the attributes to default values (0, INVALID).
2.887 + DagShortestPathWizardBase() : _graph(0), _length(0), _pred(0),
2.888 + _dist(0), _source(INVALID) {}
2.889 +
2.890 + /// Constructor.
2.891 +
2.892 + /// This constructor requires some parameters,
2.893 + /// listed in the parameters list.
2.894 + /// Others are initiated to 0.
2.895 + /// \param graph is the initial value of \ref _graph
2.896 + /// \param length is the initial value of \ref _length
2.897 + /// \param source is the initial value of \ref _source
2.898 + DagShortestPathWizardBase(const _Graph& graph,
2.899 + const _LengthMap& length,
2.900 + Node source = INVALID) :
2.901 + _graph((void *)&graph), _length((void *)&length), _pred(0),
2.902 + _dist(0), _source(source) {}
2.903 +
2.904 + };
2.905 +
2.906 + /// A class to make the usage of DagShortestPath algorithm easier
2.907 +
2.908 + /// This class is created to make it easier to use DagShortestPath algorithm.
2.909 + /// It uses the functions and features of the plain \ref DagShortestPath,
2.910 + /// but it is much simpler to use it.
2.911 + ///
2.912 + /// Simplicity means that the way to change the types defined
2.913 + /// in the traits class is based on functions that returns the new class
2.914 + /// and not on templatable built-in classes.
2.915 + /// When using the plain \ref DagShortestPath
2.916 + /// the new class with the modified type comes from
2.917 + /// the original class by using the ::
2.918 + /// operator. In the case of \ref DagShortestPathWizard only
2.919 + /// a function have to be called and it will
2.920 + /// return the needed class.
2.921 + ///
2.922 + /// It does not have own \ref run method. When its \ref run method is called
2.923 + /// it initiates a plain \ref DagShortestPath class, and calls the \ref
2.924 + /// DagShortestPath::run() method of it.
2.925 + template<class _Traits>
2.926 + class DagShortestPathWizard : public _Traits {
2.927 + typedef _Traits Base;
2.928 +
2.929 + ///The type of the underlying graph.
2.930 + typedef typename _Traits::Graph Graph;
2.931 +
2.932 + typedef typename Graph::Node Node;
2.933 + typedef typename Graph::NodeIt NodeIt;
2.934 + typedef typename Graph::Edge Edge;
2.935 + typedef typename Graph::OutEdgeIt EdgeIt;
2.936 +
2.937 + ///The type of the map that stores the edge lengths.
2.938 + typedef typename _Traits::LengthMap LengthMap;
2.939 +
2.940 + ///The type of the length of the edges.
2.941 + typedef typename LengthMap::Value Value;
2.942 +
2.943 + ///\brief The type of the map that stores the last
2.944 + ///edges of the shortest paths.
2.945 + typedef typename _Traits::PredMap PredMap;
2.946 +
2.947 + ///The type of the map that stores the dists of the nodes.
2.948 + typedef typename _Traits::DistMap DistMap;
2.949 +
2.950 + public:
2.951 + /// Constructor.
2.952 + DagShortestPathWizard() : _Traits() {}
2.953 +
2.954 + /// \brief Constructor that requires parameters.
2.955 + ///
2.956 + /// Constructor that requires parameters.
2.957 + /// These parameters will be the default values for the traits class.
2.958 + DagShortestPathWizard(const Graph& graph, const LengthMap& length,
2.959 + Node source = INVALID)
2.960 + : _Traits(graph, length, source) {}
2.961 +
2.962 + /// \brief Copy constructor
2.963 + DagShortestPathWizard(const _Traits &b) : _Traits(b) {}
2.964 +
2.965 + ~DagShortestPathWizard() {}
2.966 +
2.967 + /// \brief Runs DagShortestPath algorithm from a given node.
2.968 + ///
2.969 + /// Runs DagShortestPath algorithm from a given node.
2.970 + /// The node can be given by the \ref source function.
2.971 + void run() {
2.972 + if(Base::_source == INVALID) throw UninitializedParameter();
2.973 + DagShortestPath<Graph,LengthMap,_Traits>
2.974 + bf(*(Graph*)Base::_graph, *(LengthMap*)Base::_length);
2.975 + if (Base::_pred) bf.predMap(*(PredMap*)Base::_pred);
2.976 + if (Base::_dist) bf.distMap(*(DistMap*)Base::_dist);
2.977 + bf.run(Base::_source);
2.978 + }
2.979 +
2.980 + /// \brief Runs DagShortestPath algorithm from the given node.
2.981 + ///
2.982 + /// Runs DagShortestPath algorithm from the given node.
2.983 + /// \param s is the given source.
2.984 + void run(Node source) {
2.985 + Base::_source = source;
2.986 + run();
2.987 + }
2.988 +
2.989 + template<class T>
2.990 + struct DefPredMapBase : public Base {
2.991 + typedef T PredMap;
2.992 + static PredMap *createPredMap(const Graph &) { return 0; };
2.993 + DefPredMapBase(const _Traits &b) : _Traits(b) {}
2.994 + };
2.995 +
2.996 + ///\brief \ref named-templ-param "Named parameter"
2.997 + ///function for setting PredMap type
2.998 + ///
2.999 + /// \ref named-templ-param "Named parameter"
2.1000 + ///function for setting PredMap type
2.1001 + ///
2.1002 + template<class T>
2.1003 + DagShortestPathWizard<DefPredMapBase<T> > predMap(const T &t)
2.1004 + {
2.1005 + Base::_pred=(void *)&t;
2.1006 + return DagShortestPathWizard<DefPredMapBase<T> >(*this);
2.1007 + }
2.1008 +
2.1009 + template<class T>
2.1010 + struct DefDistMapBase : public Base {
2.1011 + typedef T DistMap;
2.1012 + static DistMap *createDistMap(const Graph &) { return 0; };
2.1013 + DefDistMapBase(const _Traits &b) : _Traits(b) {}
2.1014 + };
2.1015 +
2.1016 + ///\brief \ref named-templ-param "Named parameter"
2.1017 + ///function for setting DistMap type
2.1018 + ///
2.1019 + /// \ref named-templ-param "Named parameter"
2.1020 + ///function for setting DistMap type
2.1021 + ///
2.1022 + template<class T>
2.1023 + DagShortestPathWizard<DefDistMapBase<T> > distMap(const T &t) {
2.1024 + Base::_dist=(void *)&t;
2.1025 + return DagShortestPathWizard<DefDistMapBase<T> >(*this);
2.1026 + }
2.1027 +
2.1028 + template<class T>
2.1029 + struct DefOperationTraitsBase : public Base {
2.1030 + typedef T OperationTraits;
2.1031 + DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
2.1032 + };
2.1033 +
2.1034 + ///\brief \ref named-templ-param "Named parameter"
2.1035 + ///function for setting OperationTraits type
2.1036 + ///
2.1037 + /// \ref named-templ-param "Named parameter"
2.1038 + ///function for setting OperationTraits type
2.1039 + ///
2.1040 + template<class T>
2.1041 + DagShortestPathWizard<DefOperationTraitsBase<T> > distMap() {
2.1042 + return DagShortestPathWizard<DefDistMapBase<T> >(*this);
2.1043 + }
2.1044 +
2.1045 + /// \brief Sets the source node, from which the DagShortestPath algorithm runs.
2.1046 + ///
2.1047 + /// Sets the source node, from which the DagShortestPath algorithm runs.
2.1048 + /// \param s is the source node.
2.1049 + DagShortestPathWizard<_Traits>& source(Node source) {
2.1050 + Base::_source = source;
2.1051 + return *this;
2.1052 + }
2.1053 +
2.1054 + };
2.1055 +
2.1056 + /// \brief Function type interface for DagShortestPath algorithm.
2.1057 + ///
2.1058 + /// \ingroup flowalgs
2.1059 + /// Function type interface for DagShortestPath algorithm.
2.1060 + ///
2.1061 + /// This function also has several \ref named-templ-func-param
2.1062 + /// "named parameters", they are declared as the members of class
2.1063 + /// \ref DagShortestPathWizard.
2.1064 + /// The following
2.1065 + /// example shows how to use these parameters.
2.1066 + /// \code
2.1067 + /// dagShortestPath(g,length,source).predMap(preds).run();
2.1068 + /// \endcode
2.1069 + /// \warning Don't forget to put the \ref DagShortestPathWizard::run() "run()"
2.1070 + /// to the end of the parameter list.
2.1071 + /// \sa DagShortestPathWizard
2.1072 + /// \sa DagShortestPath
2.1073 + template<class _Graph, class _LengthMap>
2.1074 + DagShortestPathWizard<DagShortestPathWizardBase<_Graph,_LengthMap> >
2.1075 + dagShortestPath(const _Graph& graph,
2.1076 + const _LengthMap& length,
2.1077 + typename _Graph::Node source = INVALID) {
2.1078 + return DagShortestPathWizard<DagShortestPathWizardBase<_Graph,_LengthMap> >
2.1079 + (graph, length, source);
2.1080 + }
2.1081 +
2.1082 +} //END OF NAMESPACE LEMON
2.1083 +
2.1084 +#endif
2.1085 +
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/fredman_tarjan.h Fri Jan 27 08:17:25 2006 +0000
3.3 @@ -0,0 +1,509 @@
3.4 +/* -*- C++ -*-
3.5 + * lemon/fredman_tarjan.h - Part of LEMON, a generic C++ optimization library
3.6 + *
3.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.9 + *
3.10 + * Permission to use, modify and distribute this software is granted
3.11 + * provided that this copyright notice appears in all copies. For
3.12 + * precise terms see the accompanying LICENSE file.
3.13 + *
3.14 + * This software is provided "AS IS" with no warranty of any kind,
3.15 + * express or implied, and with no claim as to its suitability for any
3.16 + * purpose.
3.17 + *
3.18 + */
3.19 +
3.20 +#ifndef LEMON_FREDMAN_TARJAN_H
3.21 +#define LEMON_FREDMAN_TARJAN_H
3.22 +
3.23 +///\ingroup spantree
3.24 +///\file
3.25 +///\brief FredmanTarjan algorithm to compute minimum spanning forest.
3.26 +
3.27 +#include <limits>
3.28 +#include <vector>
3.29 +
3.30 +#include <lemon/list_graph.h>
3.31 +#include <lemon/smart_graph.h>
3.32 +#include <lemon/fib_heap.h>
3.33 +#include <lemon/radix_sort.h>
3.34 +#include <lemon/invalid.h>
3.35 +#include <lemon/error.h>
3.36 +#include <lemon/maps.h>
3.37 +#include <lemon/traits.h>
3.38 +#include <lemon/graph_utils.h>
3.39 +
3.40 +#include <lemon/concept/ugraph.h>
3.41 +
3.42 +namespace lemon {
3.43 +
3.44 + ///Default traits class of FredmanTarjan class.
3.45 +
3.46 + ///Default traits class of FredmanTarjan class.
3.47 + ///\param GR Graph type.
3.48 + ///\param LM Type of cost map.
3.49 + template<class GR, class LM>
3.50 + struct FredmanTarjanDefaultTraits{
3.51 + ///The graph type the algorithm runs on.
3.52 + typedef GR UGraph;
3.53 + ///The type of the map that stores the edge costs.
3.54 +
3.55 + ///The type of the map that stores the edge costs.
3.56 + ///It must meet the \ref concept::ReadMap "ReadMap" concept.
3.57 + typedef LM CostMap;
3.58 + //The type of the cost of the edges.
3.59 + typedef typename LM::Value Value;
3.60 + ///The type of the map that stores whether an edge is in the
3.61 + ///spanning tree or not.
3.62 +
3.63 + ///The type of the map that stores whether an edge is in the
3.64 + ///spanning tree or not.
3.65 + ///It must meet the \ref concept::ReadWriteMap "ReadWriteMap" concept.
3.66 + ///By default it is a BoolEdgeMap.
3.67 + typedef typename UGraph::template UEdgeMap<bool> TreeMap;
3.68 + ///Instantiates a TreeMap.
3.69 +
3.70 + ///This function instantiates a \ref TreeMap.
3.71 + ///\param g is the graph, to which
3.72 + ///we would like to define the \ref TreeMap
3.73 + static TreeMap *createTreeMap(const GR &_graph){
3.74 + return new TreeMap(_graph);
3.75 + }
3.76 + };
3.77 +
3.78 + ///%FredmanTarjan algorithm class to find a minimum spanning tree.
3.79 +
3.80 + /// \ingroup spantree
3.81 + ///This class provides an efficient implementation of %FredmanTarjan algorithm
3.82 + ///whitch is sometimes a bit quicker than the Prim algorithm on larger graphs.
3.83 + ///Due to the structure of the algorithm, it has less controll functions than
3.84 + ///Prim.
3.85 + ///
3.86 + ///The running time is O(e*B(e,n)) where e is the number of edges, n is the
3.87 + ///number of nodes in the graph and B(e,n) is min { i | log^(i) n <= e/n}
3.88 + ///( log^(i+1) n = log(log^(i)) n )
3.89 + ///
3.90 + ///The edge costs are passed to the algorithm using a
3.91 + ///\ref concept::ReadMap "ReadMap",
3.92 + ///so it is easy to change it to any kind of cost.
3.93 + ///
3.94 + ///The type of the cost is determined by the
3.95 + ///\ref concept::ReadMap::Value "Value" of the cost map.
3.96 + ///
3.97 + ///\param GR The graph type the algorithm runs on. The default value
3.98 + ///is \ref ListUGraph. The value of GR is not used directly by
3.99 + ///FredmanTarjan, it is only passed to \ref FredmanTarjanDefaultTraits.
3.100 + ///
3.101 + ///\param LM This read-only UEdgeMap determines the costs of the
3.102 + ///edges. It is read once for each edge, so the map may involve in
3.103 + ///relatively time consuming process to compute the edge cost if
3.104 + ///it is necessary. The default map type is \ref
3.105 + ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap<int>". The value
3.106 + ///of LM is not used directly by FredmanTarjan, it is only passed to \ref
3.107 + ///FredmanTarjanDefaultTraits.
3.108 + ///
3.109 + ///\param TR Traits class to set
3.110 + ///various data types used by the algorithm. The default traits
3.111 + ///class is \ref FredmanTarjanDefaultTraits
3.112 + ///"FredmanTarjanDefaultTraits<GR,LM>". See \ref
3.113 + ///FredmanTarjanDefaultTraits for the documentation of a FredmanTarjan traits
3.114 + ///class.
3.115 + ///
3.116 + ///\author Balazs Attila Mihaly
3.117 +
3.118 +#ifdef DOXYGEN
3.119 + template <typename GR,
3.120 + typename LM,
3.121 + typename TR>
3.122 +#else
3.123 + template <typename GR=ListUGraph,
3.124 + typename LM=typename GR::template UEdgeMap<int>,
3.125 + typename TR=FredmanTarjanDefaultTraits<GR,LM> >
3.126 +#endif
3.127 + class FredmanTarjan {
3.128 + public:
3.129 + /**
3.130 + * \brief \ref Exception for uninitialized parameters.
3.131 + *
3.132 + * This error represents problems in the initialization
3.133 + * of the parameters of the algorithms.
3.134 + */
3.135 + class UninitializedParameter : public lemon::UninitializedParameter {
3.136 + public:
3.137 + virtual const char* exceptionName() const {
3.138 + return "lemon::FredmanTarjan::UninitializedParameter";
3.139 + }
3.140 + };
3.141 +
3.142 + typedef GR Graph;
3.143 + typedef TR Traits;
3.144 + ///The type of the underlying graph.
3.145 + typedef typename TR::UGraph UGraph;
3.146 + ///\e
3.147 + typedef typename UGraph::Node Node;
3.148 + ///\e
3.149 + typedef typename UGraph::NodeIt NodeIt;
3.150 + ///\e
3.151 + typedef typename UGraph::UEdge UEdge;
3.152 + ///\e
3.153 + typedef typename UGraph::UEdgeIt UEdgeIt;
3.154 + ///\e
3.155 + typedef typename UGraph::IncEdgeIt IncEdgeIt;
3.156 +
3.157 + ///The type of the cost of the edges.
3.158 + typedef typename TR::CostMap::Value Value;
3.159 + ///The type of the map that stores the edge costs.
3.160 + typedef typename TR::CostMap CostMap;
3.161 + ///Edges of the spanning tree.
3.162 + typedef typename TR::TreeMap TreeMap;
3.163 + private:
3.164 + ///Pointer to the underlying graph.
3.165 + const UGraph *graph;
3.166 + ///Pointer to the cost map
3.167 + const CostMap *cost;
3.168 + ///Pointer to the map of tree edges.
3.169 + TreeMap *_tree;
3.170 + ///Indicates if \ref _tree is locally allocated (\c true) or not.
3.171 + bool local_tree;
3.172 +
3.173 + ///Creates the maps if necessary.
3.174 +
3.175 + void create_maps(){
3.176 + if(!_tree){
3.177 + local_tree=true;
3.178 + _tree=Traits::createTreeMap(*graph);
3.179 + }
3.180 + }
3.181 +
3.182 + public :
3.183 +
3.184 + typedef FredmanTarjan Create;
3.185 +
3.186 + ///\name Named template parameters
3.187 +
3.188 + ///@{
3.189 +
3.190 + template <class TM>
3.191 + struct DefTreeMapTraits : public Traits {
3.192 + typedef TM TreeMap;
3.193 + static TreeMap *createTreeMap(const UGraph &) {
3.194 + throw UninitializedParameter();
3.195 + }
3.196 + };
3.197 + ///\ref named-templ-param "Named parameter" for setting TreeMap
3.198 +
3.199 + ///\ref named-templ-param "Named parameter" for setting TreeMap
3.200 + ///
3.201 + template <class TM>
3.202 + struct DefTreeMap
3.203 + : public FredmanTarjan< UGraph, CostMap, DefTreeMapTraits<TM> > {
3.204 + typedef FredmanTarjan< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
3.205 + };
3.206 +
3.207 + ///@}
3.208 +
3.209 +
3.210 + protected:
3.211 +
3.212 + FredmanTarjan() {}
3.213 +
3.214 + private:
3.215 +
3.216 + template<class SrcGraph,class OrigMap,class Heap,class ProcessedMap,class PredMap>
3.217 + void processNextTree(const SrcGraph& graph,const OrigMap& orig,Heap &heap,
3.218 + ProcessedMap& processed,PredMap& pred,int& tree_counter,const int limit){
3.219 + std::vector<typename SrcGraph::Node> tree_nodes;
3.220 + int tree_index=tree_counter;
3.221 + bool stop=false;
3.222 + while(!heap.empty() && !stop){
3.223 + typename SrcGraph::Node v=heap.top();
3.224 + heap.pop();
3.225 + if(processed[v]!=-1){
3.226 + heap.state(v,Heap::PRE_HEAP);
3.227 + tree_index=processed[v];
3.228 + _tree->set(orig[pred[v]],true);
3.229 + stop=true;
3.230 + break;
3.231 + }
3.232 + tree_nodes.push_back(v);
3.233 + for(typename SrcGraph::IncEdgeIt e(graph,v);e!=INVALID;++e){
3.234 + typename SrcGraph::Node w=graph.oppositeNode(v,e);
3.235 + switch(heap.state(w)){
3.236 + case Heap::PRE_HEAP:
3.237 + if(heap.size()>=limit){
3.238 + stop=true;
3.239 + }
3.240 + else{
3.241 + heap.push(w,(*cost)[orig[e]]);
3.242 + pred.set(w,e);
3.243 + }
3.244 + break;
3.245 + case Heap::IN_HEAP:
3.246 + if ((*cost)[orig[e]]<heap[w]){
3.247 + heap.decrease(w,(*cost)[orig[e]]);
3.248 + pred.set(w,e);
3.249 + }
3.250 + break;
3.251 + case Heap::POST_HEAP:
3.252 + break;
3.253 + }
3.254 + }
3.255 + }
3.256 + for(int i=1;i<(int)tree_nodes.size();++i){
3.257 + _tree->set(orig[pred[tree_nodes[i]]],true);
3.258 + processed.set(tree_nodes[i],tree_index);
3.259 + heap.state(tree_nodes[i], Heap::PRE_HEAP);
3.260 + }
3.261 + processed.set(tree_nodes[0],tree_index);
3.262 + heap.state(tree_nodes[0],Heap::PRE_HEAP);
3.263 + while (!heap.empty()) {
3.264 + typename SrcGraph::Node v=heap.top();
3.265 + heap.pop();
3.266 + heap.state(v,Heap::PRE_HEAP);
3.267 + }
3.268 + if(!stop)++tree_counter;
3.269 + }
3.270 +
3.271 + template<class SrcGraph,class OrigMap,class ProcessedMap>
3.272 + void createTrees(const SrcGraph& graph,const OrigMap& orig, ProcessedMap& processed,
3.273 + int edgenum,int& tree_counter){
3.274 + typedef typename SrcGraph::Node Node;
3.275 + typedef typename SrcGraph::UEdge UEdge;
3.276 + typedef typename SrcGraph::NodeIt NodeIt;
3.277 + typedef typename SrcGraph::template NodeMap<int> HeapCrossRef;
3.278 + typedef typename SrcGraph::template NodeMap<UEdge> PredMap;
3.279 + HeapCrossRef crossref(graph,-1);
3.280 + FibHeap<Node,Value,HeapCrossRef> heap(crossref);
3.281 + PredMap pred(graph,INVALID);
3.282 + int rate=2*edgenum/countNodes(graph);
3.283 + int limit=(rate>std::numeric_limits<int>::digits)?std::numeric_limits<int>::max():(1<<rate);
3.284 + for(NodeIt i(graph);i!=INVALID;++i){
3.285 + if(processed[i]==-1){
3.286 + heap.push(i, Value());
3.287 + processNextTree(graph,orig,heap,processed,pred,tree_counter,limit);
3.288 + }
3.289 + }
3.290 + }
3.291 +
3.292 + template<class SrcGraph,class DestGraph,class SrcOrigMap,class DestOrigMap,class ProcessedMap>
3.293 + void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig,DestGraph& destgraph,
3.294 + DestOrigMap& destorig,const ProcessedMap& processed,const int tree_counter){
3.295 + typedef typename SrcGraph::Node Node;
3.296 + typedef typename DestGraph::Node DNode;
3.297 + typedef typename SrcGraph::UEdge UEdge;
3.298 + typedef typename DestGraph::UEdge DUEdge;
3.299 + typedef typename SrcGraph::Edge Edge;
3.300 + typedef typename SrcGraph::EdgeIt EdgeIt;
3.301 + std::vector<Edge> edges;
3.302 + std::vector<DNode> nodes(tree_counter, INVALID);
3.303 + for(EdgeIt i(srcgraph);i!=INVALID;++i){
3.304 + if(processed[srcgraph.source(i)]<processed[srcgraph.target(i)]){
3.305 + edges.push_back(i);
3.306 + if(nodes[processed[srcgraph.source(i)]]==INVALID) {
3.307 + nodes[processed[srcgraph.source(i)]]=destgraph.addNode();
3.308 + }
3.309 + if(nodes[processed[srcgraph.target(i)]]==INVALID) {
3.310 + nodes[processed[srcgraph.target(i)]]=destgraph.addNode();
3.311 + }
3.312 + }
3.313 + }
3.314 +
3.315 + radixSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,sourceMap(srcgraph))));
3.316 + counterSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,targetMap(srcgraph))));
3.317 + for(int i=0;i!=(int)edges.size();++i){
3.318 + int srcproc=processed[srcgraph.source(edges[i])];
3.319 + int trgproc=processed[srcgraph.target(edges[i])];
3.320 + Value minval=(*cost)[srcorig[edges[i]]];
3.321 + UEdge minpos=edges[i];
3.322 + while (i+1!=(int)edges.size() && srcproc==processed[srcgraph.source(edges[i+1])] &&
3.323 + trgproc==processed[srcgraph.target(edges[i+1])]) {
3.324 + if (minval>(*cost)[srcorig[edges[i+1]]]) {
3.325 + minval=(*cost)[srcorig[edges[i+1]]];
3.326 + minpos=edges[i+1];
3.327 + }
3.328 + ++i;
3.329 + }
3.330 + destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=srcorig[minpos];
3.331 + }
3.332 + }
3.333 +
3.334 + template<class SrcGraph,class OrigMap>
3.335 + void phase(const SrcGraph& graph,const OrigMap& orig,int edgenum){
3.336 + int tree_counter = 0;
3.337 + typename SrcGraph::template NodeMap<int> processed(graph,-1);
3.338 + SmartUGraph destgraph;
3.339 + SmartUGraph::UEdgeMap<typename OrigMap::Value> destorig(destgraph);
3.340 + createTrees(graph,orig,processed,edgenum,tree_counter);
3.341 + collect(graph,orig,destgraph,destorig,processed,tree_counter);
3.342 + if (countNodes(destgraph)>1) {
3.343 + phase(destgraph,destorig,edgenum);
3.344 + }
3.345 + }
3.346 +
3.347 + public:
3.348 +
3.349 + ///Constructor.
3.350 +
3.351 + ///\param _graph the graph the algorithm will run on.
3.352 + ///\param _cost the cost map used by the algorithm.
3.353 + FredmanTarjan(const UGraph& _graph, const CostMap& _cost) :
3.354 + graph(&_graph), cost(&_cost),
3.355 + _tree(0), local_tree(false)
3.356 + {
3.357 + checkConcept<concept::UGraph, UGraph>();
3.358 + }
3.359 +
3.360 + ///Destructor.
3.361 + ~FredmanTarjan(){
3.362 + if(local_tree) delete _tree;
3.363 + }
3.364 +
3.365 + ///Sets the cost map.
3.366 +
3.367 + ///Sets the cost map.
3.368 + ///\return <tt> (*this) </tt>
3.369 + FredmanTarjan &costMap(const CostMap &m){
3.370 + cost = &m;
3.371 + return *this;
3.372 + }
3.373 +
3.374 + ///Sets the map storing the tree edges.
3.375 +
3.376 + ///Sets the map storing the tree edges.
3.377 + ///If you don't use this function before calling \ref run(),
3.378 + ///it will allocate one. The destuctor deallocates this
3.379 + ///automatically allocated map, of course.
3.380 + ///By default this is a BoolEdgeMap.
3.381 + ///\return <tt> (*this) </tt>
3.382 + FredmanTarjan &treeMap(TreeMap &m){
3.383 + if(local_tree) {
3.384 + delete _tree;
3.385 + local_tree=false;
3.386 + }
3.387 + _tree = &m;
3.388 + return *this;
3.389 + }
3.390 +
3.391 + public:
3.392 + ///\name Execution control
3.393 + ///The simplest way to execute the algorithm is to use
3.394 + ///one of the member functions called \c run(...).
3.395 +
3.396 + ///@{
3.397 +
3.398 + ///Initializes the internal data structures.
3.399 +
3.400 + ///Initializes the internal data structures.
3.401 + ///
3.402 + void init(){
3.403 + create_maps();
3.404 + for(typename Graph::UEdgeIt i(*graph);i!=INVALID;++i){
3.405 + _tree->set(i,false);
3.406 + }
3.407 + }
3.408 +
3.409 + ///Executes the algorithm.
3.410 +
3.411 + ///Executes the algorithm.
3.412 + ///
3.413 + ///\pre init() must be called and at least one node should be added
3.414 + ///with addSource() before using this function.
3.415 + ///
3.416 + ///This method runs the %FredmanTarjan algorithm from the node(s)
3.417 + ///in order to compute the
3.418 + ///minimum spanning tree.
3.419 + void start(){
3.420 + phase(*graph,identityMap<UEdge>(),countEdges(*graph));
3.421 + }
3.422 +
3.423 + ///Runs %FredmanTarjan algorithm.
3.424 +
3.425 + ///This method runs the %FredmanTarjan algorithm
3.426 + ///in order to compute the minimum spanning forest.
3.427 + ///
3.428 + ///\note ft.run() is just a shortcut of the following code.
3.429 + ///\code
3.430 + /// ft.init();
3.431 + /// ft.start();
3.432 + ///\endcode
3.433 + void run() {
3.434 + init();
3.435 + start();
3.436 + }
3.437 +
3.438 + ///@}
3.439 +
3.440 + ///\name Query Functions
3.441 + ///The result of the %FredmanTarjan algorithm can be obtained using these
3.442 + ///functions.\n
3.443 + ///Before the use of these functions,
3.444 + ///either run() or start() must be called.
3.445 +
3.446 + ///@{
3.447 +
3.448 + ///Returns a reference to the tree edges map.
3.449 +
3.450 + ///Returns a reference to the TreeEdgeMap of the edges of the
3.451 + ///minimum spanning tree. The value of the map is \c true only if the
3.452 + ///edge is in the minimum spanning tree.
3.453 + ///
3.454 + ///\pre \ref run() or \ref start() must be called before using this
3.455 + ///function.
3.456 + const TreeMap &treeMap() const { return *_tree;}
3.457 +
3.458 + ///Sets the tree edges map.
3.459 +
3.460 + ///Sets the TreeMap of the edges of the minimum spanning tree.
3.461 + ///The map values belonging to the edges of the minimum
3.462 + ///spanning tree are set to \param tree_edge_value or \c true by default
3.463 + ///while the edge values not belonging to the minimum spanning tree are
3.464 + ///set to
3.465 + ///\param tree_default_value or \c false by default.
3.466 + ///
3.467 + ///\pre \ref run() or \ref start() must be called before using this
3.468 + ///function.
3.469 +
3.470 + template<class TreeMap>
3.471 + void treeEdges(
3.472 + TreeMap& tree,
3.473 + const typename TreeMap::Value& tree_edge_value=true,
3.474 + const typename TreeMap::Value& tree_default_value=false) const {
3.475 + for(typename UGraph::UEdgeIt i(*graph);i!=INVALID;++i){
3.476 + (*_tree)[i]?tree.set(i,tree_edge_value):tree.set(i,tree_default_value);
3.477 + }
3.478 + }
3.479 +
3.480 + ///\brief Checks if an edge is in the spanning tree or not.
3.481 +
3.482 + ///Checks if an edge is in the spanning tree or not.
3.483 + ///\param e is the edge that will be checked
3.484 + ///\return \c true if e is in the spanning tree, \c false otherwise
3.485 + bool tree(UEdge e){
3.486 + return (*_tree)[e];
3.487 + }
3.488 + ///@}
3.489 + };
3.490 +
3.491 + /// \ingroup spantree
3.492 + ///
3.493 + /// \brief Function type interface for FredmanTarjan algorithm.
3.494 + ///
3.495 + /// Function type interface for FredmanTarjan algorithm.
3.496 + /// \param graph the UGraph that the algorithm runs on
3.497 + /// \param cost the CostMap of the edges
3.498 + /// \retval tree the EdgeMap that contains whether an edge is in the
3.499 + /// spanning tree or not
3.500 + ///
3.501 + /// \sa Prim
3.502 + template<class Graph,class CostMap,class TreeMap>
3.503 + void fredmanTarjan(const Graph& graph, const CostMap& cost,TreeMap& tree){
3.504 + typename FredmanTarjan<Graph,CostMap>::template DefTreeMap<TreeMap>::
3.505 + Create ft(graph,cost);
3.506 + ft.treeMap(tree);
3.507 + ft.run();
3.508 + };
3.509 +
3.510 +} //END OF NAMESPACE LEMON
3.511 +
3.512 +#endif
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/prim.h Fri Jan 27 08:17:25 2006 +0000
4.3 @@ -0,0 +1,792 @@
4.4 +/* -*- C++ -*-
4.5 + * lemon/prim.h - Part of LEMON, a generic C++ optimization library
4.6 + *
4.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.9 + *
4.10 + * Permission to use, modify and distribute this software is granted
4.11 + * provided that this copyright notice appears in all copies. For
4.12 + * precise terms see the accompanying LICENSE file.
4.13 + *
4.14 + * This software is provided "AS IS" with no warranty of any kind,
4.15 + * express or implied, and with no claim as to its suitability for any
4.16 + * purpose.
4.17 + *
4.18 + */
4.19 +
4.20 +#ifndef LEMON_PRIM_H
4.21 +#define LEMON_PRIM_H
4.22 +
4.23 +///\ingroup spantree
4.24 +///\file
4.25 +///\brief Prim algorithm to compute minimum spanning tree.
4.26 +
4.27 +#include <lemon/list_graph.h>
4.28 +#include <lemon/bin_heap.h>
4.29 +#include <lemon/invalid.h>
4.30 +#include <lemon/error.h>
4.31 +#include <lemon/maps.h>
4.32 +#include <lemon/traits.h>
4.33 +
4.34 +#include <lemon/concept/ugraph.h>
4.35 +
4.36 +namespace lemon {
4.37 +
4.38 + ///Default traits class of Prim class.
4.39 +
4.40 + ///Default traits class of Prim class.
4.41 + ///\param GR Graph type.
4.42 + ///\param LM Type of cost map.
4.43 + template<class GR, class LM>
4.44 + struct PrimDefaultTraits{
4.45 + ///The graph type the algorithm runs on.
4.46 + typedef GR UGraph;
4.47 + ///The type of the map that stores the edge costs.
4.48 +
4.49 + ///The type of the map that stores the edge costs.
4.50 + ///It must meet the \ref concept::ReadMap "ReadMap" concept.
4.51 + typedef LM CostMap;
4.52 + //The type of the cost of the edges.
4.53 + typedef typename LM::Value Value;
4.54 + /// The cross reference type used by heap.
4.55 +
4.56 + /// The cross reference type used by heap.
4.57 + /// Usually it is \c UGraph::NodeMap<int>.
4.58 + typedef typename UGraph::template NodeMap<int> HeapCrossRef;
4.59 + ///Instantiates a HeapCrossRef.
4.60 +
4.61 + ///This function instantiates a \ref HeapCrossRef.
4.62 + /// \param G is the graph, to which we would like to define the
4.63 + /// HeapCrossRef.
4.64 + static HeapCrossRef *createHeapCrossRef(const GR &_graph){
4.65 + return new HeapCrossRef(_graph);
4.66 + }
4.67 +
4.68 + ///The heap type used by Prim algorithm.
4.69 +
4.70 + ///The heap type used by Prim algorithm.
4.71 + ///
4.72 + ///\sa BinHeap
4.73 + ///\sa Prim
4.74 + typedef BinHeap<typename UGraph::Node, typename LM::Value,
4.75 + HeapCrossRef, std::less<Value> > Heap;
4.76 +
4.77 + static Heap *createHeap(HeapCrossRef& _ref){
4.78 + return new Heap(_ref);
4.79 + }
4.80 +
4.81 + ///\brief The type of the map that stores the last
4.82 + ///edges of the minimum spanning tree.
4.83 + ///
4.84 + ///The type of the map that stores the last
4.85 + ///edges of the minimum spanning tree.
4.86 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
4.87 + ///
4.88 + typedef typename UGraph::template NodeMap<typename GR::UEdge> PredMap;
4.89 + ///Instantiates a PredMap.
4.90 +
4.91 + ///This function instantiates a \ref PredMap.
4.92 + ///\param G is the graph, to which we would like to define the PredMap.
4.93 + static PredMap *createPredMap(const GR &_graph){
4.94 + return new PredMap(_graph);
4.95 + }
4.96 +
4.97 + ///The type of the map that stores whether an edge is in the
4.98 + ///spanning tree or not.
4.99 +
4.100 + ///The type of the map that stores whether an edge is in the
4.101 + ///spanning tree or not.
4.102 + ///By default it is a NullMap.
4.103 + typedef NullMap<typename UGraph::UEdge,bool> TreeMap;
4.104 + ///Instantiates a TreeMap.
4.105 +
4.106 + ///This function instantiates a \ref TreeMap.
4.107 + ///\param g is the graph, to which
4.108 + ///we would like to define the \ref TreeMap
4.109 + static TreeMap *createTreeMap(const GR &){
4.110 + return new TreeMap();
4.111 + }
4.112 +
4.113 + ///The type of the map that stores whether a nodes is processed.
4.114 +
4.115 + ///The type of the map that stores whether a nodes is processed.
4.116 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
4.117 + ///By default it is a NodeMap<bool>.
4.118 + typedef NullMap<typename UGraph::Node,bool> ProcessedMap;
4.119 + ///Instantiates a ProcessedMap.
4.120 +
4.121 + ///This function instantiates a \ref ProcessedMap.
4.122 + ///\param g is the graph, to which
4.123 + ///we would like to define the \ref ProcessedMap
4.124 +#ifdef DOXYGEN
4.125 + static ProcessedMap *createProcessedMap(const GR &_graph)
4.126 +#else
4.127 + static ProcessedMap *createProcessedMap(const GR &)
4.128 +#endif
4.129 + {
4.130 + return new ProcessedMap();
4.131 + }
4.132 + };
4.133 +
4.134 + ///%Prim algorithm class to find a minimum spanning tree.
4.135 +
4.136 + /// \ingroup spantree
4.137 + ///This class provides an efficient implementation of %Prim algorithm.
4.138 + ///
4.139 + ///The running time is O(e*log n) where e is the number of edges and
4.140 + ///n is the number of nodes in the graph.
4.141 + ///
4.142 + ///The edge costs are passed to the algorithm using a
4.143 + ///\ref concept::ReadMap "ReadMap",
4.144 + ///so it is easy to change it to any kind of cost.
4.145 + ///
4.146 + ///The type of the cost is determined by the
4.147 + ///\ref concept::ReadMap::Value "Value" of the cost map.
4.148 + ///
4.149 + ///It is also possible to change the underlying priority heap.
4.150 + ///
4.151 + ///\param GR The graph type the algorithm runs on. The default value
4.152 + ///is \ref ListUGraph. The value of GR is not used directly by
4.153 + ///Prim, it is only passed to \ref PrimDefaultTraits.
4.154 + ///
4.155 + ///\param LM This read-only UEdgeMap determines the costs of the
4.156 + ///edges. It is read once for each edge, so the map may involve in
4.157 + ///relatively time consuming process to compute the edge cost if
4.158 + ///it is necessary. The default map type is \ref
4.159 + ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap<int>". The value
4.160 + ///of LM is not used directly by Prim, it is only passed to \ref
4.161 + ///PrimDefaultTraits.
4.162 + ///
4.163 + ///\param TR Traits class to set
4.164 + ///various data types used by the algorithm. The default traits
4.165 + ///class is \ref PrimDefaultTraits
4.166 + ///"PrimDefaultTraits<GR,LM>". See \ref
4.167 + ///PrimDefaultTraits for the documentation of a Prim traits
4.168 + ///class.
4.169 + ///
4.170 + ///\author Balazs Attila Mihaly
4.171 +
4.172 +#ifdef DOXYGEN
4.173 + template <typename GR,
4.174 + typename LM,
4.175 + typename TR>
4.176 +#else
4.177 + template <typename GR=ListUGraph,
4.178 + typename LM=typename GR::template UEdgeMap<int>,
4.179 + typename TR=PrimDefaultTraits<GR,LM> >
4.180 +#endif
4.181 + class Prim {
4.182 + public:
4.183 + /**
4.184 + * \brief \ref Exception for uninitialized parameters.
4.185 + *
4.186 + * This error represents problems in the initialization
4.187 + * of the parameters of the algorithms.
4.188 + */
4.189 + class UninitializedParameter : public lemon::UninitializedParameter {
4.190 + public:
4.191 + virtual const char* exceptionName() const {
4.192 + return "lemon::Prim::UninitializedParameter";
4.193 + }
4.194 + };
4.195 +
4.196 + typedef TR Traits;
4.197 + ///The type of the underlying graph.
4.198 + typedef typename TR::UGraph UGraph;
4.199 + ///\e
4.200 + typedef typename UGraph::Node Node;
4.201 + ///\e
4.202 + typedef typename UGraph::NodeIt NodeIt;
4.203 + ///\e
4.204 + typedef typename UGraph::UEdge UEdge;
4.205 + ///\e
4.206 + typedef typename UGraph::IncEdgeIt IncEdgeIt;
4.207 +
4.208 + ///The type of the cost of the edges.
4.209 + typedef typename TR::CostMap::Value Value;
4.210 + ///The type of the map that stores the edge costs.
4.211 + typedef typename TR::CostMap CostMap;
4.212 + ///\brief The type of the map that stores the last
4.213 + ///predecessor edges of the spanning tree.
4.214 + typedef typename TR::PredMap PredMap;
4.215 + ///Edges of the spanning tree.
4.216 + typedef typename TR::TreeMap TreeMap;
4.217 + ///The type of the map indicating if a node is processed.
4.218 + typedef typename TR::ProcessedMap ProcessedMap;
4.219 + ///The cross reference type used for the current heap.
4.220 + typedef typename TR::HeapCrossRef HeapCrossRef;
4.221 + ///The heap type used by the prim algorithm.
4.222 + typedef typename TR::Heap Heap;
4.223 + private:
4.224 + /// Pointer to the underlying graph.
4.225 + const UGraph *graph;
4.226 + /// Pointer to the cost map
4.227 + const CostMap *cost;
4.228 + ///Pointer to the map of predecessors edges.
4.229 + PredMap *_pred;
4.230 + ///Indicates if \ref _pred is locally allocated (\c true) or not.
4.231 + bool local_pred;
4.232 + ///Pointer to the map of tree edges.
4.233 + TreeMap *_tree;
4.234 + ///Indicates if \ref _tree is locally allocated (\c true) or not.
4.235 + bool local_tree;
4.236 + ///Pointer to the map of processed status of the nodes.
4.237 + ProcessedMap *_processed;
4.238 + ///Indicates if \ref _processed is locally allocated (\c true) or not.
4.239 + bool local_processed;
4.240 + ///Pointer to the heap cross references.
4.241 + HeapCrossRef *_heap_cross_ref;
4.242 + ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
4.243 + bool local_heap_cross_ref;
4.244 + ///Pointer to the heap.
4.245 + Heap *_heap;
4.246 + ///Indicates if \ref _heap is locally allocated (\c true) or not.
4.247 + bool local_heap;
4.248 +
4.249 + ///Creates the maps if necessary.
4.250 + void create_maps(){
4.251 + if(!_pred) {
4.252 + local_pred = true;
4.253 + _pred = Traits::createPredMap(*graph);
4.254 + }
4.255 + if(!_tree) {
4.256 + local_tree = true;
4.257 + _tree = Traits::createTreeMap(*graph);
4.258 + }
4.259 + if(!_processed) {
4.260 + local_processed = true;
4.261 + _processed = Traits::createProcessedMap(*graph);
4.262 + }
4.263 + if (!_heap_cross_ref) {
4.264 + local_heap_cross_ref = true;
4.265 + _heap_cross_ref = Traits::createHeapCrossRef(*graph);
4.266 + }
4.267 + if (!_heap) {
4.268 + local_heap = true;
4.269 + _heap = Traits::createHeap(*_heap_cross_ref);
4.270 + }
4.271 + }
4.272 +
4.273 + public :
4.274 +
4.275 + typedef Prim Create;
4.276 +
4.277 + ///\name Named template parameters
4.278 +
4.279 + ///@{
4.280 +
4.281 + template <class T>
4.282 + struct DefPredMapTraits : public Traits {
4.283 + typedef T PredMap;
4.284 + static PredMap *createPredMap(const UGraph &_graph){
4.285 + throw UninitializedParameter();
4.286 + }
4.287 + };
4.288 + ///\ref named-templ-param "Named parameter" for setting PredMap type
4.289 +
4.290 + ///\ref named-templ-param "Named parameter" for setting PredMap type
4.291 + ///
4.292 + template <class T>
4.293 + struct DefPredMap
4.294 + : public Prim< UGraph, CostMap, DefPredMapTraits<T> > {
4.295 + typedef Prim< UGraph, CostMap, DefPredMapTraits<T> > Create;
4.296 + };
4.297 +
4.298 + template <class T>
4.299 + struct DefProcessedMapTraits : public Traits {
4.300 + typedef T ProcessedMap;
4.301 + static ProcessedMap *createProcessedMap(const UGraph &_graph){
4.302 + throw UninitializedParameter();
4.303 + }
4.304 + };
4.305 + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
4.306 +
4.307 + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
4.308 + ///
4.309 + template <class T>
4.310 + struct DefProcessedMap
4.311 + : public Prim< UGraph, CostMap, DefProcessedMapTraits<T> > {
4.312 + typedef Prim< UGraph, CostMap, DefProcessedMapTraits<T> > Create;
4.313 + };
4.314 +
4.315 + struct DefGraphProcessedMapTraits : public Traits {
4.316 + typedef typename UGraph::template NodeMap<bool> ProcessedMap;
4.317 + static ProcessedMap *createProcessedMap(const UGraph &_graph){
4.318 + return new ProcessedMap(_graph);
4.319 + }
4.320 + };
4.321 +
4.322 +
4.323 + template <class H, class CR>
4.324 + struct DefHeapTraits : public Traits {
4.325 + typedef CR HeapCrossRef;
4.326 + typedef H Heap;
4.327 + static HeapCrossRef *createHeapCrossRef(const UGraph &) {
4.328 + throw UninitializedParameter();
4.329 + }
4.330 + static Heap *createHeap(HeapCrossRef &){
4.331 + return UninitializedParameter();
4.332 + }
4.333 + };
4.334 + ///\ref named-templ-param "Named parameter" for setting heap and cross
4.335 + ///reference type
4.336 +
4.337 + ///\ref named-templ-param "Named parameter" for setting heap and cross
4.338 + ///reference type
4.339 + ///
4.340 + template <class H, class CR = typename UGraph::template NodeMap<int> >
4.341 + struct DefHeap
4.342 + : public Prim< UGraph, CostMap, DefHeapTraits<H, CR> > {
4.343 + typedef Prim< UGraph, CostMap, DefHeapTraits<H, CR> > Create;
4.344 + };
4.345 +
4.346 + template <class H, class CR>
4.347 + struct DefStandardHeapTraits : public Traits {
4.348 + typedef CR HeapCrossRef;
4.349 + typedef H Heap;
4.350 + static HeapCrossRef *createHeapCrossRef(const UGraph &_graph) {
4.351 + return new HeapCrossRef(_graph);
4.352 + }
4.353 + static Heap *createHeap(HeapCrossRef &ref){
4.354 + return new Heap(ref);
4.355 + }
4.356 + };
4.357 + ///\ref named-templ-param "Named parameter" for setting heap and cross
4.358 + ///reference type with automatic allocation
4.359 +
4.360 + ///\ref named-templ-param "Named parameter" for setting heap and cross
4.361 + ///reference type. It can allocate the heap and the cross reference
4.362 + ///object if the cross reference's constructor waits for the graph as
4.363 + ///parameter and the heap's constructor waits for the cross reference.
4.364 + template <class H, class CR = typename UGraph::template NodeMap<int> >
4.365 + struct DefStandardHeap
4.366 + : public Prim< UGraph, CostMap, DefStandardHeapTraits<H, CR> > {
4.367 + typedef Prim< UGraph, CostMap, DefStandardHeapTraits<H, CR> >
4.368 + Create;
4.369 + };
4.370 +
4.371 + template <class TM>
4.372 + struct DefTreeMapTraits : public Traits {
4.373 + typedef TM TreeMap;
4.374 + static TreeMap *createTreeMap(const UGraph &) {
4.375 + throw UninitializedParameter();
4.376 + }
4.377 + };
4.378 + ///\ref named-templ-param "Named parameter" for setting TreeMap
4.379 +
4.380 + ///\ref named-templ-param "Named parameter" for setting TreeMap
4.381 + ///
4.382 + template <class TM>
4.383 + struct DefTreeMap
4.384 + : public Prim< UGraph, CostMap, DefTreeMapTraits<TM> > {
4.385 + typedef Prim< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
4.386 + };
4.387 +
4.388 + struct DefGraphTreeMapTraits : public Traits {
4.389 + typedef typename UGraph::template NodeMap<bool> TreeMap;
4.390 + static TreeMap *createTreeMap(const UGraph &_graph){
4.391 + return new TreeMap(_graph);
4.392 + }
4.393 + };
4.394 +
4.395 + ///@}
4.396 +
4.397 +
4.398 + protected:
4.399 +
4.400 + Prim() {}
4.401 +
4.402 + public:
4.403 +
4.404 + ///Constructor.
4.405 +
4.406 + ///\param _graph the graph the algorithm will run on.
4.407 + ///\param _cost the cost map used by the algorithm.
4.408 + Prim(const UGraph& _graph, const CostMap& _cost) :
4.409 + graph(&_graph), cost(&_cost),
4.410 + _pred(NULL), local_pred(false),
4.411 + _tree(NULL), local_tree(false),
4.412 + _processed(NULL), local_processed(false),
4.413 + _heap_cross_ref(NULL), local_heap_cross_ref(false),
4.414 + _heap(NULL), local_heap(false)
4.415 + {
4.416 + checkConcept<concept::UGraph, UGraph>();
4.417 + }
4.418 +
4.419 + ///Destructor.
4.420 + ~Prim(){
4.421 + if(local_pred) delete _pred;
4.422 + if(local_tree) delete _tree;
4.423 + if(local_processed) delete _processed;
4.424 + if(local_heap_cross_ref) delete _heap_cross_ref;
4.425 + if(local_heap) delete _heap;
4.426 + }
4.427 +
4.428 + ///\brief Sets the cost map.
4.429 +
4.430 + ///Sets the cost map.
4.431 + ///\return <tt> (*this) </tt>
4.432 + Prim &costMap(const CostMap &m){
4.433 + cost = &m;
4.434 + return *this;
4.435 + }
4.436 +
4.437 + ///\brief Sets the map storing the predecessor edges.
4.438 +
4.439 + ///Sets the map storing the predecessor edges.
4.440 + ///If you don't use this function before calling \ref run(),
4.441 + ///it will allocate one. The destuctor deallocates this
4.442 + ///automatically allocated map, of course.
4.443 + ///\return <tt> (*this) </tt>
4.444 + Prim &predMap(PredMap &m){
4.445 + if(local_pred) {
4.446 + delete _pred;
4.447 + local_pred=false;
4.448 + }
4.449 + _pred = &m;
4.450 + return *this;
4.451 + }
4.452 +
4.453 + ///\brief Sets the map storing the tree edges.
4.454 +
4.455 + ///Sets the map storing the tree edges.
4.456 + ///If you don't use this function before calling \ref run(),
4.457 + ///it will allocate one. The destuctor deallocates this
4.458 + ///automatically allocated map, of course.
4.459 + ///By default this is a NullMap.
4.460 + ///\return <tt> (*this) </tt>
4.461 + Prim &treeMap(TreeMap &m){
4.462 + if(local_tree) {
4.463 + delete _tree;
4.464 + local_tree=false;
4.465 + }
4.466 + _tree = &m;
4.467 + return *this;
4.468 + }
4.469 +
4.470 + ///\brief Sets the heap and the cross reference used by algorithm.
4.471 +
4.472 + ///Sets the heap and the cross reference used by algorithm.
4.473 + ///If you don't use this function before calling \ref run(),
4.474 + ///it will allocate one. The destuctor deallocates this
4.475 + ///automatically allocated map, of course.
4.476 + ///\return <tt> (*this) </tt>
4.477 + Prim &heap(Heap& heap, HeapCrossRef &crossRef){
4.478 + if(local_heap_cross_ref) {
4.479 + delete _heap_cross_ref;
4.480 + local_heap_cross_ref=false;
4.481 + }
4.482 + _heap_cross_ref = &crossRef;
4.483 + if(local_heap) {
4.484 + delete _heap;
4.485 + local_heap=false;
4.486 + }
4.487 + _heap = &heap;
4.488 + return *this;
4.489 + }
4.490 +
4.491 + public:
4.492 + ///\name Execution control
4.493 + ///The simplest way to execute the algorithm is to use
4.494 + ///one of the member functions called \c run(...).
4.495 + ///\n
4.496 + ///If you need more control on the execution,
4.497 + ///first you must call \ref init(), then you can add several source nodes
4.498 + ///with \ref addSource().
4.499 + ///Finally \ref start() will perform the actual path
4.500 + ///computation.
4.501 +
4.502 + ///@{
4.503 +
4.504 + ///\brief Initializes the internal data structures.
4.505 +
4.506 + ///Initializes the internal data structures.
4.507 + ///
4.508 + void init(){
4.509 + create_maps();
4.510 + _heap->clear();
4.511 + for ( NodeIt u(*graph) ; u!=INVALID ; ++u ) {
4.512 + _pred->set(u,INVALID);
4.513 + _processed->set(u,false);
4.514 + _heap_cross_ref->set(u,Heap::PRE_HEAP);
4.515 + }
4.516 + }
4.517 +
4.518 + ///\brief Adds a new source node.
4.519 +
4.520 + ///Adds a new source node to the priority heap.
4.521 + ///
4.522 + ///It checks if the node has already been added to the heap and
4.523 + ///it is pushed to the heap only if it was not in the heap.
4.524 + void addSource(Node s){
4.525 + if(_heap->state(s) != Heap::IN_HEAP) {
4.526 + _heap->push(s,Value());
4.527 + }
4.528 + }
4.529 + ///\brief Processes the next node in the priority heap
4.530 +
4.531 + ///Processes the next node in the priority heap.
4.532 + ///
4.533 + ///\return The processed node.
4.534 + ///
4.535 + ///\warning The priority heap must not be empty!
4.536 + Node processNextNode(){
4.537 + Node v=_heap->top();
4.538 + _heap->pop();
4.539 + _processed->set(v,true);
4.540 +
4.541 + for(IncEdgeIt e(*graph,v); e!=INVALID; ++e) {
4.542 + Node w=graph->oppositeNode(v,e);
4.543 + switch(_heap->state(w)) {
4.544 + case Heap::PRE_HEAP:
4.545 + _heap->push(w,(*cost)[e]);
4.546 + _pred->set(w,e);
4.547 + break;
4.548 + case Heap::IN_HEAP:
4.549 + if ( (*cost)[e] < (*_heap)[w] ) {
4.550 + _heap->decrease(w,(*cost)[e]);
4.551 + _pred->set(w,e);
4.552 + }
4.553 + break;
4.554 + case Heap::POST_HEAP:
4.555 + break;
4.556 + }
4.557 + }
4.558 + if ((*_pred)[v]!=INVALID)_tree->set((*_pred)[v],true);
4.559 + return v;
4.560 + }
4.561 +
4.562 + ///\brief Next node to be processed.
4.563 +
4.564 + ///Next node to be processed.
4.565 + ///
4.566 + ///\return The next node to be processed or INVALID if the priority heap
4.567 + /// is empty.
4.568 + Node nextNode(){
4.569 + return _heap->empty()?_heap->top():INVALID;
4.570 + }
4.571 +
4.572 + ///\brief Returns \c false if there are nodes to be processed in the priority heap
4.573 + ///
4.574 + ///Returns \c false if there are nodes
4.575 + ///to be processed in the priority heap
4.576 + bool emptyQueue() { return _heap->empty(); }
4.577 + ///\brief Returns the number of the nodes to be processed in the priority heap
4.578 +
4.579 + ///Returns the number of the nodes to be processed in the priority heap
4.580 + ///
4.581 + int queueSize() { return _heap->size(); }
4.582 +
4.583 + ///\brief Executes the algorithm.
4.584 +
4.585 + ///Executes the algorithm.
4.586 + ///
4.587 + ///\pre init() must be called and at least one node should be added
4.588 + ///with addSource() before using this function.
4.589 + ///
4.590 + ///This method runs the %Prim algorithm from the node(s)
4.591 + ///in order to compute the
4.592 + ///minimum spanning tree.
4.593 + ///
4.594 + void start(){
4.595 + while ( !_heap->empty() ) processNextNode();
4.596 + }
4.597 +
4.598 + ///\brief Executes the algorithm until a condition is met.
4.599 +
4.600 + ///Executes the algorithm until a condition is met.
4.601 + ///
4.602 + ///\pre init() must be called and at least one node should be added
4.603 + ///with addSource() before using this function.
4.604 + ///
4.605 + ///\param nm must be a bool (or convertible) node map. The algorithm
4.606 + ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
4.607 + template<class NodeBoolMap>
4.608 + void start(const NodeBoolMap &nm){
4.609 + while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
4.610 + if ( !_heap->empty() ) _processed->set(_heap->top(),true);
4.611 + }
4.612 +
4.613 + ///\brief Runs %Prim algorithm.
4.614 +
4.615 + ///This method runs the %Prim algorithm
4.616 + ///in order to compute the
4.617 + ///minimum spanning tree (or minimum spanning forest).
4.618 + ///The method also works on graphs that has more than one components.
4.619 + ///In this case it computes the minimum spanning forest.
4.620 + void run() {
4.621 + init();
4.622 + for(NodeIt it(*graph);it!=INVALID;++it){
4.623 + if(!processed(it)){
4.624 + addSource(it);
4.625 + start();
4.626 + }
4.627 + }
4.628 + }
4.629 +
4.630 + ///\brief Runs %Prim algorithm from node \c s.
4.631 +
4.632 + ///This method runs the %Prim algorithm from node \c s
4.633 + ///in order to
4.634 + ///compute the
4.635 + ///minimun spanning tree
4.636 + ///
4.637 + ///\note d.run(s) is just a shortcut of the following code.
4.638 + ///\code
4.639 + /// d.init();
4.640 + /// d.addSource(s);
4.641 + /// d.start();
4.642 + ///\endcode
4.643 + ///\note If the graph has more than one components, the method
4.644 + ///will compute the minimun spanning tree for only one component.
4.645 + ///
4.646 + ///See \ref run() if you want to compute the minimal spanning forest.
4.647 + void run(Node s){
4.648 + init();
4.649 + addSource(s);
4.650 + start();
4.651 + }
4.652 +
4.653 + ///@}
4.654 +
4.655 + ///\name Query Functions
4.656 + ///The result of the %Prim algorithm can be obtained using these
4.657 + ///functions.\n
4.658 + ///Before the use of these functions,
4.659 + ///either run() or start() must be called.
4.660 +
4.661 + ///@{
4.662 +
4.663 + ///\brief Returns the 'previous edge' of the minimum spanning tree.
4.664 +
4.665 + ///For a node \c v it returns the 'previous edge' of the minimum spanning tree,
4.666 + ///i.e. it returns the edge from where \c v was reached. For a source node
4.667 + ///or an unreachable node it is \ref INVALID.
4.668 + ///The minimum spanning tree used here is equal to the minimum spanning tree used
4.669 + ///in \ref predNode(). \pre \ref run() or \ref start() must be called before
4.670 + ///using this function.
4.671 + UEdge predEdge(Node v) const { return (*_pred)[v]; }
4.672 +
4.673 + ///\brief Returns the 'previous node' of the minimum spanning tree.
4.674 +
4.675 + ///For a node \c v it returns the 'previous node' of the minimum spanning tree,
4.676 + ///i.e. it returns the node from where \c v was reached. For a source node
4.677 + ///or an unreachable node it is \ref INVALID.
4.678 + //The minimum spanning tree used here is equal to the minimum spanning
4.679 + ///tree used in \ref predEdge(). \pre \ref run() or \ref start() must be called
4.680 + ///before using this function.
4.681 + Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
4.682 + graph->source((*_pred)[v]); }
4.683 +
4.684 + ///\brief Returns a reference to the NodeMap of the edges of the minimum spanning tree.
4.685 +
4.686 + ///Returns a reference to the NodeMap of the edges of the
4.687 + ///minimum spanning tree.
4.688 + ///\pre \ref run() or \ref start() must be called before using this function.
4.689 + const PredMap &predMap() const { return *_pred;}
4.690 +
4.691 + ///\brief Returns a reference to the tree edges map.
4.692 +
4.693 + ///Returns a reference to the TreeEdgeMap of the edges of the
4.694 + ///minimum spanning tree. The value of the map is \c true only if the edge is in
4.695 + ///the minimum spanning tree.
4.696 + ///\warning By default, the TreeEdgeMap is a NullMap.
4.697 + ///
4.698 + ///If it is not set before the execution of the algorithm, use the \ref
4.699 + ///treeMap(TreeMap&) function (after the execution) to set an UEdgeMap with the
4.700 + ///edges of the minimum spanning tree in O(n) time where n is the number of
4.701 + ///nodes in the graph.
4.702 + ///\pre \ref run() or \ref start() must be called before using this function.
4.703 + const TreeMap &treeMap() const { return *_tree;}
4.704 +
4.705 + ///\brief Sets the tree edges map.
4.706 +
4.707 + ///Sets the TreeMap of the edges of the minimum spanning tree.
4.708 + ///The map values belonging to the edges of the minimum
4.709 + ///spanning tree are set to \param tree_edge_value or \c true by default,
4.710 + ///the other map values remain untouched.
4.711 + ///
4.712 + ///\pre \ref run() or \ref start() must be called before using this function.
4.713 +
4.714 + template<class TreeMap>
4.715 + void quickTreeEdges(
4.716 + TreeMap& tree,
4.717 + const typename TreeMap::Value& tree_edge_value=true) const {
4.718 + for(NodeIt i(*graph);i!=INVALID;++i){
4.719 + if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value);
4.720 + }
4.721 + }
4.722 +
4.723 + ///\brief Sets the tree edges map.
4.724 +
4.725 + ///Sets the TreeMap of the edges of the minimum spanning tree.
4.726 + ///The map values belonging to the edges of the minimum
4.727 + ///spanning tree are set to \param tree_edge_value or \c true by default while
4.728 + ///the edge values not belonging to the minimum spanning tree are set to
4.729 + ///\param tree_default_value or \c false by default.
4.730 + ///
4.731 + ///\pre \ref run() or \ref start() must be called before using this function.
4.732 +
4.733 + template<class TreeMap>
4.734 + void treeEdges(
4.735 + TreeMap& tree,
4.736 + const typename TreeMap::Value& tree_edge_value=true,
4.737 + const typename TreeMap::Value& tree_default_value=false) const {
4.738 + for(typename ItemSetTraits<UGraph,UEdge>::ItemIt i(*graph);i!=INVALID;++i)
4.739 + tree.set(i,tree_default_value);
4.740 + for(NodeIt i(*graph);i!=INVALID;++i){
4.741 + if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value);
4.742 + }
4.743 + }
4.744 +
4.745 + ///\brief Checks if a node is reachable from the starting node.
4.746 +
4.747 + ///Returns \c true if \c v is reachable from the starting node.
4.748 + ///\warning The source nodes are inditated as unreached.
4.749 + ///\pre \ref run() or \ref start() must be called before using this function.
4.750 + ///
4.751 + bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
4.752 +
4.753 + ///\brief Checks if a node is processed.
4.754 +
4.755 + ///Returns \c true if \c v is processed, i.e. \c v is already connencted to the
4.756 + ///minimum spanning tree.
4.757 + ///\pre \ref run() or \ref start() must be called before using this function.
4.758 + ///
4.759 + bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
4.760 +
4.761 +
4.762 + ///\brief Checks if an edge is in the spanning tree or not.
4.763 +
4.764 + ///Checks if an edge is in the spanning tree or not.
4.765 + ///\param e is the edge that will be checked
4.766 + ///\return \c true if e is in the spanning tree, \c false otherwise
4.767 + bool tree(UEdge e){
4.768 + return (*_pred)[*graph.source(e)]==e || (*_pred)[*graph.target(e)]==e;
4.769 + }
4.770 + ///@}
4.771 + };
4.772 +
4.773 +
4.774 + /// \ingroup spantree
4.775 + ///
4.776 + /// \brief Function type interface for Prim algorithm.
4.777 + ///
4.778 + /// Function type interface for Prim algorithm.
4.779 + /// \param graph the UGraph that the algorithm runs on
4.780 + /// \param cost the CostMap of the edges
4.781 + /// \retval tree the EdgeMap that contains whether an edge is in
4.782 + /// the spanning tree or not
4.783 + ///
4.784 + ///\sa Prim
4.785 + template<class Graph,class CostMap,class TreeMap>
4.786 + void prim(const Graph& graph, const CostMap& cost,TreeMap& tree){
4.787 + typename Prim<Graph,CostMap>::template DefTreeMap<TreeMap>::
4.788 + Create prm(graph,cost);
4.789 + prm.treeMap(tree);
4.790 + prm.run();
4.791 + };
4.792 +
4.793 +} //END OF NAMESPACE LEMON
4.794 +
4.795 +#endif