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 |
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 { |