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.

Detailed Description

Classes

Public Member Functions

Private Member Functions

Constructor & Destructor Documentation

Member Function Documentation