Changeset 907:1937b6455b7d in lemon-main
- Timestamp:
- 09/22/10 09:38:23 (14 years ago)
- Branch:
- default
- Children:
- 908:10242c611190, 913:5087694945e4, 916:70bee017b584
- Parents:
- 905:de428ebb47ab (diff), 906:e24922c56bc2 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent. - Phase:
- public
- Files:
-
- 4 edited
-
lemon/dfs.h (modified) (2 diffs)
-
lemon/dfs.h (modified) (54 diffs)
-
test/dfs_test.cc (modified) (4 diffs)
-
test/dfs_test.cc (modified) (4 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/dfs.h
r877 r907 566 566 void start(Node t) 567 567 { 568 while ( !emptyQueue() && G->target(_stack[_stack_head])!=t)568 while ( !emptyQueue() && !(*_reached)[t] ) 569 569 processNextArc(); 570 570 } … … 1513 1513 /// with addSource() before using this function. 1514 1514 void start(Node t) { 1515 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t)1515 while ( !emptyQueue() && !(*_reached)[t] ) 1516 1516 processNextArc(); 1517 1517 } -
lemon/dfs.h
r906 r907 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 085 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 48 48 ///The type of the map that stores the predecessor 49 49 ///arcs of the %DFS paths. 50 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.50 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 51 51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 52 ///Instantiates a PredMap.53 54 ///This function instantiates a PredMap.52 ///Instantiates a \c PredMap. 53 54 ///This function instantiates a \ref PredMap. 55 55 ///\param g is the digraph, to which we would like to define the 56 /// PredMap.56 ///\ref PredMap. 57 57 static PredMap *createPredMap(const Digraph &g) 58 58 { … … 63 63 64 64 ///The type of the map that indicates which nodes are processed. 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 65 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 66 ///By default, it is a NullMap. 66 67 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 67 ///Instantiates a ProcessedMap.68 69 ///This function instantiates a ProcessedMap.68 ///Instantiates a \c ProcessedMap. 69 70 ///This function instantiates a \ref ProcessedMap. 70 71 ///\param g is the digraph, to which 71 ///we would like to define the ProcessedMap72 ///we would like to define the \ref ProcessedMap. 72 73 #ifdef DOXYGEN 73 74 static ProcessedMap *createProcessedMap(const Digraph &g) … … 82 83 83 84 ///The type of the map that indicates which nodes are reached. 84 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 ///It must conform to 86 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 87 typedef typename Digraph::template NodeMap<bool> ReachedMap; 86 ///Instantiates a ReachedMap.87 88 ///This function instantiates a ReachedMap.88 ///Instantiates a \c ReachedMap. 89 90 ///This function instantiates a \ref ReachedMap. 89 91 ///\param g is the digraph, to which 90 ///we would like to define the ReachedMap.92 ///we would like to define the \ref ReachedMap. 91 93 static ReachedMap *createReachedMap(const Digraph &g) 92 94 { … … 97 99 98 100 ///The type of the map that stores the distances of the nodes. 99 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.101 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 100 102 typedef typename Digraph::template NodeMap<int> DistMap; 101 ///Instantiates a DistMap.102 103 ///This function instantiates a DistMap.103 ///Instantiates a \c DistMap. 104 105 ///This function instantiates a \ref DistMap. 104 106 ///\param g is the digraph, to which we would like to define the 105 /// DistMap.107 ///\ref DistMap. 106 108 static DistMap *createDistMap(const Digraph &g) 107 109 { … … 120 122 /// 121 123 ///\tparam GR The type of the digraph the algorithm runs on. 122 ///The default value is \ref ListDigraph. The value of GR is not used 123 ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits. 124 ///\tparam TR Traits class to set various data types used by the algorithm. 125 ///The default traits class is 126 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>". 127 ///See \ref DfsDefaultTraits for the documentation of 128 ///a Dfs traits class. 124 ///The default type is \ref ListDigraph. 125 ///\tparam TR The traits class that defines various types used by the 126 ///algorithm. By default, it is \ref DfsDefaultTraits 127 ///"DfsDefaultTraits<GR>". 128 ///In most cases, this parameter should not be set directly, 129 ///consider to use the named template parameters instead. 129 130 #ifdef DOXYGEN 130 131 template <typename GR, … … 152 153 typedef PredMapPath<Digraph, PredMap> Path; 153 154 154 ///The traits class.155 ///The \ref DfsDefaultTraits "traits class" of the algorithm. 155 156 typedef TR Traits; 156 157 … … 213 214 typedef Dfs Create; 214 215 215 ///\name Named template parameters216 ///\name Named Template Parameters 216 217 217 218 ///@{ … … 227 228 }; 228 229 ///\brief \ref named-templ-param "Named parameter" for setting 229 /// PredMap type.230 ///\c PredMap type. 230 231 /// 231 232 ///\ref named-templ-param "Named parameter" for setting 232 ///PredMap type. 233 ///\c PredMap type. 234 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 233 235 template <class T> 234 236 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > { … … 246 248 }; 247 249 ///\brief \ref named-templ-param "Named parameter" for setting 248 /// DistMap type.250 ///\c DistMap type. 249 251 /// 250 252 ///\ref named-templ-param "Named parameter" for setting 251 ///DistMap type. 253 ///\c DistMap type. 254 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 252 255 template <class T> 253 256 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > { … … 265 268 }; 266 269 ///\brief \ref named-templ-param "Named parameter" for setting 267 /// ReachedMap type.270 ///\c ReachedMap type. 268 271 /// 269 272 ///\ref named-templ-param "Named parameter" for setting 270 ///ReachedMap type. 273 ///\c ReachedMap type. 274 ///It must conform to 275 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 271 276 template <class T> 272 277 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > { … … 284 289 }; 285 290 ///\brief \ref named-templ-param "Named parameter" for setting 286 /// ProcessedMap type.291 ///\c ProcessedMap type. 287 292 /// 288 293 ///\ref named-templ-param "Named parameter" for setting 289 ///ProcessedMap type. 294 ///\c ProcessedMap type. 295 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 290 296 template <class T> 291 297 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > { … … 301 307 }; 302 308 ///\brief \ref named-templ-param "Named parameter" for setting 303 /// ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.309 ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 304 310 /// 305 311 ///\ref named-templ-param "Named parameter" for setting 306 /// ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.312 ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 307 313 ///If you don't set it explicitly, it will be automatically allocated. 308 314 struct SetStandardProcessedMap : … … 339 345 340 346 ///Sets the map that stores the predecessor arcs. 341 ///If you don't use this function before calling \ref run(), 342 ///it will allocate one. The destructor deallocates this 343 ///automatically allocated map, of course. 347 ///If you don't use this function before calling \ref run(Node) "run()" 348 ///or \ref init(), an instance will be allocated automatically. 349 ///The destructor deallocates this automatically allocated map, 350 ///of course. 344 351 ///\return <tt> (*this) </tt> 345 352 Dfs &predMap(PredMap &m) … … 356 363 357 364 ///Sets the map that indicates which nodes are reached. 358 ///If you don't use this function before calling \ref run(), 359 ///it will allocate one. The destructor deallocates this 360 ///automatically allocated map, of course. 365 ///If you don't use this function before calling \ref run(Node) "run()" 366 ///or \ref init(), an instance will be allocated automatically. 367 ///The destructor deallocates this automatically allocated map, 368 ///of course. 361 369 ///\return <tt> (*this) </tt> 362 370 Dfs &reachedMap(ReachedMap &m) … … 373 381 374 382 ///Sets the map that indicates which nodes are processed. 375 ///If you don't use this function before calling \ref run(), 376 ///it will allocate one. The destructor deallocates this 377 ///automatically allocated map, of course. 383 ///If you don't use this function before calling \ref run(Node) "run()" 384 ///or \ref init(), an instance will be allocated automatically. 385 ///The destructor deallocates this automatically allocated map, 386 ///of course. 378 387 ///\return <tt> (*this) </tt> 379 388 Dfs &processedMap(ProcessedMap &m) … … 391 400 ///Sets the map that stores the distances of the nodes calculated by 392 401 ///the algorithm. 393 ///If you don't use this function before calling \ref run(), 394 ///it will allocate one. The destructor deallocates this 395 ///automatically allocated map, of course. 402 ///If you don't use this function before calling \ref run(Node) "run()" 403 ///or \ref init(), an instance will be allocated automatically. 404 ///The destructor deallocates this automatically allocated map, 405 ///of course. 396 406 ///\return <tt> (*this) </tt> 397 407 Dfs &distMap(DistMap &m) … … 407 417 public: 408 418 409 ///\name Execution control 410 ///The simplest way to execute the algorithm is to use 411 ///one of the member functions called \ref lemon::Dfs::run() "run()". 412 ///\n 413 ///If you need more control on the execution, first you must call 414 ///\ref lemon::Dfs::init() "init()", then you can add a source node 415 ///with \ref lemon::Dfs::addSource() "addSource()". 416 ///Finally \ref lemon::Dfs::start() "start()" will perform the 417 ///actual path computation. 419 ///\name Execution Control 420 ///The simplest way to execute the DFS algorithm is to use one of the 421 ///member functions called \ref run(Node) "run()".\n 422 ///If you need better control on the execution, you have to call 423 ///\ref init() first, then you can add a source node with \ref addSource() 424 ///and perform the actual computation with \ref start(). 425 ///This procedure can be repeated if there are nodes that have not 426 ///been reached. 418 427 419 428 ///@{ 420 429 430 ///\brief Initializes the internal data structures. 431 /// 421 432 ///Initializes the internal data structures. 422 423 ///Initializes the internal data structures.424 ///425 433 void init() 426 434 { … … 439 447 ///Adds a new source node to the set of nodes to be processed. 440 448 /// 441 ///\pre The stack must be empty. (Otherwise the algorithm gives 442 ///false results.) 443 /// 444 ///\warning Distances will be wrong (or at least strange) in case of 445 ///multiple sources. 449 ///\pre The stack must be empty. Otherwise the algorithm gives 450 ///wrong results. (One of the outgoing arcs of all the source nodes 451 ///except for the last one will not be visited and distances will 452 ///also be wrong.) 446 453 void addSource(Node s) 447 454 { … … 507 514 } 508 515 509 ///\brief Returns \c false if there are nodes 510 ///to be processed. 511 /// 512 ///Returns \c false if there are nodes 513 ///to be processed in the queue (stack). 516 ///Returns \c false if there are nodes to be processed. 517 518 ///Returns \c false if there are nodes to be processed 519 ///in the queue (stack). 514 520 bool emptyQueue() const { return _stack_head<0; } 515 521 516 522 ///Returns the number of the nodes to be processed. 517 523 518 ///Returns the number of the nodes to be processed in the queue (stack). 524 ///Returns the number of the nodes to be processed 525 ///in the queue (stack). 519 526 int queueSize() const { return _stack_head+1; } 520 527 … … 634 641 ///Runs the algorithm to visit all nodes in the digraph. 635 642 636 ///This method runs the %DFS algorithm in order to compute the 637 ///%DFS path to each node. 638 /// 639 ///The algorithm computes 640 ///- the %DFS tree, 641 ///- the distance of each node from the root in the %DFS tree. 643 ///This method runs the %DFS algorithm in order to visit all nodes 644 ///in the digraph. 642 645 /// 643 646 ///\note <tt>d.run()</tt> is just a shortcut of the following code. … … 664 667 665 668 ///\name Query Functions 666 ///The result of the %DFS algorithm can be obtained using these669 ///The results of the DFS algorithm can be obtained using these 667 670 ///functions.\n 668 ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()669 /// "start()" must be calledbefore using them.671 ///Either \ref run(Node) "run()" or \ref start() should be called 672 ///before using them. 670 673 671 674 ///@{ 672 675 673 ///The DFS path to anode.674 675 ///Returns the DFS path to a node.676 /// 677 ///\warning \c t should be reach able from the root.678 /// 679 ///\pre Either \ref run( ) or \ref start() must be called before680 /// using this function.676 ///The DFS path to the given node. 677 678 ///Returns the DFS path to the given node from the root(s). 679 /// 680 ///\warning \c t should be reached from the root(s). 681 /// 682 ///\pre Either \ref run(Node) "run()" or \ref init() 683 ///must be called before using this function. 681 684 Path path(Node t) const { return Path(*G, *_pred, t); } 682 685 683 ///The distance of a node from the root.684 685 ///Returns the distance of a node from the root.686 /// 687 ///\warning If node \c v is not reach able from the root, then686 ///The distance of the given node from the root(s). 687 688 ///Returns the distance of the given node from the root(s). 689 /// 690 ///\warning If node \c v is not reached from the root(s), then 688 691 ///the return value of this function is undefined. 689 692 /// 690 ///\pre Either \ref run( ) or \ref start() must be called before691 /// using this function.693 ///\pre Either \ref run(Node) "run()" or \ref init() 694 ///must be called before using this function. 692 695 int dist(Node v) const { return (*_dist)[v]; } 693 696 694 ///Returns the 'previous arc' of the %DFS tree for anode.697 ///Returns the 'previous arc' of the %DFS tree for the given node. 695 698 696 699 ///This function returns the 'previous arc' of the %DFS tree for the 697 ///node \c v, i.e. it returns the last arc of a %DFS path from the698 ///root to \c v. It is \c INVALID 699 /// if \c v is not reachable from theroot(s) or if \c v is a root.700 ///node \c v, i.e. it returns the last arc of a %DFS path from a 701 ///root to \c v. It is \c INVALID if \c v is not reached from the 702 ///root(s) or if \c v is a root. 700 703 /// 701 704 ///The %DFS tree used here is equal to the %DFS tree used in 702 ///\ref predNode() .703 /// 704 ///\pre Either \ref run( ) or \ref start() must be called before using705 /// this function.705 ///\ref predNode() and \ref predMap(). 706 /// 707 ///\pre Either \ref run(Node) "run()" or \ref init() 708 ///must be called before using this function. 706 709 Arc predArc(Node v) const { return (*_pred)[v];} 707 710 708 ///Returns the 'previous node' of the %DFS tree .711 ///Returns the 'previous node' of the %DFS tree for the given node. 709 712 710 713 ///This function returns the 'previous node' of the %DFS 711 714 ///tree for the node \c v, i.e. it returns the last but one node 712 /// from a %DFS path from theroot to \c v. It is \c INVALID713 ///if \c v is not reach ablefrom the root(s) or if \c v is a root.715 ///of a %DFS path from a root to \c v. It is \c INVALID 716 ///if \c v is not reached from the root(s) or if \c v is a root. 714 717 /// 715 718 ///The %DFS tree used here is equal to the %DFS tree used in 716 ///\ref predArc() .717 /// 718 ///\pre Either \ref run( ) or \ref start() must be called before719 /// using this function.719 ///\ref predArc() and \ref predMap(). 720 /// 721 ///\pre Either \ref run(Node) "run()" or \ref init() 722 ///must be called before using this function. 720 723 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 721 724 G->source((*_pred)[v]); } … … 727 730 ///distances of the nodes calculated by the algorithm. 728 731 /// 729 ///\pre Either \ref run( )or \ref init()732 ///\pre Either \ref run(Node) "run()" or \ref init() 730 733 ///must be called before using this function. 731 734 const DistMap &distMap() const { return *_dist;} … … 735 738 /// 736 739 ///Returns a const reference to the node map that stores the predecessor 737 ///arcs, which form the DFS tree .738 /// 739 ///\pre Either \ref run( )or \ref init()740 ///arcs, which form the DFS tree (forest). 741 /// 742 ///\pre Either \ref run(Node) "run()" or \ref init() 740 743 ///must be called before using this function. 741 744 const PredMap &predMap() const { return *_pred;} 742 745 743 ///Checks if a node is reachable from the root(s). 744 745 ///Returns \c true if \c v is reachable from the root(s). 746 ///\pre Either \ref run() or \ref start() 746 ///Checks if the given node. node is reached from the root(s). 747 748 ///Returns \c true if \c v is reached from the root(s). 749 /// 750 ///\pre Either \ref run(Node) "run()" or \ref init() 747 751 ///must be called before using this function. 748 752 bool reached(Node v) const { return (*_reached)[v]; } … … 766 770 ///The type of the map that stores the predecessor 767 771 ///arcs of the %DFS paths. 768 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.772 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 769 773 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 770 774 ///Instantiates a PredMap. … … 781 785 782 786 ///The type of the map that indicates which nodes are processed. 783 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.784 ///By default it is a NullMap.787 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 788 ///By default, it is a NullMap. 785 789 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 786 790 ///Instantiates a ProcessedMap. … … 801 805 802 806 ///The type of the map that indicates which nodes are reached. 803 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 807 ///It must conform to 808 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 804 809 typedef typename Digraph::template NodeMap<bool> ReachedMap; 805 810 ///Instantiates a ReachedMap. … … 816 821 817 822 ///The type of the map that stores the distances of the nodes. 818 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.823 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 819 824 typedef typename Digraph::template NodeMap<int> DistMap; 820 825 ///Instantiates a DistMap. … … 831 836 832 837 ///The type of the DFS paths. 833 ///It must meetthe \ref concepts::Path "Path" concept.838 ///It must conform to the \ref concepts::Path "Path" concept. 834 839 typedef lemon::Path<Digraph> Path; 835 840 }; … … 837 842 /// Default traits class used by DfsWizard 838 843 839 /// To make it easier to use Dfs algorithm 840 /// we have created a wizard class. 841 /// This \ref DfsWizard class needs default traits, 842 /// as well as the \ref Dfs class. 843 /// The \ref DfsWizardBase is a class to be the default traits of the 844 /// \ref DfsWizard class. 844 /// Default traits class used by DfsWizard. 845 /// \tparam GR The type of the digraph. 845 846 template<class GR> 846 847 class DfsWizardBase : public DfsWizardDefaultTraits<GR> … … 870 871 /// Constructor. 871 872 872 /// This constructor does not require parameters, thereforeit initiates873 /// This constructor does not require parameters, it initiates 873 874 /// all of the attributes to \c 0. 874 875 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 890 891 /// This auxiliary class is created to implement the 891 892 /// \ref dfs() "function-type interface" of \ref Dfs algorithm. 892 /// It does not have own \ref run( ) method, it uses the functions893 /// and features of the plain \ref Dfs.893 /// It does not have own \ref run(Node) "run()" method, it uses the 894 /// functions and features of the plain \ref Dfs. 894 895 /// 895 896 /// This class should only be used through the \ref dfs() function, 896 897 /// which makes it easier to use the algorithm. 898 /// 899 /// \tparam TR The traits class that defines various types used by the 900 /// algorithm. 897 901 template<class TR> 898 902 class DfsWizard : public TR … … 900 904 typedef TR Base; 901 905 902 ///The type of the digraph the algorithm runs on.903 906 typedef typename TR::Digraph Digraph; 904 907 … … 908 911 typedef typename Digraph::OutArcIt OutArcIt; 909 912 910 ///\brief The type of the map that stores the predecessor911 ///arcs of the DFS paths.912 913 typedef typename TR::PredMap PredMap; 913 ///\brief The type of the map that stores the distances of the nodes.914 914 typedef typename TR::DistMap DistMap; 915 ///\brief The type of the map that indicates which nodes are reached.916 915 typedef typename TR::ReachedMap ReachedMap; 917 ///\brief The type of the map that indicates which nodes are processed.918 916 typedef typename TR::ProcessedMap ProcessedMap; 919 ///The type of the DFS paths920 917 typedef typename TR::Path Path; 921 918 … … 987 984 ///Runs DFS algorithm to visit all nodes in the digraph. 988 985 989 ///This method runs DFS algorithm in order to compute990 /// the DFS path to each node.986 ///This method runs DFS algorithm in order to visit all nodes 987 ///in the digraph. 991 988 void run() 992 989 { … … 1000 997 SetPredMapBase(const TR &b) : TR(b) {} 1001 998 }; 1002 ///\brief \ref named-func-param "Named parameter" 1003 ///for setting PredMap object. 1004 /// 1005 ///\ref named-func-param "Named parameter" 1006 ///for setting PredMap object. 999 1000 ///\brief \ref named-templ-param "Named parameter" for setting 1001 ///the predecessor map. 1002 /// 1003 ///\ref named-templ-param "Named parameter" function for setting 1004 ///the map that stores the predecessor arcs of the nodes. 1007 1005 template<class T> 1008 1006 DfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1018 1016 SetReachedMapBase(const TR &b) : TR(b) {} 1019 1017 }; 1020 ///\brief \ref named-func-param "Named parameter" 1021 ///for setting ReachedMap object. 1022 /// 1023 /// \ref named-func-param "Named parameter" 1024 ///for setting ReachedMap object. 1018 1019 ///\brief \ref named-templ-param "Named parameter" for setting 1020 ///the reached map. 1021 /// 1022 ///\ref named-templ-param "Named parameter" function for setting 1023 ///the map that indicates which nodes are reached. 1025 1024 template<class T> 1026 1025 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1036 1035 SetDistMapBase(const TR &b) : TR(b) {} 1037 1036 }; 1038 ///\brief \ref named-func-param "Named parameter" 1039 ///for setting DistMap object. 1040 /// 1041 /// \ref named-func-param "Named parameter" 1042 ///for setting DistMap object. 1037 1038 ///\brief \ref named-templ-param "Named parameter" for setting 1039 ///the distance map. 1040 /// 1041 ///\ref named-templ-param "Named parameter" function for setting 1042 ///the map that stores the distances of the nodes calculated 1043 ///by the algorithm. 1043 1044 template<class T> 1044 1045 DfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1054 1055 SetProcessedMapBase(const TR &b) : TR(b) {} 1055 1056 }; 1056 ///\brief \ref named-func-param "Named parameter" 1057 ///for setting ProcessedMap object. 1058 /// 1059 /// \ref named-func-param "Named parameter" 1060 ///for setting ProcessedMap object. 1057 1058 ///\brief \ref named-func-param "Named parameter" for setting 1059 ///the processed map. 1060 /// 1061 ///\ref named-templ-param "Named parameter" function for setting 1062 ///the map that indicates which nodes are processed. 1061 1063 template<class T> 1062 1064 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1111 1113 /// bool reached = dfs(g).path(p).dist(d).run(s,t); 1112 1114 ///\endcode 1113 1114 ///\warning Don't forget to put the \ref DfsWizard::run() "run()" 1115 ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()" 1115 1116 ///to the end of the parameter list. 1116 1117 ///\sa DfsWizard … … 1128 1129 /// This class defines the interface of the DfsVisit events, and 1129 1130 /// it could be the base of a real visitor class. 1130 template <typename _Digraph>1131 template <typename GR> 1131 1132 struct DfsVisitor { 1132 typedef _DigraphDigraph;1133 typedef GR Digraph; 1133 1134 typedef typename Digraph::Arc Arc; 1134 1135 typedef typename Digraph::Node Node; … … 1166 1167 }; 1167 1168 #else 1168 template <typename _Digraph>1169 template <typename GR> 1169 1170 struct DfsVisitor { 1170 typedef _DigraphDigraph;1171 typedef GR Digraph; 1171 1172 typedef typename Digraph::Arc Arc; 1172 1173 typedef typename Digraph::Node Node; … … 1201 1202 /// Default traits class of DfsVisit class. 1202 1203 /// \tparam _Digraph The type of the digraph the algorithm runs on. 1203 template<class _Digraph>1204 template<class GR> 1204 1205 struct DfsVisitDefaultTraits { 1205 1206 1206 1207 /// \brief The type of the digraph the algorithm runs on. 1207 typedef _DigraphDigraph;1208 typedef GR Digraph; 1208 1209 1209 1210 /// \brief The type of the map that indicates which nodes are reached. 1210 1211 /// 1211 1212 /// The type of the map that indicates which nodes are reached. 1212 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1213 /// It must conform to the 1214 /// \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1213 1215 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1214 1216 … … 1226 1228 /// \ingroup search 1227 1229 /// 1228 /// \brief %DFS algorithm class with visitor interface.1230 /// \brief DFS algorithm class with visitor interface. 1229 1231 /// 1230 /// This class provides an efficient implementation of the %DFS algorithm1232 /// This class provides an efficient implementation of the DFS algorithm 1231 1233 /// with visitor interface. 1232 1234 /// 1233 /// The %DfsVisit class provides an alternative interface to the Dfs1235 /// The DfsVisit class provides an alternative interface to the Dfs 1234 1236 /// class. It works with callback mechanism, the DfsVisit object calls 1235 1237 /// the member functions of the \c Visitor class on every DFS event. … … 1240 1242 /// instead. 1241 1243 /// 1242 /// \tparam _DigraphThe type of the digraph the algorithm runs on.1243 /// The default value is1244 /// \ref ListDigraph. The value of _Digraph is not used directly by1245 /// \ref DfsVisit,it is only passed to \ref DfsVisitDefaultTraits.1246 /// \tparam _VisitorThe Visitor type that is used by the algorithm.1247 /// \ref DfsVisitor "DfsVisitor< _Digraph>" is an empty visitor, which1244 /// \tparam GR The type of the digraph the algorithm runs on. 1245 /// The default type is \ref ListDigraph. 1246 /// The value of GR is not used directly by \ref DfsVisit, 1247 /// it is only passed to \ref DfsVisitDefaultTraits. 1248 /// \tparam VS The Visitor type that is used by the algorithm. 1249 /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which 1248 1250 /// does not observe the DFS events. If you want to observe the DFS 1249 1251 /// events, you should implement your own visitor class. 1250 /// \tparam _Traits Traits class to set various datatypes used by the1251 /// algorithm. The default traits class is1252 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".1253 /// See \ref DfsVisitDefaultTraits for the documentation of1254 /// a DFS visit traits class.1252 /// \tparam TR The traits class that defines various types used by the 1253 /// algorithm. By default, it is \ref DfsVisitDefaultTraits 1254 /// "DfsVisitDefaultTraits<GR>". 1255 /// In most cases, this parameter should not be set directly, 1256 /// consider to use the named template parameters instead. 1255 1257 #ifdef DOXYGEN 1256 template <typename _Digraph, typename _Visitor, typename _Traits>1258 template <typename GR, typename VS, typename TR> 1257 1259 #else 1258 template <typename _Digraph= ListDigraph,1259 typename _Visitor = DfsVisitor<_Digraph>,1260 typename _Traits = DfsVisitDefaultTraits<_Digraph> >1260 template <typename GR = ListDigraph, 1261 typename VS = DfsVisitor<GR>, 1262 typename TR = DfsVisitDefaultTraits<GR> > 1261 1263 #endif 1262 1264 class DfsVisit { … … 1264 1266 1265 1267 ///The traits class. 1266 typedef _TraitsTraits;1268 typedef TR Traits; 1267 1269 1268 1270 ///The type of the digraph the algorithm runs on. … … 1270 1272 1271 1273 ///The visitor type used by the algorithm. 1272 typedef _VisitorVisitor;1274 typedef VS Visitor; 1273 1275 1274 1276 ///The type of the map that indicates which nodes are reached. … … 1310 1312 typedef DfsVisit Create; 1311 1313 1312 /// \name Named template parameters1314 /// \name Named Template Parameters 1313 1315 1314 1316 ///@{ … … 1352 1354 /// 1353 1355 /// Sets the map that indicates which nodes are reached. 1354 /// If you don't use this function before calling \ref run(), 1355 /// it will allocate one. The destructor deallocates this 1356 /// automatically allocated map, of course. 1356 /// If you don't use this function before calling \ref run(Node) "run()" 1357 /// or \ref init(), an instance will be allocated automatically. 1358 /// The destructor deallocates this automatically allocated map, 1359 /// of course. 1357 1360 /// \return <tt> (*this) </tt> 1358 1361 DfsVisit &reachedMap(ReachedMap &m) { … … 1367 1370 public: 1368 1371 1369 /// \name Execution control 1370 /// The simplest way to execute the algorithm is to use 1371 /// one of the member functions called \ref lemon::DfsVisit::run() 1372 /// "run()". 1373 /// \n 1374 /// If you need more control on the execution, first you must call 1375 /// \ref lemon::DfsVisit::init() "init()", then you can add several 1376 /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()". 1377 /// Finally \ref lemon::DfsVisit::start() "start()" will perform the 1378 /// actual path computation. 1372 /// \name Execution Control 1373 /// The simplest way to execute the DFS algorithm is to use one of the 1374 /// member functions called \ref run(Node) "run()".\n 1375 /// If you need better control on the execution, you have to call 1376 /// \ref init() first, then you can add a source node with \ref addSource() 1377 /// and perform the actual computation with \ref start(). 1378 /// This procedure can be repeated if there are nodes that have not 1379 /// been reached. 1379 1380 1380 1381 /// @{ … … 1392 1393 } 1393 1394 1394 ///Adds a new source node. 1395 1396 ///Adds a new source node to the set of nodes to be processed. 1397 /// 1398 ///\pre The stack must be empty. (Otherwise the algorithm gives 1399 ///false results.) 1400 /// 1401 ///\warning Distances will be wrong (or at least strange) in case of 1402 ///multiple sources. 1395 /// \brief Adds a new source node. 1396 /// 1397 /// Adds a new source node to the set of nodes to be processed. 1398 /// 1399 /// \pre The stack must be empty. Otherwise the algorithm gives 1400 /// wrong results. (One of the outgoing arcs of all the source nodes 1401 /// except for the last one will not be visited and distances will 1402 /// also be wrong.) 1403 1403 void addSource(Node s) 1404 1404 { … … 1414 1414 } else { 1415 1415 _visitor->leave(s); 1416 _visitor->stop(s); 1416 1417 } 1417 1418 } … … 1586 1587 /// \brief Runs the algorithm to visit all nodes in the digraph. 1587 1588 1588 /// This method runs the %DFS algorithm in order to 1589 /// compute the %DFS path to each node. 1590 /// 1591 /// The algorithm computes 1592 /// - the %DFS tree, 1593 /// - the distance of each node from the root in the %DFS tree. 1589 /// This method runs the %DFS algorithm in order to visit all nodes 1590 /// in the digraph. 1594 1591 /// 1595 1592 /// \note <tt>d.run()</tt> is just a shortcut of the following code. … … 1616 1613 1617 1614 /// \name Query Functions 1618 /// The result of the %DFS algorithm can be obtained using these1615 /// The results of the DFS algorithm can be obtained using these 1619 1616 /// functions.\n 1620 /// Either \ref lemon::DfsVisit::run() "run()" or1621 /// \ref lemon::DfsVisit::start() "start()" must be called before1622 /// using them. 1617 /// Either \ref run(Node) "run()" or \ref start() should be called 1618 /// before using them. 1619 1623 1620 ///@{ 1624 1621 1625 /// \brief Checks if a node is reachable from the root(s). 1626 /// 1627 /// Returns \c true if \c v is reachable from the root(s). 1628 /// \pre Either \ref run() or \ref start() 1622 /// \brief Checks if the given node is reached from the root(s). 1623 /// 1624 /// Returns \c true if \c v is reached from the root(s). 1625 /// 1626 /// \pre Either \ref run(Node) "run()" or \ref init() 1629 1627 /// must be called before using this function. 1630 bool reached(Node v) { return (*_reached)[v]; }1628 bool reached(Node v) const { return (*_reached)[v]; } 1631 1629 1632 1630 ///@} -
test/dfs_test.cc
r877 r907 51 51 "@attributes\n" 52 52 "source 0\n" 53 "target 5\n"; 53 "target 5\n" 54 "source1 6\n" 55 "target1 3\n"; 56 54 57 55 58 void checkDfsCompile() … … 180 183 Digraph G; 181 184 Node s, t; 185 Node s1, t1; 182 186 183 187 std::istringstream input(test_lgf); … … 185 189 node("source", s). 186 190 node("target", t). 191 node("source1", s1). 192 node("target1", t1). 187 193 run(); 188 194 … … 211 217 212 218 { 219 Dfs<Digraph> dfs(G); 220 check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6."); 221 } 222 223 { 213 224 NullMap<Node,Arc> myPredMap; 214 225 dfs(G).predMap(myPredMap).run(s); -
test/dfs_test.cc
r906 r907 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 085 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 66 66 Node s, t; 67 67 Arc e; 68 int l ;68 int l, i; 69 69 bool b; 70 70 DType::DistMap d(G); 71 71 DType::PredMap p(G); 72 72 Path<Digraph> pp; 73 concepts::ReadMap<Arc,bool> am; 73 74 74 75 { 75 76 DType dfs_test(G); 77 const DType& const_dfs_test = dfs_test; 76 78 77 79 dfs_test.run(s); … … 79 81 dfs_test.run(); 80 82 81 l = dfs_test.dist(t); 82 e = dfs_test.predArc(t); 83 s = dfs_test.predNode(t); 84 b = dfs_test.reached(t); 85 d = dfs_test.distMap(); 86 p = dfs_test.predMap(); 87 pp = dfs_test.path(t); 83 dfs_test.init(); 84 dfs_test.addSource(s); 85 e = dfs_test.processNextArc(); 86 e = const_dfs_test.nextArc(); 87 b = const_dfs_test.emptyQueue(); 88 i = const_dfs_test.queueSize(); 89 90 dfs_test.start(); 91 dfs_test.start(t); 92 dfs_test.start(am); 93 94 l = const_dfs_test.dist(t); 95 e = const_dfs_test.predArc(t); 96 s = const_dfs_test.predNode(t); 97 b = const_dfs_test.reached(t); 98 d = const_dfs_test.distMap(); 99 p = const_dfs_test.predMap(); 100 pp = const_dfs_test.path(t); 88 101 } 89 102 { … … 92 105 ::SetDistMap<concepts::ReadWriteMap<Node,int> > 93 106 ::SetReachedMap<concepts::ReadWriteMap<Node,bool> > 107 ::SetStandardProcessedMap 94 108 ::SetProcessedMap<concepts::WriteMap<Node,bool> > 95 ::SetStandardProcessedMap96 109 ::Create dfs_test(G); 110 111 concepts::ReadWriteMap<Node,Arc> pred_map; 112 concepts::ReadWriteMap<Node,int> dist_map; 113 concepts::ReadWriteMap<Node,bool> reached_map; 114 concepts::WriteMap<Node,bool> processed_map; 115 116 dfs_test 117 .predMap(pred_map) 118 .distMap(dist_map) 119 .reachedMap(reached_map) 120 .processedMap(processed_map); 97 121 98 122 dfs_test.run(s); 99 123 dfs_test.run(s,t); 100 124 dfs_test.run(); 125 dfs_test.init(); 126 127 dfs_test.addSource(s); 128 e = dfs_test.processNextArc(); 129 e = dfs_test.nextArc(); 130 b = dfs_test.emptyQueue(); 131 i = dfs_test.queueSize(); 132 133 dfs_test.start(); 134 dfs_test.start(t); 135 dfs_test.start(am); 101 136 102 137 l = dfs_test.dist(t);
Note: See TracChangeset
for help on using the changeset viewer.
