ListGraph
Declared in lemon/list_graph.h, in the group Graph Structures; the same class on the Doxygen site.
-
class ListGraph : public GraphExtender< ListGraphBase >
A general undirected graph structure.
ListGraph is a versatile and fast undirected graph implementation based on linked lists that are stored in
std::vectorstructures.This type fully conforms to the 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.
This class provides only linear time counting for nodes, edges and arcs.
See also
See also
Public Types
-
typedef Parent::IncEdgeIt IncEdgeIt
Public Functions
-
inline ListGraph()
Constructor.
-
inline Node addNode()
Add a new node to the graph.
This function adds a new node to the graph.
- Returns:
The new node.
-
inline Edge addEdge( Node u , Node v )
Add a new edge to the graph.
This function adds a new edge to the graph between nodes
uandvwith inherent orientation from nodeuto nodev.- Returns:
The new edge.
-
inline void erase( Node n )
Erase a node from the graph.
This function erases the given node along with its incident arcs from the graph.
Note
All iterators referencing the removed node or the incident edges are invalidated, of course.
-
inline void erase( Edge e )
Erase an edge from the graph.
This function erases the given edge from the graph.
Note
All iterators referencing the removed edge are invalidated, of course.
-
inline bool valid( Node n ) const
Node validity check.
This function gives back
trueif 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.
-
inline bool valid( Edge e ) const
Edge validity check.
This function gives back
trueif 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.
-
inline bool valid( Arc a ) const
Arc validity check.
This function gives back
trueif 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.
-
inline void changeU( Edge e , Node n )
Change the first node of an edge.
This function changes the first node of the given edge
eton.Note
EdgeItandArcItiterators 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 Snapshot feature.
-
inline void changeV( Edge e , Node n )
Change the second node of an edge.
This function changes the second node of the given edge
eton.Note
EdgeItiterators referencing the changed edge remain valid, butArcItiterators 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 Snapshot feature.
-
inline void contract( Node a , Node b , bool r = true )
Contract two nodes.
This function contracts the given two nodes. Node
bis removed, but instead of deleting its incident edges, they are joined to nodea. If the last parameterristrue(this is the default value), then the newly created loops are removed.Note
The moved edges are joined to node
ausing changeU() or changeV(), thus all edge and arc iterators whose base node isbare invalidated. Moreover all iterators referencing nodebor the removed loops are also invalidated. Other iterators remain valid.Warning
This functionality cannot be used together with the Snapshot feature.
-
inline void clear()
Clear the graph.
This function erases all nodes and arcs from the graph.
Note
All iterators of the graph are invalidated, of course.
-
inline void reserveNode( int n )
Reserve memory for nodes.
Using this function, it is possible to avoid superfluous memory allocation: if you know that the graph you want to build will be large (e.g. it will contain millions of nodes and/or edges), then it is worth reserving space for this amount before starting to build the graph.
See also
-
inline void reserveEdge( int m )
Reserve memory for edges.
Using this function, it is possible to avoid superfluous memory allocation: if you know that the graph you want to build will be large (e.g. it will contain millions of nodes and/or edges), then it is worth reserving space for this amount before starting to build the graph.
See also
-
class Snapshot
Class to make a snapshot of the graph and restore it later.
The newly added nodes and edges can be removed using the restore() function.
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.
Public Functions
-
inline Snapshot( ListGraph & gr )
Constructor that immediately makes a snapshot.
This constructor immediately makes a snapshot of the given graph.
-
inline void save( ListGraph & gr )
Make a snapshot.
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.
-
inline void restore()
Undo the changes until the last snapshot.
This function undos the changes until the last snapshot created by save() or Snapshot(ListGraph&).
Warning
This method invalidates the snapshot, i.e. repeated restoring is not supported unless you call save() again.
-
inline bool valid() const
Returns
trueif the snapshot is valid.This function returns
trueif the snapshot is valid.
Protected Types
-
typedef Parent::NodeNotifier NodeNotifier
Protected Functions
-
inline void addNode( const Node & node )
-
inline void eraseNode( const Node & node )
-
inline void addEdge( const Edge & edge )
-
inline void eraseEdge( const Edge & edge )
-
inline void detach()
-
inline bool attached() const
-
inline void clear()
Protected Attributes
-
NodeObserverProxy node_observer_proxy
-
EdgeObserverProxy edge_observer_proxy
-
std::list< Node > added_nodes
-
std::list< Edge > added_edges
-
class NodeObserverProxy : public AlterationNotifier< GraphExtender , Node >::ObserverBase
-
class EdgeObserverProxy : public ObserverBase
-
inline Snapshot( ListGraph & gr )
-
typedef Parent::IncEdgeIt IncEdgeIt