# HG changeset patch # User deba # Date 1138349845 0 # Node ID d9205a71132458bf4a1fe832d58c61c3981d9cc2 # Parent c925a077cf7383689fb1abdeebddfc63ab499def Algorithms by szakall diff -r c925a077cf73 -r d9205a711324 lemon/Makefile.am --- a/lemon/Makefile.am Thu Jan 26 17:18:12 2006 +0000 +++ b/lemon/Makefile.am Fri Jan 27 08:17:25 2006 +0000 @@ -30,10 +30,12 @@ counter.h \ dijkstra.h \ dimacs.h \ + dag_shortest_path.h \ edge_set.h \ error.h \ fib_heap.h \ floyd_warshall.h \ + fredman_tarjan.h \ full_graph.h \ grid_graph.h \ graph_adaptor.h \ @@ -59,6 +61,7 @@ suurballe.h \ preflow.h \ path.h \ + prim.h \ radix_heap.h \ radix_sort.h \ smart_graph.h \ diff -r c925a077cf73 -r d9205a711324 lemon/dag_shortest_path.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lemon/dag_shortest_path.h Fri Jan 27 08:17:25 2006 +0000 @@ -0,0 +1,1082 @@ +/* -*- C++ -*- + * lemon/dag_shortest_path.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_DAG_SHORTEST_PATH_H +#define LEMON_DAG_SHORTEST_PATH_H + +///\ingroup flowalgs +/// \file +/// \brief DagShortestPath algorithm. +/// + +#include +#include +#include +#include +#include + +#include + +namespace lemon { + + /// \brief Default OperationTraits for the DagShortestPath algorithm class. + /// + /// It defines all computational operations and constants which are + /// used in the dag shortest path algorithm. The default implementation + /// is based on the numeric_limits class. If the numeric type does not + /// have infinity value then the maximum value is used as extremal + /// infinity value. + template < + typename Value, + bool has_infinity = std::numeric_limits::has_infinity> + struct DagShortestPathDefaultOperationTraits { + /// \brief Gives back the zero value of the type. + static Value zero() { + return static_cast(0); + } + /// \brief Gives back the positive infinity value of the type. + static Value infinity() { + return std::numeric_limits::infinity(); + } + /// \brief Gives back the sum of the given two elements. + static Value plus(const Value& left, const Value& right) { + return left + right; + } + /// \brief Gives back true only if the first value less than the second. + static bool less(const Value& left, const Value& right) { + return left < right; + } + }; + + template + struct DagShortestPathDefaultOperationTraits { + static Value zero() { + return static_cast(0); + } + static Value infinity() { + return std::numeric_limits::max(); + } + static Value plus(const Value& left, const Value& right) { + if (left == infinity() || right == infinity()) return infinity(); + return left + right; + } + static bool less(const Value& left, const Value& right) { + return left < right; + } + }; + + /// \brief Default traits class of DagShortestPath class. + /// + /// Default traits class of DagShortestPath class. + /// \param _Graph Graph type. + /// \param _LegthMap Type of length map. + template + struct DagShortestPathDefaultTraits { + /// The graph type the algorithm runs on. + typedef _Graph Graph; + + /// \brief The type of the map that stores the edge lengths. + /// + /// The type of the map that stores the edge lengths. + /// It must meet the \ref concept::ReadMap "ReadMap" concept. + typedef _LengthMap LengthMap; + + // The type of the length of the edges. + typedef typename _LengthMap::Value Value; + + /// \brief Operation traits for dag shortest path algorithm. + /// + /// It defines the infinity type on the given Value type + /// and the used operation. + /// \see DagShortestPathDefaultOperationTraits + typedef DagShortestPathDefaultOperationTraits OperationTraits; + + /// \brief The type of the map that stores the last edges of the + /// shortest paths. + /// + /// The type of the map that stores the last + /// edges of the shortest paths. + /// It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef typename Graph::template NodeMap PredMap; + + /// \brief Instantiates a PredMap. + /// + /// This function instantiates a \ref PredMap. + /// \param G is the graph, to which we would like to define the PredMap. + /// \todo The graph alone may be insufficient for the initialization + static PredMap *createPredMap(const _Graph& graph) { + return new PredMap(graph); + } + + /// \brief The type of the map that stores the dists of the nodes. + /// + /// The type of the map that stores the dists of the nodes. + /// It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef typename Graph::template NodeMap + DistMap; + + /// \brief Instantiates a DistMap. + /// + /// This function instantiates a \ref DistMap. + /// \param G is the graph, to which we would like to define the + /// \ref DistMap + static DistMap *createDistMap(const _Graph& graph) { + return new DistMap(graph); + } + + }; + + /// \brief Inverse OperationTraits for the DagShortestPath algorithm class. + /// + /// It defines all computational operations and constants which are + /// used in the dag shortest path algorithm. It is the inverse of + /// \ref DagShortestPathDefaultOperationTraits, so it can be used to + /// calculate the longest path. The default implementation + /// is based on the numeric_limits class. If the numeric type does not + /// have infinity value then the minimum value is used as extremal + /// infinity value. + template < + typename Value, + bool has_infinity = std::numeric_limits::has_infinity> + struct DagLongestPathOperationTraits { + /// \brief Gives back the zero value of the type. + static Value zero() { + return static_cast(0); + } + /// \brief Gives back the negative infinity value of the type. + static Value infinity() { + return -(std::numeric_limits::infinity()); + } + /// \brief Gives back the sum of the given two elements. + static Value plus(const Value& left, const Value& right) { + return left + right; + } + /// \brief Gives back true only if the first value less than the second. + static bool less(const Value& left, const Value& right) { + return left > right; + } + }; + + template + struct DagLongestPathOperationTraits { + static Value zero() { + return static_cast(0); + } + static Value infinity() { + return std::numeric_limits::min(); + } + static Value plus(const Value& left, const Value& right) { + if (left == infinity() || right == infinity()) return infinity(); + return left + right; + } + static bool less(const Value& left, const Value& right) { + return left > right; + } + }; + + /// \brief Inverse traits class of DagShortestPath class. + /// + /// Inverse traits class of DagShortestPath class. + /// \param _Graph Graph type. + /// \param _LegthMap Type of length map. + template + struct DagLongestPathTraits { + /// The graph type the algorithm runs on. + typedef _Graph Graph; + + /// \brief The type of the map that stores the edge lengths. + /// + /// The type of the map that stores the edge lengths. + /// It must meet the \ref concept::ReadMap "ReadMap" concept. + typedef _LengthMap LengthMap; + + // The type of the length of the edges. + typedef typename _LengthMap::Value Value; + + /// \brief Inverse operation traits for dag shortest path algorithm. + /// + /// It defines the infinity type on the given Value type + /// and the used operation. + /// \see DagLongestPathOperationTraits + typedef DagLongestPathOperationTraits OperationTraits; + + /// \brief The type of the map that stores the last edges of the + /// longest paths. + /// + /// The type of the map that stores the last + /// edges of the longest paths. + /// It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef typename Graph::template NodeMap PredMap; + + /// \brief Instantiates a PredMap. + /// + /// This function instantiates a \ref PredMap. + /// \param G is the graph, to which we would like to define the PredMap. + /// \todo The graph alone may be insufficient for the initialization + static PredMap *createPredMap(const _Graph& graph) { + return new PredMap(graph); + } + + /// \brief The type of the map that stores the dists of the nodes. + /// + /// The type of the map that stores the dists of the nodes. + /// It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef typename Graph::template NodeMap + DistMap; + + /// \brief Instantiates a DistMap. + /// + /// This function instantiates a \ref DistMap. + /// \param G is the graph, to which we would like to define the + /// \ref DistMap + static DistMap *createDistMap(const _Graph& graph) { + return new DistMap(graph); + } + + }; + + + /// \brief %DagShortestPath algorithm class. + /// + /// \ingroup flowalgs + /// This class provides an efficient implementation of a Dag sortest path + /// searching algorithm. The edge lengths are passed to the algorithm + /// using a \ref concept::ReadMap "ReadMap", so it is easy to change it + /// to any kind of length. + /// + /// The complexity of the algorithm is O(n + e). + /// + /// The type of the length is determined by the + /// \ref concept::ReadMap::Value "Value" of the length map. + /// + /// \param _Graph The graph type the algorithm runs on. The default value + /// is \ref ListGraph. The value of _Graph is not used directly by + /// DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits. + /// \param _LengthMap This read-only EdgeMap determines the lengths of the + /// edges. The default map type is \ref concept::StaticGraph::EdgeMap + /// "Graph::EdgeMap". The value of _LengthMap is not used directly + /// by DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits. + /// \param _Traits Traits class to set various data types used by the + /// algorithm. The default traits class is \ref DagShortestPathDefaultTraits + /// "DagShortestPathDefaultTraits<_Graph,_LengthMap>". See \ref + /// DagShortestPathDefaultTraits for the documentation of a DagShortestPath traits + /// class. + /// + /// \author Balazs Attila Mihaly (based on Balazs Dezso's work) + +#ifdef DOXYGEN + template +#else + template , + typename _Traits=DagShortestPathDefaultTraits<_Graph,_LengthMap> > +#endif + class DagShortestPath { + public: + + /// \brief \ref Exception for uninitialized parameters. + /// + /// This error represents problems in the initialization + /// of the parameters of the algorithms. + + class UninitializedParameter : public lemon::UninitializedParameter { + public: + virtual const char* exceptionName() const { + return "lemon::DagShortestPath::UninitializedParameter"; + } + }; + + typedef _Traits Traits; + ///The type of the underlying graph. + typedef typename _Traits::Graph Graph; + + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; + typedef typename Graph::Edge Edge; + typedef typename Graph::EdgeIt EdgeIt; + typedef typename Graph::OutEdgeIt OutEdgeIt; + + /// \brief The type of the length of the edges. + typedef typename _Traits::LengthMap::Value Value; + /// \brief The type of the map that stores the edge lengths. + typedef typename _Traits::LengthMap LengthMap; + /// \brief The type of the map that stores the last + /// edges of the shortest paths. + typedef typename _Traits::PredMap PredMap; + /// \brief The type of the map that stores the dists of the nodes. + typedef typename _Traits::DistMap DistMap; + /// \brief The operation traits. + typedef typename _Traits::OperationTraits OperationTraits; + /// \brief The Node weight map. + typedef typename Graph::NodeMap WeightMap; + private: + /// Pointer to the underlying graph + const Graph *graph; + /// Pointer to the length map + const LengthMap *length; + ///Pointer to the map of predecessors edges + PredMap *_pred; + ///Indicates if \ref _pred is locally allocated (\c true) or not + bool local_pred; + ///Pointer to the map of distances + DistMap *_dist; + ///Indicates if \ref _dist is locally allocated (\c true) or not + bool local_dist; + ///Process step counter + unsigned int _process_step; + + std::vector _node_order; + + /// Creates the maps if necessary. + void create_maps() { + if(!_pred) { + local_pred = true; + _pred = Traits::createPredMap(*graph); + } + if(!_dist) { + local_dist = true; + _dist = Traits::createDistMap(*graph); + } + } + + public : + + typedef DagShortestPath Create; + + /// \name Named template parameters + + ///@{ + + template + struct DefPredMapTraits : public Traits { + typedef T PredMap; + static PredMap *createPredMap(const Graph&) { + throw UninitializedParameter(); + } + }; + + /// \brief \ref named-templ-param "Named parameter" for setting PredMap + /// type + /// \ref named-templ-param "Named parameter" for setting PredMap type + /// + template + struct DefPredMap { + typedef DagShortestPath< Graph, LengthMap, DefPredMapTraits > Create; + }; + + template + struct DefDistMapTraits : public Traits { + typedef T DistMap; + static DistMap *createDistMap(const Graph& graph) { + throw UninitializedParameter(); + } + }; + + /// \brief \ref named-templ-param "Named parameter" for setting DistMap + /// type + /// + /// \ref named-templ-param "Named parameter" for setting DistMap type + /// + template + struct DefDistMap + : public DagShortestPath< Graph, LengthMap, DefDistMapTraits > { + typedef DagShortestPath< Graph, LengthMap, DefDistMapTraits > Create; + }; + + template + struct DefOperationTraitsTraits : public Traits { + typedef T OperationTraits; + }; + + /// \brief \ref named-templ-param "Named parameter" for setting + /// OperationTraits type + /// + /// \ref named-templ-param "Named parameter" for setting OperationTraits + /// type + template + struct DefOperationTraits + : public DagShortestPath< Graph, LengthMap, DefOperationTraitsTraits > { + typedef DagShortestPath< Graph, LengthMap, DefOperationTraitsTraits > + Create; + }; + + ///@} + + protected: + + DagShortestPath() {} + + public: + + /// \brief Constructor. + /// + /// \param _graph the graph the algorithm will run on. + /// \param _length the length map used by the algorithm. + DagShortestPath(const Graph& _graph, const LengthMap& _length) : + graph(&_graph), length(&_length), + _pred(0), local_pred(false), + _dist(0), local_dist(false){} + + /// \brief Constructor with node weight map. + /// + /// \param _graph the graph the algorithm will run on. + /// \param _length the length map used by the algorithm. + /// The NodeMap _length will be used as the weight map. + /// Each edge will have the weight of its target node. + DagShortestPath(const Graph& _graph, const WeightMap& _length) : + graph(&_graph), + _pred(0), local_pred(false), + _dist(0), local_dist(false){ + length=new LengthMap(_graph); + _dist=new DistMap(_graph); + for(EdgeIt eit(_graph);eit!=INVALID;++eit) + (const_cast(length))->set(eit,_length[_graph.target(eit)]); + } + + ///Destructor. + ~DagShortestPath() { + if(local_pred) delete _pred; + if(local_dist) delete _dist; + } + + /// \brief Sets the length map. + /// + /// Sets the length map. + /// \return \c (*this) + DagShortestPath &lengthMap(const LengthMap &m) { + length = &m; + return *this; + } + + /// \brief Sets the map storing the predecessor edges. + /// + /// Sets the map storing the predecessor edges. + /// If you don't use this function before calling \ref run(), + /// it will allocate one. The destuctor deallocates this + /// automatically allocated map, of course. + /// \return \c (*this) + DagShortestPath &predMap(PredMap &m) { + if(local_pred) { + delete _pred; + local_pred=false; + } + _pred = &m; + return *this; + } + + /// \brief Sets the map storing the distances calculated by the algorithm. + /// + /// Sets the map storing the distances calculated by the algorithm. + /// If you don't use this function before calling \ref run(), + /// it will allocate one. The destuctor deallocates this + /// automatically allocated map, of course. + /// \return \c (*this) + DagShortestPath &distMap(DistMap &m) { + if(local_dist) { + delete _dist; + local_dist=false; + } + _dist = &m; + return *this; + } + + /// \name Execution control + /// The simplest way to execute the algorithm is to use + /// one of the member functions called \c run(...) + /// \n + /// If you need more control on the execution, + /// first you must call \ref init(...), then you can add several source + /// nodes with \ref addSource(). + /// Finally \ref start() will perform the actual path computation. + /// Some functions have an alternative form (\ref checkedInit(...), + /// \ref checkedRun(...)) which also verifies if the graph given in the + /// constructor is a dag. + + ///@{ + + /// \brief Initializes the internal data structures. + /// + /// Initializes the internal data structures. + void init(const Value value = OperationTraits::infinity()) { + typedef typename Graph::template NodeMap NodeOrderMap; + _process_step=0; + NodeOrderMap node_order(*graph); + topologicalSort(*graph,node_order); + _node_order.resize(countNodes(*graph),INVALID); + create_maps(); + for (NodeIt it(*graph); it != INVALID; ++it) { + _node_order[node_order[it]]=it; + _pred->set(it, INVALID); + _dist->set(it, value); + } + } + + /// \brief Initializes the internal data structures + /// with a given topological sort (NodeMap). + /// + /// Initializes the internal data structures + /// with a given topological sort (NodeMap). + void init(const typename Graph::template NodeMap& node_order, + const Value value = OperationTraits::infinity()) { + _process_step=0; + _node_order.resize(countNodes(*graph),INVALID); + create_maps(); + for (NodeIt it(*graph); it != INVALID; ++it) { + _node_order[node_order[it]]=it; + _pred->set(it, INVALID); + _dist->set(it, value); + } + } + + /// \brief Initializes the internal data structures + /// with a given topological sort (std::vector). + /// + /// Initializes the internal data structures + /// with a given topological sort (std::vector). + void init(const std::vector& node_order, + const Value value = OperationTraits::infinity()) { + _process_step=0; + _node_order=node_order; + create_maps(); + for (NodeIt it(*graph); it != INVALID; ++it) { + _pred->set(it, INVALID); + _dist->set(it, value); + } + } + + /// \brief Initializes the internal data structures. It also checks if the graph is dag. + /// + /// Initializes the internal data structures. It also checks if the graph is dag. + /// \return true if the graph (given in the constructor) is dag, false otherwise. + bool checkedInit(const Value value = OperationTraits::infinity()) { + typedef typename Graph::template NodeMap NodeOrderMap; + NodeOrderMap node_order(*graph); + if(!checkedTopologicalSort(*graph,node_order))return false; + init(node_order,value); + return true; + } + + /// \brief Initializes the internal data structures with a given + /// topological sort (NodeMap). It also checks if the graph is dag. + /// + /// Initializes the internal data structures with a given + /// topological sort (NodeMap). It also checks if the graph is dag. + /// \return true if the graph (given in the constructor) is dag, false otherwise. + bool checkedInit(const typename Graph::template NodeMap& node_order, + const Value value = OperationTraits::infinity()) { + for(NodeIt it(*graph);it!=INVALID;++it){ + for(OutEdgeIt oeit(*graph,it);oeit!=INVALID;++oeit){ + if(node_order[graph->target(oeit)]& node_order, + const Value value = OperationTraits::infinity()) { + typedef typename Graph::template NodeMap BoolNodeMap; + BoolNodeMap _processed(*graph,false); + for(unsigned int i=0;i<_node_order.size();++i){ + _processed[node_order[i]]=true; + for(OutEdgeIt oeit(*graph,node_order[i]);oeit!=INVALID;++oeit){ + if(_processed[graph->target(oeit)])return false; + } + } + init(node_order,value); + return true; + } + + /// \brief Adds a new source node. + /// + /// The optional second parameter is the initial distance of the node. + /// It just sets the distance of the node to the given value. + void addSource(Node source, Value dst = OperationTraits::zero()) { + if((*_dist)[source] != dst){ + _dist->set(source, dst); + } + } + + /// \brief Executes one step from the dag shortest path algorithm. + /// + /// If the algoritm calculated the distances in the previous step + /// strictly for all at most k length paths then it will calculate the + /// distances strictly for all at most k + 1 length paths. With k + /// iteration this function calculates the at most k length paths. + ///\pre the queue is not empty + ///\return the currently processed node + Node processNextNode() { + if(reached(_node_order[_process_step])){ + for (OutEdgeIt it(*graph, _node_order[_process_step]); it != INVALID; ++it) { + Node target = graph->target(it); + Value relaxed = + OperationTraits::plus((*_dist)[_node_order[_process_step]], (*length)[it]); + if (OperationTraits::less(relaxed, (*_dist)[target])) { + _pred->set(target, it); + _dist->set(target, relaxed); + } + } + } + ++_process_step; + return _node_order[_process_step-1]; + } + + ///\brief Returns \c false if there are nodes + ///to be processed in the queue + /// + ///Returns \c false if there are nodes + ///to be processed in the queue + bool emptyQueue() { return _node_order.size()-1==_process_step; } + + ///\brief Returns the number of the nodes to be processed. + /// + ///Returns the number of the nodes to be processed in the queue. + int queueSize() { return _node_order.size()-1-_process_step; } + + /// \brief Executes the algorithm. + /// + /// \pre init() must be called and at least one node should be added + /// with addSource() before using this function. + /// + /// This method runs the %DagShortestPath algorithm from the root node(s) + /// in order to compute the shortest path to each node. The algorithm + /// computes + /// - The shortest path tree. + /// - The distance of each node from the root(s). + void start() { + while(!emptyQueue()) { + processNextNode(); + } + } + + /// \brief Runs %DagShortestPath algorithm from node \c s. + /// + /// This method runs the %DagShortestPath algorithm from a root node \c s + /// in order to compute the shortest path to each node. The algorithm + /// computes + /// - The shortest path tree. + /// - The distance of each node from the root. + /// + /// \note d.run(s) is just a shortcut of the following code. + /// \code + /// d.init(); + /// d.addSource(s); + /// d.start(); + /// \endcode + void run(Node s) { + init(); + addSource(s); + start(); + } + + /// \brief Runs %DagShortestPath algorithm from node \c s. + /// It also checks if the graph is a dag. + /// + /// This method runs the %DagShortestPath algorithm from a root node \c s + /// in order to compute the shortest path to each node. The algorithm + /// computes + /// - The shortest path tree. + /// - The distance of each node from the root. + /// The algorithm checks if the graph given int the constructor is a dag. + bool checkedRun(Node s) { + if(!checkedInit())return false; + addSource(s); + start(); + return true; + } + + ///@} + + /// \name Query Functions + /// The result of the %DagShortestPath algorithm can be obtained using these + /// functions.\n + /// Before the use of these functions, + /// either run() or start() must be called. + + ///@{ + + /// \brief Copies the shortest path to \c t into \c p + /// + /// This function copies the shortest path to \c t into \c p. + /// If it \c t is a source itself or unreachable, then it does not + /// alter \c p. + /// + /// \return Returns \c true if a path to \c t was actually copied to \c p, + /// \c false otherwise. + /// \sa DirPath + template + bool getPath(Path &p, Node t) { + if(reached(t)) { + p.clear(); + typename Path::Builder b(p); + for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t)) + b.pushFront(predEdge(t)); + b.commit(); + return true; + } + return false; + } + + /// \brief The distance of a node from the root. + /// + /// Returns the distance of a node from the root. + /// \pre \ref run() must be called before using this function. + /// \warning If node \c v in unreachable from the root the return value + /// of this funcion is undefined. + Value dist(Node v) const { return (*_dist)[v]; } + + /// \brief Returns the 'previous edge' of the shortest path tree. + /// + /// For a node \c v it returns the 'previous edge' of the shortest path + /// tree, i.e. it returns the last edge of a shortest path from the root + /// to \c v. It is \ref INVALID if \c v is unreachable from the root or + /// if \c v=s. The shortest path tree used here is equal to the shortest + /// path tree used in \ref predNode(). + /// \pre \ref run() must be called before using + /// this function. + Edge predEdge(Node v) const { return (*_pred)[v]; } + + /// \brief Returns the 'previous node' of the shortest path tree. + /// + /// For a node \c v it returns the 'previous node' of the shortest path + /// tree, i.e. it returns the last but one node from a shortest path from + /// the root to \c /v. It is INVALID if \c v is unreachable from the root + /// or if \c v=s. The shortest path tree used here is equal to the + /// shortest path tree used in \ref predEdge(). \pre \ref run() must be + /// called before using this function. + Node predNode(Node v) const { + return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]); + } + + /// \brief Returns a reference to the NodeMap of distances. + /// + /// Returns a reference to the NodeMap of distances. \pre \ref run() must + /// be called before using this function. + const DistMap &distMap() const { return *_dist;} + + /// \brief Returns a reference to the shortest path tree map. + /// + /// Returns a reference to the NodeMap of the edges of the + /// shortest path tree. + /// \pre \ref run() must be called before using this function. + const PredMap &predMap() const { return *_pred; } + + /// \brief Checks if a node is reachable from the root. + /// + /// Returns \c true if \c v is reachable from the root. + /// \pre \ref run() must be called before using this function. + /// + bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); } + + ///@} + }; + + /// \brief Default traits class of DagShortestPath function. + /// + /// Default traits class of DagShortestPath function. + /// \param _Graph Graph type. + /// \param _LengthMap Type of length map. + template + struct DagShortestPathWizardDefaultTraits { + /// \brief The graph type the algorithm runs on. + typedef _Graph Graph; + + /// \brief The type of the map that stores the edge lengths. + /// + /// The type of the map that stores the edge lengths. + /// It must meet the \ref concept::ReadMap "ReadMap" concept. + typedef _LengthMap LengthMap; + + /// \brief The value type of the length map. + typedef typename _LengthMap::Value Value; + + /// \brief Operation traits for dag shortest path algorithm. + /// + /// It defines the infinity type on the given Value type + /// and the used operation. + /// \see DagShortestPathDefaultOperationTraits + typedef DagShortestPathDefaultOperationTraits OperationTraits; + + /// \brief The type of the map that stores the last + /// edges of the shortest paths. + /// + /// The type of the map that stores the last + /// edges of the shortest paths. + /// It must meet the \ref concept::WriteMap "WriteMap" concept. + typedef NullMap PredMap; + + /// \brief Instantiates a PredMap. + /// + /// This function instantiates a \ref PredMap. + static PredMap *createPredMap(const _Graph &) { + return new PredMap(); + } + /// \brief The type of the map that stores the dists of the nodes. + /// + /// The type of the map that stores the dists of the nodes. + /// It must meet the \ref concept::WriteMap "WriteMap" concept. + typedef NullMap DistMap; + /// \brief Instantiates a DistMap. + /// + /// This function instantiates a \ref DistMap. + static DistMap *createDistMap(const _Graph &) { + return new DistMap(); + } + }; + + /// \brief Default traits used by \ref DagShortestPathWizard + /// + /// To make it easier to use DagShortestPath algorithm + /// we have created a wizard class. + /// This \ref DagShortestPathWizard class needs default traits, + /// as well as the \ref DagShortestPath class. + /// The \ref DagShortestPathWizardBase is a class to be the default traits of the + /// \ref DagShortestPathWizard class. + /// \todo More named parameters are required... + template + class DagShortestPathWizardBase + : public DagShortestPathWizardDefaultTraits<_Graph,_LengthMap> { + + typedef DagShortestPathWizardDefaultTraits<_Graph,_LengthMap> Base; + protected: + /// Type of the nodes in the graph. + typedef typename Base::Graph::Node Node; + + /// Pointer to the underlying graph. + void *_graph; + /// Pointer to the length map + void *_length; + ///Pointer to the map of predecessors edges. + void *_pred; + ///Pointer to the map of distances. + void *_dist; + ///Pointer to the source node. + Node _source; + + public: + /// Constructor. + + /// This constructor does not require parameters, therefore it initiates + /// all of the attributes to default values (0, INVALID). + DagShortestPathWizardBase() : _graph(0), _length(0), _pred(0), + _dist(0), _source(INVALID) {} + + /// Constructor. + + /// This constructor requires some parameters, + /// listed in the parameters list. + /// Others are initiated to 0. + /// \param graph is the initial value of \ref _graph + /// \param length is the initial value of \ref _length + /// \param source is the initial value of \ref _source + DagShortestPathWizardBase(const _Graph& graph, + const _LengthMap& length, + Node source = INVALID) : + _graph((void *)&graph), _length((void *)&length), _pred(0), + _dist(0), _source(source) {} + + }; + + /// A class to make the usage of DagShortestPath algorithm easier + + /// This class is created to make it easier to use DagShortestPath algorithm. + /// It uses the functions and features of the plain \ref DagShortestPath, + /// but it is much simpler to use it. + /// + /// Simplicity means that the way to change the types defined + /// in the traits class is based on functions that returns the new class + /// and not on templatable built-in classes. + /// When using the plain \ref DagShortestPath + /// the new class with the modified type comes from + /// the original class by using the :: + /// operator. In the case of \ref DagShortestPathWizard only + /// a function have to be called and it will + /// return the needed class. + /// + /// It does not have own \ref run method. When its \ref run method is called + /// it initiates a plain \ref DagShortestPath class, and calls the \ref + /// DagShortestPath::run() method of it. + template + class DagShortestPathWizard : public _Traits { + typedef _Traits Base; + + ///The type of the underlying graph. + typedef typename _Traits::Graph Graph; + + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; + typedef typename Graph::Edge Edge; + typedef typename Graph::OutEdgeIt EdgeIt; + + ///The type of the map that stores the edge lengths. + typedef typename _Traits::LengthMap LengthMap; + + ///The type of the length of the edges. + typedef typename LengthMap::Value Value; + + ///\brief The type of the map that stores the last + ///edges of the shortest paths. + typedef typename _Traits::PredMap PredMap; + + ///The type of the map that stores the dists of the nodes. + typedef typename _Traits::DistMap DistMap; + + public: + /// Constructor. + DagShortestPathWizard() : _Traits() {} + + /// \brief Constructor that requires parameters. + /// + /// Constructor that requires parameters. + /// These parameters will be the default values for the traits class. + DagShortestPathWizard(const Graph& graph, const LengthMap& length, + Node source = INVALID) + : _Traits(graph, length, source) {} + + /// \brief Copy constructor + DagShortestPathWizard(const _Traits &b) : _Traits(b) {} + + ~DagShortestPathWizard() {} + + /// \brief Runs DagShortestPath algorithm from a given node. + /// + /// Runs DagShortestPath algorithm from a given node. + /// The node can be given by the \ref source function. + void run() { + if(Base::_source == INVALID) throw UninitializedParameter(); + DagShortestPath + bf(*(Graph*)Base::_graph, *(LengthMap*)Base::_length); + if (Base::_pred) bf.predMap(*(PredMap*)Base::_pred); + if (Base::_dist) bf.distMap(*(DistMap*)Base::_dist); + bf.run(Base::_source); + } + + /// \brief Runs DagShortestPath algorithm from the given node. + /// + /// Runs DagShortestPath algorithm from the given node. + /// \param s is the given source. + void run(Node source) { + Base::_source = source; + run(); + } + + template + struct DefPredMapBase : public Base { + typedef T PredMap; + static PredMap *createPredMap(const Graph &) { return 0; }; + DefPredMapBase(const _Traits &b) : _Traits(b) {} + }; + + ///\brief \ref named-templ-param "Named parameter" + ///function for setting PredMap type + /// + /// \ref named-templ-param "Named parameter" + ///function for setting PredMap type + /// + template + DagShortestPathWizard > predMap(const T &t) + { + Base::_pred=(void *)&t; + return DagShortestPathWizard >(*this); + } + + template + struct DefDistMapBase : public Base { + typedef T DistMap; + static DistMap *createDistMap(const Graph &) { return 0; }; + DefDistMapBase(const _Traits &b) : _Traits(b) {} + }; + + ///\brief \ref named-templ-param "Named parameter" + ///function for setting DistMap type + /// + /// \ref named-templ-param "Named parameter" + ///function for setting DistMap type + /// + template + DagShortestPathWizard > distMap(const T &t) { + Base::_dist=(void *)&t; + return DagShortestPathWizard >(*this); + } + + template + struct DefOperationTraitsBase : public Base { + typedef T OperationTraits; + DefOperationTraitsBase(const _Traits &b) : _Traits(b) {} + }; + + ///\brief \ref named-templ-param "Named parameter" + ///function for setting OperationTraits type + /// + /// \ref named-templ-param "Named parameter" + ///function for setting OperationTraits type + /// + template + DagShortestPathWizard > distMap() { + return DagShortestPathWizard >(*this); + } + + /// \brief Sets the source node, from which the DagShortestPath algorithm runs. + /// + /// Sets the source node, from which the DagShortestPath algorithm runs. + /// \param s is the source node. + DagShortestPathWizard<_Traits>& source(Node source) { + Base::_source = source; + return *this; + } + + }; + + /// \brief Function type interface for DagShortestPath algorithm. + /// + /// \ingroup flowalgs + /// Function type interface for DagShortestPath algorithm. + /// + /// This function also has several \ref named-templ-func-param + /// "named parameters", they are declared as the members of class + /// \ref DagShortestPathWizard. + /// The following + /// example shows how to use these parameters. + /// \code + /// dagShortestPath(g,length,source).predMap(preds).run(); + /// \endcode + /// \warning Don't forget to put the \ref DagShortestPathWizard::run() "run()" + /// to the end of the parameter list. + /// \sa DagShortestPathWizard + /// \sa DagShortestPath + template + DagShortestPathWizard > + dagShortestPath(const _Graph& graph, + const _LengthMap& length, + typename _Graph::Node source = INVALID) { + return DagShortestPathWizard > + (graph, length, source); + } + +} //END OF NAMESPACE LEMON + +#endif + diff -r c925a077cf73 -r d9205a711324 lemon/fredman_tarjan.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lemon/fredman_tarjan.h Fri Jan 27 08:17:25 2006 +0000 @@ -0,0 +1,509 @@ +/* -*- C++ -*- + * lemon/fredman_tarjan.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_FREDMAN_TARJAN_H +#define LEMON_FREDMAN_TARJAN_H + +///\ingroup spantree +///\file +///\brief FredmanTarjan algorithm to compute minimum spanning forest. + +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +namespace lemon { + + ///Default traits class of FredmanTarjan class. + + ///Default traits class of FredmanTarjan class. + ///\param GR Graph type. + ///\param LM Type of cost map. + template + struct FredmanTarjanDefaultTraits{ + ///The graph type the algorithm runs on. + typedef GR UGraph; + ///The type of the map that stores the edge costs. + + ///The type of the map that stores the edge costs. + ///It must meet the \ref concept::ReadMap "ReadMap" concept. + typedef LM CostMap; + //The type of the cost of the edges. + typedef typename LM::Value Value; + ///The type of the map that stores whether an edge is in the + ///spanning tree or not. + + ///The type of the map that stores whether an edge is in the + ///spanning tree or not. + ///It must meet the \ref concept::ReadWriteMap "ReadWriteMap" concept. + ///By default it is a BoolEdgeMap. + typedef typename UGraph::template UEdgeMap TreeMap; + ///Instantiates a TreeMap. + + ///This function instantiates a \ref TreeMap. + ///\param g is the graph, to which + ///we would like to define the \ref TreeMap + static TreeMap *createTreeMap(const GR &_graph){ + return new TreeMap(_graph); + } + }; + + ///%FredmanTarjan algorithm class to find a minimum spanning tree. + + /// \ingroup spantree + ///This class provides an efficient implementation of %FredmanTarjan algorithm + ///whitch is sometimes a bit quicker than the Prim algorithm on larger graphs. + ///Due to the structure of the algorithm, it has less controll functions than + ///Prim. + /// + ///The running time is O(e*B(e,n)) where e is the number of edges, n is the + ///number of nodes in the graph and B(e,n) is min { i | log^(i) n <= e/n} + ///( log^(i+1) n = log(log^(i)) n ) + /// + ///The edge costs are passed to the algorithm using a + ///\ref concept::ReadMap "ReadMap", + ///so it is easy to change it to any kind of cost. + /// + ///The type of the cost is determined by the + ///\ref concept::ReadMap::Value "Value" of the cost map. + /// + ///\param GR The graph type the algorithm runs on. The default value + ///is \ref ListUGraph. The value of GR is not used directly by + ///FredmanTarjan, it is only passed to \ref FredmanTarjanDefaultTraits. + /// + ///\param LM This read-only UEdgeMap determines the costs of the + ///edges. It is read once for each edge, so the map may involve in + ///relatively time consuming process to compute the edge cost if + ///it is necessary. The default map type is \ref + ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap". The value + ///of LM is not used directly by FredmanTarjan, it is only passed to \ref + ///FredmanTarjanDefaultTraits. + /// + ///\param TR Traits class to set + ///various data types used by the algorithm. The default traits + ///class is \ref FredmanTarjanDefaultTraits + ///"FredmanTarjanDefaultTraits". See \ref + ///FredmanTarjanDefaultTraits for the documentation of a FredmanTarjan traits + ///class. + /// + ///\author Balazs Attila Mihaly + +#ifdef DOXYGEN + template +#else + template , + typename TR=FredmanTarjanDefaultTraits > +#endif + class FredmanTarjan { + public: + /** + * \brief \ref Exception for uninitialized parameters. + * + * This error represents problems in the initialization + * of the parameters of the algorithms. + */ + class UninitializedParameter : public lemon::UninitializedParameter { + public: + virtual const char* exceptionName() const { + return "lemon::FredmanTarjan::UninitializedParameter"; + } + }; + + typedef GR Graph; + typedef TR Traits; + ///The type of the underlying graph. + typedef typename TR::UGraph UGraph; + ///\e + typedef typename UGraph::Node Node; + ///\e + typedef typename UGraph::NodeIt NodeIt; + ///\e + typedef typename UGraph::UEdge UEdge; + ///\e + typedef typename UGraph::UEdgeIt UEdgeIt; + ///\e + typedef typename UGraph::IncEdgeIt IncEdgeIt; + + ///The type of the cost of the edges. + typedef typename TR::CostMap::Value Value; + ///The type of the map that stores the edge costs. + typedef typename TR::CostMap CostMap; + ///Edges of the spanning tree. + typedef typename TR::TreeMap TreeMap; + private: + ///Pointer to the underlying graph. + const UGraph *graph; + ///Pointer to the cost map + const CostMap *cost; + ///Pointer to the map of tree edges. + TreeMap *_tree; + ///Indicates if \ref _tree is locally allocated (\c true) or not. + bool local_tree; + + ///Creates the maps if necessary. + + void create_maps(){ + if(!_tree){ + local_tree=true; + _tree=Traits::createTreeMap(*graph); + } + } + + public : + + typedef FredmanTarjan Create; + + ///\name Named template parameters + + ///@{ + + template + struct DefTreeMapTraits : public Traits { + typedef TM TreeMap; + static TreeMap *createTreeMap(const UGraph &) { + throw UninitializedParameter(); + } + }; + ///\ref named-templ-param "Named parameter" for setting TreeMap + + ///\ref named-templ-param "Named parameter" for setting TreeMap + /// + template + struct DefTreeMap + : public FredmanTarjan< UGraph, CostMap, DefTreeMapTraits > { + typedef FredmanTarjan< UGraph, CostMap, DefTreeMapTraits > Create; + }; + + ///@} + + + protected: + + FredmanTarjan() {} + + private: + + template + void processNextTree(const SrcGraph& graph,const OrigMap& orig,Heap &heap, + ProcessedMap& processed,PredMap& pred,int& tree_counter,const int limit){ + std::vector tree_nodes; + int tree_index=tree_counter; + bool stop=false; + while(!heap.empty() && !stop){ + typename SrcGraph::Node v=heap.top(); + heap.pop(); + if(processed[v]!=-1){ + heap.state(v,Heap::PRE_HEAP); + tree_index=processed[v]; + _tree->set(orig[pred[v]],true); + stop=true; + break; + } + tree_nodes.push_back(v); + for(typename SrcGraph::IncEdgeIt e(graph,v);e!=INVALID;++e){ + typename SrcGraph::Node w=graph.oppositeNode(v,e); + switch(heap.state(w)){ + case Heap::PRE_HEAP: + if(heap.size()>=limit){ + stop=true; + } + else{ + heap.push(w,(*cost)[orig[e]]); + pred.set(w,e); + } + break; + case Heap::IN_HEAP: + if ((*cost)[orig[e]]set(orig[pred[tree_nodes[i]]],true); + processed.set(tree_nodes[i],tree_index); + heap.state(tree_nodes[i], Heap::PRE_HEAP); + } + processed.set(tree_nodes[0],tree_index); + heap.state(tree_nodes[0],Heap::PRE_HEAP); + while (!heap.empty()) { + typename SrcGraph::Node v=heap.top(); + heap.pop(); + heap.state(v,Heap::PRE_HEAP); + } + if(!stop)++tree_counter; + } + + template + void createTrees(const SrcGraph& graph,const OrigMap& orig, ProcessedMap& processed, + int edgenum,int& tree_counter){ + typedef typename SrcGraph::Node Node; + typedef typename SrcGraph::UEdge UEdge; + typedef typename SrcGraph::NodeIt NodeIt; + typedef typename SrcGraph::template NodeMap HeapCrossRef; + typedef typename SrcGraph::template NodeMap PredMap; + HeapCrossRef crossref(graph,-1); + FibHeap heap(crossref); + PredMap pred(graph,INVALID); + int rate=2*edgenum/countNodes(graph); + int limit=(rate>std::numeric_limits::digits)?std::numeric_limits::max():(1< + void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig,DestGraph& destgraph, + DestOrigMap& destorig,const ProcessedMap& processed,const int tree_counter){ + typedef typename SrcGraph::Node Node; + typedef typename DestGraph::Node DNode; + typedef typename SrcGraph::UEdge UEdge; + typedef typename DestGraph::UEdge DUEdge; + typedef typename SrcGraph::Edge Edge; + typedef typename SrcGraph::EdgeIt EdgeIt; + std::vector edges; + std::vector nodes(tree_counter, INVALID); + for(EdgeIt i(srcgraph);i!=INVALID;++i){ + if(processed[srcgraph.source(i)](*cost)[srcorig[edges[i+1]]]) { + minval=(*cost)[srcorig[edges[i+1]]]; + minpos=edges[i+1]; + } + ++i; + } + destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=srcorig[minpos]; + } + } + + template + void phase(const SrcGraph& graph,const OrigMap& orig,int edgenum){ + int tree_counter = 0; + typename SrcGraph::template NodeMap processed(graph,-1); + SmartUGraph destgraph; + SmartUGraph::UEdgeMap destorig(destgraph); + createTrees(graph,orig,processed,edgenum,tree_counter); + collect(graph,orig,destgraph,destorig,processed,tree_counter); + if (countNodes(destgraph)>1) { + phase(destgraph,destorig,edgenum); + } + } + + public: + + ///Constructor. + + ///\param _graph the graph the algorithm will run on. + ///\param _cost the cost map used by the algorithm. + FredmanTarjan(const UGraph& _graph, const CostMap& _cost) : + graph(&_graph), cost(&_cost), + _tree(0), local_tree(false) + { + checkConcept(); + } + + ///Destructor. + ~FredmanTarjan(){ + if(local_tree) delete _tree; + } + + ///Sets the cost map. + + ///Sets the cost map. + ///\return (*this) + FredmanTarjan &costMap(const CostMap &m){ + cost = &m; + return *this; + } + + ///Sets the map storing the tree edges. + + ///Sets the map storing the tree edges. + ///If you don't use this function before calling \ref run(), + ///it will allocate one. The destuctor deallocates this + ///automatically allocated map, of course. + ///By default this is a BoolEdgeMap. + ///\return (*this) + FredmanTarjan &treeMap(TreeMap &m){ + if(local_tree) { + delete _tree; + local_tree=false; + } + _tree = &m; + return *this; + } + + public: + ///\name Execution control + ///The simplest way to execute the algorithm is to use + ///one of the member functions called \c run(...). + + ///@{ + + ///Initializes the internal data structures. + + ///Initializes the internal data structures. + /// + void init(){ + create_maps(); + for(typename Graph::UEdgeIt i(*graph);i!=INVALID;++i){ + _tree->set(i,false); + } + } + + ///Executes the algorithm. + + ///Executes the algorithm. + /// + ///\pre init() must be called and at least one node should be added + ///with addSource() before using this function. + /// + ///This method runs the %FredmanTarjan algorithm from the node(s) + ///in order to compute the + ///minimum spanning tree. + void start(){ + phase(*graph,identityMap(),countEdges(*graph)); + } + + ///Runs %FredmanTarjan algorithm. + + ///This method runs the %FredmanTarjan algorithm + ///in order to compute the minimum spanning forest. + /// + ///\note ft.run() is just a shortcut of the following code. + ///\code + /// ft.init(); + /// ft.start(); + ///\endcode + void run() { + init(); + start(); + } + + ///@} + + ///\name Query Functions + ///The result of the %FredmanTarjan algorithm can be obtained using these + ///functions.\n + ///Before the use of these functions, + ///either run() or start() must be called. + + ///@{ + + ///Returns a reference to the tree edges map. + + ///Returns a reference to the TreeEdgeMap of the edges of the + ///minimum spanning tree. The value of the map is \c true only if the + ///edge is in the minimum spanning tree. + /// + ///\pre \ref run() or \ref start() must be called before using this + ///function. + const TreeMap &treeMap() const { return *_tree;} + + ///Sets the tree edges map. + + ///Sets the TreeMap of the edges of the minimum spanning tree. + ///The map values belonging to the edges of the minimum + ///spanning tree are set to \param tree_edge_value or \c true by default + ///while the edge values not belonging to the minimum spanning tree are + ///set to + ///\param tree_default_value or \c false by default. + /// + ///\pre \ref run() or \ref start() must be called before using this + ///function. + + template + void treeEdges( + TreeMap& tree, + const typename TreeMap::Value& tree_edge_value=true, + const typename TreeMap::Value& tree_default_value=false) const { + for(typename UGraph::UEdgeIt i(*graph);i!=INVALID;++i){ + (*_tree)[i]?tree.set(i,tree_edge_value):tree.set(i,tree_default_value); + } + } + + ///\brief Checks if an edge is in the spanning tree or not. + + ///Checks if an edge is in the spanning tree or not. + ///\param e is the edge that will be checked + ///\return \c true if e is in the spanning tree, \c false otherwise + bool tree(UEdge e){ + return (*_tree)[e]; + } + ///@} + }; + + /// \ingroup spantree + /// + /// \brief Function type interface for FredmanTarjan algorithm. + /// + /// Function type interface for FredmanTarjan algorithm. + /// \param graph the UGraph that the algorithm runs on + /// \param cost the CostMap of the edges + /// \retval tree the EdgeMap that contains whether an edge is in the + /// spanning tree or not + /// + /// \sa Prim + template + void fredmanTarjan(const Graph& graph, const CostMap& cost,TreeMap& tree){ + typename FredmanTarjan::template DefTreeMap:: + Create ft(graph,cost); + ft.treeMap(tree); + ft.run(); + }; + +} //END OF NAMESPACE LEMON + +#endif diff -r c925a077cf73 -r d9205a711324 lemon/prim.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lemon/prim.h Fri Jan 27 08:17:25 2006 +0000 @@ -0,0 +1,792 @@ +/* -*- C++ -*- + * lemon/prim.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_PRIM_H +#define LEMON_PRIM_H + +///\ingroup spantree +///\file +///\brief Prim algorithm to compute minimum spanning tree. + +#include +#include +#include +#include +#include +#include + +#include + +namespace lemon { + + ///Default traits class of Prim class. + + ///Default traits class of Prim class. + ///\param GR Graph type. + ///\param LM Type of cost map. + template + struct PrimDefaultTraits{ + ///The graph type the algorithm runs on. + typedef GR UGraph; + ///The type of the map that stores the edge costs. + + ///The type of the map that stores the edge costs. + ///It must meet the \ref concept::ReadMap "ReadMap" concept. + typedef LM CostMap; + //The type of the cost of the edges. + typedef typename LM::Value Value; + /// The cross reference type used by heap. + + /// The cross reference type used by heap. + /// Usually it is \c UGraph::NodeMap. + typedef typename UGraph::template NodeMap HeapCrossRef; + ///Instantiates a HeapCrossRef. + + ///This function instantiates a \ref HeapCrossRef. + /// \param G is the graph, to which we would like to define the + /// HeapCrossRef. + static HeapCrossRef *createHeapCrossRef(const GR &_graph){ + return new HeapCrossRef(_graph); + } + + ///The heap type used by Prim algorithm. + + ///The heap type used by Prim algorithm. + /// + ///\sa BinHeap + ///\sa Prim + typedef BinHeap > Heap; + + static Heap *createHeap(HeapCrossRef& _ref){ + return new Heap(_ref); + } + + ///\brief The type of the map that stores the last + ///edges of the minimum spanning tree. + /// + ///The type of the map that stores the last + ///edges of the minimum spanning tree. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef typename UGraph::template NodeMap PredMap; + ///Instantiates a PredMap. + + ///This function instantiates a \ref PredMap. + ///\param G is the graph, to which we would like to define the PredMap. + static PredMap *createPredMap(const GR &_graph){ + return new PredMap(_graph); + } + + ///The type of the map that stores whether an edge is in the + ///spanning tree or not. + + ///The type of the map that stores whether an edge is in the + ///spanning tree or not. + ///By default it is a NullMap. + typedef NullMap TreeMap; + ///Instantiates a TreeMap. + + ///This function instantiates a \ref TreeMap. + ///\param g is the graph, to which + ///we would like to define the \ref TreeMap + static TreeMap *createTreeMap(const GR &){ + return new TreeMap(); + } + + ///The type of the map that stores whether a nodes is processed. + + ///The type of the map that stores whether a nodes is processed. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + ///By default it is a NodeMap. + typedef NullMap ProcessedMap; + ///Instantiates a ProcessedMap. + + ///This function instantiates a \ref ProcessedMap. + ///\param g is the graph, to which + ///we would like to define the \ref ProcessedMap +#ifdef DOXYGEN + static ProcessedMap *createProcessedMap(const GR &_graph) +#else + static ProcessedMap *createProcessedMap(const GR &) +#endif + { + return new ProcessedMap(); + } + }; + + ///%Prim algorithm class to find a minimum spanning tree. + + /// \ingroup spantree + ///This class provides an efficient implementation of %Prim algorithm. + /// + ///The running time is O(e*log n) where e is the number of edges and + ///n is the number of nodes in the graph. + /// + ///The edge costs are passed to the algorithm using a + ///\ref concept::ReadMap "ReadMap", + ///so it is easy to change it to any kind of cost. + /// + ///The type of the cost is determined by the + ///\ref concept::ReadMap::Value "Value" of the cost map. + /// + ///It is also possible to change the underlying priority heap. + /// + ///\param GR The graph type the algorithm runs on. The default value + ///is \ref ListUGraph. The value of GR is not used directly by + ///Prim, it is only passed to \ref PrimDefaultTraits. + /// + ///\param LM This read-only UEdgeMap determines the costs of the + ///edges. It is read once for each edge, so the map may involve in + ///relatively time consuming process to compute the edge cost if + ///it is necessary. The default map type is \ref + ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap". The value + ///of LM is not used directly by Prim, it is only passed to \ref + ///PrimDefaultTraits. + /// + ///\param TR Traits class to set + ///various data types used by the algorithm. The default traits + ///class is \ref PrimDefaultTraits + ///"PrimDefaultTraits". See \ref + ///PrimDefaultTraits for the documentation of a Prim traits + ///class. + /// + ///\author Balazs Attila Mihaly + +#ifdef DOXYGEN + template +#else + template , + typename TR=PrimDefaultTraits > +#endif + class Prim { + public: + /** + * \brief \ref Exception for uninitialized parameters. + * + * This error represents problems in the initialization + * of the parameters of the algorithms. + */ + class UninitializedParameter : public lemon::UninitializedParameter { + public: + virtual const char* exceptionName() const { + return "lemon::Prim::UninitializedParameter"; + } + }; + + typedef TR Traits; + ///The type of the underlying graph. + typedef typename TR::UGraph UGraph; + ///\e + typedef typename UGraph::Node Node; + ///\e + typedef typename UGraph::NodeIt NodeIt; + ///\e + typedef typename UGraph::UEdge UEdge; + ///\e + typedef typename UGraph::IncEdgeIt IncEdgeIt; + + ///The type of the cost of the edges. + typedef typename TR::CostMap::Value Value; + ///The type of the map that stores the edge costs. + typedef typename TR::CostMap CostMap; + ///\brief The type of the map that stores the last + ///predecessor edges of the spanning tree. + typedef typename TR::PredMap PredMap; + ///Edges of the spanning tree. + typedef typename TR::TreeMap TreeMap; + ///The type of the map indicating if a node is processed. + typedef typename TR::ProcessedMap ProcessedMap; + ///The cross reference type used for the current heap. + typedef typename TR::HeapCrossRef HeapCrossRef; + ///The heap type used by the prim algorithm. + typedef typename TR::Heap Heap; + private: + /// Pointer to the underlying graph. + const UGraph *graph; + /// Pointer to the cost map + const CostMap *cost; + ///Pointer to the map of predecessors edges. + PredMap *_pred; + ///Indicates if \ref _pred is locally allocated (\c true) or not. + bool local_pred; + ///Pointer to the map of tree edges. + TreeMap *_tree; + ///Indicates if \ref _tree is locally allocated (\c true) or not. + bool local_tree; + ///Pointer to the map of processed status of the nodes. + ProcessedMap *_processed; + ///Indicates if \ref _processed is locally allocated (\c true) or not. + bool local_processed; + ///Pointer to the heap cross references. + HeapCrossRef *_heap_cross_ref; + ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not. + bool local_heap_cross_ref; + ///Pointer to the heap. + Heap *_heap; + ///Indicates if \ref _heap is locally allocated (\c true) or not. + bool local_heap; + + ///Creates the maps if necessary. + void create_maps(){ + if(!_pred) { + local_pred = true; + _pred = Traits::createPredMap(*graph); + } + if(!_tree) { + local_tree = true; + _tree = Traits::createTreeMap(*graph); + } + if(!_processed) { + local_processed = true; + _processed = Traits::createProcessedMap(*graph); + } + if (!_heap_cross_ref) { + local_heap_cross_ref = true; + _heap_cross_ref = Traits::createHeapCrossRef(*graph); + } + if (!_heap) { + local_heap = true; + _heap = Traits::createHeap(*_heap_cross_ref); + } + } + + public : + + typedef Prim Create; + + ///\name Named template parameters + + ///@{ + + template + struct DefPredMapTraits : public Traits { + typedef T PredMap; + static PredMap *createPredMap(const UGraph &_graph){ + throw UninitializedParameter(); + } + }; + ///\ref named-templ-param "Named parameter" for setting PredMap type + + ///\ref named-templ-param "Named parameter" for setting PredMap type + /// + template + struct DefPredMap + : public Prim< UGraph, CostMap, DefPredMapTraits > { + typedef Prim< UGraph, CostMap, DefPredMapTraits > Create; + }; + + template + struct DefProcessedMapTraits : public Traits { + typedef T ProcessedMap; + static ProcessedMap *createProcessedMap(const UGraph &_graph){ + throw UninitializedParameter(); + } + }; + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type + + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type + /// + template + struct DefProcessedMap + : public Prim< UGraph, CostMap, DefProcessedMapTraits > { + typedef Prim< UGraph, CostMap, DefProcessedMapTraits > Create; + }; + + struct DefGraphProcessedMapTraits : public Traits { + typedef typename UGraph::template NodeMap ProcessedMap; + static ProcessedMap *createProcessedMap(const UGraph &_graph){ + return new ProcessedMap(_graph); + } + }; + + + template + struct DefHeapTraits : public Traits { + typedef CR HeapCrossRef; + typedef H Heap; + static HeapCrossRef *createHeapCrossRef(const UGraph &) { + throw UninitializedParameter(); + } + static Heap *createHeap(HeapCrossRef &){ + return UninitializedParameter(); + } + }; + ///\ref named-templ-param "Named parameter" for setting heap and cross + ///reference type + + ///\ref named-templ-param "Named parameter" for setting heap and cross + ///reference type + /// + template > + struct DefHeap + : public Prim< UGraph, CostMap, DefHeapTraits > { + typedef Prim< UGraph, CostMap, DefHeapTraits > Create; + }; + + template + struct DefStandardHeapTraits : public Traits { + typedef CR HeapCrossRef; + typedef H Heap; + static HeapCrossRef *createHeapCrossRef(const UGraph &_graph) { + return new HeapCrossRef(_graph); + } + static Heap *createHeap(HeapCrossRef &ref){ + return new Heap(ref); + } + }; + ///\ref named-templ-param "Named parameter" for setting heap and cross + ///reference type with automatic allocation + + ///\ref named-templ-param "Named parameter" for setting heap and cross + ///reference type. It can allocate the heap and the cross reference + ///object if the cross reference's constructor waits for the graph as + ///parameter and the heap's constructor waits for the cross reference. + template > + struct DefStandardHeap + : public Prim< UGraph, CostMap, DefStandardHeapTraits > { + typedef Prim< UGraph, CostMap, DefStandardHeapTraits > + Create; + }; + + template + struct DefTreeMapTraits : public Traits { + typedef TM TreeMap; + static TreeMap *createTreeMap(const UGraph &) { + throw UninitializedParameter(); + } + }; + ///\ref named-templ-param "Named parameter" for setting TreeMap + + ///\ref named-templ-param "Named parameter" for setting TreeMap + /// + template + struct DefTreeMap + : public Prim< UGraph, CostMap, DefTreeMapTraits > { + typedef Prim< UGraph, CostMap, DefTreeMapTraits > Create; + }; + + struct DefGraphTreeMapTraits : public Traits { + typedef typename UGraph::template NodeMap TreeMap; + static TreeMap *createTreeMap(const UGraph &_graph){ + return new TreeMap(_graph); + } + }; + + ///@} + + + protected: + + Prim() {} + + public: + + ///Constructor. + + ///\param _graph the graph the algorithm will run on. + ///\param _cost the cost map used by the algorithm. + Prim(const UGraph& _graph, const CostMap& _cost) : + graph(&_graph), cost(&_cost), + _pred(NULL), local_pred(false), + _tree(NULL), local_tree(false), + _processed(NULL), local_processed(false), + _heap_cross_ref(NULL), local_heap_cross_ref(false), + _heap(NULL), local_heap(false) + { + checkConcept(); + } + + ///Destructor. + ~Prim(){ + if(local_pred) delete _pred; + if(local_tree) delete _tree; + if(local_processed) delete _processed; + if(local_heap_cross_ref) delete _heap_cross_ref; + if(local_heap) delete _heap; + } + + ///\brief Sets the cost map. + + ///Sets the cost map. + ///\return (*this) + Prim &costMap(const CostMap &m){ + cost = &m; + return *this; + } + + ///\brief Sets the map storing the predecessor edges. + + ///Sets the map storing the predecessor edges. + ///If you don't use this function before calling \ref run(), + ///it will allocate one. The destuctor deallocates this + ///automatically allocated map, of course. + ///\return (*this) + Prim &predMap(PredMap &m){ + if(local_pred) { + delete _pred; + local_pred=false; + } + _pred = &m; + return *this; + } + + ///\brief Sets the map storing the tree edges. + + ///Sets the map storing the tree edges. + ///If you don't use this function before calling \ref run(), + ///it will allocate one. The destuctor deallocates this + ///automatically allocated map, of course. + ///By default this is a NullMap. + ///\return (*this) + Prim &treeMap(TreeMap &m){ + if(local_tree) { + delete _tree; + local_tree=false; + } + _tree = &m; + return *this; + } + + ///\brief Sets the heap and the cross reference used by algorithm. + + ///Sets the heap and the cross reference used by algorithm. + ///If you don't use this function before calling \ref run(), + ///it will allocate one. The destuctor deallocates this + ///automatically allocated map, of course. + ///\return (*this) + Prim &heap(Heap& heap, HeapCrossRef &crossRef){ + if(local_heap_cross_ref) { + delete _heap_cross_ref; + local_heap_cross_ref=false; + } + _heap_cross_ref = &crossRef; + if(local_heap) { + delete _heap; + local_heap=false; + } + _heap = &heap; + return *this; + } + + public: + ///\name Execution control + ///The simplest way to execute the algorithm is to use + ///one of the member functions called \c run(...). + ///\n + ///If you need more control on the execution, + ///first you must call \ref init(), then you can add several source nodes + ///with \ref addSource(). + ///Finally \ref start() will perform the actual path + ///computation. + + ///@{ + + ///\brief Initializes the internal data structures. + + ///Initializes the internal data structures. + /// + void init(){ + create_maps(); + _heap->clear(); + for ( NodeIt u(*graph) ; u!=INVALID ; ++u ) { + _pred->set(u,INVALID); + _processed->set(u,false); + _heap_cross_ref->set(u,Heap::PRE_HEAP); + } + } + + ///\brief Adds a new source node. + + ///Adds a new source node to the priority heap. + /// + ///It checks if the node has already been added to the heap and + ///it is pushed to the heap only if it was not in the heap. + void addSource(Node s){ + if(_heap->state(s) != Heap::IN_HEAP) { + _heap->push(s,Value()); + } + } + ///\brief Processes the next node in the priority heap + + ///Processes the next node in the priority heap. + /// + ///\return The processed node. + /// + ///\warning The priority heap must not be empty! + Node processNextNode(){ + Node v=_heap->top(); + _heap->pop(); + _processed->set(v,true); + + for(IncEdgeIt e(*graph,v); e!=INVALID; ++e) { + Node w=graph->oppositeNode(v,e); + switch(_heap->state(w)) { + case Heap::PRE_HEAP: + _heap->push(w,(*cost)[e]); + _pred->set(w,e); + break; + case Heap::IN_HEAP: + if ( (*cost)[e] < (*_heap)[w] ) { + _heap->decrease(w,(*cost)[e]); + _pred->set(w,e); + } + break; + case Heap::POST_HEAP: + break; + } + } + if ((*_pred)[v]!=INVALID)_tree->set((*_pred)[v],true); + return v; + } + + ///\brief Next node to be processed. + + ///Next node to be processed. + /// + ///\return The next node to be processed or INVALID if the priority heap + /// is empty. + Node nextNode(){ + return _heap->empty()?_heap->top():INVALID; + } + + ///\brief Returns \c false if there are nodes to be processed in the priority heap + /// + ///Returns \c false if there are nodes + ///to be processed in the priority heap + bool emptyQueue() { return _heap->empty(); } + ///\brief Returns the number of the nodes to be processed in the priority heap + + ///Returns the number of the nodes to be processed in the priority heap + /// + int queueSize() { return _heap->size(); } + + ///\brief Executes the algorithm. + + ///Executes the algorithm. + /// + ///\pre init() must be called and at least one node should be added + ///with addSource() before using this function. + /// + ///This method runs the %Prim algorithm from the node(s) + ///in order to compute the + ///minimum spanning tree. + /// + void start(){ + while ( !_heap->empty() ) processNextNode(); + } + + ///\brief Executes the algorithm until a condition is met. + + ///Executes the algorithm until a condition is met. + /// + ///\pre init() must be called and at least one node should be added + ///with addSource() before using this function. + /// + ///\param nm must be a bool (or convertible) node map. The algorithm + ///will stop when it reaches a node \c v with nm[v]==true. + template + void start(const NodeBoolMap &nm){ + while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode(); + if ( !_heap->empty() ) _processed->set(_heap->top(),true); + } + + ///\brief Runs %Prim algorithm. + + ///This method runs the %Prim algorithm + ///in order to compute the + ///minimum spanning tree (or minimum spanning forest). + ///The method also works on graphs that has more than one components. + ///In this case it computes the minimum spanning forest. + void run() { + init(); + for(NodeIt it(*graph);it!=INVALID;++it){ + if(!processed(it)){ + addSource(it); + start(); + } + } + } + + ///\brief Runs %Prim algorithm from node \c s. + + ///This method runs the %Prim algorithm from node \c s + ///in order to + ///compute the + ///minimun spanning tree + /// + ///\note d.run(s) is just a shortcut of the following code. + ///\code + /// d.init(); + /// d.addSource(s); + /// d.start(); + ///\endcode + ///\note If the graph has more than one components, the method + ///will compute the minimun spanning tree for only one component. + /// + ///See \ref run() if you want to compute the minimal spanning forest. + void run(Node s){ + init(); + addSource(s); + start(); + } + + ///@} + + ///\name Query Functions + ///The result of the %Prim algorithm can be obtained using these + ///functions.\n + ///Before the use of these functions, + ///either run() or start() must be called. + + ///@{ + + ///\brief Returns the 'previous edge' of the minimum spanning tree. + + ///For a node \c v it returns the 'previous edge' of the minimum spanning tree, + ///i.e. it returns the edge from where \c v was reached. For a source node + ///or an unreachable node it is \ref INVALID. + ///The minimum spanning tree used here is equal to the minimum spanning tree used + ///in \ref predNode(). \pre \ref run() or \ref start() must be called before + ///using this function. + UEdge predEdge(Node v) const { return (*_pred)[v]; } + + ///\brief Returns the 'previous node' of the minimum spanning tree. + + ///For a node \c v it returns the 'previous node' of the minimum spanning tree, + ///i.e. it returns the node from where \c v was reached. For a source node + ///or an unreachable node it is \ref INVALID. + //The minimum spanning tree used here is equal to the minimum spanning + ///tree used in \ref predEdge(). \pre \ref run() or \ref start() must be called + ///before using this function. + Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: + graph->source((*_pred)[v]); } + + ///\brief Returns a reference to the NodeMap of the edges of the minimum spanning tree. + + ///Returns a reference to the NodeMap of the edges of the + ///minimum spanning tree. + ///\pre \ref run() or \ref start() must be called before using this function. + const PredMap &predMap() const { return *_pred;} + + ///\brief Returns a reference to the tree edges map. + + ///Returns a reference to the TreeEdgeMap of the edges of the + ///minimum spanning tree. The value of the map is \c true only if the edge is in + ///the minimum spanning tree. + ///\warning By default, the TreeEdgeMap is a NullMap. + /// + ///If it is not set before the execution of the algorithm, use the \ref + ///treeMap(TreeMap&) function (after the execution) to set an UEdgeMap with the + ///edges of the minimum spanning tree in O(n) time where n is the number of + ///nodes in the graph. + ///\pre \ref run() or \ref start() must be called before using this function. + const TreeMap &treeMap() const { return *_tree;} + + ///\brief Sets the tree edges map. + + ///Sets the TreeMap of the edges of the minimum spanning tree. + ///The map values belonging to the edges of the minimum + ///spanning tree are set to \param tree_edge_value or \c true by default, + ///the other map values remain untouched. + /// + ///\pre \ref run() or \ref start() must be called before using this function. + + template + void quickTreeEdges( + TreeMap& tree, + const typename TreeMap::Value& tree_edge_value=true) const { + for(NodeIt i(*graph);i!=INVALID;++i){ + if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value); + } + } + + ///\brief Sets the tree edges map. + + ///Sets the TreeMap of the edges of the minimum spanning tree. + ///The map values belonging to the edges of the minimum + ///spanning tree are set to \param tree_edge_value or \c true by default while + ///the edge values not belonging to the minimum spanning tree are set to + ///\param tree_default_value or \c false by default. + /// + ///\pre \ref run() or \ref start() must be called before using this function. + + template + void treeEdges( + TreeMap& tree, + const typename TreeMap::Value& tree_edge_value=true, + const typename TreeMap::Value& tree_default_value=false) const { + for(typename ItemSetTraits::ItemIt i(*graph);i!=INVALID;++i) + tree.set(i,tree_default_value); + for(NodeIt i(*graph);i!=INVALID;++i){ + if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value); + } + } + + ///\brief Checks if a node is reachable from the starting node. + + ///Returns \c true if \c v is reachable from the starting node. + ///\warning The source nodes are inditated as unreached. + ///\pre \ref run() or \ref start() must be called before using this function. + /// + bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; } + + ///\brief Checks if a node is processed. + + ///Returns \c true if \c v is processed, i.e. \c v is already connencted to the + ///minimum spanning tree. + ///\pre \ref run() or \ref start() must be called before using this function. + /// + bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; } + + + ///\brief Checks if an edge is in the spanning tree or not. + + ///Checks if an edge is in the spanning tree or not. + ///\param e is the edge that will be checked + ///\return \c true if e is in the spanning tree, \c false otherwise + bool tree(UEdge e){ + return (*_pred)[*graph.source(e)]==e || (*_pred)[*graph.target(e)]==e; + } + ///@} + }; + + + /// \ingroup spantree + /// + /// \brief Function type interface for Prim algorithm. + /// + /// Function type interface for Prim algorithm. + /// \param graph the UGraph that the algorithm runs on + /// \param cost the CostMap of the edges + /// \retval tree the EdgeMap that contains whether an edge is in + /// the spanning tree or not + /// + ///\sa Prim + template + void prim(const Graph& graph, const CostMap& cost,TreeMap& tree){ + typename Prim::template DefTreeMap:: + Create prm(graph,cost); + prm.treeMap(tree); + prm.run(); + }; + +} //END OF NAMESPACE LEMON + +#endif