SmartBpGraph

Declared in lemon/smart_graph.h, in the group Graph Structures; the same class on the Doxygen site.

class SmartBpGraph : public BpGraphExtender< SmartBpGraphBase >

A smart undirected bipartite graph class.

SmartBpGraph is a simple and fast bipartite 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).

This type fully conforms to the BpGraph concept and it also provides some additional functionalities. Most of its member functions and nested classes are documented only in the concept class.

This class provides constant time counting for nodes, edges and arcs.

See also

SmartGraph

Public Functions

inline SmartBpGraph()

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 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 (using Snapshot) 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 (using Snapshot) 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 (using Snapshot) could become valid again if new edges are added to the graph.

inline void clear()

Clear the graph.

This function erases all nodes and arcs from the graph.

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

Protected Functions

inline void saveSnapshot( Snapshot & s )
inline void restoreSnapshot( const Snapshot & s )
class Snapshot

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

Public Functions

inline Snapshot()

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

inline Snapshot( SmartBpGraph & gr )

Constructor that immediately makes a snapshot.

This constructor immediately makes a snapshot of the given graph.

inline void save( SmartBpGraph & 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(SmartBpGraph&).

Protected Attributes

unsigned int node_num
unsigned int arc_num

Friends

friend class SmartBpGraph