SmartDigraph

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

class SmartDigraph : public DigraphExtender< SmartDigraphBase >

A smart directed graph class.

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

This type fully conforms to the Digraph 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 and arcs.

See also

SmartGraph

Public Functions

inline SmartDigraph()

Constructor.

inline Node addNode()

Add a new node to the digraph.

This function adds a new node to the digraph.

Returns:

The new node.

inline Arc addArc( Node s , Node t )

Add a new arc to the digraph.

This function adds a new arc to the digraph with source node s and target node t.

Returns:

The new arc.

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

Warning

A removed node (using Snapshot) could become valid again if new nodes are added to the digraph.

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

Warning

A removed arc (using Snapshot) could become valid again if new arcs are added to the graph.

inline Node split( Node n , bool connect = true )

Split a node.

This function splits the given node. First, a new node is added to the digraph, then the source of each outgoing arc of node n is moved to this new node. If the second parameter connect is true (this is the default value), then a new arc from node n to the newly created node is also added.

Note

All iterators remain valid.

Warning

This functionality cannot be used together with the Snapshot feature.

Returns:

The newly created node.

inline void clear()

Clear the digraph.

This function erases all nodes and arcs from the digraph.

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

See also

reserveArc()

inline void reserveArc( int m )

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.

See also

reserveNode()

Protected Functions

inline void restoreSnapshot( const Snapshot & s )
class Snapshot

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

Public Functions

inline Snapshot()

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

inline Snapshot( SmartDigraph & gr )

Constructor that immediately makes a snapshot.

This constructor immediately makes a snapshot of the given digraph.

inline void save( SmartDigraph & gr )

Make a snapshot.

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.

inline void restore()

Undo the changes until a snapshot.

This function undos the changes until the last snapshot created by save() or Snapshot(SmartDigraph&).

Protected Attributes

unsigned int node_num
unsigned int arc_num

Friends

friend class SmartDigraph