COIN-OR::LEMON - Graph Library

Changeset 2397:a501140ce878 in lemon-0.x


Ignore:
Timestamp:
03/07/07 12:56:53 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3228
Message:

Some design correction

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/prim.h

    r2391 r2397  
    402402   
    403403    ///Constructor.
    404    
     404    ///
    405405    ///\param _graph the graph the algorithm will run on.
    406406    ///\param _cost the cost map used by the algorithm.
    407407    Prim(const UGraph& _graph, const CostMap& _cost) :
    408408      graph(&_graph), cost(&_cost),
    409       _pred(NULL), local_pred(false),
    410       _tree(NULL), local_tree(false),
    411       _processed(NULL), local_processed(false),
    412       _heap_cross_ref(NULL), local_heap_cross_ref(false),
    413       _heap(NULL), local_heap(false)
     409      _pred(0), local_pred(false),
     410      _tree(0), local_tree(false),
     411      _processed(0), local_processed(false),
     412      _heap_cross_ref(0), local_heap_cross_ref(false),
     413      _heap(0), local_heap(false)
    414414    {
    415415      checkConcept<concepts::UGraph, UGraph>();
     
    426426
    427427    ///\brief Sets the cost map.
    428 
     428    ///
    429429    ///Sets the cost map.
    430430    ///\return <tt> (*this) </tt>
     
    435435
    436436    ///\brief Sets the map storing the predecessor edges.
    437 
     437    ///
    438438    ///Sets the map storing the predecessor edges.
    439439    ///If you don't use this function before calling \ref run(),
     
    451451
    452452    ///\brief Sets the map storing the tree edges.
    453 
     453    ///
    454454    ///Sets the map storing the tree edges.
    455455    ///If you don't use this function before calling \ref run(),
     
    468468
    469469    ///\brief Sets the heap and the cross reference used by algorithm.
    470 
     470    ///
    471471    ///Sets the heap and the cross reference used by algorithm.
    472472    ///If you don't use this function before calling \ref run(),
     
    502502
    503503    ///\brief Initializes the internal data structures.
    504 
     504    ///
    505505    ///Initializes the internal data structures.
    506506    ///
     
    516516   
    517517    ///\brief Adds a new source node.
    518 
     518    ///
    519519    ///Adds a new source node to the priority heap.
    520520    ///
     
    527527    }
    528528    ///\brief Processes the next node in the priority heap
    529 
     529    ///
    530530    ///Processes the next node in the priority heap.
    531531    ///
     
    560560
    561561    ///\brief Next node to be processed.
    562    
     562    ///
    563563    ///Next node to be processed.
    564564    ///
     
    569569    }
    570570 
    571     ///\brief Returns \c false if there are nodes to be processed in the priority heap
     571    ///\brief Returns \c false if there are nodes to be processed in
     572    ///the priority heap
    572573    ///
    573574    ///Returns \c false if there are nodes
    574575    ///to be processed in the priority heap
    575576    bool emptyQueue() { return _heap->empty(); }
    576     ///\brief Returns the number of the nodes to be processed in the priority heap
    577 
     577
     578    ///\brief Returns the number of the nodes to be processed in the
     579    ///priority heap
     580    ///
    578581    ///Returns the number of the nodes to be processed in the priority heap
    579582    ///
     
    581584   
    582585    ///\brief Executes the algorithm.
    583 
     586    ///
    584587    ///Executes the algorithm.
    585588    ///
     
    596599   
    597600    ///\brief Executes the algorithm until a condition is met.
    598 
     601    ///
    599602    ///Executes the algorithm until a condition is met.
    600603    ///
     
    611614   
    612615    ///\brief Runs %Prim algorithm.
    613    
     616    ///
    614617    ///This method runs the %Prim algorithm
    615618    ///in order to compute the
     
    628631
    629632    ///\brief Runs %Prim algorithm from node \c s.
    630    
     633    ///
    631634    ///This method runs the %Prim algorithm from node \c s
    632635    ///in order to
     
    634637    ///minimun spanning tree
    635638    ///
    636     ///\note d.run(s) is just a shortcut of the following code.
     639    ///\note p.run(s) is just a shortcut of the following code.
    637640    ///\code
    638     ///  d.init();
    639     ///  d.addSource(s);
    640     ///  d.start();
     641    ///  p.init();
     642    ///  p.addSource(s);
     643    ///  p.start();
    641644    ///\endcode
    642645    ///\note If the graph has more than one components, the method
     
    662665    ///\brief Returns the 'previous edge' of the minimum spanning tree.
    663666
    664     ///For a node \c v it returns the 'previous edge' of the minimum spanning tree,
    665     ///i.e. it returns the edge from where \c v was reached. For a source node
    666     ///or an unreachable node it is \ref INVALID.
    667     ///The minimum spanning tree used here is equal to the minimum spanning tree used
    668     ///in \ref predNode().  \pre \ref run() or \ref start() must be called before
    669     ///using this function.
     667    ///For a node \c v it returns the 'previous edge' of the minimum
     668    ///spanning tree, i.e. it returns the edge from where \c v was
     669    ///reached. For a source node or an unreachable node it is \ref
     670    ///INVALID.  The minimum spanning tree used here is equal to the
     671    ///minimum spanning tree used in \ref predNode(). 
     672    ///\pre \ref run() or \ref start() must be called before using
     673    ///this function.
    670674    UEdge predEdge(Node v) const { return (*_pred)[v]; }
    671675
    672     ///\brief Returns the 'previous node' of the minimum spanning tree.
    673 
    674     ///For a node \c v it returns the 'previous node' of the minimum spanning tree,
    675     ///i.e. it returns the node from where \c v was reached. For a source node
    676     ///or an unreachable node it is \ref INVALID.
    677     //The minimum spanning tree used here is equal to the minimum spanning
    678     ///tree used in \ref predEdge().  \pre \ref run() or \ref start() must be called
    679     ///before using this function.
     676    ///\brief Returns the 'previous node' of the minimum spanning
     677    ///tree.
     678    ///
     679    ///For a node \c v it returns the 'previous node' of the minimum
     680    ///spanning tree, i.e. it returns the node from where \c v was
     681    ///reached. For a source node or an unreachable node it is \ref
     682    ///INVALID.  //The minimum spanning tree used here is equal to the
     683    ///minimum spanning tree used in \ref predEdge(). 
     684    ///\pre \ref run() or \ref start() must be called before using
     685    ///this function.
    680686    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    681687                                  graph->source((*_pred)[v]); }
    682688   
    683     ///\brief Returns a reference to the NodeMap of the edges of the minimum spanning tree.
    684 
    685     ///Returns a reference to the NodeMap of the edges of the
     689    ///\brief Returns a reference to the NodeMap of the edges of the
    686690    ///minimum spanning tree.
    687     ///\pre \ref run() or \ref start() must be called before using this function.
     691    ///
     692    ///Returns a reference to the NodeMap of the edges of the minimum
     693    ///spanning tree.
     694    ///\pre \ref run() or \ref start() must be called before using
     695    ///this function.
    688696    const PredMap &predMap() const { return *_pred;}
    689697 
     
    691699
    692700    ///Returns a reference to the TreeEdgeMap of the edges of the
    693     ///minimum spanning tree. The value of the map is \c true only if the edge is in
    694     ///the minimum spanning tree.
     701    ///minimum spanning tree. The value of the map is \c true only if
     702    ///the edge is in the minimum spanning tree.
     703    ///
    695704    ///\warning By default, the TreeEdgeMap is a NullMap.
    696705    ///
    697     ///If it is not set before the execution of the algorithm, use the \ref
    698     ///treeMap(TreeMap&) function (after the execution) to set an UEdgeMap with the
    699     ///edges of the minimum spanning tree in O(n) time where n is the number of
    700     ///nodes in the graph.
    701     ///\pre \ref run() or \ref start() must be called before using this function.
     706    ///If it is not set before the execution of the algorithm, use the
     707    ///\ref treeMap(TreeMap&) function (after the execution) to set an
     708    ///UEdgeMap with the edges of the minimum spanning tree in O(n)
     709    ///time where n is the number of nodes in the graph.
     710    ///\pre \ref run() or \ref start() must be called before using
     711    ///this function.
    702712    const TreeMap &treeMap() const { return *_tree;}
    703713 
    704714    ///\brief Sets the tree edges map.
    705 
     715    ///
    706716    ///Sets the TreeMap of the edges of the minimum spanning tree.
    707717    ///The map values belonging to the edges of the minimum
     
    709719    ///the other map values remain untouched.
    710720    ///
    711     ///\pre \ref run() or \ref start() must be called before using this function.
     721    ///\pre \ref run() or \ref start() must be called before using
     722    ///this function.
    712723
    713724    template<class TreeMap>
    714     void quickTreeEdges(
    715         TreeMap& tree,
    716         const typename TreeMap::Value& tree_edge_value=true) const {
     725    void quickTreeEdges(TreeMap& tree) const {
    717726      for(NodeIt i(*graph);i!=INVALID;++i){
    718         if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value);
     727        if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],true);
    719728      }
    720729    }
    721730
    722731    ///\brief Sets the tree edges map.
    723 
     732    ///
    724733    ///Sets the TreeMap of the edges of the minimum spanning tree.
    725734    ///The map values belonging to the edges of the minimum
     
    728737    ///\c tree_default_value or \c false by default.
    729738    ///
    730     ///\pre \ref run() or \ref start() must be called before using this function.
    731 
    732     template<class TreeMap>
    733     void treeEdges(
    734         TreeMap& tree,
    735         const typename TreeMap::Value& tree_edge_value=true,
    736         const typename TreeMap::Value& tree_default_value=false) const {
    737       for(typename ItemSetTraits<UGraph,UEdge>::ItemIt i(*graph);i!=INVALID;++i)
    738         tree.set(i,tree_default_value);
    739       for(NodeIt i(*graph);i!=INVALID;++i){
    740         if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value);
     739    ///\pre \ref run() or \ref start() must be called before using
     740    ///this function.
     741    template <class TreeMap>
     742    void treeEdges(TreeMap& tree) const {
     743      typedef typename ItemSetTraits<UGraph,UEdge>::ItemIt TreeMapIt;
     744      for(TreeMapIt i(*graph); i != INVALID; ++i) {
     745        tree.set(i,false);
     746      }
     747      for(NodeIt i(*graph); i != INVALID; ++i){
     748        if((*_pred)[i] != INVALID) tree.set((*_pred)[i],true);
    741749      }
    742750    }
    743751
    744752    ///\brief Checks if a node is reachable from the starting node.
    745 
     753    ///
    746754    ///Returns \c true if \c v is reachable from the starting node.
    747755    ///\warning The source nodes are inditated as unreached.
    748     ///\pre \ref run() or \ref start() must be called before using this function.
     756    ///\pre \ref run() or \ref start() must be called before using
     757    ///this function.
    749758    ///
    750759    bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
    751760
    752761    ///\brief Checks if a node is processed.
    753 
    754     ///Returns \c true if \c v is processed, i.e. \c v is already connencted to the
    755     ///minimum spanning tree.
    756     ///\pre \ref run() or \ref start() must be called before using this function.
    757     ///
     762    ///
     763    ///Returns \c true if \c v is processed, i.e. \c v is already
     764    ///connencted to the minimum spanning tree.  \pre \ref run() or
     765    ///\ref start() must be called before using this function.
    758766    bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
    759767   
    760768
    761769    ///\brief Checks if an edge is in the spanning tree or not.
    762 
     770    ///
    763771    ///Checks if an edge is in the spanning tree or not.
    764772    ///\param e is the edge that will be checked
     
    767775      return (*_pred)[*graph.source(e)]==e || (*_pred)[*graph.target(e)]==e;
    768776    }
     777
     778    ///\brief Returns the value of the total cost of the spanning tree.
     779    ///
     780    /// Returns the value of the total cost of the spanning tree.
     781    Value treeValue() const {
     782      Value value = 0;
     783      for(NodeIt i(*graph); i!= INVALID; ++i){
     784        if ((*_pred)[i] != INVALID) value += (*cost)[(*_pred)[i]];
     785      }
     786      return value;
     787    }
    769788    ///@}
    770789  };
     
    780799  /// \retval tree the EdgeMap that contains whether an edge is in
    781800  /// the spanning tree or not
     801  /// \return The total cost of the spanning tree
    782802  ///
    783803  ///\sa Prim
    784804  template<class Graph,class CostMap,class TreeMap>
    785   void prim(const Graph& graph, const CostMap& cost,TreeMap& tree){
    786     typename Prim<Graph,CostMap>::template DefTreeMap<TreeMap>::
     805  typename CostMap::Value prim(const Graph& graph,
     806                               const CostMap& cost,
     807                               TreeMap& tree){
     808    typename Prim<Graph,CostMap>::
     809      template DefTreeMap<TreeMap>::
    787810      Create prm(graph,cost);
    788811    prm.treeMap(tree);
    789812    prm.run();
     813    return prm.treeValue();
    790814  }
    791815
     816  /// \ingroup spantree
     817  ///
     818  /// \brief Function type interface for Prim algorithm.
     819  ///
     820  /// Function type interface for Prim algorithm.
     821  /// \param graph the UGraph that the algorithm runs on
     822  /// \param cost the CostMap of the edges
     823  /// the spanning tree or not
     824  /// \return The total cost of the spanning tree
     825  ///
     826  ///\sa Prim
     827  template<class Graph,class CostMap,class TreeMap>
     828  typename CostMap::Value prim(const Graph& graph,
     829                               const CostMap& cost){
     830    typename Prim<Graph,CostMap>::
     831      Create prm(graph,cost);
     832    prm.run();
     833    return prm.treeValue();
     834  }
     835
    792836} //END OF NAMESPACE LEMON
    793837
Note: See TracChangeset for help on using the changeset viewer.