ListDigraph Class Reference

---

Detailed Description

ListDigraph is a simple and fast directed graph implementation based on static linked lists that are stored in std::vector structures.

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

See also:

concepts::Digraph

#include <lemon/list_graph.h>

Inherits lemon::DigraphExtender< ListDigraphBase >.

List of all members.

Classes
class	Snapshot
	Class to make a snapshot of the digraph and restore it later. More...
Public Member Functions
	ListDigraph ()
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	erase (const Node &n)
void	erase (const Arc &a)
bool	valid (Node n) const
	Node validity check.
bool	valid (Arc a) const
	Arc validity check.
void	changeTarget (Arc a, Node n)
	Change the target of a to n.
void	changeSource (Arc a, Node n)
	Change the source of a to n.
void	reverseArc (Arc e)
	Invert the direction of an arc.
void	reserveNode (int n)
	Reserve memory for nodes.
void	reserveArc (int m)
	Reserve memory for arcs.
void	contract (Node a, Node b, bool r=true)
	Contract two nodes.
Node	split (Node n, bool connect=true)
	Split a node.
Node	split (Arc e)
	Split an arc.
Private Member Functions
	ListDigraph (const ListDigraph &)
void	operator= (const ListDigraph &)

---

Constructor & Destructor Documentation

ListDigraph

(

const ListDigraph &

)

[inline, private]

ListDigraph is not copy constructible. Use copyDigraph() instead.

ListDigraph

(

)

[inline]

Constructor.

---

Member Function Documentation

void operator=

(

const ListDigraph &

)

[inline, private]

Assignment of ListDigraph to another one is not allowed. Use copyDigraph() 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 erase

(

const Node &

n

)

[inline]

Erase a node from the digraph.

void erase

(

const Arc &

a

)

[inline]

Erase an arc from the digraph.

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 Node pointing to a removed item could become valid again later if 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:

An Arc pointing to a removed item could become valid again later if new nodes are added to the graph.

void changeTarget	(	Arc	a,
		Node	n
	)		[inline]

Change the target of a to n

Note:

The ArcIts and OutArcIts referencing the changed arc remain valid. However InArcIts are invalidated.

Warning:

This functionality cannot be used together with the Snapshot feature.

void changeSource	(	Arc	a,
		Node	n
	)		[inline]

Change the source of a to n

Note:

The InArcIts referencing the changed arc remain valid. However the ArcIts and OutArcIts are invalidated.

Warning:

This functionality cannot be used together with the Snapshot feature.

void reverseArc

(

Arc

e

)

[inline]

Note:

The ArcIts referencing the changed arc remain valid. However OutArcIts and InArcIts are invalidated.

Warning:

This functionality cannot be used together with the Snapshot feature.

void reserveNode

(

int

n

)

[inline]

Using this function 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 function 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

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 arcs, they will be joined to a. The last parameter r controls whether to remove loops. true means that loops will be removed.

Note:

The ArcIts referencing a moved arc remain valid. However InArcIts and OutArcIts 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 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 ArcIts referencing a moved arc remain valid. However InArcIts and OutArcIts may be invalidated.

Warning:

This functionality cannot be used in conjunction with the Snapshot feature.

Node split

(

Arc

e

)

[inline]

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

Returns:

The newly created node.

Warning:

This functionality cannot be used together with the Snapshot feature.