r281:e9b4fbe163f5
Fri, 26 Sep 2008 09:52:28
[Not Reviewed]
0 comments (0 inline)
0
7
0
131
93
133
95
125
97
28
11
26
6
| ... | ... |
@@ -30,2 +30,3 @@ |
| 30 | 30 |
#include <lemon/maps.h> |
| 31 |
#include <lemon/path.h> |
|
| 31 | 32 |
|
| ... | ... |
@@ -115,3 +116,3 @@ |
| 115 | 116 |
/// |
| 116 |
///There is also a \ref bfs() "function |
|
| 117 |
///There is also a \ref bfs() "function-type interface" for the BFS |
|
| 117 | 118 |
///algorithm, which is convenient in the simplier cases and it can be |
| ... | ... |
@@ -840,3 +841,3 @@ |
| 840 | 841 |
///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
| 841 |
typedef |
|
| 842 |
typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
|
| 842 | 843 |
///Instantiates a \ref PredMap. |
| ... | ... |
@@ -846,9 +847,5 @@ |
| 846 | 847 |
///\ref PredMap. |
| 847 |
#ifdef DOXYGEN |
|
| 848 | 848 |
static PredMap *createPredMap(const Digraph &g) |
| 849 |
#else |
|
| 850 |
static PredMap *createPredMap(const Digraph &) |
|
| 851 |
#endif |
|
| 852 | 849 |
{
|
| 853 |
return new PredMap(); |
|
| 850 |
return new PredMap(g); |
|
| 854 | 851 |
} |
| ... | ... |
@@ -859,2 +856,3 @@ |
| 859 | 856 |
///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
| 857 |
///By default it is a NullMap. |
|
| 860 | 858 |
typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
| ... | ... |
@@ -893,4 +891,3 @@ |
| 893 | 891 |
///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
| 894 |
/// |
|
| 895 |
typedef NullMap<typename Digraph::Node,int> DistMap; |
|
| 892 |
typedef typename Digraph::template NodeMap<int> DistMap; |
|
| 896 | 893 |
///Instantiates a \ref DistMap. |
| ... | ... |
@@ -900,10 +897,12 @@ |
| 900 | 897 |
///the \ref DistMap |
| 901 |
#ifdef DOXYGEN |
|
| 902 | 898 |
static DistMap *createDistMap(const Digraph &g) |
| 903 |
#else |
|
| 904 |
static DistMap *createDistMap(const Digraph &) |
|
| 905 |
#endif |
|
| 906 | 899 |
{
|
| 907 |
return new DistMap(); |
|
| 900 |
return new DistMap(g); |
|
| 908 | 901 |
} |
| 902 |
|
|
| 903 |
///The type of the shortest paths. |
|
| 904 |
|
|
| 905 |
///The type of the shortest paths. |
|
| 906 |
///It must meet the \ref concepts::Path "Path" concept. |
|
| 907 |
typedef lemon::Path<Digraph> Path; |
|
| 909 | 908 |
}; |
| ... | ... |
@@ -937,4 +936,6 @@ |
| 937 | 936 |
void *_dist; |
| 938 |
//Pointer to the source node. |
|
| 939 |
Node _source; |
|
| 937 |
//Pointer to the shortest path to the target node. |
|
| 938 |
void *_path; |
|
| 939 |
//Pointer to the distance of the target node. |
|
| 940 |
int *_di; |
|
| 940 | 941 |
|
| ... | ... |
@@ -944,5 +945,5 @@ |
| 944 | 945 |
/// This constructor does not require parameters, therefore it initiates |
| 945 |
/// all of the attributes to |
|
| 946 |
/// all of the attributes to \c 0. |
|
| 946 | 947 |
BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), |
| 947 |
_dist(0), |
|
| 948 |
_dist(0), _path(0), _di(0) {}
|
|
| 948 | 949 |
|
| ... | ... |
@@ -950,10 +951,8 @@ |
| 950 | 951 |
|
| 951 |
/// This constructor requires some parameters, |
|
| 952 |
/// listed in the parameters list. |
|
| 953 |
/// |
|
| 952 |
/// This constructor requires one parameter, |
|
| 953 |
/// others are initiated to \c 0. |
|
| 954 | 954 |
/// \param g The digraph the algorithm runs on. |
| 955 |
/// \param s The source node. |
|
| 956 |
BfsWizardBase(const GR &g, Node s=INVALID) : |
|
| 955 |
BfsWizardBase(const GR &g) : |
|
| 957 | 956 |
_g(reinterpret_cast<void*>(const_cast<GR*>(&g))), |
| 958 |
_reached(0), _processed(0), _pred(0), _dist(0), |
|
| 957 |
_reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
|
|
| 959 | 958 |
|
| ... | ... |
@@ -961,23 +960,11 @@ |
| 961 | 960 |
|
| 962 |
/// Auxiliary class for the function |
|
| 961 |
/// Auxiliary class for the function-type interface of BFS algorithm. |
|
| 963 | 962 |
|
| 964 |
/// This auxiliary class is created to implement the function type |
|
| 965 |
/// interface of \ref Bfs algorithm. It uses the functions and features |
|
| 966 |
/// of the plain \ref Bfs, but it is much simpler to use it. |
|
| 967 |
/// It should only be used through the \ref bfs() function, which makes |
|
| 968 |
/// |
|
| 963 |
/// This auxiliary class is created to implement the |
|
| 964 |
/// \ref bfs() "function-type interface" of \ref Bfs algorithm. |
|
| 965 |
/// It does not have own \ref run() method, it uses the functions |
|
| 966 |
/// and features of the plain \ref Bfs. |
|
| 969 | 967 |
/// |
| 970 |
/// Simplicity means that the way to change the types defined |
|
| 971 |
/// in the traits class is based on functions that returns the new class |
|
| 972 |
/// and not on templatable built-in classes. |
|
| 973 |
/// When using the plain \ref Bfs |
|
| 974 |
/// the new class with the modified type comes from |
|
| 975 |
/// the original class by using the :: |
|
| 976 |
/// operator. In the case of \ref BfsWizard only |
|
| 977 |
/// a function have to be called, and it will |
|
| 978 |
/// return the needed class. |
|
| 979 |
/// |
|
| 980 |
/// It does not have own \ref run() method. When its \ref run() method |
|
| 981 |
/// is called, it initiates a plain \ref Bfs object, and calls the |
|
| 982 |
/// \ref |
|
| 968 |
/// This class should only be used through the \ref bfs() function, |
|
| 969 |
/// which makes it easier to use the algorithm. |
|
| 983 | 970 |
template<class TR> |
| ... | ... |
@@ -1004,2 +991,4 @@ |
| 1004 | 991 |
typedef typename TR::ProcessedMap ProcessedMap; |
| 992 |
///The type of the shortest paths |
|
| 993 |
typedef typename TR::Path Path; |
|
| 1005 | 994 |
|
| ... | ... |
@@ -1014,4 +1003,5 @@ |
| 1014 | 1003 |
/// These parameters will be the default values for the traits class. |
| 1015 |
BfsWizard(const Digraph &g, Node s=INVALID) : |
|
| 1016 |
TR(g,s) {}
|
|
| 1004 |
/// \param g The digraph the algorithm runs on. |
|
| 1005 |
BfsWizard(const Digraph &g) : |
|
| 1006 |
TR(g) {}
|
|
| 1017 | 1007 |
|
| ... | ... |
@@ -1022,10 +1012,13 @@ |
| 1022 | 1012 |
|
| 1023 |
///Runs BFS algorithm from |
|
| 1013 |
///Runs BFS algorithm from the given source node. |
|
| 1024 | 1014 |
|
| 1025 |
///Runs BFS algorithm from a source node. |
|
| 1026 |
///The node can be given with the \ref source() function. |
|
| 1027 |
|
|
| 1015 |
///This method runs BFS algorithm from node \c s |
|
| 1016 |
///in order to compute the shortest path to each node. |
|
| 1017 |
void run(Node s) |
|
| 1028 | 1018 |
{
|
| 1029 |
if(Base::_source==INVALID) throw UninitializedParameter(); |
|
| 1030 | 1019 |
Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); |
| 1020 |
if (Base::_pred) |
|
| 1021 |
alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); |
|
| 1022 |
if (Base::_dist) |
|
| 1023 |
alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
|
| 1031 | 1024 |
if(Base::_reached) |
| ... | ... |
@@ -1034,2 +1027,19 @@ |
| 1034 | 1027 |
alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); |
| 1028 |
if (s!=INVALID) |
|
| 1029 |
alg.run(s); |
|
| 1030 |
else |
|
| 1031 |
alg.run(); |
|
| 1032 |
} |
|
| 1033 |
|
|
| 1034 |
///Finds the shortest path between \c s and \c t. |
|
| 1035 |
|
|
| 1036 |
///This method runs BFS algorithm from node \c s |
|
| 1037 |
///in order to compute the shortest path to node \c t |
|
| 1038 |
///(it stops searching when \c t is processed). |
|
| 1039 |
/// |
|
| 1040 |
///\return \c true if \c t is reachable form \c s. |
|
| 1041 |
bool run(Node s, Node t) |
|
| 1042 |
{
|
|
| 1043 |
if (s==INVALID || t==INVALID) throw UninitializedParameter(); |
|
| 1044 |
Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); |
|
| 1035 | 1045 |
if(Base::_pred) |
| ... | ... |
@@ -1038,23 +1048,21 @@ |
| 1038 | 1048 |
alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
| 1039 |
|
|
| 1049 |
if (Base::_reached) |
|
| 1050 |
alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); |
|
| 1051 |
if (Base::_processed) |
|
| 1052 |
alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); |
|
| 1053 |
alg.run(s,t); |
|
| 1054 |
if (Base::_path) |
|
| 1055 |
*reinterpret_cast<Path*>(Base::_path) = alg.path(t); |
|
| 1056 |
if (Base::_di) |
|
| 1057 |
*Base::_di = alg.dist(t); |
|
| 1058 |
return alg.reached(t); |
|
| 1040 | 1059 |
} |
| 1041 | 1060 |
|
| 1042 |
///Runs BFS algorithm |
|
| 1061 |
///Runs BFS algorithm to visit all nodes in the digraph. |
|
| 1043 | 1062 |
|
| 1044 |
///Runs BFS algorithm from the given node. |
|
| 1045 |
///\param s is the given source. |
|
| 1046 |
|
|
| 1063 |
///This method runs BFS algorithm in order to compute |
|
| 1064 |
///the shortest path to each node. |
|
| 1065 |
void run() |
|
| 1047 | 1066 |
{
|
| 1048 |
Base::_source=s; |
|
| 1049 |
run(); |
|
| 1050 |
} |
|
| 1051 |
|
|
| 1052 |
/// Sets the source node, from which the Bfs algorithm runs. |
|
| 1053 |
|
|
| 1054 |
/// Sets the source node, from which the Bfs algorithm runs. |
|
| 1055 |
/// \param s is the source node. |
|
| 1056 |
BfsWizard<TR> &source(Node s) |
|
| 1057 |
{
|
|
| 1058 |
Base::_source=s; |
|
| 1059 |
return *this; |
|
| 1067 |
run(INVALID); |
|
| 1060 | 1068 |
} |
| ... | ... |
@@ -1067,6 +1075,6 @@ |
| 1067 | 1075 |
}; |
| 1068 |
///\brief \ref named- |
|
| 1076 |
///\brief \ref named-func-param "Named parameter" |
|
| 1069 | 1077 |
///for setting \ref PredMap object. |
| 1070 | 1078 |
/// |
| 1071 |
/// |
|
| 1079 |
///\ref named-func-param "Named parameter" |
|
| 1072 | 1080 |
///for setting \ref PredMap object. |
| ... | ... |
@@ -1085,6 +1093,6 @@ |
| 1085 | 1093 |
}; |
| 1086 |
///\brief \ref named- |
|
| 1094 |
///\brief \ref named-func-param "Named parameter" |
|
| 1087 | 1095 |
///for setting \ref ReachedMap object. |
| 1088 | 1096 |
/// |
| 1089 |
/// \ref named- |
|
| 1097 |
/// \ref named-func-param "Named parameter" |
|
| 1090 | 1098 |
///for setting \ref ReachedMap object. |
| ... | ... |
@@ -1098,2 +1106,20 @@ |
| 1098 | 1106 |
template<class T> |
| 1107 |
struct SetDistMapBase : public Base {
|
|
| 1108 |
typedef T DistMap; |
|
| 1109 |
static DistMap *createDistMap(const Digraph &) { return 0; };
|
|
| 1110 |
SetDistMapBase(const TR &b) : TR(b) {}
|
|
| 1111 |
}; |
|
| 1112 |
///\brief \ref named-func-param "Named parameter" |
|
| 1113 |
///for setting \ref DistMap object. |
|
| 1114 |
/// |
|
| 1115 |
/// \ref named-func-param "Named parameter" |
|
| 1116 |
///for setting \ref DistMap object. |
|
| 1117 |
template<class T> |
|
| 1118 |
BfsWizard<SetDistMapBase<T> > distMap(const T &t) |
|
| 1119 |
{
|
|
| 1120 |
Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
|
| 1121 |
return BfsWizard<SetDistMapBase<T> >(*this); |
|
| 1122 |
} |
|
| 1123 |
|
|
| 1124 |
template<class T> |
|
| 1099 | 1125 |
struct SetProcessedMapBase : public Base {
|
| ... | ... |
@@ -1103,6 +1129,6 @@ |
| 1103 | 1129 |
}; |
| 1104 |
///\brief \ref named- |
|
| 1130 |
///\brief \ref named-func-param "Named parameter" |
|
| 1105 | 1131 |
///for setting \ref ProcessedMap object. |
| 1106 | 1132 |
/// |
| 1107 |
/// \ref named- |
|
| 1133 |
/// \ref named-func-param "Named parameter" |
|
| 1108 | 1134 |
///for setting \ref ProcessedMap object. |
| ... | ... |
@@ -1116,17 +1142,27 @@ |
| 1116 | 1142 |
template<class T> |
| 1117 |
struct SetDistMapBase : public Base {
|
|
| 1118 |
typedef T DistMap; |
|
| 1119 |
static DistMap *createDistMap(const Digraph &) { return 0; };
|
|
| 1120 |
SetDistMapBase(const TR &b) : TR(b) {}
|
|
| 1143 |
struct SetPathBase : public Base {
|
|
| 1144 |
typedef T Path; |
|
| 1145 |
SetPathBase(const TR &b) : TR(b) {}
|
|
| 1121 | 1146 |
}; |
| 1122 |
///\brief \ref named-templ-param "Named parameter" |
|
| 1123 |
///for setting \ref DistMap object. |
|
| 1147 |
///\brief \ref named-func-param "Named parameter" |
|
| 1148 |
///for getting the shortest path to the target node. |
|
| 1124 | 1149 |
/// |
| 1125 |
/// \ref named-templ-param "Named parameter" |
|
| 1126 |
///for setting \ref DistMap object. |
|
| 1150 |
///\ref named-func-param "Named parameter" |
|
| 1151 |
///for getting the shortest path to the target node. |
|
| 1127 | 1152 |
template<class T> |
| 1128 |
BfsWizard< |
|
| 1153 |
BfsWizard<SetPathBase<T> > path(const T &t) |
|
| 1129 | 1154 |
{
|
| 1130 |
Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
|
| 1131 |
return BfsWizard<SetDistMapBase<T> >(*this); |
|
| 1155 |
Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t)); |
|
| 1156 |
return BfsWizard<SetPathBase<T> >(*this); |
|
| 1157 |
} |
|
| 1158 |
|
|
| 1159 |
///\brief \ref named-func-param "Named parameter" |
|
| 1160 |
///for getting the distance of the target node. |
|
| 1161 |
/// |
|
| 1162 |
///\ref named-func-param "Named parameter" |
|
| 1163 |
///for getting the distance of the target node. |
|
| 1164 |
BfsWizard dist(const int &d) |
|
| 1165 |
{
|
|
| 1166 |
Base::_di=const_cast<int*>(&d); |
|
| 1167 |
return *this; |
|
| 1132 | 1168 |
} |
| ... | ... |
@@ -1135,14 +1171,16 @@ |
| 1135 | 1171 |
|
| 1136 |
///Function |
|
| 1172 |
///Function-type interface for BFS algorithm. |
|
| 1137 | 1173 |
|
| 1138 | 1174 |
/// \ingroup search |
| 1139 |
///Function |
|
| 1175 |
///Function-type interface for BFS algorithm. |
|
| 1140 | 1176 |
/// |
| 1141 |
///This function also has several |
|
| 1142 |
///\ref named-templ-func-param "named parameters", |
|
| 1177 |
///This function also has several \ref named-func-param "named parameters", |
|
| 1143 | 1178 |
///they are declared as the members of class \ref BfsWizard. |
| 1144 |
///The following |
|
| 1145 |
///example shows how to use these parameters. |
|
| 1179 |
///The following examples show how to use these parameters. |
|
| 1146 | 1180 |
///\code |
| 1147 |
/// |
|
| 1181 |
/// // Compute shortest path from node s to each node |
|
| 1182 |
/// bfs(g).predMap(preds).distMap(dists).run(s); |
|
| 1183 |
/// |
|
| 1184 |
/// // Compute shortest path from s to t |
|
| 1185 |
/// bool reached = bfs(g).path(p).dist(d).run(s,t); |
|
| 1148 | 1186 |
///\endcode |
| ... | ... |
@@ -1154,5 +1192,5 @@ |
| 1154 | 1192 |
BfsWizard<BfsWizardBase<GR> > |
| 1155 |
bfs(const GR & |
|
| 1193 |
bfs(const GR &digraph) |
|
| 1156 | 1194 |
{
|
| 1157 |
return BfsWizard<BfsWizardBase<GR> >( |
|
| 1195 |
return BfsWizard<BfsWizardBase<GR> >(digraph); |
|
| 1158 | 1196 |
} |
| ... | ... |
@@ -31,2 +31,3 @@ |
| 31 | 31 |
#include <lemon/maps.h> |
| 32 |
#include <lemon/path.h> |
|
| 32 | 33 |
|
| ... | ... |
@@ -116,3 +117,3 @@ |
| 116 | 117 |
/// |
| 117 |
///There is also a \ref dfs() "function |
|
| 118 |
///There is also a \ref dfs() "function-type interface" for the DFS |
|
| 118 | 119 |
///algorithm, which is convenient in the simplier cases and it can be |
| ... | ... |
@@ -774,4 +775,3 @@ |
| 774 | 775 |
///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
| 775 |
/// |
|
| 776 |
typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap; |
|
| 776 |
typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
|
| 777 | 777 |
///Instantiates a \ref PredMap. |
| ... | ... |
@@ -781,9 +781,5 @@ |
| 781 | 781 |
///\ref PredMap. |
| 782 |
#ifdef DOXYGEN |
|
| 783 | 782 |
static PredMap *createPredMap(const Digraph &g) |
| 784 |
#else |
|
| 785 |
static PredMap *createPredMap(const Digraph &) |
|
| 786 |
#endif |
|
| 787 | 783 |
{
|
| 788 |
return new PredMap(); |
|
| 784 |
return new PredMap(g); |
|
| 789 | 785 |
} |
| ... | ... |
@@ -794,2 +790,3 @@ |
| 794 | 790 |
///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
| 791 |
///By default it is a NullMap. |
|
| 795 | 792 |
typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
| ... | ... |
@@ -828,4 +825,3 @@ |
| 828 | 825 |
///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
| 829 |
/// |
|
| 830 |
typedef NullMap<typename Digraph::Node,int> DistMap; |
|
| 826 |
typedef typename Digraph::template NodeMap<int> DistMap; |
|
| 831 | 827 |
///Instantiates a \ref DistMap. |
| ... | ... |
@@ -835,10 +831,12 @@ |
| 835 | 831 |
///the \ref DistMap |
| 836 |
#ifdef DOXYGEN |
|
| 837 | 832 |
static DistMap *createDistMap(const Digraph &g) |
| 838 |
#else |
|
| 839 |
static DistMap *createDistMap(const Digraph &) |
|
| 840 |
#endif |
|
| 841 | 833 |
{
|
| 842 |
return new DistMap(); |
|
| 834 |
return new DistMap(g); |
|
| 843 | 835 |
} |
| 836 |
|
|
| 837 |
///The type of the DFS paths. |
|
| 838 |
|
|
| 839 |
///The type of the DFS paths. |
|
| 840 |
///It must meet the \ref concepts::Path "Path" concept. |
|
| 841 |
typedef lemon::Path<Digraph> Path; |
|
| 844 | 842 |
}; |
| ... | ... |
@@ -872,4 +870,6 @@ |
| 872 | 870 |
void *_dist; |
| 873 |
//Pointer to the source node. |
|
| 874 |
Node _source; |
|
| 871 |
//Pointer to the DFS path to the target node. |
|
| 872 |
void *_path; |
|
| 873 |
//Pointer to the distance of the target node. |
|
| 874 |
int *_di; |
|
| 875 | 875 |
|
| ... | ... |
@@ -879,5 +879,5 @@ |
| 879 | 879 |
/// This constructor does not require parameters, therefore it initiates |
| 880 |
/// all of the attributes to |
|
| 880 |
/// all of the attributes to \c 0. |
|
| 881 | 881 |
DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), |
| 882 |
_dist(0), |
|
| 882 |
_dist(0), _path(0), _di(0) {}
|
|
| 883 | 883 |
|
| ... | ... |
@@ -885,10 +885,8 @@ |
| 885 | 885 |
|
| 886 |
/// This constructor requires some parameters, |
|
| 887 |
/// listed in the parameters list. |
|
| 888 |
/// |
|
| 886 |
/// This constructor requires one parameter, |
|
| 887 |
/// others are initiated to \c 0. |
|
| 889 | 888 |
/// \param g The digraph the algorithm runs on. |
| 890 |
/// \param s The source node. |
|
| 891 |
DfsWizardBase(const GR &g, Node s=INVALID) : |
|
| 889 |
DfsWizardBase(const GR &g) : |
|
| 892 | 890 |
_g(reinterpret_cast<void*>(const_cast<GR*>(&g))), |
| 893 |
_reached(0), _processed(0), _pred(0), _dist(0), |
|
| 891 |
_reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
|
|
| 894 | 892 |
|
| ... | ... |
@@ -896,23 +894,11 @@ |
| 896 | 894 |
|
| 897 |
/// Auxiliary class for the function |
|
| 895 |
/// Auxiliary class for the function-type interface of DFS algorithm. |
|
| 898 | 896 |
|
| 899 |
/// This auxiliary class is created to implement the function type |
|
| 900 |
/// interface of \ref Dfs algorithm. It uses the functions and features |
|
| 901 |
/// of the plain \ref Dfs, but it is much simpler to use it. |
|
| 902 |
/// It should only be used through the \ref dfs() function, which makes |
|
| 903 |
/// |
|
| 897 |
/// This auxiliary class is created to implement the |
|
| 898 |
/// \ref dfs() "function-type interface" of \ref Dfs algorithm. |
|
| 899 |
/// It does not have own \ref run() method, it uses the functions |
|
| 900 |
/// and features of the plain \ref Dfs. |
|
| 904 | 901 |
/// |
| 905 |
/// Simplicity means that the way to change the types defined |
|
| 906 |
/// in the traits class is based on functions that returns the new class |
|
| 907 |
/// and not on templatable built-in classes. |
|
| 908 |
/// When using the plain \ref Dfs |
|
| 909 |
/// the new class with the modified type comes from |
|
| 910 |
/// the original class by using the :: |
|
| 911 |
/// operator. In the case of \ref DfsWizard only |
|
| 912 |
/// a function have to be called, and it will |
|
| 913 |
/// return the needed class. |
|
| 914 |
/// |
|
| 915 |
/// It does not have own \ref run() method. When its \ref run() method |
|
| 916 |
/// is called, it initiates a plain \ref Dfs object, and calls the |
|
| 917 |
/// \ref |
|
| 902 |
/// This class should only be used through the \ref dfs() function, |
|
| 903 |
/// which makes it easier to use the algorithm. |
|
| 918 | 904 |
template<class TR> |
| ... | ... |
@@ -931,3 +917,3 @@ |
| 931 | 917 |
///\brief The type of the map that stores the predecessor |
| 932 |
///arcs of the |
|
| 918 |
///arcs of the DFS paths. |
|
| 933 | 919 |
typedef typename TR::PredMap PredMap; |
| ... | ... |
@@ -939,2 +925,4 @@ |
| 939 | 925 |
typedef typename TR::ProcessedMap ProcessedMap; |
| 926 |
///The type of the DFS paths |
|
| 927 |
typedef typename TR::Path Path; |
|
| 940 | 928 |
|
| ... | ... |
@@ -949,4 +937,5 @@ |
| 949 | 937 |
/// These parameters will be the default values for the traits class. |
| 950 |
DfsWizard(const Digraph &g, Node s=INVALID) : |
|
| 951 |
TR(g,s) {}
|
|
| 938 |
/// \param g The digraph the algorithm runs on. |
|
| 939 |
DfsWizard(const Digraph &g) : |
|
| 940 |
TR(g) {}
|
|
| 952 | 941 |
|
| ... | ... |
@@ -957,10 +946,13 @@ |
| 957 | 946 |
|
| 958 |
///Runs DFS algorithm from |
|
| 947 |
///Runs DFS algorithm from the given source node. |
|
| 959 | 948 |
|
| 960 |
///Runs DFS algorithm from a source node. |
|
| 961 |
///The node can be given with the \ref source() function. |
|
| 962 |
|
|
| 949 |
///This method runs DFS algorithm from node \c s |
|
| 950 |
///in order to compute the DFS path to each node. |
|
| 951 |
void run(Node s) |
|
| 963 | 952 |
{
|
| 964 |
if(Base::_source==INVALID) throw UninitializedParameter(); |
|
| 965 | 953 |
Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); |
| 954 |
if (Base::_pred) |
|
| 955 |
alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); |
|
| 956 |
if (Base::_dist) |
|
| 957 |
alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
|
| 966 | 958 |
if(Base::_reached) |
| ... | ... |
@@ -969,2 +961,19 @@ |
| 969 | 961 |
alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); |
| 962 |
if (s!=INVALID) |
|
| 963 |
alg.run(s); |
|
| 964 |
else |
|
| 965 |
alg.run(); |
|
| 966 |
} |
|
| 967 |
|
|
| 968 |
///Finds the DFS path between \c s and \c t. |
|
| 969 |
|
|
| 970 |
///This method runs DFS algorithm from node \c s |
|
| 971 |
///in order to compute the DFS path to node \c t |
|
| 972 |
///(it stops searching when \c t is processed). |
|
| 973 |
/// |
|
| 974 |
///\return \c true if \c t is reachable form \c s. |
|
| 975 |
bool run(Node s, Node t) |
|
| 976 |
{
|
|
| 977 |
if (s==INVALID || t==INVALID) throw UninitializedParameter(); |
|
| 978 |
Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); |
|
| 970 | 979 |
if(Base::_pred) |
| ... | ... |
@@ -973,23 +982,21 @@ |
| 973 | 982 |
alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
| 974 |
|
|
| 983 |
if (Base::_reached) |
|
| 984 |
alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); |
|
| 985 |
if (Base::_processed) |
|
| 986 |
alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); |
|
| 987 |
alg.run(s,t); |
|
| 988 |
if (Base::_path) |
|
| 989 |
*reinterpret_cast<Path*>(Base::_path) = alg.path(t); |
|
| 990 |
if (Base::_di) |
|
| 991 |
*Base::_di = alg.dist(t); |
|
| 992 |
return alg.reached(t); |
|
| 975 | 993 |
} |
| 976 | 994 |
|
| 977 |
///Runs DFS algorithm |
|
| 995 |
///Runs DFS algorithm to visit all nodes in the digraph. |
|
| 978 | 996 |
|
| 979 |
///Runs DFS algorithm from the given node. |
|
| 980 |
///\param s is the given source. |
|
| 981 |
|
|
| 997 |
///This method runs DFS algorithm in order to compute |
|
| 998 |
///the DFS path to each node. |
|
| 999 |
void run() |
|
| 982 | 1000 |
{
|
| 983 |
Base::_source=s; |
|
| 984 |
run(); |
|
| 985 |
} |
|
| 986 |
|
|
| 987 |
/// Sets the source node, from which the Dfs algorithm runs. |
|
| 988 |
|
|
| 989 |
/// Sets the source node, from which the Dfs algorithm runs. |
|
| 990 |
/// \param s is the source node. |
|
| 991 |
DfsWizard<TR> &source(Node s) |
|
| 992 |
{
|
|
| 993 |
Base::_source=s; |
|
| 994 |
return *this; |
|
| 1001 |
run(INVALID); |
|
| 995 | 1002 |
} |
| ... | ... |
@@ -1002,6 +1009,6 @@ |
| 1002 | 1009 |
}; |
| 1003 |
///\brief \ref named- |
|
| 1010 |
///\brief \ref named-func-param "Named parameter" |
|
| 1004 | 1011 |
///for setting \ref PredMap object. |
| 1005 | 1012 |
/// |
| 1006 |
///\ref named- |
|
| 1013 |
///\ref named-func-param "Named parameter" |
|
| 1007 | 1014 |
///for setting \ref PredMap object. |
| ... | ... |
@@ -1020,6 +1027,6 @@ |
| 1020 | 1027 |
}; |
| 1021 |
///\brief \ref named- |
|
| 1028 |
///\brief \ref named-func-param "Named parameter" |
|
| 1022 | 1029 |
///for setting \ref ReachedMap object. |
| 1023 | 1030 |
/// |
| 1024 |
/// \ref named- |
|
| 1031 |
/// \ref named-func-param "Named parameter" |
|
| 1025 | 1032 |
///for setting \ref ReachedMap object. |
| ... | ... |
@@ -1033,2 +1040,20 @@ |
| 1033 | 1040 |
template<class T> |
| 1041 |
struct SetDistMapBase : public Base {
|
|
| 1042 |
typedef T DistMap; |
|
| 1043 |
static DistMap *createDistMap(const Digraph &) { return 0; };
|
|
| 1044 |
SetDistMapBase(const TR &b) : TR(b) {}
|
|
| 1045 |
}; |
|
| 1046 |
///\brief \ref named-func-param "Named parameter" |
|
| 1047 |
///for setting \ref DistMap object. |
|
| 1048 |
/// |
|
| 1049 |
/// \ref named-func-param "Named parameter" |
|
| 1050 |
///for setting \ref DistMap object. |
|
| 1051 |
template<class T> |
|
| 1052 |
DfsWizard<SetDistMapBase<T> > distMap(const T &t) |
|
| 1053 |
{
|
|
| 1054 |
Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
|
| 1055 |
return DfsWizard<SetDistMapBase<T> >(*this); |
|
| 1056 |
} |
|
| 1057 |
|
|
| 1058 |
template<class T> |
|
| 1034 | 1059 |
struct SetProcessedMapBase : public Base {
|
| ... | ... |
@@ -1038,6 +1063,6 @@ |
| 1038 | 1063 |
}; |
| 1039 |
///\brief \ref named- |
|
| 1064 |
///\brief \ref named-func-param "Named parameter" |
|
| 1040 | 1065 |
///for setting \ref ProcessedMap object. |
| 1041 | 1066 |
/// |
| 1042 |
/// \ref named- |
|
| 1067 |
/// \ref named-func-param "Named parameter" |
|
| 1043 | 1068 |
///for setting \ref ProcessedMap object. |
| ... | ... |
@@ -1051,17 +1076,27 @@ |
| 1051 | 1076 |
template<class T> |
| 1052 |
struct SetDistMapBase : public Base {
|
|
| 1053 |
typedef T DistMap; |
|
| 1054 |
static DistMap *createDistMap(const Digraph &) { return 0; };
|
|
| 1055 |
SetDistMapBase(const TR &b) : TR(b) {}
|
|
| 1077 |
struct SetPathBase : public Base {
|
|
| 1078 |
typedef T Path; |
|
| 1079 |
SetPathBase(const TR &b) : TR(b) {}
|
|
| 1056 | 1080 |
}; |
| 1057 |
///\brief \ref named-templ-param "Named parameter" |
|
| 1058 |
///for setting \ref DistMap object. |
|
| 1081 |
///\brief \ref named-func-param "Named parameter" |
|
| 1082 |
///for getting the DFS path to the target node. |
|
| 1059 | 1083 |
/// |
| 1060 |
///\ref named-templ-param "Named parameter" |
|
| 1061 |
///for setting \ref DistMap object. |
|
| 1084 |
///\ref named-func-param "Named parameter" |
|
| 1085 |
///for getting the DFS path to the target node. |
|
| 1062 | 1086 |
template<class T> |
| 1063 |
DfsWizard< |
|
| 1087 |
DfsWizard<SetPathBase<T> > path(const T &t) |
|
| 1064 | 1088 |
{
|
| 1065 |
Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
|
| 1066 |
return DfsWizard<SetDistMapBase<T> >(*this); |
|
| 1089 |
Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t)); |
|
| 1090 |
return DfsWizard<SetPathBase<T> >(*this); |
|
| 1091 |
} |
|
| 1092 |
|
|
| 1093 |
///\brief \ref named-func-param "Named parameter" |
|
| 1094 |
///for getting the distance of the target node. |
|
| 1095 |
/// |
|
| 1096 |
///\ref named-func-param "Named parameter" |
|
| 1097 |
///for getting the distance of the target node. |
|
| 1098 |
DfsWizard dist(const int &d) |
|
| 1099 |
{
|
|
| 1100 |
Base::_di=const_cast<int*>(&d); |
|
| 1101 |
return *this; |
|
| 1067 | 1102 |
} |
| ... | ... |
@@ -1070,15 +1105,18 @@ |
| 1070 | 1105 |
|
| 1071 |
///Function |
|
| 1106 |
///Function-type interface for DFS algorithm. |
|
| 1072 | 1107 |
|
| 1073 | 1108 |
///\ingroup search |
| 1074 |
///Function |
|
| 1109 |
///Function-type interface for DFS algorithm. |
|
| 1075 | 1110 |
/// |
| 1076 |
///This function also has several |
|
| 1077 |
///\ref named-templ-func-param "named parameters", |
|
| 1111 |
///This function also has several \ref named-func-param "named parameters", |
|
| 1078 | 1112 |
///they are declared as the members of class \ref DfsWizard. |
| 1079 |
///The following |
|
| 1080 |
///example shows how to use these parameters. |
|
| 1113 |
///The following examples show how to use these parameters. |
|
| 1081 | 1114 |
///\code |
| 1082 |
/// |
|
| 1115 |
/// // Compute the DFS tree |
|
| 1116 |
/// dfs(g).predMap(preds).distMap(dists).run(s); |
|
| 1117 |
/// |
|
| 1118 |
/// // Compute the DFS path from s to t |
|
| 1119 |
/// bool reached = dfs(g).path(p).dist(d).run(s,t); |
|
| 1083 | 1120 |
///\endcode |
| 1121 |
|
|
| 1084 | 1122 |
///\warning Don't forget to put the \ref DfsWizard::run() "run()" |
| ... | ... |
@@ -1089,5 +1127,5 @@ |
| 1089 | 1127 |
DfsWizard<DfsWizardBase<GR> > |
| 1090 |
dfs(const GR & |
|
| 1128 |
dfs(const GR &digraph) |
|
| 1091 | 1129 |
{
|
| 1092 |
return DfsWizard<DfsWizardBase<GR> >( |
|
| 1130 |
return DfsWizard<DfsWizardBase<GR> >(digraph); |
|
| 1093 | 1131 |
} |
| ... | ... |
@@ -32,2 +32,3 @@ |
| 32 | 32 |
#include <lemon/maps.h> |
| 33 |
#include <lemon/path.h> |
|
| 33 | 34 |
|
| ... | ... |
@@ -198,3 +199,3 @@ |
| 198 | 199 |
/// |
| 199 |
///There is also a \ref dijkstra() "function |
|
| 200 |
///There is also a \ref dijkstra() "function-type interface" for the |
|
| 200 | 201 |
///%Dijkstra algorithm, which is convenient in the simplier cases and |
| ... | ... |
@@ -984,3 +985,3 @@ |
| 984 | 985 |
///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
| 985 |
typedef |
|
| 986 |
typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
|
| 986 | 987 |
///Instantiates a \ref PredMap. |
| ... | ... |
@@ -990,9 +991,5 @@ |
| 990 | 991 |
///\ref PredMap. |
| 991 |
#ifdef DOXYGEN |
|
| 992 | 992 |
static PredMap *createPredMap(const Digraph &g) |
| 993 |
#else |
|
| 994 |
static PredMap *createPredMap(const Digraph &) |
|
| 995 |
#endif |
|
| 996 | 993 |
{
|
| 997 |
return new PredMap(); |
|
| 994 |
return new PredMap(g); |
|
| 998 | 995 |
} |
| ... | ... |
@@ -1023,3 +1020,3 @@ |
| 1023 | 1020 |
///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
| 1024 |
typedef |
|
| 1021 |
typedef typename Digraph::template NodeMap<typename LM::Value> DistMap; |
|
| 1025 | 1022 |
///Instantiates a \ref DistMap. |
| ... | ... |
@@ -1029,10 +1026,12 @@ |
| 1029 | 1026 |
///the \ref DistMap |
| 1030 |
#ifdef DOXYGEN |
|
| 1031 | 1027 |
static DistMap *createDistMap(const Digraph &g) |
| 1032 |
#else |
|
| 1033 |
static DistMap *createDistMap(const Digraph &) |
|
| 1034 |
#endif |
|
| 1035 | 1028 |
{
|
| 1036 |
return new DistMap(); |
|
| 1029 |
return new DistMap(g); |
|
| 1037 | 1030 |
} |
| 1031 |
|
|
| 1032 |
///The type of the shortest paths. |
|
| 1033 |
|
|
| 1034 |
///The type of the shortest paths. |
|
| 1035 |
///It must meet the \ref concepts::Path "Path" concept. |
|
| 1036 |
typedef lemon::Path<Digraph> Path; |
|
| 1038 | 1037 |
}; |
| ... | ... |
@@ -1057,3 +1056,3 @@ |
| 1057 | 1056 |
void *_g; |
| 1058 |
//Pointer to the length map |
|
| 1057 |
//Pointer to the length map. |
|
| 1059 | 1058 |
void *_length; |
| ... | ... |
@@ -1065,4 +1064,6 @@ |
| 1065 | 1064 |
void *_dist; |
| 1066 |
//Pointer to the source node. |
|
| 1067 |
Node _source; |
|
| 1065 |
//Pointer to the shortest path to the target node. |
|
| 1066 |
void *_path; |
|
| 1067 |
//Pointer to the distance of the target node. |
|
| 1068 |
void *_di; |
|
| 1068 | 1069 |
|
| ... | ... |
@@ -1072,5 +1073,5 @@ |
| 1072 | 1073 |
/// This constructor does not require parameters, therefore it initiates |
| 1073 |
/// all of the attributes to |
|
| 1074 |
/// all of the attributes to \c 0. |
|
| 1074 | 1075 |
DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0), |
| 1075 |
_dist(0), |
|
| 1076 |
_dist(0), _path(0), _di(0) {}
|
|
| 1076 | 1077 |
|
| ... | ... |
@@ -1078,12 +1079,10 @@ |
| 1078 | 1079 |
|
| 1079 |
/// This constructor requires some parameters, |
|
| 1080 |
/// listed in the parameters list. |
|
| 1081 |
/// |
|
| 1080 |
/// This constructor requires two parameters, |
|
| 1081 |
/// others are initiated to \c 0. |
|
| 1082 | 1082 |
/// \param g The digraph the algorithm runs on. |
| 1083 | 1083 |
/// \param l The length map. |
| 1084 |
/// \param s The source node. |
|
| 1085 |
DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : |
|
| 1084 |
DijkstraWizardBase(const GR &g,const LM &l) : |
|
| 1086 | 1085 |
_g(reinterpret_cast<void*>(const_cast<GR*>(&g))), |
| 1087 | 1086 |
_length(reinterpret_cast<void*>(const_cast<LM*>(&l))), |
| 1088 |
_processed(0), _pred(0), _dist(0), |
|
| 1087 |
_processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
|
|
| 1089 | 1088 |
|
| ... | ... |
@@ -1091,23 +1090,11 @@ |
| 1091 | 1090 |
|
| 1092 |
/// Auxiliary class for the function |
|
| 1091 |
/// Auxiliary class for the function-type interface of Dijkstra algorithm. |
|
| 1093 | 1092 |
|
| 1094 |
/// This auxiliary class is created to implement the function type |
|
| 1095 |
/// interface of \ref Dijkstra algorithm. It uses the functions and features |
|
| 1096 |
/// of the plain \ref Dijkstra, but it is much simpler to use it. |
|
| 1097 |
/// It should only be used through the \ref dijkstra() function, which makes |
|
| 1098 |
/// |
|
| 1093 |
/// This auxiliary class is created to implement the |
|
| 1094 |
/// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm. |
|
| 1095 |
/// It does not have own \ref run() method, it uses the functions |
|
| 1096 |
/// and features of the plain \ref Dijkstra. |
|
| 1099 | 1097 |
/// |
| 1100 |
/// Simplicity means that the way to change the types defined |
|
| 1101 |
/// in the traits class is based on functions that returns the new class |
|
| 1102 |
/// and not on templatable built-in classes. |
|
| 1103 |
/// When using the plain \ref Dijkstra |
|
| 1104 |
/// the new class with the modified type comes from |
|
| 1105 |
/// the original class by using the :: |
|
| 1106 |
/// operator. In the case of \ref DijkstraWizard only |
|
| 1107 |
/// a function have to be called, and it will |
|
| 1108 |
/// return the needed class. |
|
| 1109 |
/// |
|
| 1110 |
/// It does not have own \ref run() method. When its \ref run() method |
|
| 1111 |
/// is called, it initiates a plain \ref Dijkstra object, and calls the |
|
| 1112 |
/// \ref |
|
| 1098 |
/// This class should only be used through the \ref dijkstra() function, |
|
| 1099 |
/// which makes it easier to use the algorithm. |
|
| 1113 | 1100 |
template<class TR> |
| ... | ... |
@@ -1136,2 +1123,4 @@ |
| 1136 | 1123 |
typedef typename TR::ProcessedMap ProcessedMap; |
| 1124 |
///The type of the shortest paths |
|
| 1125 |
typedef typename TR::Path Path; |
|
| 1137 | 1126 |
///The heap type used by the dijkstra algorithm. |
| ... | ... |
@@ -1148,4 +1137,6 @@ |
| 1148 | 1137 |
/// These parameters will be the default values for the traits class. |
| 1149 |
DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) : |
|
| 1150 |
TR(g,l,s) {}
|
|
| 1138 |
/// \param g The digraph the algorithm runs on. |
|
| 1139 |
/// \param l The length map. |
|
| 1140 |
DijkstraWizard(const Digraph &g, const LengthMap &l) : |
|
| 1141 |
TR(g,l) {}
|
|
| 1151 | 1142 |
|
| ... | ... |
@@ -1156,39 +1147,46 @@ |
| 1156 | 1147 |
|
| 1157 |
///Runs Dijkstra algorithm from |
|
| 1148 |
///Runs Dijkstra algorithm from the given source node. |
|
| 1158 | 1149 |
|
| 1159 |
///Runs Dijkstra algorithm from a source node. |
|
| 1160 |
///The node can be given with the \ref source() function. |
|
| 1161 |
|
|
| 1150 |
///This method runs %Dijkstra algorithm from the given source node |
|
| 1151 |
///in order to compute the shortest path to each node. |
|
| 1152 |
void run(Node s) |
|
| 1162 | 1153 |
{
|
| 1163 |
if |
|
| 1154 |
if (s==INVALID) throw UninitializedParameter(); |
|
| 1164 | 1155 |
Dijkstra<Digraph,LengthMap,TR> |
| 1165 |
|
|
| 1156 |
dijk(*reinterpret_cast<const Digraph*>(Base::_g), |
|
| 1166 | 1157 |
*reinterpret_cast<const LengthMap*>(Base::_length)); |
| 1158 |
if (Base::_pred) |
|
| 1159 |
dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); |
|
| 1160 |
if (Base::_dist) |
|
| 1161 |
dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
|
| 1167 | 1162 |
if(Base::_processed) |
| 1168 |
dij.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); |
|
| 1169 |
if(Base::_pred) |
|
| 1170 |
dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); |
|
| 1171 |
if(Base::_dist) |
|
| 1172 |
dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
|
| 1173 |
dij.run(Base::_source); |
|
| 1163 |
dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); |
|
| 1164 |
dijk.run(s); |
|
| 1174 | 1165 |
} |
| 1175 | 1166 |
|
| 1176 |
/// |
|
| 1167 |
///Finds the shortest path between \c s and \c t. |
|
| 1177 | 1168 |
|
| 1178 |
///Runs Dijkstra algorithm from the given node. |
|
| 1179 |
///\param s is the given source. |
|
| 1180 |
|
|
| 1169 |
///This method runs the %Dijkstra algorithm from node \c s |
|
| 1170 |
///in order to compute the shortest path to node \c t |
|
| 1171 |
///(it stops searching when \c t is processed). |
|
| 1172 |
/// |
|
| 1173 |
///\return \c true if \c t is reachable form \c s. |
|
| 1174 |
bool run(Node s, Node t) |
|
| 1181 | 1175 |
{
|
| 1182 |
Base::_source=s; |
|
| 1183 |
run(); |
|
| 1184 |
} |
|
| 1185 |
|
|
| 1186 |
/// Sets the source node, from which the Dijkstra algorithm runs. |
|
| 1187 |
|
|
| 1188 |
/// Sets the source node, from which the Dijkstra algorithm runs. |
|
| 1189 |
/// \param s is the source node. |
|
| 1190 |
DijkstraWizard<TR> &source(Node s) |
|
| 1191 |
{
|
|
| 1192 |
Base::_source=s; |
|
| 1193 |
return *this; |
|
| 1176 |
if (s==INVALID || t==INVALID) throw UninitializedParameter(); |
|
| 1177 |
Dijkstra<Digraph,LengthMap,TR> |
|
| 1178 |
dijk(*reinterpret_cast<const Digraph*>(Base::_g), |
|
| 1179 |
*reinterpret_cast<const LengthMap*>(Base::_length)); |
|
| 1180 |
if (Base::_pred) |
|
| 1181 |
dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); |
|
| 1182 |
if (Base::_dist) |
|
| 1183 |
dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
|
| 1184 |
if (Base::_processed) |
|
| 1185 |
dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); |
|
| 1186 |
dijk.run(s,t); |
|
| 1187 |
if (Base::_path) |
|
| 1188 |
*reinterpret_cast<Path*>(Base::_path) = dijk.path(t); |
|
| 1189 |
if (Base::_di) |
|
| 1190 |
*reinterpret_cast<Value*>(Base::_di) = dijk.dist(t); |
|
| 1191 |
return dijk.reached(t); |
|
| 1194 | 1192 |
} |
| ... | ... |
@@ -1201,6 +1199,6 @@ |
| 1201 | 1199 |
}; |
| 1202 |
///\brief \ref named- |
|
| 1200 |
///\brief \ref named-func-param "Named parameter" |
|
| 1203 | 1201 |
///for setting \ref PredMap object. |
| 1204 | 1202 |
/// |
| 1205 |
///\ref named- |
|
| 1203 |
///\ref named-func-param "Named parameter" |
|
| 1206 | 1204 |
///for setting \ref PredMap object. |
| ... | ... |
@@ -1214,2 +1212,20 @@ |
| 1214 | 1212 |
template<class T> |
| 1213 |
struct SetDistMapBase : public Base {
|
|
| 1214 |
typedef T DistMap; |
|
| 1215 |
static DistMap *createDistMap(const Digraph &) { return 0; };
|
|
| 1216 |
SetDistMapBase(const TR &b) : TR(b) {}
|
|
| 1217 |
}; |
|
| 1218 |
///\brief \ref named-func-param "Named parameter" |
|
| 1219 |
///for setting \ref DistMap object. |
|
| 1220 |
/// |
|
| 1221 |
///\ref named-func-param "Named parameter" |
|
| 1222 |
///for setting \ref DistMap object. |
|
| 1223 |
template<class T> |
|
| 1224 |
DijkstraWizard<SetDistMapBase<T> > distMap(const T &t) |
|
| 1225 |
{
|
|
| 1226 |
Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
|
| 1227 |
return DijkstraWizard<SetDistMapBase<T> >(*this); |
|
| 1228 |
} |
|
| 1229 |
|
|
| 1230 |
template<class T> |
|
| 1215 | 1231 |
struct SetProcessedMapBase : public Base {
|
| ... | ... |
@@ -1219,6 +1235,6 @@ |
| 1219 | 1235 |
}; |
| 1220 |
///\brief \ref named- |
|
| 1236 |
///\brief \ref named-func-param "Named parameter" |
|
| 1221 | 1237 |
///for setting \ref ProcessedMap object. |
| 1222 | 1238 |
/// |
| 1223 |
/// \ref named- |
|
| 1239 |
/// \ref named-func-param "Named parameter" |
|
| 1224 | 1240 |
///for setting \ref ProcessedMap object. |
| ... | ... |
@@ -1232,17 +1248,27 @@ |
| 1232 | 1248 |
template<class T> |
| 1233 |
struct SetDistMapBase : public Base {
|
|
| 1234 |
typedef T DistMap; |
|
| 1235 |
static DistMap *createDistMap(const Digraph &) { return 0; };
|
|
| 1236 |
SetDistMapBase(const TR &b) : TR(b) {}
|
|
| 1249 |
struct SetPathBase : public Base {
|
|
| 1250 |
typedef T Path; |
|
| 1251 |
SetPathBase(const TR &b) : TR(b) {}
|
|
| 1237 | 1252 |
}; |
| 1238 |
///\brief \ref named-templ-param "Named parameter" |
|
| 1239 |
///for setting \ref DistMap object. |
|
| 1253 |
///\brief \ref named-func-param "Named parameter" |
|
| 1254 |
///for getting the shortest path to the target node. |
|
| 1240 | 1255 |
/// |
| 1241 |
///\ref named-templ-param "Named parameter" |
|
| 1242 |
///for setting \ref DistMap object. |
|
| 1256 |
///\ref named-func-param "Named parameter" |
|
| 1257 |
///for getting the shortest path to the target node. |
|
| 1243 | 1258 |
template<class T> |
| 1244 |
DijkstraWizard< |
|
| 1259 |
DijkstraWizard<SetPathBase<T> > path(const T &t) |
|
| 1245 | 1260 |
{
|
| 1246 |
Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
|
| 1247 |
return DijkstraWizard<SetDistMapBase<T> >(*this); |
|
| 1261 |
Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t)); |
|
| 1262 |
return DijkstraWizard<SetPathBase<T> >(*this); |
|
| 1263 |
} |
|
| 1264 |
|
|
| 1265 |
///\brief \ref named-func-param "Named parameter" |
|
| 1266 |
///for getting the distance of the target node. |
|
| 1267 |
/// |
|
| 1268 |
///\ref named-func-param "Named parameter" |
|
| 1269 |
///for getting the distance of the target node. |
|
| 1270 |
DijkstraWizard dist(const Value &d) |
|
| 1271 |
{
|
|
| 1272 |
Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d)); |
|
| 1273 |
return *this; |
|
| 1248 | 1274 |
} |
| ... | ... |
@@ -1251,14 +1277,16 @@ |
| 1251 | 1277 |
|
| 1252 |
///Function |
|
| 1278 |
///Function-type interface for Dijkstra algorithm. |
|
| 1253 | 1279 |
|
| 1254 | 1280 |
/// \ingroup shortest_path |
| 1255 |
///Function |
|
| 1281 |
///Function-type interface for Dijkstra algorithm. |
|
| 1256 | 1282 |
/// |
| 1257 |
///This function also has several |
|
| 1258 |
///\ref named-templ-func-param "named parameters", |
|
| 1283 |
///This function also has several \ref named-func-param "named parameters", |
|
| 1259 | 1284 |
///they are declared as the members of class \ref DijkstraWizard. |
| 1260 |
///The following |
|
| 1261 |
///example shows how to use these parameters. |
|
| 1285 |
///The following examples show how to use these parameters. |
|
| 1262 | 1286 |
///\code |
| 1263 |
/// |
|
| 1287 |
/// // Compute shortest path from node s to each node |
|
| 1288 |
/// dijkstra(g,length).predMap(preds).distMap(dists).run(s); |
|
| 1289 |
/// |
|
| 1290 |
/// // Compute shortest path from s to t |
|
| 1291 |
/// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t); |
|
| 1264 | 1292 |
///\endcode |
| ... | ... |
@@ -1270,5 +1298,5 @@ |
| 1270 | 1298 |
DijkstraWizard<DijkstraWizardBase<GR,LM> > |
| 1271 |
dijkstra(const GR & |
|
| 1299 |
dijkstra(const GR &digraph, const LM &length) |
|
| 1272 | 1300 |
{
|
| 1273 |
return DijkstraWizard<DijkstraWizardBase<GR,LM> >( |
|
| 1301 |
return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length); |
|
| 1274 | 1302 |
} |
| ... | ... |
@@ -64,3 +64,2 @@ |
| 64 | 64 |
BType::PredMap p(G); |
| 65 |
// BType::PredNodeMap pn(G); |
|
| 66 | 65 |
|
| ... | ... |
@@ -74,5 +73,3 @@ |
| 74 | 73 |
d = bfs_test.distMap(); |
| 75 |
|
|
| 76 | 74 |
p = bfs_test.predMap(); |
| 77 |
// pn = bfs_test.predNodeMap(); |
|
| 78 | 75 |
b = bfs_test.reached(n); |
| ... | ... |
@@ -90,7 +87,9 @@ |
| 90 | 87 |
Digraph g; |
| 91 |
bfs(g,Node()).run(); |
|
| 92 |
bfs(g).source(Node()).run(); |
|
| 88 |
bool b; |
|
| 89 |
bfs(g).run(Node()); |
|
| 90 |
b=bfs(g).run(Node(),Node()); |
|
| 91 |
bfs(g).run(); |
|
| 93 | 92 |
bfs(g) |
| 94 |
.predMap(concepts::WriteMap<Node,Arc>()) |
|
| 95 |
.distMap(concepts::WriteMap<Node,VType>()) |
|
| 93 |
.predMap(concepts::ReadWriteMap<Node,Arc>()) |
|
| 94 |
.distMap(concepts::ReadWriteMap<Node,VType>()) |
|
| 96 | 95 |
.reachedMap(concepts::ReadWriteMap<Node,bool>()) |
| ... | ... |
@@ -98,2 +97,16 @@ |
| 98 | 97 |
.run(Node()); |
| 98 |
b=bfs(g) |
|
| 99 |
.predMap(concepts::ReadWriteMap<Node,Arc>()) |
|
| 100 |
.distMap(concepts::ReadWriteMap<Node,VType>()) |
|
| 101 |
.reachedMap(concepts::ReadWriteMap<Node,bool>()) |
|
| 102 |
.processedMap(concepts::WriteMap<Node,bool>()) |
|
| 103 |
.path(concepts::Path<Digraph>()) |
|
| 104 |
.dist(VType()) |
|
| 105 |
.run(Node(),Node()); |
|
| 106 |
bfs(g) |
|
| 107 |
.predMap(concepts::ReadWriteMap<Node,Arc>()) |
|
| 108 |
.distMap(concepts::ReadWriteMap<Node,VType>()) |
|
| 109 |
.reachedMap(concepts::ReadWriteMap<Node,bool>()) |
|
| 110 |
.processedMap(concepts::WriteMap<Node,bool>()) |
|
| 111 |
.run(); |
|
| 99 | 112 |
} |
| ... | ... |
@@ -116,3 +129,3 @@ |
| 116 | 129 |
|
| 117 |
check(bfs_test.dist(t)==2,"Bfs found a wrong path." |
|
| 130 |
check(bfs_test.dist(t)==2,"Bfs found a wrong path."); |
|
| 118 | 131 |
|
| ... | ... |
@@ -130,3 +143,3 @@ |
| 130 | 143 |
(bfs_test.dist(v) <= bfs_test.dist(u)+1), |
| 131 |
"Wrong output." << G.id(v) |
|
| 144 |
"Wrong output. " << G.id(u) << "->" << G.id(v)); |
|
| 132 | 145 |
} |
| ... | ... |
@@ -142,4 +155,3 @@ |
| 142 | 155 |
"Wrong distance. Difference: " |
| 143 |
<< std::abs(bfs_test.dist(v) - bfs_test.dist(u) |
|
| 144 |
- 1)); |
|
| 156 |
<< std::abs(bfs_test.dist(v) - bfs_test.dist(u) - 1)); |
|
| 145 | 157 |
} |
| ... | ... |
@@ -147,2 +159,7 @@ |
| 147 | 159 |
} |
| 160 |
|
|
| 161 |
{
|
|
| 162 |
NullMap<Node,Arc> myPredMap; |
|
| 163 |
bfs(G).predMap(myPredMap).run(s); |
|
| 164 |
} |
|
| 148 | 165 |
} |
| ... | ... |
@@ -22,3 +22,2 @@ |
| 22 | 22 |
#include <lemon/lgf_reader.h> |
| 23 |
|
|
| 24 | 23 |
#include <lemon/dfs.h> |
| ... | ... |
@@ -90,7 +89,9 @@ |
| 90 | 89 |
Digraph g; |
| 91 |
dfs(g,Node()).run(); |
|
| 92 |
dfs(g).source(Node()).run(); |
|
| 90 |
bool b; |
|
| 91 |
dfs(g).run(Node()); |
|
| 92 |
b=dfs(g).run(Node(),Node()); |
|
| 93 |
dfs(g).run(); |
|
| 93 | 94 |
dfs(g) |
| 94 |
.predMap(concepts::WriteMap<Node,Arc>()) |
|
| 95 |
.distMap(concepts::WriteMap<Node,VType>()) |
|
| 95 |
.predMap(concepts::ReadWriteMap<Node,Arc>()) |
|
| 96 |
.distMap(concepts::ReadWriteMap<Node,VType>()) |
|
| 96 | 97 |
.reachedMap(concepts::ReadWriteMap<Node,bool>()) |
| ... | ... |
@@ -98,2 +99,16 @@ |
| 98 | 99 |
.run(Node()); |
| 100 |
b=dfs(g) |
|
| 101 |
.predMap(concepts::ReadWriteMap<Node,Arc>()) |
|
| 102 |
.distMap(concepts::ReadWriteMap<Node,VType>()) |
|
| 103 |
.reachedMap(concepts::ReadWriteMap<Node,bool>()) |
|
| 104 |
.processedMap(concepts::WriteMap<Node,bool>()) |
|
| 105 |
.path(concepts::Path<Digraph>()) |
|
| 106 |
.dist(VType()) |
|
| 107 |
.run(Node(),Node()); |
|
| 108 |
dfs(g) |
|
| 109 |
.predMap(concepts::ReadWriteMap<Node,Arc>()) |
|
| 110 |
.distMap(concepts::ReadWriteMap<Node,VType>()) |
|
| 111 |
.reachedMap(concepts::ReadWriteMap<Node,bool>()) |
|
| 112 |
.processedMap(concepts::WriteMap<Node,bool>()) |
|
| 113 |
.run(); |
|
| 99 | 114 |
} |
| ... | ... |
@@ -131,3 +146,3 @@ |
| 131 | 146 |
"Wrong distance. (" << dfs_test.dist(u) << "->"
|
| 132 |
<<dfs_test.dist(v) << |
|
| 147 |
<< dfs_test.dist(v) << ")"); |
|
| 133 | 148 |
} |
| ... | ... |
@@ -135,2 +150,7 @@ |
| 135 | 150 |
} |
| 151 |
|
|
| 152 |
{
|
|
| 153 |
NullMap<Node,Arc> myPredMap; |
|
| 154 |
dfs(G).predMap(myPredMap).run(s); |
|
| 155 |
} |
|
| 136 | 156 |
} |
| ... | ... |
@@ -22,3 +22,2 @@ |
| 22 | 22 |
#include <lemon/lgf_reader.h> |
| 23 |
|
|
| 24 | 23 |
#include <lemon/dijkstra.h> |
| ... | ... |
@@ -66,3 +65,2 @@ |
| 66 | 65 |
DType::PredMap p(G); |
| 67 |
// DType::PredNodeMap pn(G); |
|
| 68 | 66 |
LengthMap length; |
| ... | ... |
@@ -78,3 +76,2 @@ |
| 78 | 76 |
p = dijkstra_test.predMap(); |
| 79 |
// pn = dijkstra_test.predNodeMap(); |
|
| 80 | 77 |
b = dijkstra_test.reached(n); |
| ... | ... |
@@ -93,8 +90,17 @@ |
| 93 | 90 |
Digraph g; |
| 94 |
dijkstra(g,LengthMap(),Node()).run(); |
|
| 95 |
dijkstra(g,LengthMap()).source(Node()).run(); |
|
| 91 |
bool b; |
|
| 92 |
dijkstra(g,LengthMap()).run(Node()); |
|
| 93 |
b=dijkstra(g,LengthMap()).run(Node(),Node()); |
|
| 96 | 94 |
dijkstra(g,LengthMap()) |
| 97 |
.predMap(concepts::WriteMap<Node,Arc>()) |
|
| 98 |
.distMap(concepts::WriteMap<Node,VType>()) |
|
| 95 |
.predMap(concepts::ReadWriteMap<Node,Arc>()) |
|
| 96 |
.distMap(concepts::ReadWriteMap<Node,VType>()) |
|
| 97 |
.processedMap(concepts::WriteMap<Node,bool>()) |
|
| 99 | 98 |
.run(Node()); |
| 99 |
b=dijkstra(g,LengthMap()) |
|
| 100 |
.predMap(concepts::ReadWriteMap<Node,Arc>()) |
|
| 101 |
.distMap(concepts::ReadWriteMap<Node,VType>()) |
|
| 102 |
.processedMap(concepts::WriteMap<Node,bool>()) |
|
| 103 |
.path(concepts::Path<Digraph>()) |
|
| 104 |
.dist(VType()) |
|
| 105 |
.run(Node(),Node()); |
|
| 100 | 106 |
} |
| ... | ... |
@@ -124,3 +130,3 @@ |
| 124 | 130 |
Path<Digraph> p = dijkstra_test.path(t); |
| 125 |
check(p.length()==3," |
|
| 131 |
check(p.length()==3,"path() found a wrong path."); |
|
| 126 | 132 |
check(checkPath(G, p),"path() found a wrong path."); |
| ... | ... |
@@ -134,3 +140,3 @@ |
| 134 | 140 |
(dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]), |
| 135 |
"dist(target)-dist(source)-arc_length= |
|
| 141 |
"Wrong output. dist(target)-dist(source)-arc_length=" << |
|
| 136 | 142 |
dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]); |
0 comments (0 inline)