48 /// |
48 /// |
49 ///The type of the map that stores the predecessor |
49 ///The type of the map that stores the predecessor |
50 ///arcs of the %DFS paths. |
50 ///arcs of the %DFS paths. |
51 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
51 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
52 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
52 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
53 ///Instantiates a \ref PredMap. |
53 ///Instantiates a PredMap. |
54 |
54 |
55 ///This function instantiates a \ref PredMap. |
55 ///This function instantiates a PredMap. |
56 ///\param g is the digraph, to which we would like to define the |
56 ///\param g is the digraph, to which we would like to define the |
57 ///\ref PredMap. |
57 ///PredMap. |
58 static PredMap *createPredMap(const Digraph &g) |
58 static PredMap *createPredMap(const Digraph &g) |
59 { |
59 { |
60 return new PredMap(g); |
60 return new PredMap(g); |
61 } |
61 } |
62 |
62 |
63 ///The type of the map that indicates which nodes are processed. |
63 ///The type of the map that indicates which nodes are processed. |
64 |
64 |
65 ///The type of the map that indicates which nodes are processed. |
65 ///The type of the map that indicates which nodes are processed. |
66 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
66 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
67 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
67 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
68 ///Instantiates a \ref ProcessedMap. |
68 ///Instantiates a ProcessedMap. |
69 |
69 |
70 ///This function instantiates a \ref ProcessedMap. |
70 ///This function instantiates a ProcessedMap. |
71 ///\param g is the digraph, to which |
71 ///\param g is the digraph, to which |
72 ///we would like to define the \ref ProcessedMap |
72 ///we would like to define the ProcessedMap |
73 #ifdef DOXYGEN |
73 #ifdef DOXYGEN |
74 static ProcessedMap *createProcessedMap(const Digraph &g) |
74 static ProcessedMap *createProcessedMap(const Digraph &g) |
75 #else |
75 #else |
76 static ProcessedMap *createProcessedMap(const Digraph &) |
76 static ProcessedMap *createProcessedMap(const Digraph &) |
77 #endif |
77 #endif |
82 ///The type of the map that indicates which nodes are reached. |
82 ///The type of the map that indicates which nodes are reached. |
83 |
83 |
84 ///The type of the map that indicates which nodes are reached. |
84 ///The type of the map that indicates which nodes are reached. |
85 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
85 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
86 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
86 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
87 ///Instantiates a \ref ReachedMap. |
87 ///Instantiates a ReachedMap. |
88 |
88 |
89 ///This function instantiates a \ref ReachedMap. |
89 ///This function instantiates a ReachedMap. |
90 ///\param g is the digraph, to which |
90 ///\param g is the digraph, to which |
91 ///we would like to define the \ref ReachedMap. |
91 ///we would like to define the ReachedMap. |
92 static ReachedMap *createReachedMap(const Digraph &g) |
92 static ReachedMap *createReachedMap(const Digraph &g) |
93 { |
93 { |
94 return new ReachedMap(g); |
94 return new ReachedMap(g); |
95 } |
95 } |
96 |
96 |
97 ///The type of the map that stores the distances of the nodes. |
97 ///The type of the map that stores the distances of the nodes. |
98 |
98 |
99 ///The type of the map that stores the distances of the nodes. |
99 ///The type of the map that stores the distances of the nodes. |
100 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
100 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
101 typedef typename Digraph::template NodeMap<int> DistMap; |
101 typedef typename Digraph::template NodeMap<int> DistMap; |
102 ///Instantiates a \ref DistMap. |
102 ///Instantiates a DistMap. |
103 |
103 |
104 ///This function instantiates a \ref DistMap. |
104 ///This function instantiates a DistMap. |
105 ///\param g is the digraph, to which we would like to define the |
105 ///\param g is the digraph, to which we would like to define the |
106 ///\ref DistMap. |
106 ///DistMap. |
107 static DistMap *createDistMap(const Digraph &g) |
107 static DistMap *createDistMap(const Digraph &g) |
108 { |
108 { |
109 return new DistMap(g); |
109 return new DistMap(g); |
110 } |
110 } |
111 }; |
111 }; |
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 Dfs<Digraph, SetPredMapTraits<T> > { |
235 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > { |
236 typedef Dfs<Digraph, SetPredMapTraits<T> > Create; |
236 typedef Dfs<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 Dfs< Digraph, SetDistMapTraits<T> > { |
254 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > { |
255 typedef Dfs<Digraph, SetDistMapTraits<T> > Create; |
255 typedef Dfs<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 Dfs< Digraph, SetReachedMapTraits<T> > { |
273 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > { |
274 typedef Dfs< Digraph, SetReachedMapTraits<T> > Create; |
274 typedef Dfs< 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 Dfs< Digraph, SetProcessedMapTraits<T> > { |
292 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > { |
293 typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create; |
293 typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create; |
294 }; |
294 }; |
295 |
295 |
299 { |
299 { |
300 return new ProcessedMap(g); |
300 return new ProcessedMap(g); |
301 } |
301 } |
302 }; |
302 }; |
303 ///\brief \ref named-templ-param "Named parameter" for setting |
303 ///\brief \ref named-templ-param "Named parameter" for setting |
304 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. |
304 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. |
305 /// |
305 /// |
306 ///\ref named-templ-param "Named parameter" for setting |
306 ///\ref named-templ-param "Named parameter" for setting |
307 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. |
307 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. |
308 ///If you don't set it explicitly, it will be automatically allocated. |
308 ///If you don't set it explicitly, it will be automatically allocated. |
309 struct SetStandardProcessedMap : |
309 struct SetStandardProcessedMap : |
310 public Dfs< Digraph, SetStandardProcessedMapTraits > { |
310 public Dfs< Digraph, SetStandardProcessedMapTraits > { |
311 typedef Dfs< Digraph, SetStandardProcessedMapTraits > Create; |
311 typedef Dfs< Digraph, SetStandardProcessedMapTraits > Create; |
312 }; |
312 }; |
766 /// |
766 /// |
767 ///The type of the map that stores the predecessor |
767 ///The type of the map that stores the predecessor |
768 ///arcs of the %DFS paths. |
768 ///arcs of the %DFS paths. |
769 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
769 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
770 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
770 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
771 ///Instantiates a \ref PredMap. |
771 ///Instantiates a PredMap. |
772 |
772 |
773 ///This function instantiates a \ref PredMap. |
773 ///This function instantiates a PredMap. |
774 ///\param g is the digraph, to which we would like to define the |
774 ///\param g is the digraph, to which we would like to define the |
775 ///\ref PredMap. |
775 ///PredMap. |
776 static PredMap *createPredMap(const Digraph &g) |
776 static PredMap *createPredMap(const Digraph &g) |
777 { |
777 { |
778 return new PredMap(g); |
778 return new PredMap(g); |
779 } |
779 } |
780 |
780 |
782 |
782 |
783 ///The type of the map that indicates which nodes are processed. |
783 ///The type of the map that indicates which nodes are processed. |
784 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
784 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
785 ///By default it is a NullMap. |
785 ///By default it is a NullMap. |
786 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
786 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
787 ///Instantiates a \ref ProcessedMap. |
787 ///Instantiates a ProcessedMap. |
788 |
788 |
789 ///This function instantiates a \ref ProcessedMap. |
789 ///This function instantiates a ProcessedMap. |
790 ///\param g is the digraph, to which |
790 ///\param g is the digraph, to which |
791 ///we would like to define the \ref ProcessedMap. |
791 ///we would like to define the ProcessedMap. |
792 #ifdef DOXYGEN |
792 #ifdef DOXYGEN |
793 static ProcessedMap *createProcessedMap(const Digraph &g) |
793 static ProcessedMap *createProcessedMap(const Digraph &g) |
794 #else |
794 #else |
795 static ProcessedMap *createProcessedMap(const Digraph &) |
795 static ProcessedMap *createProcessedMap(const Digraph &) |
796 #endif |
796 #endif |
801 ///The type of the map that indicates which nodes are reached. |
801 ///The type of the map that indicates which nodes are reached. |
802 |
802 |
803 ///The type of the map that indicates which nodes are reached. |
803 ///The type of the map that indicates which nodes are reached. |
804 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
804 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
805 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
805 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
806 ///Instantiates a \ref ReachedMap. |
806 ///Instantiates a ReachedMap. |
807 |
807 |
808 ///This function instantiates a \ref ReachedMap. |
808 ///This function instantiates a ReachedMap. |
809 ///\param g is the digraph, to which |
809 ///\param g is the digraph, to which |
810 ///we would like to define the \ref ReachedMap. |
810 ///we would like to define the ReachedMap. |
811 static ReachedMap *createReachedMap(const Digraph &g) |
811 static ReachedMap *createReachedMap(const Digraph &g) |
812 { |
812 { |
813 return new ReachedMap(g); |
813 return new ReachedMap(g); |
814 } |
814 } |
815 |
815 |
816 ///The type of the map that stores the distances of the nodes. |
816 ///The type of the map that stores the distances of the nodes. |
817 |
817 |
818 ///The type of the map that stores the distances of the nodes. |
818 ///The type of the map that stores the distances of the nodes. |
819 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
819 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
820 typedef typename Digraph::template NodeMap<int> DistMap; |
820 typedef typename Digraph::template NodeMap<int> DistMap; |
821 ///Instantiates a \ref DistMap. |
821 ///Instantiates a DistMap. |
822 |
822 |
823 ///This function instantiates a \ref DistMap. |
823 ///This function instantiates a DistMap. |
824 ///\param g is the digraph, to which we would like to define |
824 ///\param g is the digraph, to which we would like to define |
825 ///the \ref DistMap |
825 ///the DistMap |
826 static DistMap *createDistMap(const Digraph &g) |
826 static DistMap *createDistMap(const Digraph &g) |
827 { |
827 { |
828 return new DistMap(g); |
828 return new DistMap(g); |
829 } |
829 } |
830 |
830 |
999 typedef T PredMap; |
999 typedef T PredMap; |
1000 static PredMap *createPredMap(const Digraph &) { return 0; }; |
1000 static PredMap *createPredMap(const Digraph &) { return 0; }; |
1001 SetPredMapBase(const TR &b) : TR(b) {} |
1001 SetPredMapBase(const TR &b) : TR(b) {} |
1002 }; |
1002 }; |
1003 ///\brief \ref named-func-param "Named parameter" |
1003 ///\brief \ref named-func-param "Named parameter" |
1004 ///for setting \ref PredMap object. |
1004 ///for setting PredMap object. |
1005 /// |
1005 /// |
1006 ///\ref named-func-param "Named parameter" |
1006 ///\ref named-func-param "Named parameter" |
1007 ///for setting \ref PredMap object. |
1007 ///for setting PredMap object. |
1008 template<class T> |
1008 template<class T> |
1009 DfsWizard<SetPredMapBase<T> > predMap(const T &t) |
1009 DfsWizard<SetPredMapBase<T> > predMap(const T &t) |
1010 { |
1010 { |
1011 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1011 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1012 return DfsWizard<SetPredMapBase<T> >(*this); |
1012 return DfsWizard<SetPredMapBase<T> >(*this); |
1017 typedef T ReachedMap; |
1017 typedef T ReachedMap; |
1018 static ReachedMap *createReachedMap(const Digraph &) { return 0; }; |
1018 static ReachedMap *createReachedMap(const Digraph &) { return 0; }; |
1019 SetReachedMapBase(const TR &b) : TR(b) {} |
1019 SetReachedMapBase(const TR &b) : TR(b) {} |
1020 }; |
1020 }; |
1021 ///\brief \ref named-func-param "Named parameter" |
1021 ///\brief \ref named-func-param "Named parameter" |
1022 ///for setting \ref ReachedMap object. |
1022 ///for setting ReachedMap object. |
1023 /// |
1023 /// |
1024 /// \ref named-func-param "Named parameter" |
1024 /// \ref named-func-param "Named parameter" |
1025 ///for setting \ref ReachedMap object. |
1025 ///for setting ReachedMap object. |
1026 template<class T> |
1026 template<class T> |
1027 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) |
1027 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) |
1028 { |
1028 { |
1029 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1029 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1030 return DfsWizard<SetReachedMapBase<T> >(*this); |
1030 return DfsWizard<SetReachedMapBase<T> >(*this); |
1035 typedef T DistMap; |
1035 typedef T DistMap; |
1036 static DistMap *createDistMap(const Digraph &) { return 0; }; |
1036 static DistMap *createDistMap(const Digraph &) { return 0; }; |
1037 SetDistMapBase(const TR &b) : TR(b) {} |
1037 SetDistMapBase(const TR &b) : TR(b) {} |
1038 }; |
1038 }; |
1039 ///\brief \ref named-func-param "Named parameter" |
1039 ///\brief \ref named-func-param "Named parameter" |
1040 ///for setting \ref DistMap object. |
1040 ///for setting DistMap object. |
1041 /// |
1041 /// |
1042 /// \ref named-func-param "Named parameter" |
1042 /// \ref named-func-param "Named parameter" |
1043 ///for setting \ref DistMap object. |
1043 ///for setting DistMap object. |
1044 template<class T> |
1044 template<class T> |
1045 DfsWizard<SetDistMapBase<T> > distMap(const T &t) |
1045 DfsWizard<SetDistMapBase<T> > distMap(const T &t) |
1046 { |
1046 { |
1047 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1047 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1048 return DfsWizard<SetDistMapBase<T> >(*this); |
1048 return DfsWizard<SetDistMapBase<T> >(*this); |
1053 typedef T ProcessedMap; |
1053 typedef T ProcessedMap; |
1054 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; |
1054 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; |
1055 SetProcessedMapBase(const TR &b) : TR(b) {} |
1055 SetProcessedMapBase(const TR &b) : TR(b) {} |
1056 }; |
1056 }; |
1057 ///\brief \ref named-func-param "Named parameter" |
1057 ///\brief \ref named-func-param "Named parameter" |
1058 ///for setting \ref ProcessedMap object. |
1058 ///for setting ProcessedMap object. |
1059 /// |
1059 /// |
1060 /// \ref named-func-param "Named parameter" |
1060 /// \ref named-func-param "Named parameter" |
1061 ///for setting \ref ProcessedMap object. |
1061 ///for setting ProcessedMap object. |
1062 template<class T> |
1062 template<class T> |
1063 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) |
1063 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) |
1064 { |
1064 { |
1065 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1065 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1066 return DfsWizard<SetProcessedMapBase<T> >(*this); |
1066 return DfsWizard<SetProcessedMapBase<T> >(*this); |
1211 /// |
1211 /// |
1212 /// The type of the map that indicates which nodes are reached. |
1212 /// The type of the map that indicates which nodes are reached. |
1213 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
1213 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
1214 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
1214 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
1215 |
1215 |
1216 /// \brief Instantiates a \ref ReachedMap. |
1216 /// \brief Instantiates a ReachedMap. |
1217 /// |
1217 /// |
1218 /// This function instantiates a \ref ReachedMap. |
1218 /// This function instantiates a ReachedMap. |
1219 /// \param digraph is the digraph, to which |
1219 /// \param digraph is the digraph, to which |
1220 /// we would like to define the \ref ReachedMap. |
1220 /// we would like to define the ReachedMap. |
1221 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1221 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1222 return new ReachedMap(digraph); |
1222 return new ReachedMap(digraph); |
1223 } |
1223 } |
1224 |
1224 |
1225 }; |
1225 }; |