47 /// |
47 /// |
48 ///The type of the map that stores the predecessor |
48 ///The type of the map that stores the predecessor |
49 ///arcs of the shortest paths. |
49 ///arcs of the shortest paths. |
50 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
50 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
52 ///Instantiates a \ref PredMap. |
52 ///Instantiates a PredMap. |
53 |
53 |
54 ///This function instantiates a \ref PredMap. |
54 ///This function instantiates a PredMap. |
55 ///\param g is the digraph, to which we would like to define the |
55 ///\param g is the digraph, to which we would like to define the |
56 ///\ref PredMap. |
56 ///PredMap. |
57 static PredMap *createPredMap(const Digraph &g) |
57 static PredMap *createPredMap(const Digraph &g) |
58 { |
58 { |
59 return new PredMap(g); |
59 return new PredMap(g); |
60 } |
60 } |
61 |
61 |
62 ///The type of the map that indicates which nodes are processed. |
62 ///The type of the map that indicates which nodes are processed. |
63 |
63 |
64 ///The type of the map that indicates which nodes are processed. |
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 meet the \ref concepts::WriteMap "WriteMap" concept. |
66 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
66 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
67 ///Instantiates a \ref ProcessedMap. |
67 ///Instantiates a ProcessedMap. |
68 |
68 |
69 ///This function instantiates a \ref ProcessedMap. |
69 ///This function instantiates a ProcessedMap. |
70 ///\param g is the digraph, to which |
70 ///\param g is the digraph, to which |
71 ///we would like to define the \ref ProcessedMap |
71 ///we would like to define the ProcessedMap |
72 #ifdef DOXYGEN |
72 #ifdef DOXYGEN |
73 static ProcessedMap *createProcessedMap(const Digraph &g) |
73 static ProcessedMap *createProcessedMap(const Digraph &g) |
74 #else |
74 #else |
75 static ProcessedMap *createProcessedMap(const Digraph &) |
75 static ProcessedMap *createProcessedMap(const Digraph &) |
76 #endif |
76 #endif |
81 ///The type of the map that indicates which nodes are reached. |
81 ///The type of the map that indicates which nodes are reached. |
82 |
82 |
83 ///The type of the map that indicates which nodes are reached. |
83 ///The type of the map that indicates which nodes are reached. |
84 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
84 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
85 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
85 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
86 ///Instantiates a \ref ReachedMap. |
86 ///Instantiates a ReachedMap. |
87 |
87 |
88 ///This function instantiates a \ref ReachedMap. |
88 ///This function instantiates a ReachedMap. |
89 ///\param g is the digraph, to which |
89 ///\param g is the digraph, to which |
90 ///we would like to define the \ref ReachedMap. |
90 ///we would like to define the ReachedMap. |
91 static ReachedMap *createReachedMap(const Digraph &g) |
91 static ReachedMap *createReachedMap(const Digraph &g) |
92 { |
92 { |
93 return new ReachedMap(g); |
93 return new ReachedMap(g); |
94 } |
94 } |
95 |
95 |
96 ///The type of the map that stores the distances of the nodes. |
96 ///The type of the map that stores the distances of the nodes. |
97 |
97 |
98 ///The type of the map that stores the distances of the nodes. |
98 ///The type of the map that stores the distances of the nodes. |
99 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
99 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
100 typedef typename Digraph::template NodeMap<int> DistMap; |
100 typedef typename Digraph::template NodeMap<int> DistMap; |
101 ///Instantiates a \ref DistMap. |
101 ///Instantiates a DistMap. |
102 |
102 |
103 ///This function instantiates a \ref DistMap. |
103 ///This function instantiates a DistMap. |
104 ///\param g is the digraph, to which we would like to define the |
104 ///\param g is the digraph, to which we would like to define the |
105 ///\ref DistMap. |
105 ///DistMap. |
106 static DistMap *createDistMap(const Digraph &g) |
106 static DistMap *createDistMap(const Digraph &g) |
107 { |
107 { |
108 return new DistMap(g); |
108 return new DistMap(g); |
109 } |
109 } |
110 }; |
110 }; |
225 LEMON_ASSERT(false, "PredMap is not initialized"); |
225 LEMON_ASSERT(false, "PredMap is not initialized"); |
226 return 0; // ignore warnings |
226 return 0; // ignore warnings |
227 } |
227 } |
228 }; |
228 }; |
229 ///\brief \ref named-templ-param "Named parameter" for setting |
229 ///\brief \ref named-templ-param "Named parameter" for setting |
230 ///\ref PredMap type. |
230 ///PredMap type. |
231 /// |
231 /// |
232 ///\ref named-templ-param "Named parameter" for setting |
232 ///\ref named-templ-param "Named parameter" for setting |
233 ///\ref PredMap type. |
233 ///PredMap type. |
234 template <class T> |
234 template <class T> |
235 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { |
235 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { |
236 typedef Bfs< Digraph, SetPredMapTraits<T> > Create; |
236 typedef Bfs< Digraph, SetPredMapTraits<T> > Create; |
237 }; |
237 }; |
238 |
238 |
244 LEMON_ASSERT(false, "DistMap is not initialized"); |
244 LEMON_ASSERT(false, "DistMap is not initialized"); |
245 return 0; // ignore warnings |
245 return 0; // ignore warnings |
246 } |
246 } |
247 }; |
247 }; |
248 ///\brief \ref named-templ-param "Named parameter" for setting |
248 ///\brief \ref named-templ-param "Named parameter" for setting |
249 ///\ref DistMap type. |
249 ///DistMap type. |
250 /// |
250 /// |
251 ///\ref named-templ-param "Named parameter" for setting |
251 ///\ref named-templ-param "Named parameter" for setting |
252 ///\ref DistMap type. |
252 ///DistMap type. |
253 template <class T> |
253 template <class T> |
254 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { |
254 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { |
255 typedef Bfs< Digraph, SetDistMapTraits<T> > Create; |
255 typedef Bfs< Digraph, SetDistMapTraits<T> > Create; |
256 }; |
256 }; |
257 |
257 |
263 LEMON_ASSERT(false, "ReachedMap is not initialized"); |
263 LEMON_ASSERT(false, "ReachedMap is not initialized"); |
264 return 0; // ignore warnings |
264 return 0; // ignore warnings |
265 } |
265 } |
266 }; |
266 }; |
267 ///\brief \ref named-templ-param "Named parameter" for setting |
267 ///\brief \ref named-templ-param "Named parameter" for setting |
268 ///\ref ReachedMap type. |
268 ///ReachedMap type. |
269 /// |
269 /// |
270 ///\ref named-templ-param "Named parameter" for setting |
270 ///\ref named-templ-param "Named parameter" for setting |
271 ///\ref ReachedMap type. |
271 ///ReachedMap type. |
272 template <class T> |
272 template <class T> |
273 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { |
273 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { |
274 typedef Bfs< Digraph, SetReachedMapTraits<T> > Create; |
274 typedef Bfs< Digraph, SetReachedMapTraits<T> > Create; |
275 }; |
275 }; |
276 |
276 |
282 LEMON_ASSERT(false, "ProcessedMap is not initialized"); |
282 LEMON_ASSERT(false, "ProcessedMap is not initialized"); |
283 return 0; // ignore warnings |
283 return 0; // ignore warnings |
284 } |
284 } |
285 }; |
285 }; |
286 ///\brief \ref named-templ-param "Named parameter" for setting |
286 ///\brief \ref named-templ-param "Named parameter" for setting |
287 ///\ref ProcessedMap type. |
287 ///ProcessedMap type. |
288 /// |
288 /// |
289 ///\ref named-templ-param "Named parameter" for setting |
289 ///\ref named-templ-param "Named parameter" for setting |
290 ///\ref ProcessedMap type. |
290 ///ProcessedMap type. |
291 template <class T> |
291 template <class T> |
292 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { |
292 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { |
293 typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create; |
293 typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create; |
294 }; |
294 }; |
295 |
295 |
300 return new ProcessedMap(g); |
300 return new ProcessedMap(g); |
301 return 0; // ignore warnings |
301 return 0; // ignore warnings |
302 } |
302 } |
303 }; |
303 }; |
304 ///\brief \ref named-templ-param "Named parameter" for setting |
304 ///\brief \ref named-templ-param "Named parameter" for setting |
305 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. |
305 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. |
306 /// |
306 /// |
307 ///\ref named-templ-param "Named parameter" for setting |
307 ///\ref named-templ-param "Named parameter" for setting |
308 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. |
308 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. |
309 ///If you don't set it explicitly, it will be automatically allocated. |
309 ///If you don't set it explicitly, it will be automatically allocated. |
310 struct SetStandardProcessedMap : |
310 struct SetStandardProcessedMap : |
311 public Bfs< Digraph, SetStandardProcessedMapTraits > { |
311 public Bfs< Digraph, SetStandardProcessedMapTraits > { |
312 typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create; |
312 typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create; |
313 }; |
313 }; |
833 /// |
833 /// |
834 ///The type of the map that stores the predecessor |
834 ///The type of the map that stores the predecessor |
835 ///arcs of the shortest paths. |
835 ///arcs of the shortest paths. |
836 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
836 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
837 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
837 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
838 ///Instantiates a \ref PredMap. |
838 ///Instantiates a PredMap. |
839 |
839 |
840 ///This function instantiates a \ref PredMap. |
840 ///This function instantiates a PredMap. |
841 ///\param g is the digraph, to which we would like to define the |
841 ///\param g is the digraph, to which we would like to define the |
842 ///\ref PredMap. |
842 ///PredMap. |
843 static PredMap *createPredMap(const Digraph &g) |
843 static PredMap *createPredMap(const Digraph &g) |
844 { |
844 { |
845 return new PredMap(g); |
845 return new PredMap(g); |
846 } |
846 } |
847 |
847 |
849 |
849 |
850 ///The type of the map that indicates which nodes are processed. |
850 ///The type of the map that indicates which nodes are processed. |
851 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
851 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
852 ///By default it is a NullMap. |
852 ///By default it is a NullMap. |
853 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
853 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
854 ///Instantiates a \ref ProcessedMap. |
854 ///Instantiates a ProcessedMap. |
855 |
855 |
856 ///This function instantiates a \ref ProcessedMap. |
856 ///This function instantiates a ProcessedMap. |
857 ///\param g is the digraph, to which |
857 ///\param g is the digraph, to which |
858 ///we would like to define the \ref ProcessedMap. |
858 ///we would like to define the ProcessedMap. |
859 #ifdef DOXYGEN |
859 #ifdef DOXYGEN |
860 static ProcessedMap *createProcessedMap(const Digraph &g) |
860 static ProcessedMap *createProcessedMap(const Digraph &g) |
861 #else |
861 #else |
862 static ProcessedMap *createProcessedMap(const Digraph &) |
862 static ProcessedMap *createProcessedMap(const Digraph &) |
863 #endif |
863 #endif |
868 ///The type of the map that indicates which nodes are reached. |
868 ///The type of the map that indicates which nodes are reached. |
869 |
869 |
870 ///The type of the map that indicates which nodes are reached. |
870 ///The type of the map that indicates which nodes are reached. |
871 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
871 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
872 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
872 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
873 ///Instantiates a \ref ReachedMap. |
873 ///Instantiates a ReachedMap. |
874 |
874 |
875 ///This function instantiates a \ref ReachedMap. |
875 ///This function instantiates a ReachedMap. |
876 ///\param g is the digraph, to which |
876 ///\param g is the digraph, to which |
877 ///we would like to define the \ref ReachedMap. |
877 ///we would like to define the ReachedMap. |
878 static ReachedMap *createReachedMap(const Digraph &g) |
878 static ReachedMap *createReachedMap(const Digraph &g) |
879 { |
879 { |
880 return new ReachedMap(g); |
880 return new ReachedMap(g); |
881 } |
881 } |
882 |
882 |
883 ///The type of the map that stores the distances of the nodes. |
883 ///The type of the map that stores the distances of the nodes. |
884 |
884 |
885 ///The type of the map that stores the distances of the nodes. |
885 ///The type of the map that stores the distances of the nodes. |
886 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
886 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
887 typedef typename Digraph::template NodeMap<int> DistMap; |
887 typedef typename Digraph::template NodeMap<int> DistMap; |
888 ///Instantiates a \ref DistMap. |
888 ///Instantiates a DistMap. |
889 |
889 |
890 ///This function instantiates a \ref DistMap. |
890 ///This function instantiates a DistMap. |
891 ///\param g is the digraph, to which we would like to define |
891 ///\param g is the digraph, to which we would like to define |
892 ///the \ref DistMap |
892 ///the DistMap |
893 static DistMap *createDistMap(const Digraph &g) |
893 static DistMap *createDistMap(const Digraph &g) |
894 { |
894 { |
895 return new DistMap(g); |
895 return new DistMap(g); |
896 } |
896 } |
897 |
897 |
900 ///The type of the shortest paths. |
900 ///The type of the shortest paths. |
901 ///It must meet the \ref concepts::Path "Path" concept. |
901 ///It must meet the \ref concepts::Path "Path" concept. |
902 typedef lemon::Path<Digraph> Path; |
902 typedef lemon::Path<Digraph> Path; |
903 }; |
903 }; |
904 |
904 |
905 /// Default traits class used by \ref BfsWizard |
905 /// Default traits class used by BfsWizard |
906 |
906 |
907 /// To make it easier to use Bfs algorithm |
907 /// To make it easier to use Bfs algorithm |
908 /// we have created a wizard class. |
908 /// we have created a wizard class. |
909 /// This \ref BfsWizard class needs default traits, |
909 /// This \ref BfsWizard class needs default traits, |
910 /// as well as the \ref Bfs class. |
910 /// as well as the \ref Bfs class. |
1066 typedef T PredMap; |
1066 typedef T PredMap; |
1067 static PredMap *createPredMap(const Digraph &) { return 0; }; |
1067 static PredMap *createPredMap(const Digraph &) { return 0; }; |
1068 SetPredMapBase(const TR &b) : TR(b) {} |
1068 SetPredMapBase(const TR &b) : TR(b) {} |
1069 }; |
1069 }; |
1070 ///\brief \ref named-func-param "Named parameter" |
1070 ///\brief \ref named-func-param "Named parameter" |
1071 ///for setting \ref PredMap object. |
1071 ///for setting PredMap object. |
1072 /// |
1072 /// |
1073 ///\ref named-func-param "Named parameter" |
1073 ///\ref named-func-param "Named parameter" |
1074 ///for setting \ref PredMap object. |
1074 ///for setting PredMap object. |
1075 template<class T> |
1075 template<class T> |
1076 BfsWizard<SetPredMapBase<T> > predMap(const T &t) |
1076 BfsWizard<SetPredMapBase<T> > predMap(const T &t) |
1077 { |
1077 { |
1078 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1078 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1079 return BfsWizard<SetPredMapBase<T> >(*this); |
1079 return BfsWizard<SetPredMapBase<T> >(*this); |
1084 typedef T ReachedMap; |
1084 typedef T ReachedMap; |
1085 static ReachedMap *createReachedMap(const Digraph &) { return 0; }; |
1085 static ReachedMap *createReachedMap(const Digraph &) { return 0; }; |
1086 SetReachedMapBase(const TR &b) : TR(b) {} |
1086 SetReachedMapBase(const TR &b) : TR(b) {} |
1087 }; |
1087 }; |
1088 ///\brief \ref named-func-param "Named parameter" |
1088 ///\brief \ref named-func-param "Named parameter" |
1089 ///for setting \ref ReachedMap object. |
1089 ///for setting ReachedMap object. |
1090 /// |
1090 /// |
1091 /// \ref named-func-param "Named parameter" |
1091 /// \ref named-func-param "Named parameter" |
1092 ///for setting \ref ReachedMap object. |
1092 ///for setting ReachedMap object. |
1093 template<class T> |
1093 template<class T> |
1094 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) |
1094 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) |
1095 { |
1095 { |
1096 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1096 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1097 return BfsWizard<SetReachedMapBase<T> >(*this); |
1097 return BfsWizard<SetReachedMapBase<T> >(*this); |
1102 typedef T DistMap; |
1102 typedef T DistMap; |
1103 static DistMap *createDistMap(const Digraph &) { return 0; }; |
1103 static DistMap *createDistMap(const Digraph &) { return 0; }; |
1104 SetDistMapBase(const TR &b) : TR(b) {} |
1104 SetDistMapBase(const TR &b) : TR(b) {} |
1105 }; |
1105 }; |
1106 ///\brief \ref named-func-param "Named parameter" |
1106 ///\brief \ref named-func-param "Named parameter" |
1107 ///for setting \ref DistMap object. |
1107 ///for setting DistMap object. |
1108 /// |
1108 /// |
1109 /// \ref named-func-param "Named parameter" |
1109 /// \ref named-func-param "Named parameter" |
1110 ///for setting \ref DistMap object. |
1110 ///for setting DistMap object. |
1111 template<class T> |
1111 template<class T> |
1112 BfsWizard<SetDistMapBase<T> > distMap(const T &t) |
1112 BfsWizard<SetDistMapBase<T> > distMap(const T &t) |
1113 { |
1113 { |
1114 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1114 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1115 return BfsWizard<SetDistMapBase<T> >(*this); |
1115 return BfsWizard<SetDistMapBase<T> >(*this); |
1120 typedef T ProcessedMap; |
1120 typedef T ProcessedMap; |
1121 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; |
1121 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; |
1122 SetProcessedMapBase(const TR &b) : TR(b) {} |
1122 SetProcessedMapBase(const TR &b) : TR(b) {} |
1123 }; |
1123 }; |
1124 ///\brief \ref named-func-param "Named parameter" |
1124 ///\brief \ref named-func-param "Named parameter" |
1125 ///for setting \ref ProcessedMap object. |
1125 ///for setting ProcessedMap object. |
1126 /// |
1126 /// |
1127 /// \ref named-func-param "Named parameter" |
1127 /// \ref named-func-param "Named parameter" |
1128 ///for setting \ref ProcessedMap object. |
1128 ///for setting ProcessedMap object. |
1129 template<class T> |
1129 template<class T> |
1130 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) |
1130 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) |
1131 { |
1131 { |
1132 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1132 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1133 return BfsWizard<SetProcessedMapBase<T> >(*this); |
1133 return BfsWizard<SetProcessedMapBase<T> >(*this); |
1265 /// |
1265 /// |
1266 /// The type of the map that indicates which nodes are reached. |
1266 /// The type of the map that indicates which nodes are reached. |
1267 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
1267 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
1268 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
1268 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
1269 |
1269 |
1270 /// \brief Instantiates a \ref ReachedMap. |
1270 /// \brief Instantiates a ReachedMap. |
1271 /// |
1271 /// |
1272 /// This function instantiates a \ref ReachedMap. |
1272 /// This function instantiates a ReachedMap. |
1273 /// \param digraph is the digraph, to which |
1273 /// \param digraph is the digraph, to which |
1274 /// we would like to define the \ref ReachedMap. |
1274 /// we would like to define the ReachedMap. |
1275 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1275 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1276 return new ReachedMap(digraph); |
1276 return new ReachedMap(digraph); |
1277 } |
1277 } |
1278 |
1278 |
1279 }; |
1279 }; |