253 /// node the outgoing and the incoming arcs make up lists, therefore |
253 /// node the outgoing and the incoming arcs make up lists, therefore |
254 /// one arc can be erased in constant time. It also makes possible, |
254 /// one arc can be erased in constant time. It also makes possible, |
255 /// that node can be removed from the underlying graph, in this case |
255 /// that node can be removed from the underlying graph, in this case |
256 /// all arcs incident to the given node is erased from the arc set. |
256 /// all arcs incident to the given node is erased from the arc set. |
257 /// |
257 /// |
|
258 /// This class fully conforms to the \ref concepts::Digraph |
|
259 /// "Digraph" concept. |
|
260 /// It provides only linear time counting for nodes and arcs. |
|
261 /// |
258 /// \param GR The type of the graph which shares its node set with |
262 /// \param GR The type of the graph which shares its node set with |
259 /// this class. Its interface must conform to the |
263 /// this class. Its interface must conform to the |
260 /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" |
264 /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" |
261 /// concept. |
265 /// concept. |
262 /// |
|
263 /// This class fully conforms to the \ref concepts::Digraph |
|
264 /// "Digraph" concept. |
|
265 template <typename GR> |
266 template <typename GR> |
266 class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > { |
267 class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > { |
267 typedef ArcSetExtender<ListArcSetBase<GR> > Parent; |
268 typedef ArcSetExtender<ListArcSetBase<GR> > Parent; |
268 |
269 |
269 public: |
270 public: |
683 /// node the incident edges make up lists, therefore one edge can be |
684 /// node the incident edges make up lists, therefore one edge can be |
684 /// erased in constant time. It also makes possible, that node can |
685 /// erased in constant time. It also makes possible, that node can |
685 /// be removed from the underlying graph, in this case all edges |
686 /// be removed from the underlying graph, in this case all edges |
686 /// incident to the given node is erased from the arc set. |
687 /// incident to the given node is erased from the arc set. |
687 /// |
688 /// |
|
689 /// This class fully conforms to the \ref concepts::Graph "Graph" |
|
690 /// concept. |
|
691 /// It provides only linear time counting for nodes, edges and arcs. |
|
692 /// |
688 /// \param GR The type of the graph which shares its node set |
693 /// \param GR The type of the graph which shares its node set |
689 /// with this class. Its interface must conform to the |
694 /// with this class. Its interface must conform to the |
690 /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" |
695 /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" |
691 /// concept. |
|
692 /// |
|
693 /// This class fully conforms to the \ref concepts::Graph "Graph" |
|
694 /// concept. |
696 /// concept. |
695 template <typename GR> |
697 template <typename GR> |
696 class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > { |
698 class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > { |
697 typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent; |
699 typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent; |
698 |
700 |
952 /// This implementation is slightly faster than the \c ListArcSet, |
954 /// This implementation is slightly faster than the \c ListArcSet, |
953 /// because it uses continuous storage for arcs and it uses just |
955 /// because it uses continuous storage for arcs and it uses just |
954 /// single-linked lists for enumerate outgoing and incoming |
956 /// single-linked lists for enumerate outgoing and incoming |
955 /// arcs. Therefore the arcs cannot be erased from the arc sets. |
957 /// arcs. Therefore the arcs cannot be erased from the arc sets. |
956 /// |
958 /// |
|
959 /// This class fully conforms to the \ref concepts::Digraph "Digraph" |
|
960 /// concept. |
|
961 /// It provides only linear time counting for nodes and arcs. |
|
962 /// |
957 /// \warning If a node is erased from the underlying graph and this |
963 /// \warning If a node is erased from the underlying graph and this |
958 /// node is the source or target of one arc in the arc set, then |
964 /// node is the source or target of one arc in the arc set, then |
959 /// the arc set is invalidated, and it cannot be used anymore. The |
965 /// the arc set is invalidated, and it cannot be used anymore. The |
960 /// validity can be checked with the \c valid() member function. |
966 /// validity can be checked with the \c valid() member function. |
961 /// |
|
962 /// This class fully conforms to the \ref concepts::Digraph |
|
963 /// "Digraph" concept. |
|
964 template <typename GR> |
967 template <typename GR> |
965 class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > { |
968 class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > { |
966 typedef ArcSetExtender<SmartArcSetBase<GR> > Parent; |
969 typedef ArcSetExtender<SmartArcSetBase<GR> > Parent; |
967 |
970 |
968 public: |
971 public: |
1302 /// This implementation is slightly faster than the \c ListEdgeSet, |
1305 /// This implementation is slightly faster than the \c ListEdgeSet, |
1303 /// because it uses continuous storage for edges and it uses just |
1306 /// because it uses continuous storage for edges and it uses just |
1304 /// single-linked lists for enumerate incident edges. Therefore the |
1307 /// single-linked lists for enumerate incident edges. Therefore the |
1305 /// edges cannot be erased from the edge sets. |
1308 /// edges cannot be erased from the edge sets. |
1306 /// |
1309 /// |
|
1310 /// This class fully conforms to the \ref concepts::Graph "Graph" |
|
1311 /// concept. |
|
1312 /// It provides only linear time counting for nodes, edges and arcs. |
|
1313 /// |
1307 /// \warning If a node is erased from the underlying graph and this |
1314 /// \warning If a node is erased from the underlying graph and this |
1308 /// node is incident to one edge in the edge set, then the edge set |
1315 /// node is incident to one edge in the edge set, then the edge set |
1309 /// is invalidated, and it cannot be used anymore. The validity can |
1316 /// is invalidated, and it cannot be used anymore. The validity can |
1310 /// be checked with the \c valid() member function. |
1317 /// be checked with the \c valid() member function. |
1311 /// |
|
1312 /// This class fully conforms to the \ref concepts::Graph |
|
1313 /// "Graph" concept. |
|
1314 template <typename GR> |
1318 template <typename GR> |
1315 class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > { |
1319 class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > { |
1316 typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent; |
1320 typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent; |
1317 |
1321 |
1318 public: |
1322 public: |