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::vector structures.

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

ListDigraph

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 u and v with inherent orientation from node u to node v.

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 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.

inline bool valid( Edge e ) const

Edge validity check.

This function gives back 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.

inline bool valid( Arc a ) const

Arc validity check.

This function gives back 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.

inline void changeRed( Edge e , RedNode n )

Change the red node of an edge.

This function changes the red node of the given edge e to n.

Note

EdgeIt and 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 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 e to n.

Note

EdgeIt iterators referencing the changed edge remain valid, but 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 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

reserveEdge()

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

reserveNode()

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()

Default constructor. You have to call save() to actually make a snapshot.

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 true if the snapshot is valid.

This function returns true if 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

Public Functions

inline NodeObserverProxy( Snapshot & _snapshot )

Protected Functions

inline virtual void add( const Node & node )
inline virtual void add( const std::vector< Node > & nodes )
inline virtual void erase( const Node & node )
inline virtual void erase( const std::vector< Node > & nodes )
inline virtual void build()
inline virtual void clear()

Protected Attributes

Snapshot & snapshot
class EdgeObserverProxy : public ObserverBase

Public Functions

inline EdgeObserverProxy( Snapshot & _snapshot )

Protected Functions

inline virtual void add( const Edge & edge )
inline virtual void add( const std::vector< Edge > & edges )
inline virtual void erase( const Edge & edge )
inline virtual void erase( const std::vector< Edge > & edges )
inline virtual void build()
inline virtual void clear()

Protected Attributes

Snapshot & snapshot