ListBpGraph
Declared in lemon/list_graph.h, in the group Graph Structures; the same class on the Doxygen site.
-
class ListBpGraph : public BpGraphExtender< ListBpGraphBase >
A general undirected graph structure.
ListBpGraph is a versatile and fast undirected graph implementation based on linked lists that are stored in
std::vectorstructures.This type fully conforms to the BpGraph 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 ListBpGraph()
Constructor.
-
inline RedNode addRedNode()
Add a new red node to the graph.
This function adds a red new node to the graph.
- Returns:
The new node.
-
inline BlueNode addBlueNode()
Add a new blue node to the graph.
This function adds a blue new node to the graph.
- Returns:
The new node.
-
inline Edge addEdge( RedNode u , BlueNode 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 Edge addEdge( BlueNode v , RedNode u )
-
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 changeRed( Edge e , RedNode n )
Change the red node of an edge.
This function changes the red 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 changeBlue( Edge e , BlueNode n )
Change the blue node of an edge.
This function changes the blue 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 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( ListBpGraph & gr )
Constructor that immediately makes a snapshot.
This constructor immediately makes a snapshot of the given graph.
-
inline void save( ListBpGraph & 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(ListBpGraph&).
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 attach( ListBpGraph & _graph )
-
inline void detach()
-
inline bool attached() const
-
inline void clear()
Protected Attributes
-
ListBpGraph * graph
-
NodeObserverProxy node_observer_proxy
-
EdgeObserverProxy edge_observer_proxy
-
std::list< Node > added_nodes
-
std::list< Edge > added_edges
-
class NodeObserverProxy : public AlterationNotifier< BpGraphExtender , Node >::ObserverBase
-
class EdgeObserverProxy : public ObserverBase
-
inline Snapshot( ListBpGraph & gr )
-
typedef Parent::IncEdgeIt IncEdgeIt