All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
List of all members | Classes | Public Member Functions | Private Member Functions
SmartDigraph Class Reference

Detailed Description

This is a simple and fast digraph implementation. It is also quite memory efficient, but at the price that it does support only limited (only stack-like) node and arc deletions. It fully conforms to the Digraph concept.

See Also
concepts::Digraph.

#include <lemon/smart_graph.h>

Inherits DigraphExtender< Base >.

Classes

class  Snapshot
 Class to make a snapshot of the digraph and to restrore to it later. More...
 

Public Member Functions

 SmartDigraph ()
 
Node addNode ()
 Add a new node to the digraph.
 
Arc addArc (const Node &s, const Node &t)
 Add a new arc to the digraph.
 
void reserveNode (int n)
 Using this it is possible to avoid the superfluous memory allocation.
 
void reserveArc (int m)
 Using this it is possible to avoid the superfluous memory allocation.
 
bool valid (Node n) const
 Node validity check.
 
bool valid (Arc a) const
 Arc validity check.
 
void clear ()
 Clear the digraph.
 
Node split (Node n, bool connect=true)
 Split a node.
 

Private Member Functions

 SmartDigraph (const SmartDigraph &)
 
void operator= (const SmartDigraph &)
 

Constructor & Destructor Documentation

SmartDigraph ( const SmartDigraph )
inlineprivate

SmartDigraph is not copy constructible. Use DigraphCopy() instead.

SmartDigraph ( )
inline

Constructor.

Member Function Documentation

void operator= ( const SmartDigraph )
inlineprivate

Assignment of SmartDigraph to another one is not allowed. Use DigraphCopy() instead.

Node addNode ( )
inline

Add a new node to the digraph.

Returns
The new node.
Arc addArc ( const Node &  s,
const Node &  t 
)
inline

Add a new arc to the digraph with source node s and target node t.

Returns
The new arc.
void reserveNode ( int  n)
inline

Using this it is possible to avoid the superfluous memory allocation: if you know that the digraph you want to build will be very 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
void reserveArc ( int  m)
inline

Using this it is possible to avoid the superfluous memory allocation: if you know that the digraph you want to build will be very 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
bool valid ( Node  n) const
inline

This function gives back true if the given node is valid, ie. it is a real node of the graph.

Warning
A removed node (using Snapshot) could become valid again when new nodes are added to the graph.
bool valid ( Arc  a) const
inline

This function gives back true if the given arc is valid, ie. it is a real arc of the graph.

Warning
A removed arc (using Snapshot) could become valid again when new arcs are added to the graph.
void clear ( )
inline

Erase all the nodes and arcs from the digraph.

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

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

Returns
The newly created node.
Note
The Arcs referencing a moved arc remain valid. However InArc's and OutArc's may be invalidated.
Warning
This functionality cannot be used together with the Snapshot feature.