Changes in / [715:ece80147fb08:717:684964884a2e] in lemon-main
- Location:
- lemon
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r713 r717 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). -
lemon/dfs.h
r713 r717 48 48 ///The type of the map that stores the predecessor 49 49 ///arcs of the %DFS 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. … … 225 226 ///\ref named-templ-param "Named parameter" for setting 226 227 ///\c PredMap type. 227 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.228 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 228 229 template <class T> 229 230 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > { … … 245 246 ///\ref named-templ-param "Named parameter" for setting 246 247 ///\c DistMap type. 247 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.248 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 248 249 template <class T> 249 250 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > { … … 265 266 ///\ref named-templ-param "Named parameter" for setting 266 267 ///\c ReachedMap type. 267 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.268 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 268 269 template <class T> 269 270 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > { … … 285 286 ///\ref named-templ-param "Named parameter" for setting 286 287 ///\c ProcessedMap type. 287 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.288 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 288 289 template <class T> 289 290 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > { … … 670 671 ///@{ 671 672 672 ///The DFS path to anode.673 674 ///Returns the DFS path to a node.673 ///The DFS path to the given node. 674 675 ///Returns the DFS path to the given node from the root(s). 675 676 /// 676 677 ///\warning \c t should be reached from the root(s). … … 680 681 Path path(Node t) const { return Path(*G, *_pred, t); } 681 682 682 ///The distance of anode from the root(s).683 684 ///Returns the distance of anode from the root(s).683 ///The distance of the given node from the root(s). 684 685 ///Returns the distance of the given node from the root(s). 685 686 /// 686 687 ///\warning If node \c v is not reached from the root(s), then … … 691 692 int dist(Node v) const { return (*_dist)[v]; } 692 693 693 ///Returns the 'previous arc' of the %DFS tree for anode.694 ///Returns the 'previous arc' of the %DFS tree for the given node. 694 695 695 696 ///This function returns the 'previous arc' of the %DFS tree for the … … 699 700 /// 700 701 ///The %DFS tree used here is equal to the %DFS tree used in 701 ///\ref predNode() .702 ///\ref predNode() and \ref predMap(). 702 703 /// 703 704 ///\pre Either \ref run(Node) "run()" or \ref init() … … 705 706 Arc predArc(Node v) const { return (*_pred)[v];} 706 707 707 ///Returns the 'previous node' of the %DFS tree .708 ///Returns the 'previous node' of the %DFS tree for the given node. 708 709 709 710 ///This function returns the 'previous node' of the %DFS 710 711 ///tree for the node \c v, i.e. it returns the last but one node 711 /// froma %DFS path from a root to \c v. It is \c INVALID712 ///of a %DFS path from a root to \c v. It is \c INVALID 712 713 ///if \c v is not reached from the root(s) or if \c v is a root. 713 714 /// 714 715 ///The %DFS tree used here is equal to the %DFS tree used in 715 ///\ref predArc() .716 ///\ref predArc() and \ref predMap(). 716 717 /// 717 718 ///\pre Either \ref run(Node) "run()" or \ref init() … … 734 735 /// 735 736 ///Returns a const reference to the node map that stores the predecessor 736 ///arcs, which form the DFS tree .737 ///arcs, which form the DFS tree (forest). 737 738 /// 738 739 ///\pre Either \ref run(Node) "run()" or \ref init() … … 740 741 const PredMap &predMap() const { return *_pred;} 741 742 742 ///Checks if anode is reached from the root(s).743 ///Checks if the given node. node is reached from the root(s). 743 744 744 745 ///Returns \c true if \c v is reached from the root(s). … … 766 767 ///The type of the map that stores the predecessor 767 768 ///arcs of the %DFS paths. 768 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.769 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 769 770 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 770 771 ///Instantiates a PredMap. … … 781 782 782 783 ///The type of the map that indicates which nodes are processed. 783 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.784 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 784 785 ///By default it is a NullMap. 785 786 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; … … 801 802 802 803 ///The type of the map that indicates which nodes are reached. 803 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.804 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 804 805 typedef typename Digraph::template NodeMap<bool> ReachedMap; 805 806 ///Instantiates a ReachedMap. … … 816 817 817 818 ///The type of the map that stores the distances of the nodes. 818 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.819 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 819 820 typedef typename Digraph::template NodeMap<int> DistMap; 820 821 ///Instantiates a DistMap. … … 831 832 832 833 ///The type of the DFS paths. 833 ///It must meetthe \ref concepts::Path "Path" concept.834 ///It must conform to the \ref concepts::Path "Path" concept. 834 835 typedef lemon::Path<Digraph> Path; 835 836 }; … … 837 838 /// Default traits class used by DfsWizard 838 839 839 /// To make it easier to use Dfs algorithm 840 /// we have created a wizard class. 841 /// This \ref DfsWizard class needs default traits, 842 /// as well as the \ref Dfs class. 843 /// The \ref DfsWizardBase is a class to be the default traits of the 844 /// \ref DfsWizard class. 840 /// Default traits class used by DfsWizard. 841 /// \tparam GR The type of the digraph. 845 842 template<class GR> 846 843 class DfsWizardBase : public DfsWizardDefaultTraits<GR> … … 870 867 /// Constructor. 871 868 872 /// This constructor does not require parameters, thereforeit initiates869 /// This constructor does not require parameters, it initiates 873 870 /// all of the attributes to \c 0. 874 871 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 900 897 typedef TR Base; 901 898 902 ///The type of the digraph the algorithm runs on.903 899 typedef typename TR::Digraph Digraph; 904 900 … … 908 904 typedef typename Digraph::OutArcIt OutArcIt; 909 905 910 ///\brief The type of the map that stores the predecessor911 ///arcs of the DFS paths.912 906 typedef typename TR::PredMap PredMap; 913 ///\brief The type of the map that stores the distances of the nodes.914 907 typedef typename TR::DistMap DistMap; 915 ///\brief The type of the map that indicates which nodes are reached.916 908 typedef typename TR::ReachedMap ReachedMap; 917 ///\brief The type of the map that indicates which nodes are processed.918 909 typedef typename TR::ProcessedMap ProcessedMap; 919 ///The type of the DFS paths920 910 typedef typename TR::Path Path; 921 911 … … 1000 990 SetPredMapBase(const TR &b) : TR(b) {} 1001 991 }; 1002 ///\brief \ref named-func-param "Named parameter" 1003 ///for setting PredMap object. 1004 /// 1005 ///\ref named-func-param "Named parameter" 1006 ///for setting PredMap object. 992 993 ///\brief \ref named-templ-param "Named parameter" for setting 994 ///the predecessor map. 995 /// 996 ///\ref named-templ-param "Named parameter" function for setting 997 ///the map that stores the predecessor arcs of the nodes. 1007 998 template<class T> 1008 999 DfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1018 1009 SetReachedMapBase(const TR &b) : TR(b) {} 1019 1010 }; 1020 ///\brief \ref named-func-param "Named parameter" 1021 ///for setting ReachedMap object. 1022 /// 1023 /// \ref named-func-param "Named parameter" 1024 ///for setting ReachedMap object. 1011 1012 ///\brief \ref named-templ-param "Named parameter" for setting 1013 ///the reached map. 1014 /// 1015 ///\ref named-templ-param "Named parameter" function for setting 1016 ///the map that indicates which nodes are reached. 1025 1017 template<class T> 1026 1018 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1036 1028 SetDistMapBase(const TR &b) : TR(b) {} 1037 1029 }; 1038 ///\brief \ref named-func-param "Named parameter" 1039 ///for setting DistMap object. 1040 /// 1041 /// \ref named-func-param "Named parameter" 1042 ///for setting DistMap object. 1030 1031 ///\brief \ref named-templ-param "Named parameter" for setting 1032 ///the distance map. 1033 /// 1034 ///\ref named-templ-param "Named parameter" function for setting 1035 ///the map that stores the distances of the nodes calculated 1036 ///by the algorithm. 1043 1037 template<class T> 1044 1038 DfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1054 1048 SetProcessedMapBase(const TR &b) : TR(b) {} 1055 1049 }; 1056 ///\brief \ref named-func-param "Named parameter" 1057 ///for setting ProcessedMap object. 1058 /// 1059 /// \ref named-func-param "Named parameter" 1060 ///for setting ProcessedMap object. 1050 1051 ///\brief \ref named-func-param "Named parameter" for setting 1052 ///the processed map. 1053 /// 1054 ///\ref named-templ-param "Named parameter" function for setting 1055 ///the map that indicates which nodes are processed. 1061 1056 template<class T> 1062 1057 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1209 1204 /// 1210 1205 /// The type of the map that indicates which nodes are reached. 1211 /// It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.1206 /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1212 1207 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1213 1208 … … 1621 1616 ///@{ 1622 1617 1623 /// \brief Checks if anode is reached from the root(s).1618 /// \brief Checks if the given node is reached from the root(s). 1624 1619 /// 1625 1620 /// Returns \c true if \c v is reached from the root(s). -
lemon/dijkstra.h
r713 r717 71 71 72 72 ///The type of the map that stores the arc lengths. 73 ///It must meetthe \ref concepts::ReadMap "ReadMap" concept.73 ///It must conform to the \ref concepts::ReadMap "ReadMap" concept. 74 74 typedef LEN LengthMap; 75 ///The type of the length of the arcs.75 ///The type of the arc lengths. 76 76 typedef typename LEN::Value Value; 77 77 … … 117 117 ///The type of the map that stores the predecessor 118 118 ///arcs of the shortest paths. 119 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.119 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 120 120 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 121 121 ///Instantiates a \c PredMap. … … 132 132 133 133 ///The type of the map that indicates which nodes are processed. 134 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.134 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 135 135 ///By default it is a NullMap. 136 136 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; … … 152 152 153 153 ///The type of the map that stores the distances of the nodes. 154 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.154 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 155 155 typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap; 156 156 ///Instantiates a \c DistMap. … … 169 169 /// \ingroup shortest_path 170 170 ///This class provides an efficient implementation of the %Dijkstra algorithm. 171 /// 172 ///The %Dijkstra algorithm solves the single-source shortest path problem 173 ///when all arc lengths are non-negative. If there are negative lengths, 174 ///the BellmanFord algorithm should be used instead. 171 175 /// 172 176 ///The arc lengths are passed to the algorithm using a … … 202 206 typedef typename TR::Digraph Digraph; 203 207 204 ///The type of the length of the arcs.208 ///The type of the arc lengths. 205 209 typedef typename TR::LengthMap::Value Value; 206 210 ///The type of the map that stores the arc lengths. … … 305 309 ///\ref named-templ-param "Named parameter" for setting 306 310 ///\c PredMap type. 307 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.311 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 308 312 template <class T> 309 313 struct SetPredMap … … 326 330 ///\ref named-templ-param "Named parameter" for setting 327 331 ///\c DistMap type. 328 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.332 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 329 333 template <class T> 330 334 struct SetDistMap … … 347 351 ///\ref named-templ-param "Named parameter" for setting 348 352 ///\c ProcessedMap type. 349 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.353 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 350 354 template <class T> 351 355 struct SetProcessedMap … … 444 448 ///\ref named-templ-param "Named parameter" for setting 445 449 ///\c OperationTraits type. 450 /// For more information see \ref DijkstraDefaultOperationTraits. 446 451 template <class T> 447 452 struct SetOperationTraits … … 802 807 ///The results of the %Dijkstra algorithm can be obtained using these 803 808 ///functions.\n 804 ///Either \ref run(Node) "run()" or \ref start() should be called809 ///Either \ref run(Node) "run()" or \ref init() should be called 805 810 ///before using them. 806 811 807 812 ///@{ 808 813 809 ///The shortest path to anode.810 811 ///Returns the shortest path to a node.814 ///The shortest path to the given node. 815 816 ///Returns the shortest path to the given node from the root(s). 812 817 /// 813 818 ///\warning \c t should be reached from the root(s). … … 817 822 Path path(Node t) const { return Path(*G, *_pred, t); } 818 823 819 ///The distance of anode from the root(s).820 821 ///Returns the distance of anode from the root(s).824 ///The distance of the given node from the root(s). 825 826 ///Returns the distance of the given node from the root(s). 822 827 /// 823 828 ///\warning If node \c v is not reached from the root(s), then … … 828 833 Value dist(Node v) const { return (*_dist)[v]; } 829 834 830 ///Returns the 'previous arc' of the shortest path tree for a node. 831 835 ///\brief Returns the 'previous arc' of the shortest path tree for 836 ///the given node. 837 /// 832 838 ///This function returns the 'previous arc' of the shortest path 833 839 ///tree for the node \c v, i.e. it returns the last arc of a … … 836 842 /// 837 843 ///The shortest path tree used here is equal to the shortest path 838 ///tree used in \ref predNode() .844 ///tree used in \ref predNode() and \ref predMap(). 839 845 /// 840 846 ///\pre Either \ref run(Node) "run()" or \ref init() … … 842 848 Arc predArc(Node v) const { return (*_pred)[v]; } 843 849 844 ///Returns the 'previous node' of the shortest path tree for a node. 845 850 ///\brief Returns the 'previous node' of the shortest path tree for 851 ///the given node. 852 /// 846 853 ///This function returns the 'previous node' of the shortest path 847 854 ///tree for the node \c v, i.e. it returns the last but one node 848 /// froma shortest path from a root to \c v. It is \c INVALID855 ///of a shortest path from a root to \c v. It is \c INVALID 849 856 ///if \c v is not reached from the root(s) or if \c v is a root. 850 857 /// 851 858 ///The shortest path tree used here is equal to the shortest path 852 ///tree used in \ref predArc() .859 ///tree used in \ref predArc() and \ref predMap(). 853 860 /// 854 861 ///\pre Either \ref run(Node) "run()" or \ref init() … … 871 878 /// 872 879 ///Returns a const reference to the node map that stores the predecessor 873 ///arcs, which form the shortest path tree .880 ///arcs, which form the shortest path tree (forest). 874 881 /// 875 882 ///\pre Either \ref run(Node) "run()" or \ref init() … … 877 884 const PredMap &predMap() const { return *_pred;} 878 885 879 ///Checks if anode is reached from the root(s).886 ///Checks if the given node is reached from the root(s). 880 887 881 888 ///Returns \c true if \c v is reached from the root(s). … … 896 903 Heap::POST_HEAP; } 897 904 898 ///The current distance of anode from the root(s).899 900 ///Returns the current distance of anode from the root(s).905 ///The current distance of the given node from the root(s). 906 907 ///Returns the current distance of the given node from the root(s). 901 908 ///It may be decreased in the following processes. 902 909 /// … … 925 932 926 933 ///The type of the map that stores the arc lengths. 927 ///It must meetthe \ref concepts::ReadMap "ReadMap" concept.934 ///It must conform to the \ref concepts::ReadMap "ReadMap" concept. 928 935 typedef LEN LengthMap; 929 ///The type of the length of the arcs.936 ///The type of the arc lengths. 930 937 typedef typename LEN::Value Value; 931 938 … … 974 981 ///The type of the map that stores the predecessor 975 982 ///arcs of the shortest paths. 976 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.983 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 977 984 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 978 985 ///Instantiates a PredMap. … … 989 996 990 997 ///The type of the map that indicates which nodes are processed. 991 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.998 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 992 999 ///By default it is a NullMap. 993 1000 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; … … 1009 1016 1010 1017 ///The type of the map that stores the distances of the nodes. 1011 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.1018 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 1012 1019 typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap; 1013 1020 ///Instantiates a DistMap. … … 1024 1031 1025 1032 ///The type of the shortest paths. 1026 ///It must meetthe \ref concepts::Path "Path" concept.1033 ///It must conform to the \ref concepts::Path "Path" concept. 1027 1034 typedef lemon::Path<Digraph> Path; 1028 1035 }; … … 1030 1037 /// Default traits class used by DijkstraWizard 1031 1038 1032 /// To make it easier to use Dijkstra algorithm 1033 /// we have created a wizard class. 1034 /// This \ref DijkstraWizard class needs default traits, 1035 /// as well as the \ref Dijkstra class. 1036 /// The \ref DijkstraWizardBase is a class to be the default traits of the 1037 /// \ref DijkstraWizard class. 1039 /// Default traits class used by DijkstraWizard. 1040 /// \tparam GR The type of the digraph. 1041 /// \tparam LEN The type of the length map. 1038 1042 template<typename GR, typename LEN> 1039 1043 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN> … … 1094 1098 typedef TR Base; 1095 1099 1096 ///The type of the digraph the algorithm runs on.1097 1100 typedef typename TR::Digraph Digraph; 1098 1101 … … 1102 1105 typedef typename Digraph::OutArcIt OutArcIt; 1103 1106 1104 ///The type of the map that stores the arc lengths.1105 1107 typedef typename TR::LengthMap LengthMap; 1106 ///The type of the length of the arcs.1107 1108 typedef typename LengthMap::Value Value; 1108 ///\brief The type of the map that stores the predecessor1109 ///arcs of the shortest paths.1110 1109 typedef typename TR::PredMap PredMap; 1111 ///The type of the map that stores the distances of the nodes.1112 1110 typedef typename TR::DistMap DistMap; 1113 ///The type of the map that indicates which nodes are processed.1114 1111 typedef typename TR::ProcessedMap ProcessedMap; 1115 ///The type of the shortest paths1116 1112 typedef typename TR::Path Path; 1117 ///The heap type used by the dijkstra algorithm.1118 1113 typedef typename TR::Heap Heap; 1119 1114 … … 1187 1182 SetPredMapBase(const TR &b) : TR(b) {} 1188 1183 }; 1189 ///\brief \ref named-func-param "Named parameter" 1190 ///for setting PredMap object. 1191 /// 1192 ///\ref named-func-param "Named parameter" 1193 ///for setting PredMap object. 1184 1185 ///\brief \ref named-templ-param "Named parameter" for setting 1186 ///the predecessor map. 1187 /// 1188 ///\ref named-templ-param "Named parameter" function for setting 1189 ///the map that stores the predecessor arcs of the nodes. 1194 1190 template<class T> 1195 1191 DijkstraWizard<SetPredMapBase<T> > predMap(const T &t) … … 1205 1201 SetDistMapBase(const TR &b) : TR(b) {} 1206 1202 }; 1207 ///\brief \ref named-func-param "Named parameter" 1208 ///for setting DistMap object. 1209 /// 1210 ///\ref named-func-param "Named parameter" 1211 ///for setting DistMap object. 1203 1204 ///\brief \ref named-templ-param "Named parameter" for setting 1205 ///the distance map. 1206 /// 1207 ///\ref named-templ-param "Named parameter" function for setting 1208 ///the map that stores the distances of the nodes calculated 1209 ///by the algorithm. 1212 1210 template<class T> 1213 1211 DijkstraWizard<SetDistMapBase<T> > distMap(const T &t) … … 1223 1221 SetProcessedMapBase(const TR &b) : TR(b) {} 1224 1222 }; 1225 ///\brief \ref named-func-param "Named parameter" 1226 ///for setting ProcessedMap object. 1227 /// 1228 /// \ref named-func-param "Named parameter" 1229 ///for setting ProcessedMap object. 1223 1224 ///\brief \ref named-func-param "Named parameter" for setting 1225 ///the processed map. 1226 /// 1227 ///\ref named-templ-param "Named parameter" function for setting 1228 ///the map that indicates which nodes are processed. 1230 1229 template<class T> 1231 1230 DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1240 1239 SetPathBase(const TR &b) : TR(b) {} 1241 1240 }; 1241 1242 1242 ///\brief \ref named-func-param "Named parameter" 1243 1243 ///for getting the shortest path to the target node. -
lemon/maps.h
r695 r717 1790 1790 /// \code 1791 1791 /// std::vector<Node> v; 1792 /// dfs(g ,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();1792 /// dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s); 1793 1793 /// \endcode 1794 1794 /// \code 1795 1795 /// std::vector<Node> v(countNodes(g)); 1796 /// dfs(g ,s).processedMap(loggerBoolMap(v.begin())).run();1796 /// dfs(g).processedMap(loggerBoolMap(v.begin())).run(s); 1797 1797 /// \endcode 1798 1798 ///
Note: See TracChangeset
for help on using the changeset viewer.
