lemon/core.h
changeset 635 89705c452130
parent 581 aa1804409f29
child 639 72ac25ad276e
equal deleted inserted replaced
14:6bf3037a46c8 15:af1b694b5b44
  1034   ///
  1034   ///
  1035   ///\sa findArc()
  1035   ///\sa findArc()
  1036   ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
  1036   ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
  1037   template <typename GR>
  1037   template <typename GR>
  1038   class ConArcIt : public GR::Arc {
  1038   class ConArcIt : public GR::Arc {
       
  1039     typedef typename GR::Arc Parent;
       
  1040 
  1039   public:
  1041   public:
  1040 
  1042 
  1041     typedef GR Graph;
  1043     typedef typename GR::Arc Arc;
  1042     typedef typename Graph::Arc Parent;
  1044     typedef typename GR::Node Node;
  1043 
       
  1044     typedef typename Graph::Arc Arc;
       
  1045     typedef typename Graph::Node Node;
       
  1046 
  1045 
  1047     /// \brief Constructor.
  1046     /// \brief Constructor.
  1048     ///
  1047     ///
  1049     /// Construct a new ConArcIt iterating on the arcs that
  1048     /// Construct a new ConArcIt iterating on the arcs that
  1050     /// connects nodes \c u and \c v.
  1049     /// connects nodes \c u and \c v.
  1051     ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
  1050     ConArcIt(const GR& g, Node u, Node v) : _graph(g) {
  1052       Parent::operator=(findArc(_graph, u, v));
  1051       Parent::operator=(findArc(_graph, u, v));
  1053     }
  1052     }
  1054 
  1053 
  1055     /// \brief Constructor.
  1054     /// \brief Constructor.
  1056     ///
  1055     ///
  1057     /// Construct a new ConArcIt that continues the iterating from arc \c a.
  1056     /// Construct a new ConArcIt that continues the iterating from arc \c a.
  1058     ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
  1057     ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {}
  1059 
  1058 
  1060     /// \brief Increment operator.
  1059     /// \brief Increment operator.
  1061     ///
  1060     ///
  1062     /// It increments the iterator and gives back the next arc.
  1061     /// It increments the iterator and gives back the next arc.
  1063     ConArcIt& operator++() {
  1062     ConArcIt& operator++() {
  1064       Parent::operator=(findArc(_graph, _graph.source(*this),
  1063       Parent::operator=(findArc(_graph, _graph.source(*this),
  1065                                 _graph.target(*this), *this));
  1064                                 _graph.target(*this), *this));
  1066       return *this;
  1065       return *this;
  1067     }
  1066     }
  1068   private:
  1067   private:
  1069     const Graph& _graph;
  1068     const GR& _graph;
  1070   };
  1069   };
  1071 
  1070 
  1072   namespace _core_bits {
  1071   namespace _core_bits {
  1073 
  1072 
  1074     template <typename Graph, typename Enable = void>
  1073     template <typename Graph, typename Enable = void>
  1157   ///\endcode
  1156   ///\endcode
  1158   ///
  1157   ///
  1159   ///\sa findEdge()
  1158   ///\sa findEdge()
  1160   template <typename GR>
  1159   template <typename GR>
  1161   class ConEdgeIt : public GR::Edge {
  1160   class ConEdgeIt : public GR::Edge {
       
  1161     typedef typename GR::Edge Parent;
       
  1162 
  1162   public:
  1163   public:
  1163 
  1164 
  1164     typedef GR Graph;
  1165     typedef typename GR::Edge Edge;
  1165     typedef typename Graph::Edge Parent;
  1166     typedef typename GR::Node Node;
  1166 
       
  1167     typedef typename Graph::Edge Edge;
       
  1168     typedef typename Graph::Node Node;
       
  1169 
  1167 
  1170     /// \brief Constructor.
  1168     /// \brief Constructor.
  1171     ///
  1169     ///
  1172     /// Construct a new ConEdgeIt iterating on the edges that
  1170     /// Construct a new ConEdgeIt iterating on the edges that
  1173     /// connects nodes \c u and \c v.
  1171     /// connects nodes \c u and \c v.
  1174     ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
  1172     ConEdgeIt(const GR& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
  1175       Parent::operator=(findEdge(_graph, _u, _v));
  1173       Parent::operator=(findEdge(_graph, _u, _v));
  1176     }
  1174     }
  1177 
  1175 
  1178     /// \brief Constructor.
  1176     /// \brief Constructor.
  1179     ///
  1177     ///
  1180     /// Construct a new ConEdgeIt that continues iterating from edge \c e.
  1178     /// Construct a new ConEdgeIt that continues iterating from edge \c e.
  1181     ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
  1179     ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {}
  1182 
  1180 
  1183     /// \brief Increment operator.
  1181     /// \brief Increment operator.
  1184     ///
  1182     ///
  1185     /// It increments the iterator and gives back the next edge.
  1183     /// It increments the iterator and gives back the next edge.
  1186     ConEdgeIt& operator++() {
  1184     ConEdgeIt& operator++() {
  1187       Parent::operator=(findEdge(_graph, _u, _v, *this));
  1185       Parent::operator=(findEdge(_graph, _u, _v, *this));
  1188       return *this;
  1186       return *this;
  1189     }
  1187     }
  1190   private:
  1188   private:
  1191     const Graph& _graph;
  1189     const GR& _graph;
  1192     Node _u, _v;
  1190     Node _u, _v;
  1193   };
  1191   };
  1194 
  1192 
  1195 
  1193 
  1196   ///Dynamic arc look-up between given endpoints.
  1194   ///Dynamic arc look-up between given endpoints.
  1217   ///\sa AllArcLookUp
  1215   ///\sa AllArcLookUp
  1218   template <typename GR>
  1216   template <typename GR>
  1219   class DynArcLookUp
  1217   class DynArcLookUp
  1220     : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
  1218     : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
  1221   {
  1219   {
  1222   public:
       
  1223     typedef typename ItemSetTraits<GR, typename GR::Arc>
  1220     typedef typename ItemSetTraits<GR, typename GR::Arc>
  1224     ::ItemNotifier::ObserverBase Parent;
  1221     ::ItemNotifier::ObserverBase Parent;
  1225 
  1222 
  1226     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
  1223     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
       
  1224 
       
  1225   public:
       
  1226 
       
  1227     /// The Digraph type
  1227     typedef GR Digraph;
  1228     typedef GR Digraph;
  1228 
  1229 
  1229   protected:
  1230   protected:
  1230 
  1231 
  1231     class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
  1232     class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
       
  1233       typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
       
  1234 
  1232     public:
  1235     public:
  1233 
       
  1234       typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
       
  1235 
  1236 
  1236       AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
  1237       AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
  1237 
  1238 
  1238       virtual void add(const Node& node) {
  1239       virtual void add(const Node& node) {
  1239         Parent::add(node);
  1240         Parent::add(node);
  1254         for (nf->first(it); it != INVALID; nf->next(it)) {
  1255         for (nf->first(it); it != INVALID; nf->next(it)) {
  1255           Parent::set(it, INVALID);
  1256           Parent::set(it, INVALID);
  1256         }
  1257         }
  1257       }
  1258       }
  1258     };
  1259     };
  1259 
       
  1260     const Digraph &_g;
       
  1261     AutoNodeMap _head;
       
  1262     typename Digraph::template ArcMap<Arc> _parent;
       
  1263     typename Digraph::template ArcMap<Arc> _left;
       
  1264     typename Digraph::template ArcMap<Arc> _right;
       
  1265 
  1260 
  1266     class ArcLess {
  1261     class ArcLess {
  1267       const Digraph &g;
  1262       const Digraph &g;
  1268     public:
  1263     public:
  1269       ArcLess(const Digraph &_g) : g(_g) {}
  1264       ArcLess(const Digraph &_g) : g(_g) {}
  1270       bool operator()(Arc a,Arc b) const
  1265       bool operator()(Arc a,Arc b) const
  1271       {
  1266       {
  1272         return g.target(a)<g.target(b);
  1267         return g.target(a)<g.target(b);
  1273       }
  1268       }
  1274     };
  1269     };
       
  1270 
       
  1271   protected: 
       
  1272 
       
  1273     const Digraph &_g;
       
  1274     AutoNodeMap _head;
       
  1275     typename Digraph::template ArcMap<Arc> _parent;
       
  1276     typename Digraph::template ArcMap<Arc> _left;
       
  1277     typename Digraph::template ArcMap<Arc> _right;
  1275 
  1278 
  1276   public:
  1279   public:
  1277 
  1280 
  1278     ///Constructor
  1281     ///Constructor
  1279 
  1282 
  1628   ///\sa DynArcLookUp
  1631   ///\sa DynArcLookUp
  1629   ///\sa AllArcLookUp
  1632   ///\sa AllArcLookUp
  1630   template<class GR>
  1633   template<class GR>
  1631   class ArcLookUp
  1634   class ArcLookUp
  1632   {
  1635   {
       
  1636     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
       
  1637 
  1633   public:
  1638   public:
  1634     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
  1639 
       
  1640     /// The Digraph type
  1635     typedef GR Digraph;
  1641     typedef GR Digraph;
  1636 
  1642 
  1637   protected:
  1643   protected:
  1638     const Digraph &_g;
  1644     const Digraph &_g;
  1639     typename Digraph::template NodeMap<Arc> _head;
  1645     typename Digraph::template NodeMap<Arc> _head;
  1744     using ArcLookUp<GR>::_right;
  1750     using ArcLookUp<GR>::_right;
  1745     using ArcLookUp<GR>::_left;
  1751     using ArcLookUp<GR>::_left;
  1746     using ArcLookUp<GR>::_head;
  1752     using ArcLookUp<GR>::_head;
  1747 
  1753 
  1748     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
  1754     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
  1749     typedef GR Digraph;
  1755 
  1750 
  1756     typename GR::template ArcMap<Arc> _next;
  1751     typename Digraph::template ArcMap<Arc> _next;
       
  1752 
  1757 
  1753     Arc refreshNext(Arc head,Arc next=INVALID)
  1758     Arc refreshNext(Arc head,Arc next=INVALID)
  1754     {
  1759     {
  1755       if(head==INVALID) return next;
  1760       if(head==INVALID) return next;
  1756       else {
  1761       else {
  1765     {
  1770     {
  1766       for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
  1771       for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
  1767     }
  1772     }
  1768 
  1773 
  1769   public:
  1774   public:
       
  1775 
       
  1776     /// The Digraph type
       
  1777     typedef GR Digraph;
       
  1778 
  1770     ///Constructor
  1779     ///Constructor
  1771 
  1780 
  1772     ///Constructor.
  1781     ///Constructor.
  1773     ///
  1782     ///
  1774     ///It builds up the search database, which remains valid until the digraph
  1783     ///It builds up the search database, which remains valid until the digraph