lemon/graph_utils.h
changeset 162 33247f6fff16
parent 148 4e2581021300
child 169 5b507a86ad72
equal deleted inserted replaced
4:82636f6c00ff 5:2577e0b9d8ec
   352   /// 
   352   /// 
   353   ///\sa findArc()
   353   ///\sa findArc()
   354   ///\sa ArcLookUp
   354   ///\sa ArcLookUp
   355   ///\sa AllArcLookUp
   355   ///\sa AllArcLookUp
   356   ///\sa DynArcLookUp
   356   ///\sa DynArcLookUp
   357   ///
       
   358   /// \author Balazs Dezso 
       
   359   template <typename _Graph>
   357   template <typename _Graph>
   360   class ConArcIt : public _Graph::Arc {
   358   class ConArcIt : public _Graph::Arc {
   361   public:
   359   public:
   362 
   360 
   363     typedef _Graph Graph;
   361     typedef _Graph Graph;
   476   ///   ...
   474   ///   ...
   477   /// }
   475   /// }
   478   ///\endcode
   476   ///\endcode
   479   ///
   477   ///
   480   ///\sa findEdge()
   478   ///\sa findEdge()
   481   ///
       
   482   /// \author Balazs Dezso 
       
   483   template <typename _Graph>
   479   template <typename _Graph>
   484   class ConEdgeIt : public _Graph::Edge {
   480   class ConEdgeIt : public _Graph::Edge {
   485   public:
   481   public:
   486 
   482 
   487     typedef _Graph Graph;
   483     typedef _Graph Graph;
  1240   /// in the inverse map.
  1236   /// in the inverse map.
  1241   ///
  1237   ///
  1242   /// The values of the map can be accessed
  1238   /// The values of the map can be accessed
  1243   /// with stl compatible forward iterator.
  1239   /// with stl compatible forward iterator.
  1244   ///
  1240   ///
  1245   /// \param _Graph The graph type.
  1241   /// \tparam _Graph The graph type.
  1246   /// \param _Item The item type of the graph.
  1242   /// \tparam _Item The item type of the graph.
  1247   /// \param _Value The value type of the map.
  1243   /// \tparam _Value The value type of the map.
  1248   ///
  1244   ///
  1249   /// \see IterableValueMap
  1245   /// \see IterableValueMap
  1250   template <typename _Graph, typename _Item, typename _Value>
  1246   template <typename _Graph, typename _Item, typename _Value>
  1251   class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
  1247   class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
  1252   private:
  1248   private:
  1445   /// integers between 0 and \c n-1, where \c n is the number of the items of
  1441   /// integers between 0 and \c n-1, where \c n is the number of the items of
  1446   /// this type (e.g. nodes) (so the id of a node can change if you delete an
  1442   /// this type (e.g. nodes) (so the id of a node can change if you delete an
  1447   /// other node, i.e. this id is mutable).  </ul> This map can be inverted
  1443   /// other node, i.e. this id is mutable).  </ul> This map can be inverted
  1448   /// with its member class \c InverseMap, or with the \c operator() member.
  1444   /// with its member class \c InverseMap, or with the \c operator() member.
  1449   ///
  1445   ///
  1450   /// \param _Graph The graph class the \c DescriptorMap belongs to.
  1446   /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
  1451   /// \param _Item The Item is the Key of the Map. It may be Node, Arc or 
  1447   /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or 
  1452   /// Edge.
  1448   /// Edge.
  1453   template <typename _Graph, typename _Item>
  1449   template <typename _Graph, typename _Item>
  1454   class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
  1450   class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
  1455 
  1451 
  1456     typedef _Item Item;
  1452     typedef _Item Item;
  1635 
  1631 
  1636   /// \brief Returns the source of the given arc.
  1632   /// \brief Returns the source of the given arc.
  1637   ///
  1633   ///
  1638   /// The SourceMap gives back the source Node of the given arc. 
  1634   /// The SourceMap gives back the source Node of the given arc. 
  1639   /// \see TargetMap
  1635   /// \see TargetMap
  1640   /// \author Balazs Dezso
       
  1641   template <typename Digraph>
  1636   template <typename Digraph>
  1642   class SourceMap {
  1637   class SourceMap {
  1643   public:
  1638   public:
  1644 
  1639 
  1645     typedef typename Digraph::Node Value;
  1640     typedef typename Digraph::Node Value;
  1675 
  1670 
  1676   /// \brief Returns the target of the given arc.
  1671   /// \brief Returns the target of the given arc.
  1677   ///
  1672   ///
  1678   /// The TargetMap gives back the target Node of the given arc. 
  1673   /// The TargetMap gives back the target Node of the given arc. 
  1679   /// \see SourceMap
  1674   /// \see SourceMap
  1680   /// \author Balazs Dezso
       
  1681   template <typename Digraph>
  1675   template <typename Digraph>
  1682   class TargetMap {
  1676   class TargetMap {
  1683   public:
  1677   public:
  1684 
  1678 
  1685     typedef typename Digraph::Node Value;
  1679     typedef typename Digraph::Node Value;
  1715 
  1709 
  1716   /// \brief Returns the "forward" directed arc view of an edge.
  1710   /// \brief Returns the "forward" directed arc view of an edge.
  1717   ///
  1711   ///
  1718   /// Returns the "forward" directed arc view of an edge.
  1712   /// Returns the "forward" directed arc view of an edge.
  1719   /// \see BackwardMap
  1713   /// \see BackwardMap
  1720   /// \author Balazs Dezso
       
  1721   template <typename Graph>
  1714   template <typename Graph>
  1722   class ForwardMap {
  1715   class ForwardMap {
  1723   public:
  1716   public:
  1724 
  1717 
  1725     typedef typename Graph::Arc Value;
  1718     typedef typename Graph::Arc Value;
  1755 
  1748 
  1756   /// \brief Returns the "backward" directed arc view of an edge.
  1749   /// \brief Returns the "backward" directed arc view of an edge.
  1757   ///
  1750   ///
  1758   /// Returns the "backward" directed arc view of an edge.
  1751   /// Returns the "backward" directed arc view of an edge.
  1759   /// \see ForwardMap
  1752   /// \see ForwardMap
  1760   /// \author Balazs Dezso
       
  1761   template <typename Graph>
  1753   template <typename Graph>
  1762   class BackwardMap {
  1754   class BackwardMap {
  1763   public:
  1755   public:
  1764 
  1756 
  1765     typedef typename Graph::Arc Value;
  1757     typedef typename Graph::Arc Value;
  2094   ///and Tarjan's Splay tree for guarantee the logarithmic amortized
  2086   ///and Tarjan's Splay tree for guarantee the logarithmic amortized
  2095   ///time bound for arc lookups. This class also guarantees the
  2087   ///time bound for arc lookups. This class also guarantees the
  2096   ///optimal time bound in a constant factor for any distribution of
  2088   ///optimal time bound in a constant factor for any distribution of
  2097   ///queries.
  2089   ///queries.
  2098   ///
  2090   ///
  2099   ///\param G The type of the underlying digraph.  
  2091   ///\tparam G The type of the underlying digraph.  
  2100   ///
  2092   ///
  2101   ///\sa ArcLookUp  
  2093   ///\sa ArcLookUp  
  2102   ///\sa AllArcLookUp  
  2094   ///\sa AllArcLookUp  
  2103   template<class G>
  2095   template<class G>
  2104   class DynArcLookUp 
  2096   class DynArcLookUp 
  2535   ///\warning This class is static, so you should refresh() (or at least
  2527   ///\warning This class is static, so you should refresh() (or at least
  2536   ///refresh(Node)) this data structure
  2528   ///refresh(Node)) this data structure
  2537   ///whenever the digraph changes. This is a time consuming (superlinearly
  2529   ///whenever the digraph changes. This is a time consuming (superlinearly
  2538   ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
  2530   ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
  2539   ///
  2531   ///
  2540   ///\param G The type of the underlying digraph.
  2532   ///\tparam G The type of the underlying digraph.
  2541   ///
  2533   ///
  2542   ///\sa DynArcLookUp
  2534   ///\sa DynArcLookUp
  2543   ///\sa AllArcLookUp  
  2535   ///\sa AllArcLookUp  
  2544   template<class G>
  2536   template<class G>
  2545   class ArcLookUp 
  2537   class ArcLookUp 
  2648   ///\warning This class is static, so you should refresh() (or at least
  2640   ///\warning This class is static, so you should refresh() (or at least
  2649   ///refresh(Node)) this data structure
  2641   ///refresh(Node)) this data structure
  2650   ///whenever the digraph changes. This is a time consuming (superlinearly
  2642   ///whenever the digraph changes. This is a time consuming (superlinearly
  2651   ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
  2643   ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
  2652   ///
  2644   ///
  2653   ///\param G The type of the underlying digraph.
  2645   ///\tparam G The type of the underlying digraph.
  2654   ///
  2646   ///
  2655   ///\sa DynArcLookUp
  2647   ///\sa DynArcLookUp
  2656   ///\sa ArcLookUp  
  2648   ///\sa ArcLookUp  
  2657   template<class G>
  2649   template<class G>
  2658   class AllArcLookUp : public ArcLookUp<G>
  2650   class AllArcLookUp : public ArcLookUp<G>