ListGraph Class Reference
[Graph Structures]

---

Detailed Description

This is a simple and fast graph implementation.

It conforms to the Graph concept and it also provides several additional useful extra functionalities. The most of the member functions and nested classes are documented only in the concept class.

An important extra feature of this graph implementation is that its maps are real reference maps.

See also:

concepts::Graph.

#include <lemon/list_graph.h>

Inheritance diagram for ListGraph:

[legend]

List of all members.

Classes
class	Snapshot
	Class to make a snapshot of the graph and restore to it later. More...
Public Member Functions
	ListGraph ()
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	changeTarget (Edge e, Node n)
	Changes the target of e to n.
void	changeSource (Edge e, Node n)
	Changes the source of e to n.
void	reverseEdge (Edge e)
	Invert the direction of an edge.
void	reserveNode (int n)
void	reserveEdge (int m)
	Using this it is possible to avoid the superfluous memory allocation.
void	contract (Node a, Node b, bool r=true)
	Contract two nodes.
Node	split (Node n, bool connect=true)
	Split a node.
Node	split (Edge e)
	Split an edge.
Private Member Functions
	ListGraph (const ListGraph &)
void	operator= (const ListGraph &)

---

Constructor & Destructor Documentation

ListGraph

(

const ListGraph &

)

[inline, private]

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

ListGraph

(

)

[inline]

Constructor.

---

Member Function Documentation

void operator=

(

const ListGraph &

)

[inline, private]

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

Node addNode

(

)

[inline]

Returns:

the new node.

Reimplemented from GraphExtender< ListGraphBase >.

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

void changeTarget	(	Edge	e,
		Node	n
	)			[inline]

Changes the target of e to n

Note:

The EdgeIts and OutEdgeIts referencing the changed edge remain valid. However InEdgeIts are invalidated.

Warning:

This functionality cannot be used together with the Snapshot feature.

void changeSource	(	Edge	e,
		Node	n
	)			[inline]

Changes the source of e to n

Note:

The EdgeIts and InEdgeIts referencing the changed edge remain valid. However OutEdgeIts are invalidated.

Warning:

This functionality cannot be used together with the Snapshot feature.

void reverseEdge

(

Edge

e

)

[inline]

Note:

The EdgeIts referencing the changed edge remain valid. However OutEdgeIts and InEdgeIts are invalidated.

Warning:

This functionality cannot be used together with the Snapshot feature.

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 contract	(	Node	a,
		Node	b,
		bool	r = true
	)			[inline]

This function contracts two nodes.

Node b will be removed but instead of deleting incident edges, they will be joined to a. The last parameter r controls whether to remove loops. true means that loops will be removed.

Note:

The EdgeIts referencing a moved edge remain valid. However InEdgeIts and OutEdgeIts may be invalidated.

Warning:

This functionality cannot be used together with the Snapshot feature.

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 EdgeIts referencing a moved edge remain valid. However InEdgeIts and OutEdgeIts may be invalidated.

Warning:

This functionality cannot be used together with the Snapshot feature.

Todo:

It could be implemented in a bit faster way.

Node split

(

Edge

e

)

[inline]

This function splits an edge. First a new node b is added to the graph, then the original edge is re-targeted to b. Finally an edge from b to the original target is added.

Returns:

The newly created node.

Warning:

This functionality cannot be used together with the Snapshot feature.