Changes in lemon/bfs.h [956:141f9c0db4a3:525:9605e051942f] in lemon
- File:
-
- 1 edited
-
lemon/bfs.h (modified) (39 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r956 r525 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 105 * Copyright (C) 2003-2009 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 shortest paths. 50 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.50 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 51 51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 52 52 ///Instantiates a \c PredMap. … … 63 63 64 64 ///The type of the map that indicates which nodes are processed. 65 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 66 ///By default, it is a NullMap. 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 67 66 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 68 67 ///Instantiates a \c ProcessedMap. … … 83 82 84 83 ///The type of the map that indicates which nodes are reached. 85 ///It must conform to 86 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 84 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 87 85 typedef typename Digraph::template NodeMap<bool> ReachedMap; 88 86 ///Instantiates a \c ReachedMap. … … 99 97 100 98 ///The type of the map that stores the distances of the nodes. 101 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.99 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 102 100 typedef typename Digraph::template NodeMap<int> DistMap; 103 101 ///Instantiates a \c DistMap. … … 123 121 ///\tparam GR The type of the digraph the algorithm runs on. 124 122 ///The default type is \ref ListDigraph. 125 ///\tparam TR The traits class that defines various types used by the126 ///algorithm. By default, it is \ref BfsDefaultTraits127 ///"BfsDefaultTraits<GR>".128 ///In most cases, this parameter should not be set directly,129 ///consider to use the named template parameters instead.130 123 #ifdef DOXYGEN 131 124 template <typename GR, … … 233 226 ///\ref named-templ-param "Named parameter" for setting 234 227 ///\c PredMap type. 235 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.228 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 236 229 template <class T> 237 230 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { … … 253 246 ///\ref named-templ-param "Named parameter" for setting 254 247 ///\c DistMap type. 255 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.248 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 256 249 template <class T> 257 250 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { … … 273 266 ///\ref named-templ-param "Named parameter" for setting 274 267 ///\c ReachedMap type. 275 ///It must conform to 276 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 268 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 277 269 template <class T> 278 270 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { … … 294 286 ///\ref named-templ-param "Named parameter" for setting 295 287 ///\c ProcessedMap type. 296 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.288 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 297 289 template <class T> 298 290 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { … … 422 414 ///The simplest way to execute the BFS algorithm is to use one of the 423 415 ///member functions called \ref run(Node) "run()".\n 424 ///If you need better control on the execution,you have to call425 ///\ref init() first, then you can add several source nodes with416 ///If you need more control on the execution, first you have to call 417 ///\ref init(), then you can add several source nodes with 426 418 ///\ref addSource(). Finally the actual path computation can be 427 419 ///performed with one of the \ref start() functions. … … 709 701 ///Runs the algorithm to visit all nodes in the digraph. 710 702 711 ///This method runs the %BFS algorithm in order to visit all nodes 712 ///in the digraph. 703 ///This method runs the %BFS algorithm in order to 704 ///compute the shortest path to each node. 705 /// 706 ///The algorithm computes 707 ///- the shortest path tree (forest), 708 ///- the distance of each node from the root(s). 713 709 /// 714 710 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code. … … 742 738 ///@{ 743 739 744 ///The shortest path to the givennode.745 746 ///Returns the shortest path to the given node from the root(s).740 ///The shortest path to a node. 741 742 ///Returns the shortest path to a node. 747 743 /// 748 744 ///\warning \c t should be reached from the root(s). … … 752 748 Path path(Node t) const { return Path(*G, *_pred, t); } 753 749 754 ///The distance of the givennode from the root(s).755 756 ///Returns the distance of the givennode from the root(s).750 ///The distance of a node from the root(s). 751 752 ///Returns the distance of a node from the root(s). 757 753 /// 758 754 ///\warning If node \c v is not reached from the root(s), then … … 763 759 int dist(Node v) const { return (*_dist)[v]; } 764 760 765 ///\brief Returns the 'previous arc' of the shortest path tree for 766 ///the given node. 767 /// 761 ///Returns the 'previous arc' of the shortest path tree for a node. 762 768 763 ///This function returns the 'previous arc' of the shortest path 769 764 ///tree for the node \c v, i.e. it returns the last arc of a … … 772 767 /// 773 768 ///The shortest path tree used here is equal to the shortest path 774 ///tree used in \ref predNode() and \ref predMap().769 ///tree used in \ref predNode(). 775 770 /// 776 771 ///\pre Either \ref run(Node) "run()" or \ref init() … … 778 773 Arc predArc(Node v) const { return (*_pred)[v];} 779 774 780 ///\brief Returns the 'previous node' of the shortest path tree for 781 ///the given node. 782 /// 775 ///Returns the 'previous node' of the shortest path tree for a node. 776 783 777 ///This function returns the 'previous node' of the shortest path 784 778 ///tree for the node \c v, i.e. it returns the last but one node 785 /// ofa shortest path from a root to \c v. It is \c INVALID779 ///from a shortest path from a root to \c v. It is \c INVALID 786 780 ///if \c v is not reached from the root(s) or if \c v is a root. 787 781 /// 788 782 ///The shortest path tree used here is equal to the shortest path 789 ///tree used in \ref predArc() and \ref predMap().783 ///tree used in \ref predArc(). 790 784 /// 791 785 ///\pre Either \ref run(Node) "run()" or \ref init() … … 808 802 /// 809 803 ///Returns a const reference to the node map that stores the predecessor 810 ///arcs, which form the shortest path tree (forest).804 ///arcs, which form the shortest path tree. 811 805 /// 812 806 ///\pre Either \ref run(Node) "run()" or \ref init() … … 814 808 const PredMap &predMap() const { return *_pred;} 815 809 816 ///Checks if the givennode is reached from the root(s).810 ///Checks if a node is reached from the root(s). 817 811 818 812 ///Returns \c true if \c v is reached from the root(s). … … 840 834 ///The type of the map that stores the predecessor 841 835 ///arcs of the shortest paths. 842 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.836 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 843 837 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 844 838 ///Instantiates a PredMap. … … 855 849 856 850 ///The type of the map that indicates which nodes are processed. 857 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.858 ///By default ,it is a NullMap.851 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 852 ///By default it is a NullMap. 859 853 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 860 854 ///Instantiates a ProcessedMap. … … 875 869 876 870 ///The type of the map that indicates which nodes are reached. 877 ///It must conform to 878 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 871 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 879 872 typedef typename Digraph::template NodeMap<bool> ReachedMap; 880 873 ///Instantiates a ReachedMap. … … 891 884 892 885 ///The type of the map that stores the distances of the nodes. 893 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.886 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 894 887 typedef typename Digraph::template NodeMap<int> DistMap; 895 888 ///Instantiates a DistMap. … … 906 899 907 900 ///The type of the shortest paths. 908 ///It must conform tothe \ref concepts::Path "Path" concept.901 ///It must meet the \ref concepts::Path "Path" concept. 909 902 typedef lemon::Path<Digraph> Path; 910 903 }; … … 912 905 /// Default traits class used by BfsWizard 913 906 914 /// Default traits class used by BfsWizard. 915 /// \tparam GR The type of the digraph. 907 /// To make it easier to use Bfs algorithm 908 /// we have created a wizard class. 909 /// This \ref BfsWizard class needs default traits, 910 /// as well as the \ref Bfs class. 911 /// The \ref BfsWizardBase is a class to be the default traits of the 912 /// \ref BfsWizard class. 916 913 template<class GR> 917 914 class BfsWizardBase : public BfsWizardDefaultTraits<GR> … … 941 938 /// Constructor. 942 939 943 /// This constructor does not require parameters, it initiates940 /// This constructor does not require parameters, therefore it initiates 944 941 /// all of the attributes to \c 0. 945 942 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 966 963 /// This class should only be used through the \ref bfs() function, 967 964 /// which makes it easier to use the algorithm. 968 ///969 /// \tparam TR The traits class that defines various types used by the970 /// algorithm.971 965 template<class TR> 972 966 class BfsWizard : public TR … … 974 968 typedef TR Base; 975 969 970 ///The type of the digraph the algorithm runs on. 976 971 typedef typename TR::Digraph Digraph; 977 972 … … 981 976 typedef typename Digraph::OutArcIt OutArcIt; 982 977 978 ///\brief The type of the map that stores the predecessor 979 ///arcs of the shortest paths. 983 980 typedef typename TR::PredMap PredMap; 981 ///\brief The type of the map that stores the distances of the nodes. 984 982 typedef typename TR::DistMap DistMap; 983 ///\brief The type of the map that indicates which nodes are reached. 985 984 typedef typename TR::ReachedMap ReachedMap; 985 ///\brief The type of the map that indicates which nodes are processed. 986 986 typedef typename TR::ProcessedMap ProcessedMap; 987 ///The type of the shortest paths 987 988 typedef typename TR::Path Path; 988 989 … … 1054 1055 ///Runs BFS algorithm to visit all nodes in the digraph. 1055 1056 1056 ///This method runs BFS algorithm in order to visit all nodes1057 /// in the digraph.1057 ///This method runs BFS algorithm in order to compute 1058 ///the shortest path to each node. 1058 1059 void run() 1059 1060 { … … 1067 1068 SetPredMapBase(const TR &b) : TR(b) {} 1068 1069 }; 1069 1070 ///\brief \ref named-templ-param "Named parameter" for setting 1071 ///the predecessor map. 1072 /// 1073 ///\ref named-templ-param "Named parameter" function for setting 1074 ///the map that stores the predecessor arcs of the nodes. 1070 ///\brief \ref named-func-param "Named parameter" 1071 ///for setting PredMap object. 1072 /// 1073 ///\ref named-func-param "Named parameter" 1074 ///for setting PredMap object. 1075 1075 template<class T> 1076 1076 BfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1086 1086 SetReachedMapBase(const TR &b) : TR(b) {} 1087 1087 }; 1088 1089 ///\brief \ref named-templ-param "Named parameter" for setting 1090 ///the reached map. 1091 /// 1092 ///\ref named-templ-param "Named parameter" function for setting 1093 ///the map that indicates which nodes are reached. 1088 ///\brief \ref named-func-param "Named parameter" 1089 ///for setting ReachedMap object. 1090 /// 1091 /// \ref named-func-param "Named parameter" 1092 ///for setting ReachedMap object. 1094 1093 template<class T> 1095 1094 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1105 1104 SetDistMapBase(const TR &b) : TR(b) {} 1106 1105 }; 1107 1108 ///\brief \ref named-templ-param "Named parameter" for setting 1109 ///the distance map. 1110 /// 1111 ///\ref named-templ-param "Named parameter" function for setting 1112 ///the map that stores the distances of the nodes calculated 1113 ///by the algorithm. 1106 ///\brief \ref named-func-param "Named parameter" 1107 ///for setting DistMap object. 1108 /// 1109 /// \ref named-func-param "Named parameter" 1110 ///for setting DistMap object. 1114 1111 template<class T> 1115 1112 BfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1125 1122 SetProcessedMapBase(const TR &b) : TR(b) {} 1126 1123 }; 1127 1128 ///\brief \ref named-func-param "Named parameter" for setting 1129 ///the processed map. 1130 /// 1131 ///\ref named-templ-param "Named parameter" function for setting 1132 ///the map that indicates which nodes are processed. 1124 ///\brief \ref named-func-param "Named parameter" 1125 ///for setting ProcessedMap object. 1126 /// 1127 /// \ref named-func-param "Named parameter" 1128 ///for setting ProcessedMap object. 1133 1129 template<class T> 1134 1130 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1269 1265 /// 1270 1266 /// The type of the map that indicates which nodes are reached. 1271 /// It must conform to 1272 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1267 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1273 1268 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1274 1269 … … 1308 1303 /// does not observe the BFS events. If you want to observe the BFS 1309 1304 /// events, you should implement your own visitor class. 1310 /// \tparam TR T he traits class that defines varioustypes used by the1311 /// algorithm. By default, it is \ref BfsVisitDefaultTraits1312 /// "BfsVisitDefaultTraits<GR>".1313 /// In most cases, this parameter should not be set directly,1314 /// consider to use the named template parameters instead.1305 /// \tparam TR Traits class to set various data types used by the 1306 /// algorithm. The default traits class is 1307 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>". 1308 /// See \ref BfsVisitDefaultTraits for the documentation of 1309 /// a BFS visit traits class. 1315 1310 #ifdef DOXYGEN 1316 1311 template <typename GR, typename VS, typename TR> … … 1431 1426 /// The simplest way to execute the BFS algorithm is to use one of the 1432 1427 /// member functions called \ref run(Node) "run()".\n 1433 /// If you need better control on the execution,you have to call1434 /// \ref init() first, then you can add several source nodes with1428 /// If you need more control on the execution, first you have to call 1429 /// \ref init(), then you can add several source nodes with 1435 1430 /// \ref addSource(). Finally the actual path computation can be 1436 1431 /// performed with one of the \ref start() functions. … … 1704 1699 /// \brief Runs the algorithm to visit all nodes in the digraph. 1705 1700 /// 1706 /// This method runs the %BFS algorithm in order to visit all nodes 1707 /// in the digraph. 1701 /// This method runs the %BFS algorithm in order to 1702 /// compute the shortest path to each node. 1703 /// 1704 /// The algorithm computes 1705 /// - the shortest path tree (forest), 1706 /// - the distance of each node from the root(s). 1708 1707 /// 1709 1708 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code. … … 1737 1736 ///@{ 1738 1737 1739 /// \brief Checks if the givennode is reached from the root(s).1738 /// \brief Checks if a node is reached from the root(s). 1740 1739 /// 1741 1740 /// Returns \c true if \c v is reached from the root(s).
Note: See TracChangeset
for help on using the changeset viewer.
