Changeset 735:853fcddcf282 in lemon-1.2 for lemon

Ignore:
Timestamp:
08/23/09 11:09:22 (11 years ago)
Branch:
default
Phase:
public
Message:

Doc improvements, fixes and unifications for graphs (#311)

Location:
lemon
Files:
5 edited

Unmodified
Added
Removed
• lemon/full_graph.h

 r617 ///\ingroup graphs ///\file ///\brief FullGraph and FullDigraph classes. ///\brief FullDigraph and FullGraph classes. namespace lemon { /// \ingroup graphs /// /// \brief A full digraph class. /// /// This is a simple and fast directed full graph implementation. /// From each node go arcs to each node (including the source node), /// therefore the number of the arcs in the digraph is the square of /// the node number. This digraph type is completely static, so you /// can neither add nor delete either arcs or nodes, and it needs /// constant space in memory. /// /// This class fully conforms to the \ref concepts::Digraph /// "Digraph concept". /// /// The \c FullDigraph and \c FullGraph classes are very similar, /// \brief A directed full graph class. /// /// FullDigraph is a simple and fast implmenetation of directed full /// (complete) graphs. It contains an arc from each node to each node /// (including a loop for each node), therefore the number of arcs /// is the square of the number of nodes. /// This class is completely static and it needs constant memory space. /// Thus you can neither add nor delete nodes or arcs, however /// the structure can be resized using resize(). /// /// This type fully conforms to the \ref concepts::Digraph "Digraph concept". /// Most of its member functions and nested classes are documented /// only in the concept class. /// /// \note FullDigraph and FullGraph classes are very similar, /// but there are two differences. While this class conforms only /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph /// class conforms to the \ref concepts::Graph "Graph" concept, /// moreover \c FullGraph does not contain a loop arc for each /// node as \c FullDigraph does. /// to the \ref concepts::Digraph "Digraph" concept, FullGraph /// conforms to the \ref concepts::Graph "Graph" concept, /// moreover FullGraph does not contain a loop for each /// node as this class does. /// /// \sa FullGraph public: /// \brief Constructor /// \brief Default constructor. /// /// Default constructor. The number of nodes and arcs will be zero. FullDigraph() { construct(0); } /// \brief Resizes the digraph /// /// Resizes the digraph. The function will fully destroy and /// rebuild the digraph. This cause that the maps of the digraph will /// This function resizes the digraph. It fully destroys and /// rebuilds the structure, therefore the maps of the digraph will be /// reallocated automatically and the previous values will be lost. void resize(int n) { /// \brief Returns the node with the given index. /// /// Returns the node with the given index. Since it is a static /// digraph its nodes can be indexed with integers from the range /// [0..nodeNum()-1]. /// Returns the node with the given index. Since this structure is /// completely static, the nodes can be indexed with integers from /// the range [0..nodeNum()-1]. /// \sa index() Node operator()(int ix) const { return Parent::operator()(ix); } /// \brief Returns the index of the given node. /// /// Returns the index of the given node. Since it is a static /// digraph its nodes can be indexed with integers from the range /// [0..nodeNum()-1]. /// \sa operator() int index(const Node& node) const { return Parent::index(node); } /// Returns the index of the given node. Since this structure is /// completely static, the nodes can be indexed with integers from /// the range [0..nodeNum()-1]. /// \sa operator()() int index(Node node) const { return Parent::index(node); } /// \brief Returns the arc connecting the given nodes. /// /// Returns the arc connecting the given nodes. Arc arc(const Node& u, const Node& v) const { Arc arc(Node u, Node v) const { return Parent::arc(u, v); } /// \brief An undirected full graph class. /// /// This is a simple and fast undirected full graph /// implementation. From each node go edge to each other node, /// therefore the number of edges in the graph is \f$n(n-1)/2\f$. /// This graph type is completely static, so you can neither /// add nor delete either edges or nodes, and it needs constant /// space in memory. /// /// This class fully conforms to the \ref concepts::Graph "Graph concept". /// /// The \c FullGraph and \c FullDigraph classes are very similar, /// but there are two differences. While the \c FullDigraph class /// FullGraph is a simple and fast implmenetation of undirected full /// (complete) graphs. It contains an edge between every distinct pair /// of nodes, therefore the number of edges is n(n-1)/2. /// This class is completely static and it needs constant memory space. /// Thus you can neither add nor delete nodes or edges, however /// the structure can be resized using resize(). /// /// This type fully conforms to the \ref concepts::Graph "Graph concept". /// Most of its member functions and nested classes are documented /// only in the concept class. /// /// \note FullDigraph and FullGraph classes are very similar, /// but there are two differences. While FullDigraph /// conforms only to the \ref concepts::Digraph "Digraph" concept, /// this class conforms to the \ref concepts::Graph "Graph" concept, /// moreover \c FullGraph does not contain a loop arc for each /// node as \c FullDigraph does. /// moreover this class does not contain a loop for each /// node as FullDigraph does. /// /// \sa FullDigraph public: /// \brief Constructor /// \brief Default constructor. /// /// Default constructor. The number of nodes and edges will be zero. FullGraph() { construct(0); } /// \brief Resizes the graph /// /// Resizes the graph. The function will fully destroy and /// rebuild the graph. This cause that the maps of the graph will /// This function resizes the graph. It fully destroys and /// rebuilds the structure, therefore the maps of the graph will be /// reallocated automatically and the previous values will be lost. void resize(int n) { /// \brief Returns the node with the given index. /// /// Returns the node with the given index. Since it is a static /// graph its nodes can be indexed with integers from the range /// [0..nodeNum()-1]. /// Returns the node with the given index. Since this structure is /// completely static, the nodes can be indexed with integers from /// the range [0..nodeNum()-1]. /// \sa index() Node operator()(int ix) const { return Parent::operator()(ix); } /// \brief Returns the index of the given node. /// /// Returns the index of the given node. Since it is a static /// graph its nodes can be indexed with integers from the range /// [0..nodeNum()-1]. /// \sa operator() int index(const Node& node) const { return Parent::index(node); } /// Returns the index of the given node. Since this structure is /// completely static, the nodes can be indexed with integers from /// the range [0..nodeNum()-1]. /// \sa operator()() int index(Node node) const { return Parent::index(node); } /// \brief Returns the arc connecting the given nodes. /// /// Returns the arc connecting the given nodes. Arc arc(const Node& s, const Node& t) const { Arc arc(Node s, Node t) const { return Parent::arc(s, t); } /// \brief Returns the edge connects the given nodes. /// /// Returns the edge connects the given nodes. Edge edge(const Node& u, const Node& v) const { /// \brief Returns the edge connecting the given nodes. /// /// Returns the edge connecting the given nodes. Edge edge(Node u, Node v) const { return Parent::edge(u, v); }
• lemon/grid_graph.h

 r617 /// \brief Grid graph class /// /// This class implements a special graph type. The nodes of the /// graph can be indexed by two integer \c (i,j) value where \c i is /// in the \c [0..width()-1] range and j is in the \c /// [0..height()-1] range. Two nodes are connected in the graph if /// the indexes differ exactly on one position and exactly one is /// the difference. The nodes of the graph can be indexed by position /// with the \c operator()() function. The positions of the nodes can be /// get with \c pos(), \c col() and \c row() members. The outgoing /// GridGraph implements a special graph type. The nodes of the /// graph can be indexed by two integer values \c (i,j) where \c i is /// in the range [0..width()-1] and j is in the range /// [0..height()-1]. Two nodes are connected in the graph if /// the indices differ exactly on one position and the difference is /// also exactly one. The nodes of the graph can be obtained by position /// using the \c operator()() function and the indices of the nodes can /// be obtained using \c pos(), \c col() and \c row() members. The outgoing /// arcs can be retrieved with the \c right(), \c up(), \c left() /// and \c down() functions, where the bottom-left corner is the /// origin. /// /// This class is completely static and it needs constant memory space. /// Thus you can neither add nor delete nodes or edges, however /// the structure can be resized using resize(). /// /// \image html grid_graph.png ///\endcode /// /// This graph type fully conforms to the \ref concepts::Graph /// "Graph concept". /// This type fully conforms to the \ref concepts::Graph "Graph concept". /// Most of its member functions and nested classes are documented /// only in the concept class. class GridGraph : public ExtendedGridGraphBase { typedef ExtendedGridGraphBase Parent; public: /// \brief Map to get the indices of the nodes as dim2::Point. /// /// Map to get the indices of the nodes as dim2::Point. /// \brief Map to get the indices of the nodes as \ref dim2::Point /// "dim2::Point". /// /// Map to get the indices of the nodes as \ref dim2::Point /// "dim2::Point". class IndexMap { public: /// \brief Constructor /// /// Constructor IndexMap(const GridGraph& graph) : _graph(graph) {} /// \brief The subscript operator /// /// The subscript operator. Value operator[](Key key) const { return _graph.pos(key); /// \brief Constructor /// /// Constructor ColMap(const GridGraph& graph) : _graph(graph) {} /// \brief The subscript operator /// /// The subscript operator. Value operator[](Key key) const { return _graph.col(key); /// \brief Constructor /// /// Constructor RowMap(const GridGraph& graph) : _graph(graph) {} /// \brief The subscript operator /// /// The subscript operator. Value operator[](Key key) const { return _graph.row(key); /// \brief Constructor /// /// Construct a grid graph with given size. /// Construct a grid graph with the given size. GridGraph(int width, int height) { construct(width, height); } /// \brief Resize the graph /// /// Resize the graph. The function will fully destroy and rebuild /// the graph.  This cause that the maps of the graph will /// reallocated automatically and the previous values will be /// lost. /// \brief Resizes the graph /// /// This function resizes the graph. It fully destroys and /// rebuilds the structure, therefore the maps of the graph will be /// reallocated automatically and the previous values will be lost. void resize(int width, int height) { Parent::notifier(Arc()).clear(); } /// \brief Gives back the column index of the node. /// \brief The column index of the node. /// /// Gives back the column index of the node. } /// \brief Gives back the row index of the node. /// \brief The row index of the node. /// /// Gives back the row index of the node. } /// \brief Gives back the position of the node. /// \brief The position of the node. /// /// Gives back the position of the node, ie. the (col,row) pair. } /// \brief Gives back the number of the columns. /// \brief The number of the columns. /// /// Gives back the number of the columns. } /// \brief Gives back the number of the rows. /// \brief The number of the rows. /// /// Gives back the number of the rows. } /// \brief Gives back the arc goes right from the node. /// \brief The arc goes right from the node. /// /// Gives back the arc goes right from the node. If there is not } /// \brief Gives back the arc goes left from the node. /// \brief The arc goes left from the node. /// /// Gives back the arc goes left from the node. If there is not } /// \brief Gives back the arc goes up from the node. /// \brief The arc goes up from the node. /// /// Gives back the arc goes up from the node. If there is not } /// \brief Gives back the arc goes down from the node. /// \brief The arc goes down from the node. /// /// Gives back the arc goes down from the node. If there is not
• lemon/hypercube_graph.h

 r617 /// \brief Hypercube graph class /// /// This class implements a special graph type. The nodes of the graph /// are indiced with integers with at most \c dim binary digits. /// HypercubeGraph implements a special graph type. The nodes of the /// graph are indexed with integers having at most \c dim binary digits. /// Two nodes are connected in the graph if and only if their indices /// differ only on one position in the binary form. /// This class is completely static and it needs constant memory space. /// Thus you can neither add nor delete nodes or edges. /// /// This type fully conforms to the \ref concepts::Graph "Graph concept". /// Most of its member functions and nested classes are documented /// only in the concept class. /// /// \note The type of the indices is chosen to \c int for efficiency /// reasons. Thus the maximum dimension of this implementation is 26 /// (assuming that the size of \c int is 32 bit). /// /// This graph type fully conforms to the \ref concepts::Graph /// "Graph concept". class HypercubeGraph : public ExtendedHypercubeGraphBase { typedef ExtendedHypercubeGraphBase Parent; /// /// Gives back the dimension id of the given edge. /// It is in the [0..dim-1] range. /// It is in the range [0..dim-1]. int dimension(Edge edge) const { return Parent::dimension(edge); /// /// Gives back the dimension id of the given arc. /// It is in the [0..dim-1] range. /// It is in the range [0..dim-1]. int dimension(Arc arc) const { return Parent::dimension(arc);
• lemon/list_graph.h

 r617 ///\ingroup graphs ///\file ///\brief ListDigraph, ListGraph classes. ///\brief ListDigraph and ListGraph classes. #include ///A general directed graph structure. ///\ref ListDigraph is a simple and fast directed graph ///implementation based on static linked lists that are stored in ///\ref ListDigraph is a versatile and fast directed graph ///implementation based on linked lists that are stored in ///\c std::vector structures. /// ///It conforms to the \ref concepts::Digraph "Digraph concept" and it ///also provides several useful additional functionalities. ///Most of the member functions and nested classes are documented ///This type fully conforms to the \ref concepts::Digraph "Digraph concept" ///and it also provides several useful additional functionalities. ///Most of its member functions and nested classes are documented ///only in the concept class. /// ///\sa concepts::Digraph ///\sa ListGraph class ListDigraph : public ExtendedListDigraphBase { typedef ExtendedListDigraphBase Parent; private: ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. /// /// Digraphs are \e not copy constructible. Use DigraphCopy instead. ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {}; ///\brief Assignment of ListDigraph to another one is \e not allowed. ///Use copyDigraph() instead. ///Assignment of ListDigraph to another one is \e not allowed. ///Use copyDigraph() instead. /// \brief Assignment of a digraph to another one is \e not allowed. /// Use DigraphCopy instead. void operator=(const ListDigraph &) {} public: ///Add a new node to the digraph. ///Add a new node to the digraph. ///This function adds a new node to the digraph. ///\return The new node. Node addNode() { return Parent::addNode(); } ///Add a new arc to the digraph. ///Add a new arc to the digraph with source node \c s ///This function adds a new arc to the digraph with source node \c s ///and target node \c t. ///\return The new arc. Arc addArc(const Node& s, const Node& t) { Arc addArc(Node s, Node t) { return Parent::addArc(s, t); } ///\brief Erase a node from the digraph. /// ///Erase a node from the digraph. /// void erase(const Node& n) { Parent::erase(n); } ///This function erases the given node from the digraph. void erase(Node n) { Parent::erase(n); } ///\brief Erase an arc from the digraph. /// ///Erase an arc from the digraph. /// void erase(const Arc& a) { Parent::erase(a); } ///This function erases the given arc from the digraph. void erase(Arc a) { Parent::erase(a); } /// Node validity check /// This function gives back true if the given node is valid, /// ie. it is a real node of the graph. /// /// \warning A Node pointing to a removed item /// could become valid again later if new nodes are /// added to the graph. /// This function gives back \c true if the given node is valid, /// i.e. it is a real node of the digraph. /// /// \warning A removed node could become valid again if new nodes are /// added to the digraph. bool valid(Node n) const { return Parent::valid(n); } /// Arc validity check /// This function gives back true if the given arc is valid, /// ie. it is a real arc of the graph. /// /// \warning An Arc pointing to a removed item /// could become valid again later if new nodes are /// added to the graph. /// This function gives back \c true if the given arc is valid, /// i.e. it is a real arc of the digraph. /// /// \warning A removed arc could become valid again if new arcs are /// added to the digraph. bool valid(Arc a) const { return Parent::valid(a); } /// Change the target of \c a to \c n /// Change the target of \c a to \c n /// ///\note The ArcIts and OutArcIts referencing ///the changed arc remain valid. However InArcIts are ///invalidated. /// Change the target node of an arc /// This function changes the target node of the given arc \c a to \c n. /// ///\note \c ArcIt and \c OutArcIt iterators referencing the changed ///arc remain valid, however \c InArcIt iterators are invalidated. /// ///\warning This functionality cannot be used together with the Snapshot Parent::changeTarget(a,n); } /// Change the source of \c a to \c n /// Change the source of \c a to \c n /// ///\note The InArcIts referencing the changed arc remain ///valid. However the ArcIts and OutArcIts are ///invalidated. /// Change the source node of an arc /// This function changes the source node of the given arc \c a to \c n. /// ///\note \c InArcIt iterators referencing the changed arc remain ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated. /// ///\warning This functionality cannot be used together with the Snapshot } /// Invert the direction of an arc. ///\note The ArcIts referencing the changed arc remain ///valid. However OutArcIts and InArcIts are ///invalidated. /// Reverse the direction of an arc. /// This function reverses the direction of the given arc. ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing ///the changed arc are invalidated. /// ///\warning This functionality cannot be used together with the Snapshot ///feature. void reverseArc(Arc e) { Node t=target(e); changeTarget(e,source(e)); changeSource(e,t); } /// Reserve memory for nodes. /// Using this function it is possible to avoid the superfluous memory /// allocation: if you know that the digraph you want to build will /// be very large (e.g. it will contain millions of nodes and/or arcs) /// then it is worth reserving space for this amount before starting /// to build the digraph. /// \sa reserveArc void reserveNode(int n) { nodes.reserve(n); }; /// Reserve memory for arcs. /// Using this function it is possible to avoid the superfluous memory /// allocation: if you know that the digraph you want to build will /// be very large (e.g. it will contain millions of nodes and/or arcs) /// then it is worth reserving space for this amount before starting /// to build the digraph. /// \sa reserveNode void reserveArc(int m) { arcs.reserve(m); }; void reverseArc(Arc a) { Node t=target(a); changeTarget(a,source(a)); changeSource(a,t); } ///Contract two nodes. ///This function contracts two nodes. ///Node \p b will be removed but instead of deleting ///incident arcs, they will be joined to \p a. ///The last parameter \p r controls whether to remove loops. \c true ///means that loops will be removed. /// ///\note The ArcIts referencing a moved arc remain ///valid. However InArcIts and OutArcIts ///may be invalidated. ///This function contracts the given two nodes. ///Node \c v is removed, but instead of deleting its ///incident arcs, they are joined to node \c u. ///If the last parameter \c r is \c true (this is the default value), ///then the newly created loops are removed. /// ///\note The moved arcs are joined to node \c u using changeSource() ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are ///invalidated for the outgoing arcs of node \c v and \c InArcIt ///iterators are invalidated for the incomming arcs of \c v. ///Moreover all iterators referencing node \c v or the removed ///loops are also invalidated. Other iterators remain valid. /// ///\warning This functionality cannot be used together with the Snapshot ///feature. void contract(Node a, Node b, bool r = true) void contract(Node u, Node v, bool r = true) { for(OutArcIt e(*this,b);e!=INVALID;) { for(OutArcIt e(*this,v);e!=INVALID;) { OutArcIt f=e; ++f; if(r && target(e)==a) erase(e); else changeSource(e,a); if(r && target(e)==u) erase(e); else changeSource(e,u); e=f; } for(InArcIt e(*this,b);e!=INVALID;) { for(InArcIt e(*this,v);e!=INVALID;) { InArcIt f=e; ++f; if(r && source(e)==a) erase(e); else changeTarget(e,a); if(r && source(e)==u) erase(e); else changeTarget(e,u); e=f; } erase(b); erase(v); } ///Split a node. ///This function splits a node. First a new node is added to the digraph, ///then the source of each outgoing arc of \c n is moved to this new node. ///If \c connect is \c true (this is the default value), then a new arc ///from \c n to the newly created node is also added. ///This function splits the given node. First, a new node is added ///to the digraph, then the source of each outgoing arc of node \c n ///is moved to this new node. ///If the second parameter \c connect is \c true (this is the default ///value), then a new arc from node \c n to the newly created node ///is also added. ///\return The newly created node. /// ///\note The ArcIts referencing a moved arc remain ///valid. However InArcIts and OutArcIts may ///be invalidated. /// ///\warning This functionality cannot be used in conjunction with the ///\note \c ArcIt and \c OutArcIt iterators referencing the outgoing ///arcs of node \c n are invalidated. Other iterators remain valid. /// ///\warning This functionality cannot be used together with the ///Snapshot feature. Node split(Node n, bool connect = true) { ///Split an arc. ///This function splits an arc. First a new node \c b is added to ///the digraph, then the original arc is re-targeted to \c ///b. Finally an arc from \c b to the original target is added. /// ///This function splits the given arc. First, a new node \c v is ///added to the digraph, then the target node of the original arc ///is set to \c v. Finally, an arc from \c v to the original target ///is added. ///\return The newly created node. /// ///\note \c InArcIt iterators referencing the original arc are ///invalidated. Other iterators remain valid. /// ///\warning This functionality cannot be used together with the ///Snapshot feature. Node split(Arc e) { Node b = addNode(); addArc(b,target(e)); changeTarget(e,b); return b; } Node split(Arc a) { Node v = addNode(); addArc(v,target(a)); changeTarget(a,v); return v; } ///Clear the digraph. ///This function erases all nodes and arcs from the digraph. /// void clear() { Parent::clear(); } /// Reserve memory for nodes. /// Using this function, it is possible to avoid superfluous memory /// allocation: if you know that the digraph you want to build will /// be large (e.g. it will contain millions of nodes and/or arcs), /// then it is worth reserving space for this amount before starting /// to build the digraph. /// \sa reserveArc() void reserveNode(int n) { nodes.reserve(n); }; /// Reserve memory for arcs. /// Using this function, it is possible to avoid superfluous memory /// allocation: if you know that the digraph you want to build will /// be large (e.g. it will contain millions of nodes and/or arcs), /// then it is worth reserving space for this amount before starting /// to build the digraph. /// \sa reserveNode() void reserveArc(int m) { arcs.reserve(m); }; /// \brief Class to make a snapshot of the digraph and restore /// restore() function. /// /// \warning Arc and node deletions and other modifications (e.g. /// contracting, splitting, reversing arcs or nodes) cannot be /// \note After a state is restored, you cannot restore a later state, /// i.e. you cannot add the removed nodes and arcs again using /// another Snapshot instance. /// /// \warning Node and arc deletions and other modifications (e.g. /// reversing, contracting, splitting arcs or nodes) cannot be /// restored. These events invalidate the snapshot. /// However the arcs and nodes that were added to the digraph after /// making the current snapshot can be removed without invalidating it. class Snapshot { protected: /// /// Default constructor. /// To actually make a snapshot you must call save(). /// You have to call save() to actually make a snapshot. Snapshot() : digraph(0), node_observer_proxy(*this), /// \brief Constructor that immediately makes a snapshot. /// /// This constructor immediately makes a snapshot of the digraph. /// \param _digraph The digraph we make a snapshot of. Snapshot(ListDigraph &_digraph) /// This constructor immediately makes a snapshot of the given digraph. Snapshot(ListDigraph &gr) : node_observer_proxy(*this), arc_observer_proxy(*this) { attach(_digraph); attach(gr); } /// \brief Make a snapshot. /// /// Make a snapshot of the digraph. /// /// This function can be called more than once. In case of a repeated /// This function makes a snapshot of the given digraph. /// It can be called more than once. In case of a repeated /// call, the previous snapshot gets lost. /// \param _digraph The digraph we make the snapshot of. void save(ListDigraph &_digraph) { void save(ListDigraph &gr) { if (attached()) { detach(); clear(); } attach(_digraph); attach(gr); } /// \brief Undo the changes until the last snapshot. // /// Undo the changes until the last snapshot created by save(). /// /// This function undos the changes until the last snapshot /// created by save() or Snapshot(ListDigraph&). void restore() { detach(); } /// \brief Gives back true when the snapshot is valid. /// \brief Returns \c true if the snapshot is valid. /// /// Gives back true when the snapshot is valid. /// This function returns \c true if the snapshot is valid. bool valid() const { return attached(); typedef ListGraphBase Graph; class Node; class Arc; class Edge; class Node { bool operator<(const Arc& arc) const {return id < arc.id;} }; ListGraphBase() ///A general undirected graph structure. ///\ref ListGraph is a simple and fast undirected graph ///implementation based on static linked lists that are stored in ///\ref ListGraph is a versatile and fast undirected graph ///implementation based on linked lists that are stored in ///\c std::vector structures. /// ///It conforms to the \ref concepts::Graph "Graph concept" and it ///also provides several useful additional functionalities. ///Most of the member functions and nested classes are documented ///This type fully conforms to the \ref concepts::Graph "Graph concept" ///and it also provides several useful additional functionalities. ///Most of its member functions and nested classes are documented ///only in the concept class. /// ///\sa concepts::Graph ///\sa ListDigraph class ListGraph : public ExtendedListGraphBase { typedef ExtendedListGraphBase Parent; private: ///ListGraph is \e not copy constructible. Use copyGraph() instead. ///ListGraph is \e not copy constructible. Use copyGraph() instead. /// /// Graphs are \e not copy constructible. Use GraphCopy instead. ListGraph(const ListGraph &) :ExtendedListGraphBase()  {}; ///\brief Assignment of ListGraph to another one is \e not allowed. ///Use copyGraph() instead. ///Assignment of ListGraph to another one is \e not allowed. ///Use copyGraph() instead. /// \brief Assignment of a graph to another one is \e not allowed. /// Use GraphCopy instead. void operator=(const ListGraph &) {} public: /// \brief Add a new node to the graph. /// /// Add a new node to the graph. /// This function adds a new node to the graph. /// \return The new node. Node addNode() { return Parent::addNode(); } /// \brief Add a new edge to the graph. /// /// Add a new edge to the graph with source node \c s /// and target node \c t. /// This function adds a new edge to the graph between nodes /// \c u and \c v with inherent orientation from node \c u to /// node \c v. /// \return The new edge. Edge addEdge(const Node& s, const Node& t) { return Parent::addEdge(s, t); } /// \brief Erase a node from the graph. /// /// Erase a node from the graph. /// void erase(const Node& n) { Parent::erase(n); } /// \brief Erase an edge from the graph. /// /// Erase an edge from the graph. /// void erase(const Edge& e) { Parent::erase(e); } Edge addEdge(Node u, Node v) { return Parent::addEdge(u, v); } ///\brief Erase a node from the graph. /// /// This function erases the given node from the graph. void erase(Node n) { Parent::erase(n); } ///\brief Erase an edge from the graph. /// /// This function erases the given edge from the graph. void erase(Edge e) { Parent::erase(e); } /// Node validity check /// This function gives back true if the given node is valid, /// ie. it is a real node of the graph. /// /// \warning A Node pointing to a removed item /// could become valid again later if new nodes are /// This function gives back \c true if the given node is valid, /// i.e. it is a real node of the graph. /// /// \warning A removed node could become valid again if new nodes are /// added to the graph. bool valid(Node n) const { return Parent::valid(n); } /// Edge validity check /// This function gives back \c true if the given edge is valid, /// i.e. it is a real edge of the graph. /// /// \warning A removed edge could become valid again if new edges are /// added to the graph. bool valid(Edge e) const { return Parent::valid(e); } /// Arc validity check /// This function gives back true if the given arc is valid, /// ie. it is a real arc of the graph. /// /// \warning An Arc pointing to a removed item /// could become valid again later if new edges are /// This function gives back \c true if the given arc is valid, /// i.e. it is a real arc of the graph. /// /// \warning A removed arc could become valid again if new edges are /// added to the graph. bool valid(Arc a) const { return Parent::valid(a); } /// Edge validity check /// This function gives back true if the given edge is valid, /// ie. it is a real arc of the graph. /// /// \warning A Edge pointing to a removed item /// could become valid again later if new edges are /// added to the graph. bool valid(Edge e) const { return Parent::valid(e); } /// \brief Change the end \c u of \c e to \c n /// /// This function changes the end \c u of \c e to node \c n. /// ///\note The EdgeIts and ArcIts referencing the ///changed edge are invalidated and if the changed node is the ///base node of an iterator then this iterator is also ///invalidated. /// \brief Change the first node of an edge. /// /// This function changes the first node of the given edge \c e to \c n. /// ///\note \c EdgeIt and \c ArcIt iterators referencing the ///changed edge are invalidated and all other iterators whose ///base node is the changed node are also invalidated. /// ///\warning This functionality cannot be used together with the Parent::changeU(e,n); } /// \brief Change the end \c v of \c e to \c n /// /// This function changes the end \c v of \c e to \c n. /// ///\note The EdgeIts referencing the changed edge remain ///valid, however ArcIts and if the changed node is the ///base node of an iterator then this iterator is invalidated. /// \brief Change the second node of an edge. /// /// This function changes the second node of the given edge \c e to \c n. /// ///\note \c EdgeIt iterators referencing the changed edge remain ///valid, however \c ArcIt iterators referencing the changed edge and ///all other iterators whose base node is the changed node are also ///invalidated. /// ///\warning This functionality cannot be used together with the Parent::changeV(e,n); } /// \brief Contract two nodes. /// /// This function contracts two nodes. /// Node \p b will be removed but instead of deleting /// its neighboring arcs, they will be joined to \p a. /// The last parameter \p r controls whether to remove loops. \c true /// means that loops will be removed. /// /// \note The ArcIts referencing a moved arc remain /// valid. /// This function contracts the given two nodes. /// Node \c b is removed, but instead of deleting /// its incident edges, they are joined to node \c a. /// If the last parameter \c r is \c true (this is the default value), /// then the newly created loops are removed. /// /// \note The moved edges are joined to node \c a using changeU() /// or changeV(), thus all edge and arc iterators whose base node is /// \c b are invalidated. /// Moreover all iterators referencing node \c b or the removed /// loops are also invalidated. Other iterators remain valid. /// ///\warning This functionality cannot be used together with the } ///Clear the graph. ///This function erases all nodes and arcs from the graph. /// void clear() { Parent::clear(); } /// \brief Class to make a snapshot of the graph and restore /// using the restore() function. /// /// \warning Edge and node deletions and other modifications /// (e.g. changing nodes of edges, contracting nodes) cannot be /// restored. These events invalidate the snapshot. /// \note After a state is restored, you cannot restore a later state, /// i.e. you cannot add the removed nodes and edges again using /// another Snapshot instance. /// /// \warning Node and edge deletions and other modifications /// (e.g. changing the end-nodes of edges or contracting nodes) /// cannot be restored. These events invalidate the snapshot. /// However the edges and nodes that were added to the graph after /// making the current snapshot can be removed without invalidating it. class Snapshot { protected: /// /// Default constructor. /// To actually make a snapshot you must call save(). /// You have to call save() to actually make a snapshot. Snapshot() : graph(0), node_observer_proxy(*this), /// \brief Constructor that immediately makes a snapshot. /// /// This constructor immediately makes a snapshot of the graph. /// \param _graph The graph we make a snapshot of. Snapshot(ListGraph &_graph) /// This constructor immediately makes a snapshot of the given graph. Snapshot(ListGraph &gr) : node_observer_proxy(*this), edge_observer_proxy(*this) { attach(_graph); attach(gr); } /// \brief Make a snapshot. /// /// Make a snapshot of the graph. /// /// This function can be called more than once. In case of a repeated /// This function makes a snapshot of the given graph. /// It can be called more than once. In case of a repeated /// call, the previous snapshot gets lost. /// \param _graph The graph we make the snapshot of. void save(ListGraph &_graph) { void save(ListGraph &gr) { if (attached()) { detach(); clear(); } attach(_graph); attach(gr); } /// \brief Undo the changes until the last snapshot. // /// Undo the changes until the last snapshot created by save(). /// /// This function undos the changes until the last snapshot /// created by save() or Snapshot(ListGraph&). void restore() { detach(); } /// \brief Gives back true when the snapshot is valid. /// \brief Returns \c true if the snapshot is valid. /// /// Gives back true when the snapshot is valid. /// This function returns \c true if the snapshot is valid. bool valid() const { return attached();
• lemon/smart_graph.h

 r617 class SmartDigraph; ///Base of SmartDigraph ///Base of SmartDigraph /// class SmartDigraphBase { protected: ///\brief A smart directed graph class. /// ///This is a simple and fast digraph implementation. ///It is also quite memory efficient, but at the price ///that it does support only limited (only stack-like) ///node and arc deletions. ///It fully conforms to the \ref concepts::Digraph "Digraph concept". ///\ref SmartDigraph is a simple and fast digraph implementation. ///It is also quite memory efficient but at the price ///that it does not support node and arc deletion ///(except for the Snapshot feature). /// ///\sa concepts::Digraph. ///This type fully conforms to the \ref concepts::Digraph "Digraph concept" ///and it also provides some additional functionalities. ///Most of its member functions and nested classes are documented ///only in the concept class. /// ///\sa concepts::Digraph ///\sa SmartGraph class SmartDigraph : public ExtendedSmartDigraphBase { typedef ExtendedSmartDigraphBase Parent; private: ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead. ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead. /// /// Digraphs are \e not copy constructible. Use DigraphCopy instead. SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {}; ///\brief Assignment of SmartDigraph to another one is \e not allowed. ///Use DigraphCopy() instead. ///Assignment of SmartDigraph to another one is \e not allowed. ///Use DigraphCopy() instead. /// \brief Assignment of a digraph to another one is \e not allowed. /// Use DigraphCopy instead. void operator=(const SmartDigraph &) {} ///Add a new node to the digraph. /// Add a new node to the digraph. /// \return The new node. ///This function adds a new node to the digraph. ///\return The new node. Node addNode() { return Parent::addNode(); } ///Add a new arc to the digraph. ///Add a new arc to the digraph with source node \c s ///This function adds a new arc to the digraph with source node \c s ///and target node \c t. ///\return The new arc. Arc addArc(const Node& s, const Node& t) { Arc addArc(Node s, Node t) { return Parent::addArc(s, t); } /// \brief Using this it is possible to avoid the superfluous memory /// allocation. /// Using this it is possible to avoid the superfluous memory /// allocation: if you know that the digraph you want to build will /// be very large (e.g. it will contain millions of nodes and/or arcs) /// then it is worth reserving space for this amount before starting /// to build the digraph. /// \sa reserveArc void reserveNode(int n) { nodes.reserve(n); }; /// \brief Using this it is possible to avoid the superfluous memory /// allocation. /// Using this it is possible to avoid the superfluous memory /// allocation: if you know that the digraph you want to build will /// be very large (e.g. it will contain millions of nodes and/or arcs) /// then it is worth reserving space for this amount before starting /// to build the digraph. /// \sa reserveNode void reserveArc(int m) { arcs.reserve(m); }; /// \brief Node validity check /// /// This function gives back true if the given node is valid, /// ie. it is a real node of the graph. /// This function gives back \c true if the given node is valid, /// i.e. it is a real node of the digraph. /// /// \warning A removed node (using Snapshot) could become valid again /// when new nodes are added to the graph. /// if new nodes are added to the digraph. bool valid(Node n) const { return Parent::valid(n); } /// \brief Arc validity check /// /// This function gives back true if the given arc is valid, /// ie. it is a real arc of the graph. /// This function gives back \c true if the given arc is valid, /// i.e. it is a real arc of the digraph. /// /// \warning A removed arc (using Snapshot) could become valid again /// when new arcs are added to the graph. /// if new arcs are added to the graph. bool valid(Arc a) const { return Parent::valid(a); } ///Clear the digraph. ///Erase all the nodes and arcs from the digraph. /// void clear() { Parent::clear(); } ///Split a node. ///This function splits a node. First a new node is added to the digraph, ///then the source of each outgoing arc of \c n is moved to this new node. ///If \c connect is \c true (this is the default value), then a new arc ///from \c n to the newly created node is also added. ///This function splits the given node. First, a new node is added ///to the digraph, then the source of each outgoing arc of node \c n ///is moved to this new node. ///If the second parameter \c connect is \c true (this is the default ///value), then a new arc from node \c n to the newly created node ///is also added. ///\return The newly created node. /// ///\note The Arcs ///referencing a moved arc remain ///valid. However InArc's and OutArc's ///may be invalidated. ///\note All iterators remain valid. /// ///\warning This functionality cannot be used together with the Snapshot ///feature. } ///Clear the digraph. ///This function erases all nodes and arcs from the digraph. /// void clear() { Parent::clear(); } /// Reserve memory for nodes. /// Using this function, it is possible to avoid superfluous memory /// allocation: if you know that the digraph you want to build will /// be large (e.g. it will contain millions of nodes and/or arcs), /// then it is worth reserving space for this amount before starting /// to build the digraph. /// \sa reserveArc() void reserveNode(int n) { nodes.reserve(n); }; /// Reserve memory for arcs. /// Using this function, it is possible to avoid superfluous memory /// allocation: if you know that the digraph you want to build will /// be large (e.g. it will contain millions of nodes and/or arcs), /// then it is worth reserving space for this amount before starting /// to build the digraph. /// \sa reserveNode() void reserveArc(int m) { arcs.reserve(m); }; public: public: ///Class to make a snapshot of the digraph and to restrore to it later. ///Class to make a snapshot of the digraph and to restrore to it later. ///Class to make a snapshot of the digraph and to restore it later. ///Class to make a snapshot of the digraph and to restore it later. /// ///The newly added nodes and arcs can be removed using the ///restore() function. ///\note After you restore a state, you cannot restore ///a later state, in other word you cannot add again the arcs deleted ///by restore() using another one Snapshot instance. /// ///\warning If you do not use correctly the snapshot that can cause ///either broken program, invalid state of the digraph, valid but ///not the restored digraph or no change. Because the runtime performance ///the validity of the snapshot is not stored. ///restore() function. This is the only way for deleting nodes and/or ///arcs from a SmartDigraph structure. /// ///\note After a state is restored, you cannot restore a later state, ///i.e. you cannot add the removed nodes and arcs again using ///another Snapshot instance. /// ///\warning Node splitting cannot be restored. ///\warning The validity of the snapshot is not stored due to ///performance reasons. If you do not use the snapshot correctly, ///it can cause broken program, invalid or not restored state of ///the digraph or no change. class Snapshot { ///Default constructor. ///To actually make a snapshot you must call save(). /// ///You have to call save() to actually make a snapshot. Snapshot() : _graph(0) {} ///Constructor that immediately makes a snapshot ///This constructor immediately makes a snapshot of the digraph. ///\param graph The digraph we make a snapshot of. Snapshot(SmartDigraph &graph) : _graph(&graph) { ///This constructor immediately makes a snapshot of the given digraph. /// Snapshot(SmartDigraph &gr) : _graph(&gr) { node_num=_graph->nodes.size(); arc_num=_graph->arcs.size(); ///Make a snapshot. ///Make a snapshot of the digraph. /// ///This function can be called more than once. In case of a repeated ///This function makes a snapshot of the given digraph. ///It can be called more than once. In case of a repeated ///call, the previous snapshot gets lost. ///\param graph The digraph we make the snapshot of. void save(SmartDigraph &graph) { _graph=&graph; void save(SmartDigraph &gr) { _graph=&gr; node_num=_graph->nodes.size(); arc_num=_graph->arcs.size(); ///Undo the changes until a snapshot. ///Undo the changes until a snapshot created by save(). /// ///\note After you restored a state, you cannot restore ///a later state, in other word you cannot add again the arcs deleted ///by restore(). ///This function undos the changes until the last snapshot ///created by save() or Snapshot(SmartDigraph&). void restore() { /// \brief A smart undirected graph class. /// /// This is a simple and fast graph implementation. /// It is also quite memory efficient, but at the price /// that it does support only limited (only stack-like) /// node and arc deletions. /// It fully conforms to the \ref concepts::Graph "Graph concept". /// \ref SmartGraph is a simple and fast graph implementation. /// It is also quite memory efficient but at the price /// that it does not support node and edge deletion /// (except for the Snapshot feature). /// /// \sa concepts::Graph. /// This type fully conforms to the \ref concepts::Graph "Graph concept" /// and it also provides some additional functionalities. /// Most of its member functions and nested classes are documented /// only in the concept class. /// /// \sa concepts::Graph /// \sa SmartDigraph class SmartGraph : public ExtendedSmartGraphBase { typedef ExtendedSmartGraphBase Parent; private: ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. /// /// Graphs are \e not copy constructible. Use GraphCopy instead. SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {}; ///\brief Assignment of SmartGraph to another one is \e not allowed. ///Use GraphCopy() instead. ///Assignment of SmartGraph to another one is \e not allowed. ///Use GraphCopy() instead. /// \brief Assignment of a graph to another one is \e not allowed. /// Use GraphCopy instead. void operator=(const SmartGraph &) {} SmartGraph() {} ///Add a new node to the graph. /// Add a new node to the graph. /// \brief Add a new node to the graph. /// /// This function adds a new node to the graph. /// \return The new node. Node addNode() { return Parent::addNode(); } ///Add a new edge to the graph. ///Add a new edge to the graph with node \c s ///and \c t. ///\return The new edge. Edge addEdge(const Node& s, const Node& t) { return Parent::addEdge(s, t); /// \brief Add a new edge to the graph. /// /// This function adds a new edge to the graph between nodes /// \c u and \c v with inherent orientation from node \c u to /// node \c v. /// \return The new edge. Edge addEdge(Node u, Node v) { return Parent::addEdge(u, v); } /// \brief Node validity check /// /// This function gives back true if the given node is valid, /// ie. it is a real node of the graph. /// This function gives back \c true if the given node is valid, /// i.e. it is a real node of the graph. /// /// \warning A removed node (using Snapshot) could become valid again /// when new nodes are added to the graph. /// if new nodes are added to the graph. bool valid(Node n) const { return Parent::valid(n); } /// \brief Edge validity check /// /// This function gives back \c true if the given edge is valid, /// i.e. it is a real edge of the graph. /// /// \warning A removed edge (using Snapshot) could become valid again /// if new edges are added to the graph. bool valid(Edge e) const { return Parent::valid(e); } /// \brief Arc validity check /// /// This function gives back true if the given arc is valid, /// ie. it is a real arc of the graph. /// This function gives back \c true if the given arc is valid, /// i.e. it is a real arc of the graph. /// /// \warning A removed arc (using Snapshot) could become valid again /// when new edges are added to the graph. /// if new edges are added to the graph. bool valid(Arc a) const { return Parent::valid(a); } /// \brief Edge validity check /// /// This function gives back true if the given edge is valid, /// ie. it is a real edge of the graph. /// /// \warning A removed edge (using Snapshot) could become valid again /// when new edges are added to the graph. bool valid(Edge e) const { return Parent::valid(e); } ///Clear the graph. ///Erase all the nodes and edges from the graph. ///This function erases all nodes and arcs from the graph. /// void clear() { public: ///Class to make a snapshot of the digraph and to restrore to it later. ///Class to make a snapshot of the digraph and to restrore to it later. /// ///The newly added nodes and arcs can be removed using the ///restore() function. /// ///\note After you restore a state, you cannot restore ///a later state, in other word you cannot add again the arcs deleted ///by restore() using another one Snapshot instance. /// ///\warning If you do not use correctly the snapshot that can cause ///either broken program, invalid state of the digraph, valid but ///not the restored digraph or no change. Because the runtime performance ///the validity of the snapshot is not stored. ///Class to make a snapshot of the graph and to restore it later. ///Class to make a snapshot of the graph and to restore it later. /// ///The newly added nodes and edges can be removed using the ///restore() function. This is the only way for deleting nodes and/or ///edges from a SmartGraph structure. /// ///\note After a state is restored, you cannot restore a later state, ///i.e. you cannot add the removed nodes and edges again using ///another Snapshot instance. /// ///\warning The validity of the snapshot is not stored due to ///performance reasons. If you do not use the snapshot correctly, ///it can cause broken program, invalid or not restored state of ///the graph or no change. class Snapshot { ///Default constructor. ///To actually make a snapshot you must call save(). /// ///You have to call save() to actually make a snapshot. Snapshot() : _graph(0) {} ///Constructor that immediately makes a snapshot ///This constructor immediately makes a snapshot of the digraph. ///\param graph The digraph we make a snapshot of. Snapshot(SmartGraph &graph) { graph.saveSnapshot(*this); /// This constructor immediately makes a snapshot of the given graph. /// Snapshot(SmartGraph &gr) { gr.saveSnapshot(*this); } ///Make a snapshot. ///Make a snapshot of the graph. /// ///This function can be called more than once. In case of a repeated ///This function makes a snapshot of the given graph. ///It can be called more than once. In case of a repeated ///call, the previous snapshot gets lost. ///\param graph The digraph we make the snapshot of. void save(SmartGraph &graph) void save(SmartGraph &gr) { graph.saveSnapshot(*this); } ///Undo the changes until a snapshot. ///Undo the changes until a snapshot created by save(). /// ///\note After you restored a state, you cannot restore ///a later state, in other word you cannot add again the arcs deleted ///by restore(). gr.saveSnapshot(*this); } ///Undo the changes until the last snapshot. ///This function undos the changes until the last snapshot ///created by save() or Snapshot(SmartGraph&). void restore() {
Note: See TracChangeset for help on using the changeset viewer.