00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
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
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
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 }
00794
00795 #endif