prim.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
00016  *
00017  */
00018 
00019 #ifndef LEMON_PRIM_H
00020 #define LEMON_PRIM_H
00021 
00025 
00026 #include <lemon/list_graph.h>
00027 #include <lemon/bin_heap.h>
00028 #include <lemon/invalid.h>
00029 #include <lemon/error.h>
00030 #include <lemon/maps.h>
00031 #include <lemon/traits.h>
00032 
00033 #include <lemon/concept/ugraph.h>
00034 
00035 namespace lemon {
00036 
00038 
00042   template<class GR, class LM>
00043   struct PrimDefaultTraits{
00045     typedef GR UGraph;
00047 
00050     typedef LM CostMap;
00051     //The type of the cost of the edges.
00052     typedef typename LM::Value Value;
00054 
00057     typedef typename UGraph::template NodeMap<int> HeapCrossRef;
00059 
00063     static HeapCrossRef *createHeapCrossRef(const GR &_graph){
00064       return new HeapCrossRef(_graph);
00065     }
00066     
00068 
00073     typedef BinHeap<typename UGraph::Node, typename LM::Value,
00074                     HeapCrossRef, std::less<Value> > Heap;
00075 
00076     static Heap *createHeap(HeapCrossRef& _ref){
00077       return new Heap(_ref);
00078     }
00079 
00087     typedef typename UGraph::template NodeMap<typename GR::UEdge> PredMap;
00089  
00092     static PredMap *createPredMap(const GR &_graph){
00093       return new PredMap(_graph);
00094     }
00095 
00098 
00102     typedef NullMap<typename UGraph::UEdge,bool> TreeMap;
00104 
00109     static TreeMap *createTreeMap(const GR &){
00110       return new TreeMap();
00111     }
00112 
00114  
00118     typedef NullMap<typename UGraph::Node,bool> ProcessedMap;
00120  
00124 #ifdef DOXYGEN
00125     static ProcessedMap *createProcessedMap(const GR &_graph)
00126 #else
00127     static ProcessedMap *createProcessedMap(const GR &)
00128 #endif
00129     {
00130       return new ProcessedMap();
00131     }
00132   };
00133   
00135   
00171 
00172 #ifdef DOXYGEN
00173   template <typename GR,
00174             typename LM,
00175             typename TR>
00176 #else
00177   template <typename GR=ListUGraph,
00178             typename LM=typename GR::template UEdgeMap<int>,
00179             typename TR=PrimDefaultTraits<GR,LM> >
00180 #endif
00181   class Prim {
00182   public:
00189     class UninitializedParameter : public lemon::UninitializedParameter {
00190     public:
00191       virtual const char* exceptionName() const {
00192         return "lemon::Prim::UninitializedParameter";
00193       }
00194     };
00195 
00196     typedef TR Traits;
00198     typedef typename TR::UGraph UGraph;
00200     typedef typename UGraph::Node Node;
00202     typedef typename UGraph::NodeIt NodeIt;
00204     typedef typename UGraph::UEdge UEdge;
00206     typedef typename UGraph::IncEdgeIt IncEdgeIt;
00207     
00209     typedef typename TR::CostMap::Value Value;
00211     typedef typename TR::CostMap CostMap;
00214     typedef typename TR::PredMap PredMap;
00216     typedef typename TR::TreeMap TreeMap;
00218     typedef typename TR::ProcessedMap ProcessedMap;
00220     typedef typename TR::HeapCrossRef HeapCrossRef;
00222     typedef typename TR::Heap Heap;
00223   private:
00225     const UGraph *graph;
00227     const CostMap *cost;
00229     PredMap *_pred;
00231     bool local_pred;
00233     TreeMap *_tree;
00235     bool local_tree;
00237     ProcessedMap *_processed;
00239     bool local_processed;
00241     HeapCrossRef *_heap_cross_ref;
00243     bool local_heap_cross_ref;
00245     Heap *_heap;
00247     bool local_heap;
00248 
00250     void create_maps(){
00251       if(!_pred) {
00252         local_pred = true;
00253         _pred = Traits::createPredMap(*graph);
00254       }
00255       if(!_tree) {
00256         local_tree = true;
00257         _tree = Traits::createTreeMap(*graph);
00258       }
00259       if(!_processed) {
00260         local_processed = true;
00261         _processed = Traits::createProcessedMap(*graph);
00262       }
00263       if (!_heap_cross_ref) {
00264         local_heap_cross_ref = true;
00265         _heap_cross_ref = Traits::createHeapCrossRef(*graph);
00266       }
00267       if (!_heap) {
00268         local_heap = true;
00269         _heap = Traits::createHeap(*_heap_cross_ref);
00270       }
00271     }
00272     
00273   public :
00274 
00275     typedef Prim Create;
00276  
00278 
00280 
00281     template <class T>
00282     struct DefPredMapTraits : public Traits {
00283       typedef T PredMap;
00284       static PredMap *createPredMap(const UGraph &_graph){
00285         throw UninitializedParameter();
00286       }
00287     };
00289 
00292     template <class T>
00293     struct DefPredMap 
00294       : public Prim< UGraph, CostMap, DefPredMapTraits<T> > {
00295       typedef Prim< UGraph, CostMap, DefPredMapTraits<T> > Create;
00296     };
00297     
00298     template <class T>
00299     struct DefProcessedMapTraits : public Traits {
00300       typedef T ProcessedMap;
00301       static ProcessedMap *createProcessedMap(const UGraph &_graph){
00302         throw UninitializedParameter();
00303       }
00304     };
00306 
00309     template <class T>
00310     struct DefProcessedMap 
00311       : public Prim< UGraph, CostMap, DefProcessedMapTraits<T> > { 
00312       typedef Prim< UGraph, CostMap, DefProcessedMapTraits<T> > Create;
00313     };
00314     
00315     struct DefGraphProcessedMapTraits : public Traits {
00316       typedef typename UGraph::template NodeMap<bool> ProcessedMap;
00317       static ProcessedMap *createProcessedMap(const UGraph &_graph){
00318         return new ProcessedMap(_graph);
00319       }
00320     };
00321 
00322 
00323     template <class H, class CR>
00324     struct DefHeapTraits : public Traits {
00325       typedef CR HeapCrossRef;
00326       typedef H Heap;
00327       static HeapCrossRef *createHeapCrossRef(const UGraph &) {
00328         throw UninitializedParameter();
00329       }
00330       static Heap *createHeap(HeapCrossRef &){
00331         return UninitializedParameter();
00332       }
00333     };
00336 
00340     template <class H, class CR = typename UGraph::template NodeMap<int> >
00341     struct DefHeap
00342       : public Prim< UGraph, CostMap, DefHeapTraits<H, CR> > {
00343       typedef Prim< UGraph, CostMap, DefHeapTraits<H, CR> > Create;
00344     };
00345 
00346     template <class H, class CR>
00347     struct DefStandardHeapTraits : public Traits {
00348       typedef CR HeapCrossRef;
00349       typedef H Heap;
00350       static HeapCrossRef *createHeapCrossRef(const UGraph &_graph) {
00351         return new HeapCrossRef(_graph);
00352       }
00353       static Heap *createHeap(HeapCrossRef &ref){
00354         return new Heap(ref);
00355       }
00356     };
00359 
00364     template <class H, class CR = typename UGraph::template NodeMap<int> >
00365     struct DefStandardHeap
00366       : public Prim< UGraph, CostMap, DefStandardHeapTraits<H, CR> > { 
00367       typedef Prim< UGraph, CostMap, DefStandardHeapTraits<H, CR> > 
00368       Create;
00369     };
00370 
00371     template <class TM>
00372     struct DefTreeMapTraits : public Traits {
00373       typedef TM TreeMap;
00374       static TreeMap *createTreeMap(const UGraph &) {
00375         throw UninitializedParameter();
00376       }
00377     };
00379 
00382     template <class TM>
00383     struct DefTreeMap
00384       : public Prim< UGraph, CostMap, DefTreeMapTraits<TM> > {
00385       typedef Prim< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
00386     };    
00387 
00388     struct DefGraphTreeMapTraits : public Traits {
00389       typedef typename UGraph::template NodeMap<bool> TreeMap;
00390       static TreeMap *createTreeMap(const UGraph &_graph){
00391         return new TreeMap(_graph);
00392       }
00393     };
00394 
00396 
00397 
00398   protected:
00399 
00400     Prim() {}
00401 
00402   public:      
00403     
00405     
00408     Prim(const UGraph& _graph, const CostMap& _cost) :
00409       graph(&_graph), cost(&_cost),
00410       _pred(NULL), local_pred(false),
00411       _tree(NULL), local_tree(false),
00412       _processed(NULL), local_processed(false),
00413       _heap_cross_ref(NULL), local_heap_cross_ref(false),
00414       _heap(NULL), local_heap(false)
00415     {
00416       checkConcept<concept::UGraph, UGraph>();
00417     }
00418     
00420     ~Prim(){
00421       if(local_pred) delete _pred;
00422       if(local_tree) delete _tree;
00423       if(local_processed) delete _processed;
00424       if(local_heap_cross_ref) delete _heap_cross_ref;
00425       if(local_heap) delete _heap;
00426     }
00427 
00429 
00432     Prim &costMap(const CostMap &m){
00433       cost = &m;
00434       return *this;
00435     }
00436 
00438 
00444     Prim &predMap(PredMap &m){
00445       if(local_pred) {
00446         delete _pred;
00447         local_pred=false;
00448       }
00449       _pred = &m;
00450       return *this;
00451     }
00452 
00454 
00461     Prim &treeMap(TreeMap &m){
00462       if(local_tree) {
00463         delete _tree;
00464         local_tree=false;
00465       }
00466       _tree = &m;
00467       return *this;
00468     }
00469 
00471 
00477     Prim &heap(Heap& heap, HeapCrossRef &crossRef){
00478       if(local_heap_cross_ref) {
00479         delete _heap_cross_ref;
00480         local_heap_cross_ref=false;
00481       }
00482       _heap_cross_ref = &crossRef;
00483       if(local_heap) {
00484         delete _heap;
00485         local_heap=false;
00486       }
00487       _heap = &heap;
00488       return *this;
00489     }
00490 
00491   public:
00501 
00503 
00505 
00508     void init(){
00509       create_maps();
00510       _heap->clear();
00511       for ( NodeIt u(*graph) ; u!=INVALID ; ++u ) {
00512         _pred->set(u,INVALID);
00513         _processed->set(u,false);
00514         _heap_cross_ref->set(u,Heap::PRE_HEAP);
00515       }
00516     }
00517     
00519 
00524     void addSource(Node s){
00525       if(_heap->state(s) != Heap::IN_HEAP) {
00526         _heap->push(s,Value());
00527       }
00528     }
00530 
00536     Node processNextNode(){
00537       Node v=_heap->top(); 
00538       _heap->pop();
00539       _processed->set(v,true);
00540       
00541       for(IncEdgeIt e(*graph,v); e!=INVALID; ++e) {
00542         Node w=graph->oppositeNode(v,e);
00543         switch(_heap->state(w)) {
00544         case Heap::PRE_HEAP:
00545           _heap->push(w,(*cost)[e]);
00546           _pred->set(w,e);
00547           break;
00548         case Heap::IN_HEAP:
00549           if ( (*cost)[e] < (*_heap)[w] ) {
00550             _heap->decrease(w,(*cost)[e]); 
00551             _pred->set(w,e);
00552           }
00553           break;
00554         case Heap::POST_HEAP:
00555           break;
00556         }
00557       }
00558       if ((*_pred)[v]!=INVALID)_tree->set((*_pred)[v],true);
00559       return v;
00560     }
00561 
00563     
00568     Node nextNode(){ 
00569       return _heap->empty()?_heap->top():INVALID;
00570     }
00571  
00576     bool emptyQueue() { return _heap->empty(); }
00578 
00581     int queueSize() { return _heap->size(); }
00582     
00584 
00594     void start(){
00595       while ( !_heap->empty() ) processNextNode();
00596     }
00597     
00599 
00607     template<class NodeBoolMap>
00608     void start(const NodeBoolMap &nm){
00609       while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
00610       if ( !_heap->empty() ) _processed->set(_heap->top(),true);
00611     }
00612     
00614     
00620     void run() {
00621       init();
00622       for(NodeIt it(*graph);it!=INVALID;++it){
00623         if(!processed(it)){
00624           addSource(it);
00625           start();
00626         }
00627       }
00628     }
00629 
00631     
00647     void run(Node s){
00648       init();
00649       addSource(s);
00650       start();
00651     }
00652     
00654 
00660     
00662 
00664 
00671     UEdge predEdge(Node v) const { return (*_pred)[v]; }
00672 
00674 
00678     //The minimum spanning tree used here is equal to the minimum spanning
00681     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
00682                                   graph->source((*_pred)[v]); }
00683     
00685 
00689     const PredMap &predMap() const { return *_pred;}
00690  
00692 
00703     const TreeMap &treeMap() const { return *_tree;}
00704  
00706 
00713 
00714     template<class TreeMap>
00715     void quickTreeEdges(
00716         TreeMap& tree,
00717         const typename TreeMap::Value& tree_edge_value=true) const {
00718       for(NodeIt i(*graph);i!=INVALID;++i){
00719         if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value);
00720       }
00721     }
00722 
00724 
00732 
00733     template<class TreeMap>
00734     void treeEdges(
00735         TreeMap& tree,
00736         const typename TreeMap::Value& tree_edge_value=true,
00737         const typename TreeMap::Value& tree_default_value=false) const {
00738       for(typename ItemSetTraits<UGraph,UEdge>::ItemIt i(*graph);i!=INVALID;++i)
00739         tree.set(i,tree_default_value);
00740       for(NodeIt i(*graph);i!=INVALID;++i){
00741         if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value);
00742       }
00743     }
00744 
00746 
00751     bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
00752 
00754 
00759     bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
00760     
00761 
00763 
00767     bool tree(UEdge e){
00768       return (*_pred)[*graph.source(e)]==e || (*_pred)[*graph.target(e)]==e;
00769     }
00771   };
00772 
00773 
00785   template<class Graph,class CostMap,class TreeMap>
00786   void prim(const Graph& graph, const CostMap& cost,TreeMap& tree){
00787     typename Prim<Graph,CostMap>::template DefTreeMap<TreeMap>::
00788       Create prm(graph,cost);
00789     prm.treeMap(tree);
00790     prm.run();
00791   };
00792 
00793 } //END OF NAMESPACE LEMON
00794 
00795 #endif

Generated on Fri Feb 3 18:39:41 2006 for LEMON by  doxygen 1.4.6