#include <lemon/list_graph.h>
Inherits GraphExtender< lemon::ListGraphBase >.
Inheritance diagram for ListGraph:
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.
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... |
ListGraph is not copy constructible. Use GraphCopy() instead.
ListGraph | ( | ) | [inline] |
Constructor.
void operator= | ( | const ListGraph & | ) | [inline, private] |
Assignment of ListGraph to another one is not allowed. Use GraphCopy() instead.
Node addNode | ( | ) | [inline] |
Edge addEdge | ( | const Node & | s, | |
const Node & | t | |||
) | [inline] |
Add a new edge to the graph with source node s
and target node t
.
void changeTarget | ( | Edge | e, | |
Node | n | |||
) | [inline] |
Changes the target of e
to n
EdgeIt
s and OutEdgeIt
s referencing the changed edge remain valid. However InEdgeIt
s are invalidated. void changeSource | ( | Edge | e, | |
Node | n | |||
) | [inline] |
Changes the source of e
to n
EdgeIt
s and InEdgeIt
s referencing the changed edge remain valid. However OutEdgeIt
s are invalidated. void reverseEdge | ( | Edge | e | ) | [inline] |
EdgeIt
s referencing the changed edge remain valid. However OutEdgeIt
s and InEdgeIt
s are invalidated. 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.
EdgeIt
s referencing a moved edge remain valid. However InEdgeIt
s and OutEdgeIt
s may be invalidated. 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.
EdgeIt
s referencing a moved edge remain valid. However InEdgeIt
s and OutEdgeIt
s may be invalidated.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.