Changes in lemon/bfs.h [492:9605e051942f:788:c92296660262] in lemon-1.2
- File:
-
- 1 edited
-
lemon/bfs.h (modified) (35 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r492 r788 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> > { … … 414 415 ///The simplest way to execute the BFS algorithm is to use one of the 415 416 ///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 with417 ///If you need better control on the execution, you have to call 418 ///\ref init() first, then you can add several source nodes with 418 419 ///\ref addSource(). Finally the actual path computation can be 419 420 ///performed with one of the \ref start() functions. … … 701 702 ///Runs the algorithm to visit all nodes in the digraph. 702 703 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). 704 ///This method runs the %BFS algorithm in order to visit all nodes 705 ///in the digraph. 709 706 /// 710 707 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code. … … 738 735 ///@{ 739 736 740 ///The shortest path to anode.741 742 ///Returns the shortest path to a node.737 ///The shortest path to the given node. 738 739 ///Returns the shortest path to the given node from the root(s). 743 740 /// 744 741 ///\warning \c t should be reached from the root(s). … … 748 745 Path path(Node t) const { return Path(*G, *_pred, t); } 749 746 750 ///The distance of anode from the root(s).751 752 ///Returns the distance of anode from the root(s).747 ///The distance of the given node from the root(s). 748 749 ///Returns the distance of the given node from the root(s). 753 750 /// 754 751 ///\warning If node \c v is not reached from the root(s), then … … 759 756 int dist(Node v) const { return (*_dist)[v]; } 760 757 761 ///Returns the 'previous arc' of the shortest path tree for a node. 762 758 ///\brief Returns the 'previous arc' of the shortest path tree for 759 ///the given node. 760 /// 763 761 ///This function returns the 'previous arc' of the shortest path 764 762 ///tree for the node \c v, i.e. it returns the last arc of a … … 767 765 /// 768 766 ///The shortest path tree used here is equal to the shortest path 769 ///tree used in \ref predNode() .767 ///tree used in \ref predNode() and \ref predMap(). 770 768 /// 771 769 ///\pre Either \ref run(Node) "run()" or \ref init() … … 773 771 Arc predArc(Node v) const { return (*_pred)[v];} 774 772 775 ///Returns the 'previous node' of the shortest path tree for a node. 776 773 ///\brief Returns the 'previous node' of the shortest path tree for 774 ///the given node. 775 /// 777 776 ///This function returns the 'previous node' of the shortest path 778 777 ///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 INVALID778 ///of a shortest path from a root to \c v. It is \c INVALID 780 779 ///if \c v is not reached from the root(s) or if \c v is a root. 781 780 /// 782 781 ///The shortest path tree used here is equal to the shortest path 783 ///tree used in \ref predArc() .782 ///tree used in \ref predArc() and \ref predMap(). 784 783 /// 785 784 ///\pre Either \ref run(Node) "run()" or \ref init() … … 802 801 /// 803 802 ///Returns a const reference to the node map that stores the predecessor 804 ///arcs, which form the shortest path tree .803 ///arcs, which form the shortest path tree (forest). 805 804 /// 806 805 ///\pre Either \ref run(Node) "run()" or \ref init() … … 808 807 const PredMap &predMap() const { return *_pred;} 809 808 810 ///Checks if anode is reached from the root(s).809 ///Checks if the given node is reached from the root(s). 811 810 812 811 ///Returns \c true if \c v is reached from the root(s). … … 834 833 ///The type of the map that stores the predecessor 835 834 ///arcs of the shortest paths. 836 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.835 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 837 836 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 838 837 ///Instantiates a PredMap. … … 849 848 850 849 ///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.850 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 851 ///By default, it is a NullMap. 853 852 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 854 853 ///Instantiates a ProcessedMap. … … 869 868 870 869 ///The type of the map that indicates which nodes are reached. 871 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.870 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 872 871 typedef typename Digraph::template NodeMap<bool> ReachedMap; 873 872 ///Instantiates a ReachedMap. … … 884 883 885 884 ///The type of the map that stores the distances of the nodes. 886 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.885 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 887 886 typedef typename Digraph::template NodeMap<int> DistMap; 888 887 ///Instantiates a DistMap. … … 899 898 900 899 ///The type of the shortest paths. 901 ///It must meetthe \ref concepts::Path "Path" concept.900 ///It must conform to the \ref concepts::Path "Path" concept. 902 901 typedef lemon::Path<Digraph> Path; 903 902 }; … … 905 904 /// Default traits class used by BfsWizard 906 905 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. 906 /// Default traits class used by BfsWizard. 907 /// \tparam GR The type of the digraph. 913 908 template<class GR> 914 909 class BfsWizardBase : public BfsWizardDefaultTraits<GR> … … 938 933 /// Constructor. 939 934 940 /// This constructor does not require parameters, thereforeit initiates935 /// This constructor does not require parameters, it initiates 941 936 /// all of the attributes to \c 0. 942 937 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 968 963 typedef TR Base; 969 964 970 ///The type of the digraph the algorithm runs on.971 965 typedef typename TR::Digraph Digraph; 972 966 … … 976 970 typedef typename Digraph::OutArcIt OutArcIt; 977 971 978 ///\brief The type of the map that stores the predecessor979 ///arcs of the shortest paths.980 972 typedef typename TR::PredMap PredMap; 981 ///\brief The type of the map that stores the distances of the nodes.982 973 typedef typename TR::DistMap DistMap; 983 ///\brief The type of the map that indicates which nodes are reached.984 974 typedef typename TR::ReachedMap ReachedMap; 985 ///\brief The type of the map that indicates which nodes are processed.986 975 typedef typename TR::ProcessedMap ProcessedMap; 987 ///The type of the shortest paths988 976 typedef typename TR::Path Path; 989 977 … … 1055 1043 ///Runs BFS algorithm to visit all nodes in the digraph. 1056 1044 1057 ///This method runs BFS algorithm in order to compute1058 /// the shortest path to each node.1045 ///This method runs BFS algorithm in order to visit all nodes 1046 ///in the digraph. 1059 1047 void run() 1060 1048 { … … 1068 1056 SetPredMapBase(const TR &b) : TR(b) {} 1069 1057 }; 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. 1058 1059 ///\brief \ref named-templ-param "Named parameter" for setting 1060 ///the predecessor map. 1061 /// 1062 ///\ref named-templ-param "Named parameter" function for setting 1063 ///the map that stores the predecessor arcs of the nodes. 1075 1064 template<class T> 1076 1065 BfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1086 1075 SetReachedMapBase(const TR &b) : TR(b) {} 1087 1076 }; 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. 1077 1078 ///\brief \ref named-templ-param "Named parameter" for setting 1079 ///the reached map. 1080 /// 1081 ///\ref named-templ-param "Named parameter" function for setting 1082 ///the map that indicates which nodes are reached. 1093 1083 template<class T> 1094 1084 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1104 1094 SetDistMapBase(const TR &b) : TR(b) {} 1105 1095 }; 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. 1096 1097 ///\brief \ref named-templ-param "Named parameter" for setting 1098 ///the distance map. 1099 /// 1100 ///\ref named-templ-param "Named parameter" function for setting 1101 ///the map that stores the distances of the nodes calculated 1102 ///by the algorithm. 1111 1103 template<class T> 1112 1104 BfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1122 1114 SetProcessedMapBase(const TR &b) : TR(b) {} 1123 1115 }; 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. 1116 1117 ///\brief \ref named-func-param "Named parameter" for setting 1118 ///the processed map. 1119 /// 1120 ///\ref named-templ-param "Named parameter" function for setting 1121 ///the map that indicates which nodes are processed. 1129 1122 template<class T> 1130 1123 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1265 1258 /// 1266 1259 /// The type of the map that indicates which nodes are reached. 1267 /// It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.1260 /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1268 1261 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1269 1262 … … 1426 1419 /// The simplest way to execute the BFS algorithm is to use one of the 1427 1420 /// 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 with1421 /// If you need better control on the execution, you have to call 1422 /// \ref init() first, then you can add several source nodes with 1430 1423 /// \ref addSource(). Finally the actual path computation can be 1431 1424 /// performed with one of the \ref start() functions. … … 1699 1692 /// \brief Runs the algorithm to visit all nodes in the digraph. 1700 1693 /// 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). 1694 /// This method runs the %BFS algorithm in order to visit all nodes 1695 /// in the digraph. 1707 1696 /// 1708 1697 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code. … … 1736 1725 ///@{ 1737 1726 1738 /// \brief Checks if anode is reached from the root(s).1727 /// \brief Checks if the given node is reached from the root(s). 1739 1728 /// 1740 1729 /// Returns \c true if \c v is reached from the root(s).
Note: See TracChangeset
for help on using the changeset viewer.
