lemon/bfs.h
changeset 436 561be42c4b99
parent 292 e7af73f1805e
child 329 d900fd1e760f
equal deleted inserted replaced
18:b9bd71bea080 19:1781789f8210
    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   };