lemon/core.h
changeset 565 7ab97e2a0c33
parent 535 6a17a722b50e
child 581 aa1804409f29
equal deleted inserted replaced
12:a575e99f7891 13:0d1b228b5e4e
  1032   /// }
  1032   /// }
  1033   ///\endcode
  1033   ///\endcode
  1034   ///
  1034   ///
  1035   ///\sa findArc()
  1035   ///\sa findArc()
  1036   ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
  1036   ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
  1037   template <typename _Graph>
  1037   template <typename GR>
  1038   class ConArcIt : public _Graph::Arc {
  1038   class ConArcIt : public GR::Arc {
  1039   public:
  1039   public:
  1040 
  1040 
  1041     typedef _Graph Graph;
  1041     typedef GR Graph;
  1042     typedef typename Graph::Arc Parent;
  1042     typedef typename Graph::Arc Parent;
  1043 
  1043 
  1044     typedef typename Graph::Arc Arc;
  1044     typedef typename Graph::Arc Arc;
  1045     typedef typename Graph::Node Node;
  1045     typedef typename Graph::Node Node;
  1046 
  1046 
  1155   ///   ...
  1155   ///   ...
  1156   /// }
  1156   /// }
  1157   ///\endcode
  1157   ///\endcode
  1158   ///
  1158   ///
  1159   ///\sa findEdge()
  1159   ///\sa findEdge()
  1160   template <typename _Graph>
  1160   template <typename GR>
  1161   class ConEdgeIt : public _Graph::Edge {
  1161   class ConEdgeIt : public GR::Edge {
  1162   public:
  1162   public:
  1163 
  1163 
  1164     typedef _Graph Graph;
  1164     typedef GR Graph;
  1165     typedef typename Graph::Edge Parent;
  1165     typedef typename Graph::Edge Parent;
  1166 
  1166 
  1167     typedef typename Graph::Edge Edge;
  1167     typedef typename Graph::Edge Edge;
  1168     typedef typename Graph::Node Node;
  1168     typedef typename Graph::Node Node;
  1169 
  1169 
  1209   ///of Sleator and Tarjan to guarantee the logarithmic amortized
  1209   ///of Sleator and Tarjan to guarantee the logarithmic amortized
  1210   ///time bound for arc look-ups. This class also guarantees the
  1210   ///time bound for arc look-ups. This class also guarantees the
  1211   ///optimal time bound in a constant factor for any distribution of
  1211   ///optimal time bound in a constant factor for any distribution of
  1212   ///queries.
  1212   ///queries.
  1213   ///
  1213   ///
  1214   ///\tparam G The type of the underlying digraph.
  1214   ///\tparam GR The type of the underlying digraph.
  1215   ///
  1215   ///
  1216   ///\sa ArcLookUp
  1216   ///\sa ArcLookUp
  1217   ///\sa AllArcLookUp
  1217   ///\sa AllArcLookUp
  1218   template<class G>
  1218   template <typename GR>
  1219   class DynArcLookUp
  1219   class DynArcLookUp
  1220     : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
  1220     : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
  1221   {
  1221   {
  1222   public:
  1222   public:
  1223     typedef typename ItemSetTraits<G, typename G::Arc>
  1223     typedef typename ItemSetTraits<GR, typename GR::Arc>
  1224     ::ItemNotifier::ObserverBase Parent;
  1224     ::ItemNotifier::ObserverBase Parent;
  1225 
  1225 
  1226     TEMPLATE_DIGRAPH_TYPEDEFS(G);
  1226     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
  1227     typedef G Digraph;
  1227     typedef GR Digraph;
  1228 
  1228 
  1229   protected:
  1229   protected:
  1230 
  1230 
  1231     class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
  1231     class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
  1232     public:
  1232     public:
  1233 
  1233 
  1234       typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
  1234       typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
  1235 
  1235 
  1236       AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
  1236       AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
  1237 
  1237 
  1238       virtual void add(const Node& node) {
  1238       virtual void add(const Node& node) {
  1239         Parent::add(node);
  1239         Parent::add(node);
  1240         Parent::set(node, INVALID);
  1240         Parent::set(node, INVALID);
  1241       }
  1241       }
  1621   ///\warning This class is static, so you should call refresh() (or at
  1621   ///\warning This class is static, so you should call refresh() (or at
  1622   ///least refresh(Node)) to refresh this data structure whenever the
  1622   ///least refresh(Node)) to refresh this data structure whenever the
  1623   ///digraph changes. This is a time consuming (superlinearly proportional
  1623   ///digraph changes. This is a time consuming (superlinearly proportional
  1624   ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
  1624   ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
  1625   ///
  1625   ///
  1626   ///\tparam G The type of the underlying digraph.
  1626   ///\tparam GR The type of the underlying digraph.
  1627   ///
  1627   ///
  1628   ///\sa DynArcLookUp
  1628   ///\sa DynArcLookUp
  1629   ///\sa AllArcLookUp
  1629   ///\sa AllArcLookUp
  1630   template<class G>
  1630   template<class GR>
  1631   class ArcLookUp
  1631   class ArcLookUp
  1632   {
  1632   {
  1633   public:
  1633   public:
  1634     TEMPLATE_DIGRAPH_TYPEDEFS(G);
  1634     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
  1635     typedef G Digraph;
  1635     typedef GR Digraph;
  1636 
  1636 
  1637   protected:
  1637   protected:
  1638     const Digraph &_g;
  1638     const Digraph &_g;
  1639     typename Digraph::template NodeMap<Arc> _head;
  1639     typename Digraph::template NodeMap<Arc> _head;
  1640     typename Digraph::template ArcMap<Arc> _left;
  1640     typename Digraph::template ArcMap<Arc> _left;
  1731   ///\warning This class is static, so you should call refresh() (or at
  1731   ///\warning This class is static, so you should call refresh() (or at
  1732   ///least refresh(Node)) to refresh this data structure whenever the
  1732   ///least refresh(Node)) to refresh this data structure whenever the
  1733   ///digraph changes. This is a time consuming (superlinearly proportional
  1733   ///digraph changes. This is a time consuming (superlinearly proportional
  1734   ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
  1734   ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
  1735   ///
  1735   ///
  1736   ///\tparam G The type of the underlying digraph.
  1736   ///\tparam GR The type of the underlying digraph.
  1737   ///
  1737   ///
  1738   ///\sa DynArcLookUp
  1738   ///\sa DynArcLookUp
  1739   ///\sa ArcLookUp
  1739   ///\sa ArcLookUp
  1740   template<class G>
  1740   template<class GR>
  1741   class AllArcLookUp : public ArcLookUp<G>
  1741   class AllArcLookUp : public ArcLookUp<GR>
  1742   {
  1742   {
  1743     using ArcLookUp<G>::_g;
  1743     using ArcLookUp<GR>::_g;
  1744     using ArcLookUp<G>::_right;
  1744     using ArcLookUp<GR>::_right;
  1745     using ArcLookUp<G>::_left;
  1745     using ArcLookUp<GR>::_left;
  1746     using ArcLookUp<G>::_head;
  1746     using ArcLookUp<GR>::_head;
  1747 
  1747 
  1748     TEMPLATE_DIGRAPH_TYPEDEFS(G);
  1748     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
  1749     typedef G Digraph;
  1749     typedef GR Digraph;
  1750 
  1750 
  1751     typename Digraph::template ArcMap<Arc> _next;
  1751     typename Digraph::template ArcMap<Arc> _next;
  1752 
  1752 
  1753     Arc refreshNext(Arc head,Arc next=INVALID)
  1753     Arc refreshNext(Arc head,Arc next=INVALID)
  1754     {
  1754     {
  1771 
  1771 
  1772     ///Constructor.
  1772     ///Constructor.
  1773     ///
  1773     ///
  1774     ///It builds up the search database, which remains valid until the digraph
  1774     ///It builds up the search database, which remains valid until the digraph
  1775     ///changes.
  1775     ///changes.
  1776     AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
  1776     AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();}
  1777 
  1777 
  1778     ///Refresh the data structure at a node.
  1778     ///Refresh the data structure at a node.
  1779 
  1779 
  1780     ///Build up the search database of node \c n.
  1780     ///Build up the search database of node \c n.
  1781     ///
  1781     ///
  1782     ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is
  1782     ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is
  1783     ///the number of the outgoing arcs of \c n.
  1783     ///the number of the outgoing arcs of \c n.
  1784     void refresh(Node n)
  1784     void refresh(Node n)
  1785     {
  1785     {
  1786       ArcLookUp<G>::refresh(n);
  1786       ArcLookUp<GR>::refresh(n);
  1787       refreshNext(_head[n]);
  1787       refreshNext(_head[n]);
  1788     }
  1788     }
  1789 
  1789 
  1790     ///Refresh the full data structure.
  1790     ///Refresh the full data structure.
  1791 
  1791 
  1828     ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
  1828     ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
  1829     ///
  1829     ///
  1830 #ifdef DOXYGEN
  1830 #ifdef DOXYGEN
  1831     Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
  1831     Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
  1832 #else
  1832 #else
  1833     using ArcLookUp<G>::operator() ;
  1833     using ArcLookUp<GR>::operator() ;
  1834     Arc operator()(Node s, Node t, Arc prev) const
  1834     Arc operator()(Node s, Node t, Arc prev) const
  1835     {
  1835     {
  1836       return prev==INVALID?(*this)(s,t):_next[prev];
  1836       return prev==INVALID?(*this)(s,t):_next[prev];
  1837     }
  1837     }
  1838 #endif
  1838 #endif