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 lemon::DigraphExtender< SmartDigraphBase >.

List of all members.

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 &

)

[inline, private]

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

SmartDigraph

(

)

[inline]

Constructor.

---

Member Function Documentation

void operator=

(

const SmartDigraph &

)

[inline, private]

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.