ListGraph Class Reference
[Graph Structures]

#include <lemon/list_graph.h>

Inherits GraphExtender< lemon::ListGraphBase >.

Inheritance diagram for ListGraph:

Inheritance graph
[legend]
List of all members.

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.


Public Member Functions

 ListGraph ()
 Constructor.
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)
 Using this it is possible to avoid the superfluous memory allocation.
void reserveEdge (int n)
 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 &)
 ListGraph is not copy constructible. Use GraphCopy() instead.
void operator= (const ListGraph &)
 Assignment of ListGraph to another one is not allowed. Use GraphCopy() instead.

Classes

class  Snapshot
 Class to make a snapshot of the graph and restore to it later. More...


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.

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 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 contain at least 10 million nodes then it is worth reserving space for this amount before starting to build the graph.

void reserveEdge ( int  n  )  [inline]

Using this it is possible to avoid the superfluous memory allocation: see the reserveNode function.

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.


The documentation for this class was generated from the following file:
Generated on Tue Oct 31 09:51:01 2006 for LEMON by  doxygen 1.5.1