lemon/dfs.h
changeset 302 1871777f62b7
parent 292 e7af73f1805e
child 313 64f8f7cc6168
equal deleted inserted replaced
18:0f33963d166a 19:19dd14d9b581
    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   };