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