SmartGraph Class Reference
[Graph Structures]

---

Detailed Description

This is a simple and fast graph implementation. It is also quite memory efficient, but at the price that it does support only limited (only stack-like) node and edge deletions. It conforms to the Graph concept with an important extra feature that its maps are real reference maps.

See also:

concepts::Graph.

Author:

Alpar Juttner

#include <lemon/smart_graph.h>

Inheritance diagram for SmartGraph:

[legend]

List of all members.

Classes
class	Snapshot
	Class to make a snapshot of the graph and to restrore to it later. More...
Public Member Functions
	SmartGraph ()
Node	addNode ()
	Add a new node to the graph.
Edge	addEdge (const Node &s, const Node &t)
	Add a new edge to the graph.
void	reserveNode (int n)
	Using this it is possible to avoid the superfluous memory allocation.
void	reserveEdge (int m)
	Using this it is possible to avoid the superfluous memory allocation.
void	clear ()
	Clear the graph.
Node	split (Node n, bool connect=true)
	Split a node.
Private Member Functions
	SmartGraph (const SmartGraph &)
void	operator= (const SmartGraph &)

---

Constructor & Destructor Documentation

SmartGraph

(

const SmartGraph &

)

[inline, private]

SmartGraph is not copy constructible. Use GraphCopy() instead.

SmartGraph

(

)

[inline]

Constructor.

---

Member Function Documentation

void operator=

(

const SmartGraph &

)

[inline, private]

Assignment of SmartGraph to another one is not allowed. Use GraphCopy() instead.

Node addNode

(

)

[inline]

Returns:

the new node.

Reimplemented from GraphExtender< Base >.

Edge addEdge	(	const Node &	s,
		const Node &	t
	)			[inline]

Add a new edge to the graph with source node s and target node t.

Returns:

the new edge.

Reimplemented from GraphExtender< Base >.

void reserveNode

(

int

n

)

[inline]

Using this it is possible to avoid the superfluous memory allocation: if you know that the graph you want to build will be very 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

void reserveEdge

(

int

m

)

[inline]

Using this it is possible to avoid the superfluous memory allocation: if you know that the graph you want to build will be very 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

void clear

(

)

[inline]

Erase all the nodes and edges from the graph.

Reimplemented from GraphExtender< Base >.

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

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

Returns:

The newly created node.

Note:

The Edges referencing a moved edge remain valid. However InEdge's and OutEdge's may be invalidated.

Warning:

This functionality cannot be used together with the Snapshot feature.

Todo:

It could be implemented in a bit faster way.