ListDigraph Class Reference

---

Detailed Description

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

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

This class provides only linear time counting for nodes and arcs.

See also:

concepts::Digraph

ListGraph

#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 (Node s, Node t)
	Add a new arc to the digraph.
void	erase (Node n)
	Erase a node from the digraph.
void	erase (Arc a)
	Erase an arc from the digraph.
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 node of an arc.
void	changeSource (Arc a, Node n)
	Change the source node of an arc.
void	reverseArc (Arc a)
	Reverse the direction of an arc.
void	contract (Node u, Node v, bool r=true)
	Contract two nodes.
Node	split (Node n, bool connect=true)
	Split a node.
Node	split (Arc a)
	Split an arc.
void	clear ()
	Clear the digraph.
void	reserveNode (int n)
	Reserve memory for nodes.
void	reserveArc (int m)
	Reserve memory for arcs.
Private Member Functions
	ListDigraph (const ListDigraph &)
	Digraphs are not copy constructible. Use DigraphCopy instead.
void	operator= (const ListDigraph &)
	Assignment of a digraph to another one is not allowed. Use DigraphCopy instead.

---

Constructor & Destructor Documentation

ListDigraph

(

)

[inline]

Constructor.

---

Member Function Documentation

Node addNode

(

)

[inline]

This function adds a new node to the digraph.

Returns:

The new node.

Arc addArc	(	Node	s,
		Node	t
	)		[inline]

This function adds a new arc to the digraph with source node s and target node t.

Returns:

The new arc.

void erase

(

Node

n

)

[inline]

This function erases the given node along with its outgoing and incoming arcs from the digraph.

Note:

All iterators referencing the removed node or the connected arcs are invalidated, of course.

void erase

(

Arc

a

)

[inline]

This function erases the given arc from the digraph.

Note:

All iterators referencing the removed arc are invalidated, of course.

bool valid

(

Node

n

)

const [inline]

This function gives back true if the given node is valid, i.e. it is a real node of the digraph.

Warning:

A removed node could become valid again if new nodes are added to the digraph.

bool valid

(

Arc

a

)

const [inline]

This function gives back true if the given arc is valid, i.e. it is a real arc of the digraph.

Warning:

A removed arc could become valid again if new arcs are added to the digraph.

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

This function changes the target node of the given arc a to n.

Note:

ArcIt and OutArcIt iterators referencing the changed arc remain valid, but InArcIt iterators are invalidated.

Warning:

This functionality cannot be used together with the Snapshot feature.

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

This function changes the source node of the given arc a to n.

Note:

InArcIt iterators referencing the changed arc remain valid, but ArcIt and OutArcIt iterators are invalidated.

Warning:

This functionality cannot be used together with the Snapshot feature.

void reverseArc

(

Arc

a

)

[inline]

This function reverses the direction of the given arc.

Note:

ArcIt, OutArcIt and InArcIt iterators referencing the changed arc are invalidated.

Warning:

This functionality cannot be used together with the Snapshot feature.

void contract	(	Node	u,
		Node	v,
		bool	r = true
	)		[inline]

This function contracts the given two nodes. Node v is removed, but instead of deleting its incident arcs, they are joined to node u. If the last parameter r is true (this is the default value), then the newly created loops are removed.

Note:

The moved arcs are joined to node u using changeSource() or changeTarget(), thus ArcIt and OutArcIt iterators are invalidated for the outgoing arcs of node v and InArcIt iterators are invalidated for the incomming arcs of v. Moreover all iterators referencing node v or the removed loops are also invalidated. Other iterators remain valid.

Warning:

This functionality cannot be used together with the Snapshot feature.

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

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

Returns:

The newly created node.

Note:

All iterators remain valid.

Warning:

This functionality cannot be used together with the Snapshot feature.

Node split

(

Arc

a

)

[inline]

This function splits the given arc. First, a new node v is added to the digraph, then the target node of the original arc is set to v. Finally, an arc from v to the original target is added.

Returns:

The newly created node.

Note:

InArcIt iterators referencing the original arc are invalidated. Other iterators remain valid.

Warning:

This functionality cannot be used together with the Snapshot feature.

void clear

(

)

[inline]

This function erases all nodes and arcs from the digraph.

Note:

All iterators of the digraph are invalidated, of course.

void reserveNode

(

int

n

)

[inline]

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