Detailed Description

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

It conforms to the Graph 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::Graph

#include <lemon/list_graph.h>

Inherits GraphExtender< Base >.

Classes
class	Snapshot
	Class to make a snapshot of the graph and restore 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	erase (const Node &n)

void	erase (const Edge &e)

bool	valid (Node n) const
	Node validity check.

bool	valid (Arc a) const
	Arc validity check.

bool	valid (Edge e) const
	Edge validity check.

void	changeU (Edge e, Node n)
	Change the end `u` of `e` to `n`.

void	changeV (Edge e, Node n)
	Change the end `v` of `e` to `n`.

void	contract (Node a, Node b, bool r=true)
	Contract two nodes.

Private Member Functions
	ListGraph (const ListGraph &)

void	operator= (const ListGraph &)

Constructor & Destructor Documentation

ListGraph ( const ListGraph & )

inlineprivate

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

ListGraph ( )

inline

Constructor.

Member Function Documentation

void operator= ( const ListGraph & )

inlineprivate

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

Node addNode ( )

inline

Add a new node to the graph.

Returns: The new node.

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.

void erase ( const Node & n )

inline

Erase a node from the graph.

void erase ( const Edge & e )

inline

Erase an edge from the graph.

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 edges are added to the graph.

bool valid ( Edge e ) const

inline

This function gives back true if the given edge is valid, ie. it is a real arc of the graph.

Warning: A Edge pointing to a removed item could become valid again later if new edges are added to the graph.

void changeU	(	Edge	e,
		Node	n
	)

inline

This function changes the end u of e to node n.

Note: The EdgeIts and ArcIts referencing the changed edge are invalidated and if the changed node is the base node of an iterator then this iterator is also invalidated.

Warning: This functionality cannot be used together with the Snapshot feature.

void changeV	(	Edge	e,
		Node	n
	)

inline

This function changes the end v of e to n.

Note: The EdgeIts referencing the changed edge remain valid, however ArcIts and if the changed node is the base node of an iterator then this iterator is invalidated.

Warning: This functionality cannot be used together with the Snapshot feature.

void contract	(	Node	a,
		Node	b,
		bool	r = `true`
	)

inline

This function contracts two nodes. Node b will be removed but instead of deleting its neighboring 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.

Warning: This functionality cannot be used together with the Snapshot feature.

Detailed Description

Classes

Public Member Functions

Private Member Functions

Constructor & Destructor Documentation

Member Function Documentation