lemon/edge_set.h
changeset 864 d3ea191c3412
parent 778 a143f19f465b
child 877 141f9c0db4a3
equal deleted inserted replaced
6:bf5d97c5dd79 7:22a09ececaea
   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: