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 DigraphExtender< Base >.

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 &  )

inlineprivate

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

ListDigraph ( )

inline

Constructor.

Member Function Documentation

void operator= ( const ListDigraph &  )

inlineprivate

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.