Changes in lemon/bfs.h [764:684964884a2e:525:9605e051942f] in lemon
- File:
-
- 1 edited
-
lemon/bfs.h (modified) (32 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r764 r525 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 tothe \ref concepts::ReadWriteMap "ReadWriteMap" concept.84 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 86 85 typedef typename Digraph::template NodeMap<bool> ReachedMap; 87 86 ///Instantiates a \c ReachedMap. … … 98 97 99 98 ///The type of the map that stores the distances of the nodes. 100 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.99 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 101 100 typedef typename Digraph::template NodeMap<int> DistMap; 102 101 ///Instantiates a \c DistMap. … … 227 226 ///\ref named-templ-param "Named parameter" for setting 228 227 ///\c PredMap type. 229 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.228 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 230 229 template <class T> 231 230 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { … … 247 246 ///\ref named-templ-param "Named parameter" for setting 248 247 ///\c DistMap type. 249 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.248 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 250 249 template <class T> 251 250 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { … … 267 266 ///\ref named-templ-param "Named parameter" for setting 268 267 ///\c ReachedMap type. 269 ///It must conform tothe \ref concepts::ReadWriteMap "ReadWriteMap" concept.268 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 270 269 template <class T> 271 270 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { … … 287 286 ///\ref named-templ-param "Named parameter" for setting 288 287 ///\c ProcessedMap type. 289 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.288 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 290 289 template <class T> 291 290 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { … … 415 414 ///The simplest way to execute the BFS algorithm is to use one of the 416 415 ///member functions called \ref run(Node) "run()".\n 417 ///If you need better control on the execution,you have to call418 ///\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 419 418 ///\ref addSource(). Finally the actual path computation can be 420 419 ///performed with one of the \ref start() functions. … … 739 738 ///@{ 740 739 741 ///The shortest path to the givennode.742 743 ///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. 744 743 /// 745 744 ///\warning \c t should be reached from the root(s). … … 749 748 Path path(Node t) const { return Path(*G, *_pred, t); } 750 749 751 ///The distance of the givennode from the root(s).752 753 ///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). 754 753 /// 755 754 ///\warning If node \c v is not reached from the root(s), then … … 760 759 int dist(Node v) const { return (*_dist)[v]; } 761 760 762 ///\brief Returns the 'previous arc' of the shortest path tree for 763 ///the given node. 764 /// 761 ///Returns the 'previous arc' of the shortest path tree for a node. 762 765 763 ///This function returns the 'previous arc' of the shortest path 766 764 ///tree for the node \c v, i.e. it returns the last arc of a … … 769 767 /// 770 768 ///The shortest path tree used here is equal to the shortest path 771 ///tree used in \ref predNode() and \ref predMap().769 ///tree used in \ref predNode(). 772 770 /// 773 771 ///\pre Either \ref run(Node) "run()" or \ref init() … … 775 773 Arc predArc(Node v) const { return (*_pred)[v];} 776 774 777 ///\brief Returns the 'previous node' of the shortest path tree for 778 ///the given node. 779 /// 775 ///Returns the 'previous node' of the shortest path tree for a node. 776 780 777 ///This function returns the 'previous node' of the shortest path 781 778 ///tree for the node \c v, i.e. it returns the last but one node 782 /// 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 783 780 ///if \c v is not reached from the root(s) or if \c v is a root. 784 781 /// 785 782 ///The shortest path tree used here is equal to the shortest path 786 ///tree used in \ref predArc() and \ref predMap().783 ///tree used in \ref predArc(). 787 784 /// 788 785 ///\pre Either \ref run(Node) "run()" or \ref init() … … 805 802 /// 806 803 ///Returns a const reference to the node map that stores the predecessor 807 ///arcs, which form the shortest path tree (forest).804 ///arcs, which form the shortest path tree. 808 805 /// 809 806 ///\pre Either \ref run(Node) "run()" or \ref init() … … 811 808 const PredMap &predMap() const { return *_pred;} 812 809 813 ///Checks if the givennode is reached from the root(s).810 ///Checks if a node is reached from the root(s). 814 811 815 812 ///Returns \c true if \c v is reached from the root(s). … … 837 834 ///The type of the map that stores the predecessor 838 835 ///arcs of the shortest paths. 839 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.836 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 840 837 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 841 838 ///Instantiates a PredMap. … … 852 849 853 850 ///The type of the map that indicates which nodes are processed. 854 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.851 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 855 852 ///By default it is a NullMap. 856 853 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; … … 872 869 873 870 ///The type of the map that indicates which nodes are reached. 874 ///It must conform tothe \ref concepts::ReadWriteMap "ReadWriteMap" concept.871 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 875 872 typedef typename Digraph::template NodeMap<bool> ReachedMap; 876 873 ///Instantiates a ReachedMap. … … 887 884 888 885 ///The type of the map that stores the distances of the nodes. 889 ///It must conform tothe \ref concepts::WriteMap "WriteMap" concept.886 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 890 887 typedef typename Digraph::template NodeMap<int> DistMap; 891 888 ///Instantiates a DistMap. … … 902 899 903 900 ///The type of the shortest paths. 904 ///It must conform tothe \ref concepts::Path "Path" concept.901 ///It must meet the \ref concepts::Path "Path" concept. 905 902 typedef lemon::Path<Digraph> Path; 906 903 }; … … 908 905 /// Default traits class used by BfsWizard 909 906 910 /// Default traits class used by BfsWizard. 911 /// \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. 912 913 template<class GR> 913 914 class BfsWizardBase : public BfsWizardDefaultTraits<GR> … … 937 938 /// Constructor. 938 939 939 /// This constructor does not require parameters, it initiates940 /// This constructor does not require parameters, therefore it initiates 940 941 /// all of the attributes to \c 0. 941 942 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 967 968 typedef TR Base; 968 969 970 ///The type of the digraph the algorithm runs on. 969 971 typedef typename TR::Digraph Digraph; 970 972 … … 974 976 typedef typename Digraph::OutArcIt OutArcIt; 975 977 978 ///\brief The type of the map that stores the predecessor 979 ///arcs of the shortest paths. 976 980 typedef typename TR::PredMap PredMap; 981 ///\brief The type of the map that stores the distances of the nodes. 977 982 typedef typename TR::DistMap DistMap; 983 ///\brief The type of the map that indicates which nodes are reached. 978 984 typedef typename TR::ReachedMap ReachedMap; 985 ///\brief The type of the map that indicates which nodes are processed. 979 986 typedef typename TR::ProcessedMap ProcessedMap; 987 ///The type of the shortest paths 980 988 typedef typename TR::Path Path; 981 989 … … 1060 1068 SetPredMapBase(const TR &b) : TR(b) {} 1061 1069 }; 1062 1063 ///\brief \ref named-templ-param "Named parameter" for setting 1064 ///the predecessor map. 1065 /// 1066 ///\ref named-templ-param "Named parameter" function for setting 1067 ///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. 1068 1075 template<class T> 1069 1076 BfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1079 1086 SetReachedMapBase(const TR &b) : TR(b) {} 1080 1087 }; 1081 1082 ///\brief \ref named-templ-param "Named parameter" for setting 1083 ///the reached map. 1084 /// 1085 ///\ref named-templ-param "Named parameter" function for setting 1086 ///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. 1087 1093 template<class T> 1088 1094 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1098 1104 SetDistMapBase(const TR &b) : TR(b) {} 1099 1105 }; 1100 1101 ///\brief \ref named-templ-param "Named parameter" for setting 1102 ///the distance map. 1103 /// 1104 ///\ref named-templ-param "Named parameter" function for setting 1105 ///the map that stores the distances of the nodes calculated 1106 ///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. 1107 1111 template<class T> 1108 1112 BfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1118 1122 SetProcessedMapBase(const TR &b) : TR(b) {} 1119 1123 }; 1120 1121 ///\brief \ref named-func-param "Named parameter" for setting 1122 ///the processed map. 1123 /// 1124 ///\ref named-templ-param "Named parameter" function for setting 1125 ///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. 1126 1129 template<class T> 1127 1130 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1262 1265 /// 1263 1266 /// The type of the map that indicates which nodes are reached. 1264 /// It must conform tothe \ref concepts::ReadWriteMap "ReadWriteMap" concept.1267 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1265 1268 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1266 1269 … … 1423 1426 /// The simplest way to execute the BFS algorithm is to use one of the 1424 1427 /// member functions called \ref run(Node) "run()".\n 1425 /// If you need better control on the execution,you have to call1426 /// \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 1427 1430 /// \ref addSource(). Finally the actual path computation can be 1428 1431 /// performed with one of the \ref start() functions. … … 1733 1736 ///@{ 1734 1737 1735 /// \brief Checks if the givennode is reached from the root(s).1738 /// \brief Checks if a node is reached from the root(s). 1736 1739 /// 1737 1740 /// Returns \c true if \c v is reached from the root(s).
Note: See TracChangeset
for help on using the changeset viewer.
