Changes in lemon/bfs.h [525:9605e051942f:891:75e6020b19b1] in lemon
- File:
-
- 1 edited
-
lemon/bfs.h (modified) (38 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r525 r891 48 48 ///The type of the map that stores the predecessor 49 49 ///arcs of the shortest 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 52 ///Instantiates a \c PredMap. … … 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 68 ///Instantiates a \c ProcessedMap. … … 82 83 83 84 ///The type of the map that indicates which nodes are reached. 84 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.85 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 86 typedef typename Digraph::template NodeMap<bool> ReachedMap; 86 87 ///Instantiates a \c ReachedMap. … … 97 98 98 99 ///The type of the map that stores the distances of the nodes. 99 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.100 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 100 101 typedef typename Digraph::template NodeMap<int> DistMap; 101 102 ///Instantiates a \c DistMap. … … 121 122 ///\tparam GR The type of the digraph the algorithm runs on. 122 123 ///The default type is \ref ListDigraph. 124 ///\tparam TR The traits class that defines various types used by the 125 ///algorithm. By default, it is \ref BfsDefaultTraits 126 ///"BfsDefaultTraits<GR>". 127 ///In most cases, this parameter should not be set directly, 128 ///consider to use the named template parameters instead. 123 129 #ifdef DOXYGEN 124 130 template <typename GR, … … 226 232 ///\ref named-templ-param "Named parameter" for setting 227 233 ///\c PredMap type. 228 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.234 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 229 235 template <class T> 230 236 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { … … 246 252 ///\ref named-templ-param "Named parameter" for setting 247 253 ///\c DistMap type. 248 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.254 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 249 255 template <class T> 250 256 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { … … 266 272 ///\ref named-templ-param "Named parameter" for setting 267 273 ///\c ReachedMap type. 268 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.274 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 269 275 template <class T> 270 276 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { … … 286 292 ///\ref named-templ-param "Named parameter" for setting 287 293 ///\c ProcessedMap type. 288 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.294 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 289 295 template <class T> 290 296 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { … … 414 420 ///The simplest way to execute the BFS algorithm is to use one of the 415 421 ///member functions called \ref run(Node) "run()".\n 416 ///If you need more control on the execution, firstyou have to call417 ///\ref init() , then you can add several source nodes with422 ///If you need better control on the execution, you have to call 423 ///\ref init() first, then you can add several source nodes with 418 424 ///\ref addSource(). Finally the actual path computation can be 419 425 ///performed with one of the \ref start() functions. … … 701 707 ///Runs the algorithm to visit all nodes in the digraph. 702 708 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). 709 ///This method runs the %BFS algorithm in order to visit all nodes 710 ///in the digraph. 709 711 /// 710 712 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code. … … 738 740 ///@{ 739 741 740 ///The shortest path to anode.741 742 ///Returns the shortest path to a node.742 ///The shortest path to the given node. 743 744 ///Returns the shortest path to the given node from the root(s). 743 745 /// 744 746 ///\warning \c t should be reached from the root(s). … … 748 750 Path path(Node t) const { return Path(*G, *_pred, t); } 749 751 750 ///The distance of anode from the root(s).751 752 ///Returns the distance of anode from the root(s).752 ///The distance of the given node from the root(s). 753 754 ///Returns the distance of the given node from the root(s). 753 755 /// 754 756 ///\warning If node \c v is not reached from the root(s), then … … 759 761 int dist(Node v) const { return (*_dist)[v]; } 760 762 761 ///Returns the 'previous arc' of the shortest path tree for a node. 762 763 ///\brief Returns the 'previous arc' of the shortest path tree for 764 ///the given node. 765 /// 763 766 ///This function returns the 'previous arc' of the shortest path 764 767 ///tree for the node \c v, i.e. it returns the last arc of a … … 767 770 /// 768 771 ///The shortest path tree used here is equal to the shortest path 769 ///tree used in \ref predNode() .772 ///tree used in \ref predNode() and \ref predMap(). 770 773 /// 771 774 ///\pre Either \ref run(Node) "run()" or \ref init() … … 773 776 Arc predArc(Node v) const { return (*_pred)[v];} 774 777 775 ///Returns the 'previous node' of the shortest path tree for a node. 776 778 ///\brief Returns the 'previous node' of the shortest path tree for 779 ///the given node. 780 /// 777 781 ///This function returns the 'previous node' of the shortest path 778 782 ///tree for the node \c v, i.e. it returns the last but one node 779 /// froma shortest path from a root to \c v. It is \c INVALID783 ///of a shortest path from a root to \c v. It is \c INVALID 780 784 ///if \c v is not reached from the root(s) or if \c v is a root. 781 785 /// 782 786 ///The shortest path tree used here is equal to the shortest path 783 ///tree used in \ref predArc() .787 ///tree used in \ref predArc() and \ref predMap(). 784 788 /// 785 789 ///\pre Either \ref run(Node) "run()" or \ref init() … … 802 806 /// 803 807 ///Returns a const reference to the node map that stores the predecessor 804 ///arcs, which form the shortest path tree .808 ///arcs, which form the shortest path tree (forest). 805 809 /// 806 810 ///\pre Either \ref run(Node) "run()" or \ref init() … … 808 812 const PredMap &predMap() const { return *_pred;} 809 813 810 ///Checks if anode is reached from the root(s).814 ///Checks if the given node is reached from the root(s). 811 815 812 816 ///Returns \c true if \c v is reached from the root(s). … … 834 838 ///The type of the map that stores the predecessor 835 839 ///arcs of the shortest paths. 836 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.840 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 837 841 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 838 842 ///Instantiates a PredMap. … … 849 853 850 854 ///The type of the map that indicates which nodes are processed. 851 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.852 ///By default it is a NullMap.855 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 856 ///By default, it is a NullMap. 853 857 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 854 858 ///Instantiates a ProcessedMap. … … 869 873 870 874 ///The type of the map that indicates which nodes are reached. 871 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.875 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 872 876 typedef typename Digraph::template NodeMap<bool> ReachedMap; 873 877 ///Instantiates a ReachedMap. … … 884 888 885 889 ///The type of the map that stores the distances of the nodes. 886 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.890 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 887 891 typedef typename Digraph::template NodeMap<int> DistMap; 888 892 ///Instantiates a DistMap. … … 899 903 900 904 ///The type of the shortest paths. 901 ///It must meetthe \ref concepts::Path "Path" concept.905 ///It must conform to the \ref concepts::Path "Path" concept. 902 906 typedef lemon::Path<Digraph> Path; 903 907 }; … … 905 909 /// Default traits class used by BfsWizard 906 910 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. 911 /// Default traits class used by BfsWizard. 912 /// \tparam GR The type of the digraph. 913 913 template<class GR> 914 914 class BfsWizardBase : public BfsWizardDefaultTraits<GR> … … 938 938 /// Constructor. 939 939 940 /// This constructor does not require parameters, thereforeit initiates940 /// This constructor does not require parameters, it initiates 941 941 /// all of the attributes to \c 0. 942 942 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 963 963 /// This class should only be used through the \ref bfs() function, 964 964 /// which makes it easier to use the algorithm. 965 /// 966 /// \tparam TR The traits class that defines various types used by the 967 /// algorithm. 965 968 template<class TR> 966 969 class BfsWizard : public TR … … 968 971 typedef TR Base; 969 972 970 ///The type of the digraph the algorithm runs on.971 973 typedef typename TR::Digraph Digraph; 972 974 … … 976 978 typedef typename Digraph::OutArcIt OutArcIt; 977 979 978 ///\brief The type of the map that stores the predecessor979 ///arcs of the shortest paths.980 980 typedef typename TR::PredMap PredMap; 981 ///\brief The type of the map that stores the distances of the nodes.982 981 typedef typename TR::DistMap DistMap; 983 ///\brief The type of the map that indicates which nodes are reached.984 982 typedef typename TR::ReachedMap ReachedMap; 985 ///\brief The type of the map that indicates which nodes are processed.986 983 typedef typename TR::ProcessedMap ProcessedMap; 987 ///The type of the shortest paths988 984 typedef typename TR::Path Path; 989 985 … … 1055 1051 ///Runs BFS algorithm to visit all nodes in the digraph. 1056 1052 1057 ///This method runs BFS algorithm in order to compute1058 /// the shortest path to each node.1053 ///This method runs BFS algorithm in order to visit all nodes 1054 ///in the digraph. 1059 1055 void run() 1060 1056 { … … 1068 1064 SetPredMapBase(const TR &b) : TR(b) {} 1069 1065 }; 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. 1066 1067 ///\brief \ref named-templ-param "Named parameter" for setting 1068 ///the predecessor map. 1069 /// 1070 ///\ref named-templ-param "Named parameter" function for setting 1071 ///the map that stores the predecessor arcs of the nodes. 1075 1072 template<class T> 1076 1073 BfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1086 1083 SetReachedMapBase(const TR &b) : TR(b) {} 1087 1084 }; 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. 1085 1086 ///\brief \ref named-templ-param "Named parameter" for setting 1087 ///the reached map. 1088 /// 1089 ///\ref named-templ-param "Named parameter" function for setting 1090 ///the map that indicates which nodes are reached. 1093 1091 template<class T> 1094 1092 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1104 1102 SetDistMapBase(const TR &b) : TR(b) {} 1105 1103 }; 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. 1104 1105 ///\brief \ref named-templ-param "Named parameter" for setting 1106 ///the distance map. 1107 /// 1108 ///\ref named-templ-param "Named parameter" function for setting 1109 ///the map that stores the distances of the nodes calculated 1110 ///by the algorithm. 1111 1111 template<class T> 1112 1112 BfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1122 1122 SetProcessedMapBase(const TR &b) : TR(b) {} 1123 1123 }; 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. 1124 1125 ///\brief \ref named-func-param "Named parameter" for setting 1126 ///the processed map. 1127 /// 1128 ///\ref named-templ-param "Named parameter" function for setting 1129 ///the map that indicates which nodes are processed. 1129 1130 template<class T> 1130 1131 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1265 1266 /// 1266 1267 /// The type of the map that indicates which nodes are reached. 1267 /// It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.1268 /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1268 1269 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1269 1270 … … 1303 1304 /// does not observe the BFS events. If you want to observe the BFS 1304 1305 /// events, you should implement your own visitor class. 1305 /// \tparam TR T raits class to set various datatypes used by the1306 /// algorithm. The default traits class is1307 /// \ref BfsVisitDefaultTraits"BfsVisitDefaultTraits<GR>".1308 /// See \ref BfsVisitDefaultTraits for the documentation of1309 /// a BFS visit traits class.1306 /// \tparam TR The traits class that defines various types used by the 1307 /// algorithm. By default, it is \ref BfsVisitDefaultTraits 1308 /// "BfsVisitDefaultTraits<GR>". 1309 /// In most cases, this parameter should not be set directly, 1310 /// consider to use the named template parameters instead. 1310 1311 #ifdef DOXYGEN 1311 1312 template <typename GR, typename VS, typename TR> … … 1426 1427 /// The simplest way to execute the BFS algorithm is to use one of the 1427 1428 /// member functions called \ref run(Node) "run()".\n 1428 /// If you need more control on the execution, firstyou have to call1429 /// \ref init() , then you can add several source nodes with1429 /// If you need better control on the execution, you have to call 1430 /// \ref init() first, then you can add several source nodes with 1430 1431 /// \ref addSource(). Finally the actual path computation can be 1431 1432 /// performed with one of the \ref start() functions. … … 1699 1700 /// \brief Runs the algorithm to visit all nodes in the digraph. 1700 1701 /// 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). 1702 /// This method runs the %BFS algorithm in order to visit all nodes 1703 /// in the digraph. 1707 1704 /// 1708 1705 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code. … … 1736 1733 ///@{ 1737 1734 1738 /// \brief Checks if anode is reached from the root(s).1735 /// \brief Checks if the given node is reached from the root(s). 1739 1736 /// 1740 1737 /// Returns \c true if \c v is reached from the root(s).
Note: See TracChangeset
for help on using the changeset viewer.
