Changeset 1270:dceba191c00d in lemon for lemon/max_cardinality_search.h
- Timestamp:
- 08/09/13 11:28:17 (11 years ago)
- Branch:
- default
- Children:
- 1271:fb1c7da561ce, 1381:e0ccc1f0268f
- Phase:
- public
- File:
-
- 1 edited
-
lemon/max_cardinality_search.h (modified) (43 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/max_cardinality_search.h
r1129 r1270 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 05 * Copyright (C) 2003-2013 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 22 22 23 23 /// \ingroup search 24 /// \file 24 /// \file 25 25 /// \brief Maximum cardinality search in undirected digraphs. 26 26 … … 42 42 template <typename GR, typename CAP> 43 43 struct MaxCardinalitySearchDefaultTraits { 44 /// The digraph type the algorithm runs on. 44 /// The digraph type the algorithm runs on. 45 45 typedef GR Digraph; 46 46 … … 51 51 52 52 static CapacityMap *createCapacityMap(const Digraph& g) { 53 53 return new CapacityMap(g); 54 54 } 55 55 }; … … 61 61 62 62 static CapacityMap *createCapacityMap(const Digraph&) { 63 63 return new CapacityMap; 64 64 } 65 65 }; … … 91 91 /// \brief Instantiates a HeapCrossRef. 92 92 /// 93 /// This function instantiates a \ref HeapCrossRef. 94 /// \param digraph is the digraph, to which we would like to define the 93 /// This function instantiates a \ref HeapCrossRef. 94 /// \param digraph is the digraph, to which we would like to define the 95 95 /// HeapCrossRef. 96 96 static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) { 97 97 return new HeapCrossRef(digraph); 98 98 } 99 99 100 100 template <typename CapacityMap> 101 101 struct HeapSelector { 102 102 template <typename Value, typename Ref> 103 struct Selector { 103 struct Selector { 104 104 typedef BinHeap<Value, Ref, std::greater<Value> > Heap; 105 105 }; … … 129 129 /// \brief Instantiates a Heap. 130 130 /// 131 /// This function instantiates a \ref Heap. 131 /// This function instantiates a \ref Heap. 132 132 /// \param crossref The cross reference of the heap. 133 133 static Heap *createHeap(HeapCrossRef& crossref) { … … 144 144 /// \brief Instantiates a ProcessedMap. 145 145 /// 146 /// This function instantiates a \ref ProcessedMap. 146 /// This function instantiates a \ref ProcessedMap. 147 147 /// \param digraph is the digraph, to which 148 148 /// we would like to define the \ref ProcessedMap … … 157 157 158 158 /// \brief The type of the map that stores the cardinalities of the nodes. 159 /// 159 /// 160 160 /// The type of the map that stores the cardinalities of the nodes. 161 161 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. … … 164 164 /// \brief Instantiates a CardinalityMap. 165 165 /// 166 /// This function instantiates a \ref CardinalityMap. 167 /// \param digraph is the digraph, to which we would like to define the \ref 166 /// This function instantiates a \ref CardinalityMap. 167 /// \param digraph is the digraph, to which we would like to define the \ref 168 168 /// CardinalityMap 169 169 static CardinalityMap *createCardinalityMap(const Digraph &digraph) { … … 173 173 174 174 }; 175 175 176 176 /// \ingroup search 177 177 /// 178 178 /// \brief Maximum Cardinality Search algorithm class. 179 179 /// 180 /// This class provides an efficient implementation of Maximum Cardinality 181 /// Search algorithm. The maximum cardinality search first chooses any 180 /// This class provides an efficient implementation of Maximum Cardinality 181 /// Search algorithm. The maximum cardinality search first chooses any 182 182 /// node of the digraph. Then every time it chooses one unprocessed node 183 183 /// with maximum cardinality, i.e the sum of capacities on out arcs to the nodes … … 187 187 188 188 /// The arc capacities are passed to the algorithm using a 189 /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 189 /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 190 190 /// kind of capacity. 191 191 /// 192 /// The type of the capacity is determined by the \ref 192 /// The type of the capacity is determined by the \ref 193 193 /// concepts::ReadMap::Value "Value" of the capacity map. 194 194 /// … … 197 197 /// 198 198 /// \param GR The digraph type the algorithm runs on. The value of 199 /// Digraph is not used directly by the search algorithm, it 199 /// Digraph is not used directly by the search algorithm, it 200 200 /// is only passed to \ref MaxCardinalitySearchDefaultTraits. 201 /// \param CAP This read-only ArcMap determines the capacities of 201 /// \param CAP This read-only ArcMap determines the capacities of 202 202 /// the arcs. It is read once for each arc, so the map may involve in 203 203 /// relatively time consuming process to compute the arc capacity if 204 204 /// it is necessary. The default map type is \ref 205 205 /// ConstMap "ConstMap<concepts::Digraph::Arc, Const<int,1> >". The value 206 /// of CapacityMap is not used directly by search algorithm, it is only 207 /// passed to \ref MaxCardinalitySearchDefaultTraits. 208 /// \param TR Traits class to set various data types used by the 209 /// algorithm. The default traits class is 210 /// \ref MaxCardinalitySearchDefaultTraits 211 /// "MaxCardinalitySearchDefaultTraits<GR, CAP>". 212 /// See \ref MaxCardinalitySearchDefaultTraits 206 /// of CapacityMap is not used directly by search algorithm, it is only 207 /// passed to \ref MaxCardinalitySearchDefaultTraits. 208 /// \param TR Traits class to set various data types used by the 209 /// algorithm. The default traits class is 210 /// \ref MaxCardinalitySearchDefaultTraits 211 /// "MaxCardinalitySearchDefaultTraits<GR, CAP>". 212 /// See \ref MaxCardinalitySearchDefaultTraits 213 213 /// for the documentation of a MaxCardinalitySearch traits class. 214 214 … … 216 216 template <typename GR, typename CAP, typename TR> 217 217 #else 218 template <typename GR, typename CAP = 219 220 typename TR = 218 template <typename GR, typename CAP = 219 ConstMap<typename GR::Arc, Const<int,1> >, 220 typename TR = 221 221 MaxCardinalitySearchDefaultTraits<GR, CAP> > 222 222 #endif … … 227 227 ///The type of the underlying digraph. 228 228 typedef typename Traits::Digraph Digraph; 229 229 230 230 ///The type of the capacity of the arcs. 231 231 typedef typename Traits::CapacityMap::Value Value; … … 267 267 268 268 typedef MaxCardinalitySearch Create; 269 269 270 270 ///\name Named template parameters 271 271 … … 276 276 typedef T CapacityMap; 277 277 static CapacityMap *createCapacityMap(const Digraph &) { 278 279 280 } 281 }; 282 /// \brief \ref named-templ-param "Named parameter" for setting 278 LEMON_ASSERT(false,"Uninitialized parameter."); 279 return 0; 280 } 281 }; 282 /// \brief \ref named-templ-param "Named parameter" for setting 283 283 /// CapacityMap type 284 284 /// … … 286 286 /// for the algorithm. 287 287 template <class T> 288 struct SetCapacityMap 289 : public MaxCardinalitySearch<Digraph, CapacityMap, 290 DefCapacityMapTraits<T> > { 291 typedef MaxCardinalitySearch<Digraph, CapacityMap, 288 struct SetCapacityMap 289 : public MaxCardinalitySearch<Digraph, CapacityMap, 290 DefCapacityMapTraits<T> > { 291 typedef MaxCardinalitySearch<Digraph, CapacityMap, 292 292 DefCapacityMapTraits<T> > Create; 293 293 }; … … 296 296 struct DefCardinalityMapTraits : public Traits { 297 297 typedef T CardinalityMap; 298 static CardinalityMap *createCardinalityMap(const Digraph &) 298 static CardinalityMap *createCardinalityMap(const Digraph &) 299 299 { 300 301 302 } 303 }; 304 /// \brief \ref named-templ-param "Named parameter" for setting 300 LEMON_ASSERT(false,"Uninitialized parameter."); 301 return 0; 302 } 303 }; 304 /// \brief \ref named-templ-param "Named parameter" for setting 305 305 /// CardinalityMap type 306 306 /// 307 /// \ref named-templ-param "Named parameter" for setting CardinalityMap 307 /// \ref named-templ-param "Named parameter" for setting CardinalityMap 308 308 /// type for the algorithm. 309 309 template <class T> 310 struct SetCardinalityMap 311 : public MaxCardinalitySearch<Digraph, CapacityMap, 312 DefCardinalityMapTraits<T> > { 313 typedef MaxCardinalitySearch<Digraph, CapacityMap, 310 struct SetCardinalityMap 311 : public MaxCardinalitySearch<Digraph, CapacityMap, 312 DefCardinalityMapTraits<T> > { 313 typedef MaxCardinalitySearch<Digraph, CapacityMap, 314 314 DefCardinalityMapTraits<T> > Create; 315 315 }; 316 316 317 317 template <class T> 318 318 struct DefProcessedMapTraits : public Traits { 319 319 typedef T ProcessedMap; 320 320 static ProcessedMap *createProcessedMap(const Digraph &) { 321 322 323 } 324 }; 325 /// \brief \ref named-templ-param "Named parameter" for setting 321 LEMON_ASSERT(false,"Uninitialized parameter."); 322 return 0; 323 } 324 }; 325 /// \brief \ref named-templ-param "Named parameter" for setting 326 326 /// ProcessedMap type 327 327 /// … … 329 329 /// for the algorithm. 330 330 template <class T> 331 struct SetProcessedMap 332 : public MaxCardinalitySearch<Digraph, CapacityMap, 333 DefProcessedMapTraits<T> > { 334 typedef MaxCardinalitySearch<Digraph, CapacityMap, 331 struct SetProcessedMap 332 : public MaxCardinalitySearch<Digraph, CapacityMap, 333 DefProcessedMapTraits<T> > { 334 typedef MaxCardinalitySearch<Digraph, CapacityMap, 335 335 DefProcessedMapTraits<T> > Create; 336 336 }; 337 337 338 338 template <class H, class CR> 339 339 struct DefHeapTraits : public Traits { … … 341 341 typedef H Heap; 342 342 static HeapCrossRef *createHeapCrossRef(const Digraph &) { 343 344 343 LEMON_ASSERT(false,"Uninitialized parameter."); 344 return 0; 345 345 } 346 346 static Heap *createHeap(HeapCrossRef &) { 347 348 349 } 350 }; 351 /// \brief \ref named-templ-param "Named parameter" for setting heap 347 LEMON_ASSERT(false,"Uninitialized parameter."); 348 return 0; 349 } 350 }; 351 /// \brief \ref named-templ-param "Named parameter" for setting heap 352 352 /// and cross reference type 353 353 /// 354 /// \ref named-templ-param "Named parameter" for setting heap and cross 354 /// \ref named-templ-param "Named parameter" for setting heap and cross 355 355 /// reference type for the algorithm. 356 356 template <class H, class CR = typename Digraph::template NodeMap<int> > 357 357 struct SetHeap 358 : public MaxCardinalitySearch<Digraph, CapacityMap, 359 DefHeapTraits<H, CR> > { 360 typedef MaxCardinalitySearch< Digraph, CapacityMap, 358 : public MaxCardinalitySearch<Digraph, CapacityMap, 359 DefHeapTraits<H, CR> > { 360 typedef MaxCardinalitySearch< Digraph, CapacityMap, 361 361 DefHeapTraits<H, CR> > Create; 362 362 }; … … 367 367 typedef H Heap; 368 368 static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) { 369 369 return new HeapCrossRef(digraph); 370 370 } 371 371 static Heap *createHeap(HeapCrossRef &crossref) { 372 373 } 374 }; 375 376 /// \brief \ref named-templ-param "Named parameter" for setting heap and 372 return new Heap(crossref); 373 } 374 }; 375 376 /// \brief \ref named-templ-param "Named parameter" for setting heap and 377 377 /// cross reference type with automatic allocation 378 378 /// 379 /// \ref named-templ-param "Named parameter" for setting heap and cross 380 /// reference type. It can allocate the heap and the cross reference 381 /// object if the cross reference's constructor waits for the digraph as 379 /// \ref named-templ-param "Named parameter" for setting heap and cross 380 /// reference type. It can allocate the heap and the cross reference 381 /// object if the cross reference's constructor waits for the digraph as 382 382 /// parameter and the heap's constructor waits for the cross reference. 383 383 template <class H, class CR = typename Digraph::template NodeMap<int> > 384 384 struct SetStandardHeap 385 : public MaxCardinalitySearch<Digraph, CapacityMap, 386 DefStandardHeapTraits<H, CR> > { 387 typedef MaxCardinalitySearch<Digraph, CapacityMap, 388 DefStandardHeapTraits<H, CR> > 385 : public MaxCardinalitySearch<Digraph, CapacityMap, 386 DefStandardHeapTraits<H, CR> > { 387 typedef MaxCardinalitySearch<Digraph, CapacityMap, 388 DefStandardHeapTraits<H, CR> > 389 389 Create; 390 390 }; 391 391 392 392 ///@} 393 393 … … 397 397 MaxCardinalitySearch() {} 398 398 399 public: 400 399 public: 400 401 401 /// \brief Constructor. 402 402 /// … … 404 404 ///\param capacity the capacity map used by the algorithm. 405 405 MaxCardinalitySearch(const Digraph& digraph, 406 406 const CapacityMap& capacity) : 407 407 _graph(&digraph), 408 408 _capacity(&capacity), local_capacity(false), … … 442 442 MaxCardinalitySearch &capacityMap(const CapacityMap &m) { 443 443 if (local_capacity) { 444 445 444 delete _capacity; 445 local_capacity=false; 446 446 } 447 447 _capacity=&m; … … 457 457 } 458 458 459 /// \brief Sets the map storing the cardinalities calculated by the 459 /// \brief Sets the map storing the cardinalities calculated by the 460 460 /// algorithm. 461 461 /// … … 467 467 MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) { 468 468 if(local_cardinality) { 469 470 469 delete _cardinality; 470 local_cardinality=false; 471 471 } 472 472 _cardinality = &m; … … 481 481 /// automatically allocated map, of course. 482 482 /// \return <tt> (*this) </tt> 483 MaxCardinalitySearch &processedMap(ProcessedMap &m) 483 MaxCardinalitySearch &processedMap(ProcessedMap &m) 484 484 { 485 485 if(local_processed) { 486 487 486 delete _processed; 487 local_processed=false; 488 488 } 489 489 _processed = &m; … … 508 508 MaxCardinalitySearch &heap(Heap& hp, HeapCrossRef &cr) { 509 509 if(local_heap_cross_ref) { 510 511 510 delete _heap_cross_ref; 511 local_heap_cross_ref = false; 512 512 } 513 513 _heap_cross_ref = &cr; 514 514 if(local_heap) { 515 516 515 delete _heap; 516 local_heap = false; 517 517 } 518 518 _heap = &hp; … … 545 545 void create_maps() { 546 546 if(!_capacity) { 547 548 547 local_capacity = true; 548 _capacity = Traits::createCapacityMap(*_graph); 549 549 } 550 550 if(!_cardinality) { 551 552 551 local_cardinality = true; 552 _cardinality = Traits::createCardinalityMap(*_graph); 553 553 } 554 554 if(!_processed) { 555 556 555 local_processed = true; 556 _processed = Traits::createProcessedMap(*_graph); 557 557 } 558 558 if (!_heap_cross_ref) { 559 560 559 local_heap_cross_ref = true; 560 _heap_cross_ref = Traits::createHeapCrossRef(*_graph); 561 561 } 562 562 if (!_heap) { 563 564 565 } 566 } 567 563 local_heap = true; 564 _heap = Traits::createHeap(*_heap_cross_ref); 565 } 566 } 567 568 568 void finalizeNodeData(Node node, Value capacity) { 569 569 _processed->set(node, true); … … 590 590 _heap->clear(); 591 591 for (NodeIt it(*_graph) ; it != INVALID ; ++it) { 592 593 594 } 595 } 596 592 _processed->set(it, false); 593 _heap_cross_ref->set(it, Heap::PRE_HEAP); 594 } 595 } 596 597 597 /// \brief Adds a new source node. 598 /// 598 /// 599 599 /// Adds a new source node to the priority heap. 600 600 /// … … 602 602 void addSource(Node source, Value capacity = 0) { 603 603 if(_heap->state(source) == Heap::PRE_HEAP) { 604 605 } 606 } 607 604 _heap->push(source, capacity); 605 } 606 } 607 608 608 /// \brief Processes the next node in the priority heap 609 609 /// … … 614 614 /// \warning The priority heap must not be empty! 615 615 Node processNextNode() { 616 Node node = _heap->top(); 616 Node node = _heap->top(); 617 617 finalizeNodeData(node, _heap->prio()); 618 618 _heap->pop(); 619 619 620 620 for (InArcIt it(*_graph, node); it != INVALID; ++it) { 621 622 623 624 625 626 627 628 629 630 631 621 Node source = _graph->source(it); 622 switch (_heap->state(source)) { 623 case Heap::PRE_HEAP: 624 _heap->push(source, (*_capacity)[it]); 625 break; 626 case Heap::IN_HEAP: 627 _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]); 628 break; 629 case Heap::POST_HEAP: 630 break; 631 } 632 632 } 633 633 return node; … … 638 638 /// Next node to be processed. 639 639 /// 640 /// \return The next node to be processed or INVALID if the 640 /// \return The next node to be processed or INVALID if the 641 641 /// priority heap is empty. 642 Node nextNode() { 642 Node nextNode() { 643 643 return !_heap->empty() ? _heap->top() : INVALID; 644 644 } 645 645 646 646 /// \brief Returns \c false if there are nodes 647 647 /// to be processed in the priority heap … … 650 650 /// to be processed in the priority heap 651 651 bool emptyQueue() { return _heap->empty(); } 652 /// \brief Returns the number of the nodes to be processed 652 /// \brief Returns the number of the nodes to be processed 653 653 /// in the priority heap 654 654 /// 655 655 /// Returns the number of the nodes to be processed in the priority heap 656 656 int emptySize() { return _heap->size(); } 657 657 658 658 /// \brief Executes the algorithm. 659 659 /// … … 663 663 /// with addSource() before using this function. 664 664 /// 665 /// This method runs the Maximum Cardinality Search algorithm from the 665 /// This method runs the Maximum Cardinality Search algorithm from the 666 666 /// source node(s). 667 667 void start() { 668 668 while ( !_heap->empty() ) processNextNode(); 669 669 } 670 670 671 671 /// \brief Executes the algorithm until \c dest is reached. 672 672 /// … … 676 676 /// with addSource() before using this function. 677 677 /// 678 /// This method runs the %MaxCardinalitySearch algorithm from the source 678 /// This method runs the %MaxCardinalitySearch algorithm from the source 679 679 /// nodes. 680 680 void start(Node dest) { … … 682 682 if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio()); 683 683 } 684 684 685 685 /// \brief Executes the algorithm until a condition is met. 686 686 /// … … 697 697 if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio()); 698 698 } 699 699 700 700 /// \brief Runs the maximum cardinality search algorithm from node \c s. 701 701 /// 702 /// This method runs the %MaxCardinalitySearch algorithm from a root 702 /// This method runs the %MaxCardinalitySearch algorithm from a root 703 703 /// node \c s. 704 704 /// … … 715 715 } 716 716 717 /// \brief Runs the maximum cardinality search algorithm for the 717 /// \brief Runs the maximum cardinality search algorithm for the 718 718 /// whole digraph. 719 719 /// 720 /// This method runs the %MaxCardinalitySearch algorithm from all 720 /// This method runs the %MaxCardinalitySearch algorithm from all 721 721 /// unprocessed node of the digraph. 722 722 /// … … 740 740 } 741 741 } 742 742 743 743 ///@} 744 744 745 745 /// \name Query Functions 746 /// The results of the maximum cardinality search algorithm can be 746 /// The results of the maximum cardinality search algorithm can be 747 747 /// obtained using these functions. 748 748 /// \n 749 /// Before the use of these functions, either run() or start() must be 749 /// Before the use of these functions, either run() or start() must be 750 750 /// called. 751 751 752 752 ///@{ 753 753 … … 768 768 /// \brief Returns a reference to the NodeMap of cardinalities. 769 769 /// 770 /// Returns a reference to the NodeMap of cardinalities. \pre \ref run() 770 /// Returns a reference to the NodeMap of cardinalities. \pre \ref run() 771 771 /// must be called before using this function. 772 772 const CardinalityMap &cardinalityMap() const { return *_cardinality;} 773 773 774 774 /// \brief Checks if a node is reachable from the root. 775 775 /// … … 785 785 /// \pre \ref run() must be called before using this function. 786 786 bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; } 787 787 788 788 ///@} 789 789 };
Note: See TracChangeset
for help on using the changeset viewer.
