45 ///\brief The type of the map that stores the predecessor |
45 ///\brief The type of the map that stores the predecessor |
46 ///arcs of the shortest paths. |
46 ///arcs of the shortest paths. |
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 conform to 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 \c PredMap. |
52 ///Instantiates a \c PredMap. |
53 |
53 |
54 ///This function instantiates a \ref PredMap. |
54 ///This function instantiates a \ref 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 |
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 conform to the \ref concepts::WriteMap "WriteMap" concept. |
|
66 ///By default it is a NullMap. |
66 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
67 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
67 ///Instantiates a \c ProcessedMap. |
68 ///Instantiates a \c ProcessedMap. |
68 |
69 |
69 ///This function instantiates a \ref ProcessedMap. |
70 ///This function instantiates a \ref ProcessedMap. |
70 ///\param g is the digraph, to which |
71 ///\param g is the digraph, to which |
263 ///\brief \ref named-templ-param "Named parameter" for setting |
264 ///\brief \ref named-templ-param "Named parameter" for setting |
264 ///\c ReachedMap type. |
265 ///\c ReachedMap type. |
265 /// |
266 /// |
266 ///\ref named-templ-param "Named parameter" for setting |
267 ///\ref named-templ-param "Named parameter" for setting |
267 ///\c ReachedMap type. |
268 ///\c ReachedMap type. |
268 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
269 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
269 template <class T> |
270 template <class T> |
270 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { |
271 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { |
271 typedef Bfs< Digraph, SetReachedMapTraits<T> > Create; |
272 typedef Bfs< Digraph, SetReachedMapTraits<T> > Create; |
272 }; |
273 }; |
273 |
274 |
283 ///\brief \ref named-templ-param "Named parameter" for setting |
284 ///\brief \ref named-templ-param "Named parameter" for setting |
284 ///\c ProcessedMap type. |
285 ///\c ProcessedMap type. |
285 /// |
286 /// |
286 ///\ref named-templ-param "Named parameter" for setting |
287 ///\ref named-templ-param "Named parameter" for setting |
287 ///\c ProcessedMap type. |
288 ///\c ProcessedMap type. |
288 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
289 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. |
289 template <class T> |
290 template <class T> |
290 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { |
291 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { |
291 typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create; |
292 typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create; |
292 }; |
293 }; |
293 |
294 |
735 ///Either \ref run(Node) "run()" or \ref start() should be called |
736 ///Either \ref run(Node) "run()" or \ref start() should be called |
736 ///before using them. |
737 ///before using them. |
737 |
738 |
738 ///@{ |
739 ///@{ |
739 |
740 |
740 ///The shortest path to a node. |
741 ///The shortest path to the given node. |
741 |
742 |
742 ///Returns the shortest path to a node. |
743 ///Returns the shortest path to the given node from the root(s). |
743 /// |
744 /// |
744 ///\warning \c t should be reached from the root(s). |
745 ///\warning \c t should be reached from the root(s). |
745 /// |
746 /// |
746 ///\pre Either \ref run(Node) "run()" or \ref init() |
747 ///\pre Either \ref run(Node) "run()" or \ref init() |
747 ///must be called before using this function. |
748 ///must be called before using this function. |
748 Path path(Node t) const { return Path(*G, *_pred, t); } |
749 Path path(Node t) const { return Path(*G, *_pred, t); } |
749 |
750 |
750 ///The distance of a node from the root(s). |
751 ///The distance of the given node from the root(s). |
751 |
752 |
752 ///Returns the distance of a node from the root(s). |
753 ///Returns the distance of the given node from the root(s). |
753 /// |
754 /// |
754 ///\warning If node \c v is not reached from the root(s), then |
755 ///\warning If node \c v is not reached from the root(s), then |
755 ///the return value of this function is undefined. |
756 ///the return value of this function is undefined. |
756 /// |
757 /// |
757 ///\pre Either \ref run(Node) "run()" or \ref init() |
758 ///\pre Either \ref run(Node) "run()" or \ref init() |
758 ///must be called before using this function. |
759 ///must be called before using this function. |
759 int dist(Node v) const { return (*_dist)[v]; } |
760 int dist(Node v) const { return (*_dist)[v]; } |
760 |
761 |
761 ///Returns the 'previous arc' of the shortest path tree for a node. |
762 ///\brief Returns the 'previous arc' of the shortest path tree for |
762 |
763 ///the given node. |
|
764 /// |
763 ///This function returns the 'previous arc' of the shortest path |
765 ///This function returns the 'previous arc' of the shortest path |
764 ///tree for the node \c v, i.e. it returns the last arc of a |
766 ///tree for the node \c v, i.e. it returns the last arc of a |
765 ///shortest path from a root to \c v. It is \c INVALID if \c v |
767 ///shortest path from a root to \c v. It is \c INVALID if \c v |
766 ///is not reached from the root(s) or if \c v is a root. |
768 ///is not reached from the root(s) or if \c v is a root. |
767 /// |
769 /// |
768 ///The shortest path tree used here is equal to the shortest path |
770 ///The shortest path tree used here is equal to the shortest path |
769 ///tree used in \ref predNode(). |
771 ///tree used in \ref predNode() and \ref predMap(). |
770 /// |
772 /// |
771 ///\pre Either \ref run(Node) "run()" or \ref init() |
773 ///\pre Either \ref run(Node) "run()" or \ref init() |
772 ///must be called before using this function. |
774 ///must be called before using this function. |
773 Arc predArc(Node v) const { return (*_pred)[v];} |
775 Arc predArc(Node v) const { return (*_pred)[v];} |
774 |
776 |
775 ///Returns the 'previous node' of the shortest path tree for a node. |
777 ///\brief Returns the 'previous node' of the shortest path tree for |
776 |
778 ///the given node. |
|
779 /// |
777 ///This function returns the 'previous node' of the shortest path |
780 ///This function returns the 'previous node' of the shortest path |
778 ///tree for the node \c v, i.e. it returns the last but one node |
781 ///tree for the node \c v, i.e. it returns the last but one node |
779 ///from a shortest path from a root to \c v. It is \c INVALID |
782 ///of a shortest path from a root to \c v. It is \c INVALID |
780 ///if \c v is not reached from the root(s) or if \c v is a root. |
783 ///if \c v is not reached from the root(s) or if \c v is a root. |
781 /// |
784 /// |
782 ///The shortest path tree used here is equal to the shortest path |
785 ///The shortest path tree used here is equal to the shortest path |
783 ///tree used in \ref predArc(). |
786 ///tree used in \ref predArc() and \ref predMap(). |
784 /// |
787 /// |
785 ///\pre Either \ref run(Node) "run()" or \ref init() |
788 ///\pre Either \ref run(Node) "run()" or \ref init() |
786 ///must be called before using this function. |
789 ///must be called before using this function. |
787 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
790 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
788 G->source((*_pred)[v]); } |
791 G->source((*_pred)[v]); } |
799 |
802 |
800 ///\brief Returns a const reference to the node map that stores the |
803 ///\brief Returns a const reference to the node map that stores the |
801 ///predecessor arcs. |
804 ///predecessor arcs. |
802 /// |
805 /// |
803 ///Returns a const reference to the node map that stores the predecessor |
806 ///Returns a const reference to the node map that stores the predecessor |
804 ///arcs, which form the shortest path tree. |
807 ///arcs, which form the shortest path tree (forest). |
805 /// |
808 /// |
806 ///\pre Either \ref run(Node) "run()" or \ref init() |
809 ///\pre Either \ref run(Node) "run()" or \ref init() |
807 ///must be called before using this function. |
810 ///must be called before using this function. |
808 const PredMap &predMap() const { return *_pred;} |
811 const PredMap &predMap() const { return *_pred;} |
809 |
812 |
810 ///Checks if a node is reached from the root(s). |
813 ///Checks if the given node is reached from the root(s). |
811 |
814 |
812 ///Returns \c true if \c v is reached from the root(s). |
815 ///Returns \c true if \c v is reached from the root(s). |
813 /// |
816 /// |
814 ///\pre Either \ref run(Node) "run()" or \ref init() |
817 ///\pre Either \ref run(Node) "run()" or \ref init() |
815 ///must be called before using this function. |
818 ///must be called before using this function. |
831 ///\brief The type of the map that stores the predecessor |
834 ///\brief The type of the map that stores the predecessor |
832 ///arcs of the shortest paths. |
835 ///arcs of the shortest paths. |
833 /// |
836 /// |
834 ///The type of the map that stores the predecessor |
837 ///The type of the map that stores the predecessor |
835 ///arcs of the shortest paths. |
838 ///arcs of the shortest paths. |
836 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
839 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. |
837 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
840 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
838 ///Instantiates a PredMap. |
841 ///Instantiates a PredMap. |
839 |
842 |
840 ///This function instantiates a PredMap. |
843 ///This function instantiates a PredMap. |
841 ///\param g is the digraph, to which we would like to define the |
844 ///\param g is the digraph, to which we would like to define the |
896 } |
899 } |
897 |
900 |
898 ///The type of the shortest paths. |
901 ///The type of the shortest paths. |
899 |
902 |
900 ///The type of the shortest paths. |
903 ///The type of the shortest paths. |
901 ///It must meet the \ref concepts::Path "Path" concept. |
904 ///It must conform to the \ref concepts::Path "Path" concept. |
902 typedef lemon::Path<Digraph> Path; |
905 typedef lemon::Path<Digraph> Path; |
903 }; |
906 }; |
904 |
907 |
905 /// Default traits class used by BfsWizard |
908 /// Default traits class used by BfsWizard |
906 |
909 |
907 /// To make it easier to use Bfs algorithm |
910 /// Default traits class used by BfsWizard. |
908 /// we have created a wizard class. |
911 /// \tparam GR The type of the digraph. |
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. |
|
913 template<class GR> |
912 template<class GR> |
914 class BfsWizardBase : public BfsWizardDefaultTraits<GR> |
913 class BfsWizardBase : public BfsWizardDefaultTraits<GR> |
915 { |
914 { |
916 |
915 |
917 typedef BfsWizardDefaultTraits<GR> Base; |
916 typedef BfsWizardDefaultTraits<GR> Base; |
965 template<class TR> |
964 template<class TR> |
966 class BfsWizard : public TR |
965 class BfsWizard : public TR |
967 { |
966 { |
968 typedef TR Base; |
967 typedef TR Base; |
969 |
968 |
970 ///The type of the digraph the algorithm runs on. |
|
971 typedef typename TR::Digraph Digraph; |
969 typedef typename TR::Digraph Digraph; |
972 |
970 |
973 typedef typename Digraph::Node Node; |
971 typedef typename Digraph::Node Node; |
974 typedef typename Digraph::NodeIt NodeIt; |
972 typedef typename Digraph::NodeIt NodeIt; |
975 typedef typename Digraph::Arc Arc; |
973 typedef typename Digraph::Arc Arc; |
976 typedef typename Digraph::OutArcIt OutArcIt; |
974 typedef typename Digraph::OutArcIt OutArcIt; |
977 |
975 |
978 ///\brief The type of the map that stores the predecessor |
|
979 ///arcs of the shortest paths. |
|
980 typedef typename TR::PredMap PredMap; |
976 typedef typename TR::PredMap PredMap; |
981 ///\brief The type of the map that stores the distances of the nodes. |
|
982 typedef typename TR::DistMap DistMap; |
977 typedef typename TR::DistMap DistMap; |
983 ///\brief The type of the map that indicates which nodes are reached. |
|
984 typedef typename TR::ReachedMap ReachedMap; |
978 typedef typename TR::ReachedMap ReachedMap; |
985 ///\brief The type of the map that indicates which nodes are processed. |
|
986 typedef typename TR::ProcessedMap ProcessedMap; |
979 typedef typename TR::ProcessedMap ProcessedMap; |
987 ///The type of the shortest paths |
|
988 typedef typename TR::Path Path; |
980 typedef typename TR::Path Path; |
989 |
981 |
990 public: |
982 public: |
991 |
983 |
992 /// Constructor. |
984 /// Constructor. |
1065 struct SetPredMapBase : public Base { |
1057 struct SetPredMapBase : public Base { |
1066 typedef T PredMap; |
1058 typedef T PredMap; |
1067 static PredMap *createPredMap(const Digraph &) { return 0; }; |
1059 static PredMap *createPredMap(const Digraph &) { return 0; }; |
1068 SetPredMapBase(const TR &b) : TR(b) {} |
1060 SetPredMapBase(const TR &b) : TR(b) {} |
1069 }; |
1061 }; |
1070 ///\brief \ref named-func-param "Named parameter" |
1062 |
1071 ///for setting PredMap object. |
1063 ///\brief \ref named-templ-param "Named parameter" for setting |
1072 /// |
1064 ///the predecessor map. |
1073 ///\ref named-func-param "Named parameter" |
1065 /// |
1074 ///for setting PredMap object. |
1066 ///\ref named-templ-param "Named parameter" function for setting |
|
1067 ///the map that stores the predecessor arcs of the nodes. |
1075 template<class T> |
1068 template<class T> |
1076 BfsWizard<SetPredMapBase<T> > predMap(const T &t) |
1069 BfsWizard<SetPredMapBase<T> > predMap(const T &t) |
1077 { |
1070 { |
1078 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1071 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1079 return BfsWizard<SetPredMapBase<T> >(*this); |
1072 return BfsWizard<SetPredMapBase<T> >(*this); |
1083 struct SetReachedMapBase : public Base { |
1076 struct SetReachedMapBase : public Base { |
1084 typedef T ReachedMap; |
1077 typedef T ReachedMap; |
1085 static ReachedMap *createReachedMap(const Digraph &) { return 0; }; |
1078 static ReachedMap *createReachedMap(const Digraph &) { return 0; }; |
1086 SetReachedMapBase(const TR &b) : TR(b) {} |
1079 SetReachedMapBase(const TR &b) : TR(b) {} |
1087 }; |
1080 }; |
1088 ///\brief \ref named-func-param "Named parameter" |
1081 |
1089 ///for setting ReachedMap object. |
1082 ///\brief \ref named-templ-param "Named parameter" for setting |
1090 /// |
1083 ///the reached map. |
1091 /// \ref named-func-param "Named parameter" |
1084 /// |
1092 ///for setting ReachedMap object. |
1085 ///\ref named-templ-param "Named parameter" function for setting |
|
1086 ///the map that indicates which nodes are reached. |
1093 template<class T> |
1087 template<class T> |
1094 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) |
1088 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) |
1095 { |
1089 { |
1096 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1090 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1097 return BfsWizard<SetReachedMapBase<T> >(*this); |
1091 return BfsWizard<SetReachedMapBase<T> >(*this); |
1101 struct SetDistMapBase : public Base { |
1095 struct SetDistMapBase : public Base { |
1102 typedef T DistMap; |
1096 typedef T DistMap; |
1103 static DistMap *createDistMap(const Digraph &) { return 0; }; |
1097 static DistMap *createDistMap(const Digraph &) { return 0; }; |
1104 SetDistMapBase(const TR &b) : TR(b) {} |
1098 SetDistMapBase(const TR &b) : TR(b) {} |
1105 }; |
1099 }; |
1106 ///\brief \ref named-func-param "Named parameter" |
1100 |
1107 ///for setting DistMap object. |
1101 ///\brief \ref named-templ-param "Named parameter" for setting |
1108 /// |
1102 ///the distance map. |
1109 /// \ref named-func-param "Named parameter" |
1103 /// |
1110 ///for setting DistMap object. |
1104 ///\ref named-templ-param "Named parameter" function for setting |
|
1105 ///the map that stores the distances of the nodes calculated |
|
1106 ///by the algorithm. |
1111 template<class T> |
1107 template<class T> |
1112 BfsWizard<SetDistMapBase<T> > distMap(const T &t) |
1108 BfsWizard<SetDistMapBase<T> > distMap(const T &t) |
1113 { |
1109 { |
1114 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1110 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1115 return BfsWizard<SetDistMapBase<T> >(*this); |
1111 return BfsWizard<SetDistMapBase<T> >(*this); |
1119 struct SetProcessedMapBase : public Base { |
1115 struct SetProcessedMapBase : public Base { |
1120 typedef T ProcessedMap; |
1116 typedef T ProcessedMap; |
1121 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; |
1117 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; |
1122 SetProcessedMapBase(const TR &b) : TR(b) {} |
1118 SetProcessedMapBase(const TR &b) : TR(b) {} |
1123 }; |
1119 }; |
1124 ///\brief \ref named-func-param "Named parameter" |
1120 |
1125 ///for setting ProcessedMap object. |
1121 ///\brief \ref named-func-param "Named parameter" for setting |
1126 /// |
1122 ///the processed map. |
1127 /// \ref named-func-param "Named parameter" |
1123 /// |
1128 ///for setting ProcessedMap object. |
1124 ///\ref named-templ-param "Named parameter" function for setting |
|
1125 ///the map that indicates which nodes are processed. |
1129 template<class T> |
1126 template<class T> |
1130 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) |
1127 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) |
1131 { |
1128 { |
1132 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1129 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1133 return BfsWizard<SetProcessedMapBase<T> >(*this); |
1130 return BfsWizard<SetProcessedMapBase<T> >(*this); |