Changeset 763:f47b6c94577e in lemon for lemon/bfs.h
- Timestamp:
- 08/02/09 12:40:20 (15 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
-
lemon/bfs.h (modified) (30 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r525 r763 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. … … 226 227 ///\ref named-templ-param "Named parameter" for setting 227 228 ///\c PredMap type. 228 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.229 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 229 230 template <class T> 230 231 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { … … 246 247 ///\ref named-templ-param "Named parameter" for setting 247 248 ///\c DistMap type. 248 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.249 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 249 250 template <class T> 250 251 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { … … 266 267 ///\ref named-templ-param "Named parameter" for setting 267 268 ///\c ReachedMap type. 268 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.269 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 269 270 template <class T> 270 271 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { … … 286 287 ///\ref named-templ-param "Named parameter" for setting 287 288 ///\c ProcessedMap type. 288 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.289 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 289 290 template <class T> 290 291 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { … … 738 739 ///@{ 739 740 740 ///The shortest path to anode.741 742 ///Returns the shortest path to a node.741 ///The shortest path to the given node. 742 743 ///Returns the shortest path to the given node from the root(s). 743 744 /// 744 745 ///\warning \c t should be reached from the root(s). … … 748 749 Path path(Node t) const { return Path(*G, *_pred, t); } 749 750 750 ///The distance of anode from the root(s).751 752 ///Returns the distance of anode from the root(s).751 ///The distance of the given node from the root(s). 752 753 ///Returns the distance of the given node from the root(s). 753 754 /// 754 755 ///\warning If node \c v is not reached from the root(s), then … … 759 760 int dist(Node v) const { return (*_dist)[v]; } 760 761 761 ///Returns the 'previous arc' of the shortest path tree for a node. 762 762 ///\brief Returns the 'previous arc' of the shortest path tree for 763 ///the given node. 764 /// 763 765 ///This function returns the 'previous arc' of the shortest path 764 766 ///tree for the node \c v, i.e. it returns the last arc of a … … 767 769 /// 768 770 ///The shortest path tree used here is equal to the shortest path 769 ///tree used in \ref predNode() .771 ///tree used in \ref predNode() and \ref predMap(). 770 772 /// 771 773 ///\pre Either \ref run(Node) "run()" or \ref init() … … 773 775 Arc predArc(Node v) const { return (*_pred)[v];} 774 776 775 ///Returns the 'previous node' of the shortest path tree for a node. 776 777 ///\brief Returns the 'previous node' of the shortest path tree for 778 ///the given node. 779 /// 777 780 ///This function returns the 'previous node' of the shortest path 778 781 ///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 INVALID782 ///of a shortest path from a root to \c v. It is \c INVALID 780 783 ///if \c v is not reached from the root(s) or if \c v is a root. 781 784 /// 782 785 ///The shortest path tree used here is equal to the shortest path 783 ///tree used in \ref predArc() .786 ///tree used in \ref predArc() and \ref predMap(). 784 787 /// 785 788 ///\pre Either \ref run(Node) "run()" or \ref init() … … 802 805 /// 803 806 ///Returns a const reference to the node map that stores the predecessor 804 ///arcs, which form the shortest path tree .807 ///arcs, which form the shortest path tree (forest). 805 808 /// 806 809 ///\pre Either \ref run(Node) "run()" or \ref init() … … 808 811 const PredMap &predMap() const { return *_pred;} 809 812 810 ///Checks if anode is reached from the root(s).813 ///Checks if the given node is reached from the root(s). 811 814 812 815 ///Returns \c true if \c v is reached from the root(s). … … 834 837 ///The type of the map that stores the predecessor 835 838 ///arcs of the shortest paths. 836 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.839 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 837 840 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 838 841 ///Instantiates a PredMap. … … 849 852 850 853 ///The type of the map that indicates which nodes are processed. 851 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.854 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 852 855 ///By default it is a NullMap. 853 856 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; … … 869 872 870 873 ///The type of the map that indicates which nodes are reached. 871 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.874 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 872 875 typedef typename Digraph::template NodeMap<bool> ReachedMap; 873 876 ///Instantiates a ReachedMap. … … 884 887 885 888 ///The type of the map that stores the distances of the nodes. 886 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.889 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 887 890 typedef typename Digraph::template NodeMap<int> DistMap; 888 891 ///Instantiates a DistMap. … … 899 902 900 903 ///The type of the shortest paths. 901 ///It must meetthe \ref concepts::Path "Path" concept.904 ///It must conform to the \ref concepts::Path "Path" concept. 902 905 typedef lemon::Path<Digraph> Path; 903 906 }; … … 905 908 /// Default traits class used by BfsWizard 906 909 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. 910 /// Default traits class used by BfsWizard. 911 /// \tparam GR The type of the digraph. 913 912 template<class GR> 914 913 class BfsWizardBase : public BfsWizardDefaultTraits<GR> … … 938 937 /// Constructor. 939 938 940 /// This constructor does not require parameters, thereforeit initiates939 /// This constructor does not require parameters, it initiates 941 940 /// all of the attributes to \c 0. 942 941 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 968 967 typedef TR Base; 969 968 970 ///The type of the digraph the algorithm runs on.971 969 typedef typename TR::Digraph Digraph; 972 970 … … 976 974 typedef typename Digraph::OutArcIt OutArcIt; 977 975 978 ///\brief The type of the map that stores the predecessor979 ///arcs of the shortest paths.980 976 typedef typename TR::PredMap PredMap; 981 ///\brief The type of the map that stores the distances of the nodes.982 977 typedef typename TR::DistMap DistMap; 983 ///\brief The type of the map that indicates which nodes are reached.984 978 typedef typename TR::ReachedMap ReachedMap; 985 ///\brief The type of the map that indicates which nodes are processed.986 979 typedef typename TR::ProcessedMap ProcessedMap; 987 ///The type of the shortest paths988 980 typedef typename TR::Path Path; 989 981 … … 1068 1060 SetPredMapBase(const TR &b) : TR(b) {} 1069 1061 }; 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. 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. 1075 1068 template<class T> 1076 1069 BfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1086 1079 SetReachedMapBase(const TR &b) : TR(b) {} 1087 1080 }; 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. 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. 1093 1087 template<class T> 1094 1088 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1104 1098 SetDistMapBase(const TR &b) : TR(b) {} 1105 1099 }; 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. 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. 1111 1107 template<class T> 1112 1108 BfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1122 1118 SetProcessedMapBase(const TR &b) : TR(b) {} 1123 1119 }; 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. 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. 1129 1126 template<class T> 1130 1127 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1265 1262 /// 1266 1263 /// The type of the map that indicates which nodes are reached. 1267 /// It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.1264 /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1268 1265 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1269 1266 … … 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.
