Changes in lemon/max_cardinality_search.h [1129:9a3187204242:1271:fb1c7da561ce] in lemon
- File:
-
- 1 edited
-
lemon/max_cardinality_search.h (modified) (43 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/max_cardinality_search.h
r1129 r1271 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 \ref168 /// CardinalityMap166 /// This function instantiates a \ref CardinalityMap. 167 /// \param digraph is the digraph, to which we would like to 168 /// define the \ref CardinalityMap 169 169 static CardinalityMap *createCardinalityMap(const Digraph &digraph) { 170 170 return new CardinalityMap(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 /// with maximum cardinality, i.e the sum of capacities on out arcs to the nodes 183 /// with maximum cardinality, i.e the sum of capacities on out arcs 184 /// to the nodes 184 185 /// which were previusly processed. 185 186 /// If there is a cut in the digraph the algorithm should choose … … 187 188 188 189 /// The arc capacities are passed to the algorithm using a 189 /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 190 /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 190 191 /// kind of capacity. 191 192 /// 192 /// The type of the capacity is determined by the \ref 193 /// The type of the capacity is determined by the \ref 193 194 /// concepts::ReadMap::Value "Value" of the capacity map. 194 195 /// … … 197 198 /// 198 199 /// \param GR The digraph type the algorithm runs on. The value of 199 /// Digraph is not used directly by the search algorithm, it 200 /// Digraph is not used directly by the search algorithm, it 200 201 /// is only passed to \ref MaxCardinalitySearchDefaultTraits. 201 /// \param CAP This read-only ArcMap determines the capacities of 202 /// \param CAP This read-only ArcMap determines the capacities of 202 203 /// the arcs. It is read once for each arc, so the map may involve in 203 204 /// relatively time consuming process to compute the arc capacity if 204 205 /// it is necessary. The default map type is \ref 205 206 /// 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 207 /// of CapacityMap is not used directly by search algorithm, it is only 208 /// passed to \ref MaxCardinalitySearchDefaultTraits. 209 /// \param TR Traits class to set various data types used by the 210 /// algorithm. The default traits class is 211 /// \ref MaxCardinalitySearchDefaultTraits 212 /// "MaxCardinalitySearchDefaultTraits<GR, CAP>". 213 /// See \ref MaxCardinalitySearchDefaultTraits 213 214 /// for the documentation of a MaxCardinalitySearch traits class. 214 215 … … 216 217 template <typename GR, typename CAP, typename TR> 217 218 #else 218 template <typename GR, typename CAP = 219 220 typename TR = 219 template <typename GR, typename CAP = 220 ConstMap<typename GR::Arc, Const<int,1> >, 221 typename TR = 221 222 MaxCardinalitySearchDefaultTraits<GR, CAP> > 222 223 #endif … … 227 228 ///The type of the underlying digraph. 228 229 typedef typename Traits::Digraph Digraph; 229 230 230 231 ///The type of the capacity of the arcs. 231 232 typedef typename Traits::CapacityMap::Value Value; … … 267 268 268 269 typedef MaxCardinalitySearch Create; 269 270 270 271 ///\name Named template parameters 271 272 … … 276 277 typedef T CapacityMap; 277 278 static CapacityMap *createCapacityMap(const Digraph &) { 278 279 280 } 281 }; 282 /// \brief \ref named-templ-param "Named parameter" for setting 279 LEMON_ASSERT(false,"Uninitialized parameter."); 280 return 0; 281 } 282 }; 283 /// \brief \ref named-templ-param "Named parameter" for setting 283 284 /// CapacityMap type 284 285 /// … … 286 287 /// for the algorithm. 287 288 template <class T> 288 struct SetCapacityMap 289 : public MaxCardinalitySearch<Digraph, CapacityMap, 290 DefCapacityMapTraits<T> > { 291 typedef MaxCardinalitySearch<Digraph, CapacityMap, 289 struct SetCapacityMap 290 : public MaxCardinalitySearch<Digraph, CapacityMap, 291 DefCapacityMapTraits<T> > { 292 typedef MaxCardinalitySearch<Digraph, CapacityMap, 292 293 DefCapacityMapTraits<T> > Create; 293 294 }; … … 296 297 struct DefCardinalityMapTraits : public Traits { 297 298 typedef T CardinalityMap; 298 static CardinalityMap *createCardinalityMap(const Digraph &) 299 static CardinalityMap *createCardinalityMap(const Digraph &) 299 300 { 300 301 302 } 303 }; 304 /// \brief \ref named-templ-param "Named parameter" for setting 301 LEMON_ASSERT(false,"Uninitialized parameter."); 302 return 0; 303 } 304 }; 305 /// \brief \ref named-templ-param "Named parameter" for setting 305 306 /// CardinalityMap type 306 307 /// 307 /// \ref named-templ-param "Named parameter" for setting CardinalityMap 308 /// \ref named-templ-param "Named parameter" for setting CardinalityMap 308 309 /// type for the algorithm. 309 310 template <class T> 310 struct SetCardinalityMap 311 : public MaxCardinalitySearch<Digraph, CapacityMap, 312 DefCardinalityMapTraits<T> > { 313 typedef MaxCardinalitySearch<Digraph, CapacityMap, 311 struct SetCardinalityMap 312 : public MaxCardinalitySearch<Digraph, CapacityMap, 313 DefCardinalityMapTraits<T> > { 314 typedef MaxCardinalitySearch<Digraph, CapacityMap, 314 315 DefCardinalityMapTraits<T> > Create; 315 316 }; 316 317 317 318 template <class T> 318 319 struct DefProcessedMapTraits : public Traits { 319 320 typedef T ProcessedMap; 320 321 static ProcessedMap *createProcessedMap(const Digraph &) { 321 322 323 } 324 }; 325 /// \brief \ref named-templ-param "Named parameter" for setting 322 LEMON_ASSERT(false,"Uninitialized parameter."); 323 return 0; 324 } 325 }; 326 /// \brief \ref named-templ-param "Named parameter" for setting 326 327 /// ProcessedMap type 327 328 /// … … 329 330 /// for the algorithm. 330 331 template <class T> 331 struct SetProcessedMap 332 : public MaxCardinalitySearch<Digraph, CapacityMap, 333 DefProcessedMapTraits<T> > { 334 typedef MaxCardinalitySearch<Digraph, CapacityMap, 332 struct SetProcessedMap 333 : public MaxCardinalitySearch<Digraph, CapacityMap, 334 DefProcessedMapTraits<T> > { 335 typedef MaxCardinalitySearch<Digraph, CapacityMap, 335 336 DefProcessedMapTraits<T> > Create; 336 337 }; 337 338 338 339 template <class H, class CR> 339 340 struct DefHeapTraits : public Traits { … … 341 342 typedef H Heap; 342 343 static HeapCrossRef *createHeapCrossRef(const Digraph &) { 343 344 344 LEMON_ASSERT(false,"Uninitialized parameter."); 345 return 0; 345 346 } 346 347 static Heap *createHeap(HeapCrossRef &) { 347 348 349 } 350 }; 351 /// \brief \ref named-templ-param "Named parameter" for setting heap 348 LEMON_ASSERT(false,"Uninitialized parameter."); 349 return 0; 350 } 351 }; 352 /// \brief \ref named-templ-param "Named parameter" for setting heap 352 353 /// and cross reference type 353 354 /// 354 /// \ref named-templ-param "Named parameter" for setting heap and cross 355 /// \ref named-templ-param "Named parameter" for setting heap and cross 355 356 /// reference type for the algorithm. 356 357 template <class H, class CR = typename Digraph::template NodeMap<int> > 357 358 struct SetHeap 358 : public MaxCardinalitySearch<Digraph, CapacityMap, 359 DefHeapTraits<H, CR> > { 360 typedef MaxCardinalitySearch< Digraph, CapacityMap, 359 : public MaxCardinalitySearch<Digraph, CapacityMap, 360 DefHeapTraits<H, CR> > { 361 typedef MaxCardinalitySearch< Digraph, CapacityMap, 361 362 DefHeapTraits<H, CR> > Create; 362 363 }; … … 367 368 typedef H Heap; 368 369 static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) { 369 370 return new HeapCrossRef(digraph); 370 371 } 371 372 static Heap *createHeap(HeapCrossRef &crossref) { 372 373 } 374 }; 375 376 /// \brief \ref named-templ-param "Named parameter" for setting heap and 373 return new Heap(crossref); 374 } 375 }; 376 377 /// \brief \ref named-templ-param "Named parameter" for setting heap and 377 378 /// cross reference type with automatic allocation 378 379 /// 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 380 /// \ref named-templ-param "Named parameter" for setting heap and cross 381 /// reference type. It can allocate the heap and the cross reference 382 /// object if the cross reference's constructor waits for the digraph as 382 383 /// parameter and the heap's constructor waits for the cross reference. 383 384 template <class H, class CR = typename Digraph::template NodeMap<int> > 384 385 struct SetStandardHeap 385 : public MaxCardinalitySearch<Digraph, CapacityMap, 386 DefStandardHeapTraits<H, CR> > { 387 typedef MaxCardinalitySearch<Digraph, CapacityMap, 388 DefStandardHeapTraits<H, CR> > 386 : public MaxCardinalitySearch<Digraph, CapacityMap, 387 DefStandardHeapTraits<H, CR> > { 388 typedef MaxCardinalitySearch<Digraph, CapacityMap, 389 DefStandardHeapTraits<H, CR> > 389 390 Create; 390 391 }; 391 392 392 393 ///@} 393 394 … … 397 398 MaxCardinalitySearch() {} 398 399 399 public: 400 400 public: 401 401 402 /// \brief Constructor. 402 403 /// … … 404 405 ///\param capacity the capacity map used by the algorithm. 405 406 MaxCardinalitySearch(const Digraph& digraph, 406 407 const CapacityMap& capacity) : 407 408 _graph(&digraph), 408 409 _capacity(&capacity), local_capacity(false), … … 442 443 MaxCardinalitySearch &capacityMap(const CapacityMap &m) { 443 444 if (local_capacity) { 444 445 445 delete _capacity; 446 local_capacity=false; 446 447 } 447 448 _capacity=&m; … … 457 458 } 458 459 459 /// \brief Sets the map storing the cardinalities calculated by the 460 /// \brief Sets the map storing the cardinalities calculated by the 460 461 /// algorithm. 461 462 /// … … 467 468 MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) { 468 469 if(local_cardinality) { 469 470 470 delete _cardinality; 471 local_cardinality=false; 471 472 } 472 473 _cardinality = &m; … … 481 482 /// automatically allocated map, of course. 482 483 /// \return <tt> (*this) </tt> 483 MaxCardinalitySearch &processedMap(ProcessedMap &m) 484 MaxCardinalitySearch &processedMap(ProcessedMap &m) 484 485 { 485 486 if(local_processed) { 486 487 487 delete _processed; 488 local_processed=false; 488 489 } 489 490 _processed = &m; … … 508 509 MaxCardinalitySearch &heap(Heap& hp, HeapCrossRef &cr) { 509 510 if(local_heap_cross_ref) { 510 511 511 delete _heap_cross_ref; 512 local_heap_cross_ref = false; 512 513 } 513 514 _heap_cross_ref = &cr; 514 515 if(local_heap) { 515 516 516 delete _heap; 517 local_heap = false; 517 518 } 518 519 _heap = &hp; … … 545 546 void create_maps() { 546 547 if(!_capacity) { 547 548 548 local_capacity = true; 549 _capacity = Traits::createCapacityMap(*_graph); 549 550 } 550 551 if(!_cardinality) { 551 552 552 local_cardinality = true; 553 _cardinality = Traits::createCardinalityMap(*_graph); 553 554 } 554 555 if(!_processed) { 555 556 556 local_processed = true; 557 _processed = Traits::createProcessedMap(*_graph); 557 558 } 558 559 if (!_heap_cross_ref) { 559 560 560 local_heap_cross_ref = true; 561 _heap_cross_ref = Traits::createHeapCrossRef(*_graph); 561 562 } 562 563 if (!_heap) { 563 564 565 } 566 } 567 564 local_heap = true; 565 _heap = Traits::createHeap(*_heap_cross_ref); 566 } 567 } 568 568 569 void finalizeNodeData(Node node, Value capacity) { 569 570 _processed->set(node, true); … … 590 591 _heap->clear(); 591 592 for (NodeIt it(*_graph) ; it != INVALID ; ++it) { 592 593 594 } 595 } 596 593 _processed->set(it, false); 594 _heap_cross_ref->set(it, Heap::PRE_HEAP); 595 } 596 } 597 597 598 /// \brief Adds a new source node. 598 /// 599 /// 599 600 /// Adds a new source node to the priority heap. 600 601 /// … … 602 603 void addSource(Node source, Value capacity = 0) { 603 604 if(_heap->state(source) == Heap::PRE_HEAP) { 604 605 } 606 } 607 605 _heap->push(source, capacity); 606 } 607 } 608 608 609 /// \brief Processes the next node in the priority heap 609 610 /// … … 614 615 /// \warning The priority heap must not be empty! 615 616 Node processNextNode() { 616 Node node = _heap->top(); 617 Node node = _heap->top(); 617 618 finalizeNodeData(node, _heap->prio()); 618 619 _heap->pop(); 619 620 620 621 for (InArcIt it(*_graph, node); it != INVALID; ++it) { 621 622 623 624 625 626 627 628 629 630 631 622 Node source = _graph->source(it); 623 switch (_heap->state(source)) { 624 case Heap::PRE_HEAP: 625 _heap->push(source, (*_capacity)[it]); 626 break; 627 case Heap::IN_HEAP: 628 _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]); 629 break; 630 case Heap::POST_HEAP: 631 break; 632 } 632 633 } 633 634 return node; … … 638 639 /// Next node to be processed. 639 640 /// 640 /// \return The next node to be processed or INVALID if the 641 /// \return The next node to be processed or INVALID if the 641 642 /// priority heap is empty. 642 Node nextNode() { 643 Node nextNode() { 643 644 return !_heap->empty() ? _heap->top() : INVALID; 644 645 } 645 646 646 647 /// \brief Returns \c false if there are nodes 647 648 /// to be processed in the priority heap … … 650 651 /// to be processed in the priority heap 651 652 bool emptyQueue() { return _heap->empty(); } 652 /// \brief Returns the number of the nodes to be processed 653 /// \brief Returns the number of the nodes to be processed 653 654 /// in the priority heap 654 655 /// 655 656 /// Returns the number of the nodes to be processed in the priority heap 656 657 int emptySize() { return _heap->size(); } 657 658 658 659 /// \brief Executes the algorithm. 659 660 /// … … 663 664 /// with addSource() before using this function. 664 665 /// 665 /// This method runs the Maximum Cardinality Search algorithm from the 666 /// This method runs the Maximum Cardinality Search algorithm from the 666 667 /// source node(s). 667 668 void start() { 668 669 while ( !_heap->empty() ) processNextNode(); 669 670 } 670 671 671 672 /// \brief Executes the algorithm until \c dest is reached. 672 673 /// … … 676 677 /// with addSource() before using this function. 677 678 /// 678 /// This method runs the %MaxCardinalitySearch algorithm from the source 679 /// This method runs the %MaxCardinalitySearch algorithm from the source 679 680 /// nodes. 680 681 void start(Node dest) { … … 682 683 if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio()); 683 684 } 684 685 685 686 /// \brief Executes the algorithm until a condition is met. 686 687 /// … … 697 698 if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio()); 698 699 } 699 700 700 701 /// \brief Runs the maximum cardinality search algorithm from node \c s. 701 702 /// 702 /// This method runs the %MaxCardinalitySearch algorithm from a root 703 /// This method runs the %MaxCardinalitySearch algorithm from a root 703 704 /// node \c s. 704 705 /// … … 715 716 } 716 717 717 /// \brief Runs the maximum cardinality search algorithm for the 718 /// \brief Runs the maximum cardinality search algorithm for the 718 719 /// whole digraph. 719 720 /// 720 /// This method runs the %MaxCardinalitySearch algorithm from all 721 /// This method runs the %MaxCardinalitySearch algorithm from all 721 722 /// unprocessed node of the digraph. 722 723 /// … … 740 741 } 741 742 } 742 743 743 744 ///@} 744 745 745 746 /// \name Query Functions 746 /// The results of the maximum cardinality search algorithm can be 747 /// The results of the maximum cardinality search algorithm can be 747 748 /// obtained using these functions. 748 749 /// \n 749 /// Before the use of these functions, either run() or start() must be 750 /// Before the use of these functions, either run() or start() must be 750 751 /// called. 751 752 752 753 ///@{ 753 754 … … 768 769 /// \brief Returns a reference to the NodeMap of cardinalities. 769 770 /// 770 /// Returns a reference to the NodeMap of cardinalities. \pre \ref run() 771 /// Returns a reference to the NodeMap of cardinalities. \pre \ref run() 771 772 /// must be called before using this function. 772 773 const CardinalityMap &cardinalityMap() const { return *_cardinality;} 773 774 774 775 /// \brief Checks if a node is reachable from the root. 775 776 /// … … 785 786 /// \pre \ref run() must be called before using this function. 786 787 bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; } 787 788 788 789 ///@} 789 790 };
Note: See TracChangeset
for help on using the changeset viewer.
