My Project
|
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.
#include <lemon/list_graph.h>
Classes | |
class | Snapshot |
Class to make a snapshot of the digraph and restore it later. More... | |
Public Member Functions | |
ListDigraph () | |
Constructor. | |
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. | |
|
inline |
Constructor.
|
inline |
This function adds a new node to the digraph.
|
inline |
This function adds a new arc to the digraph with source node s
and target node t
.
|
inline |
This function erases the given node along with its outgoing and incoming arcs from the digraph.
|
inline |
This function erases the given arc from the digraph.
|
inline |
This function gives back true
if the given node is valid, i.e. it is a real node of the digraph.
|
inline |
This function gives back true
if the given arc is valid, i.e. it is a real arc of the digraph.
|
inline |
This function changes the target node of the given arc a
to n
.
ArcIt
and OutArcIt
iterators referencing the changed arc remain valid, but InArcIt
iterators are invalidated.
|
inline |
This function changes the source node of the given arc a
to n
.
InArcIt
iterators referencing the changed arc remain valid, but ArcIt
and OutArcIt
iterators are invalidated.
|
inline |
This function reverses the direction of the given arc.
ArcIt
, OutArcIt
and InArcIt
iterators referencing the changed arc are invalidated.
|
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.
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 incoming arcs of v
. Moreover all iterators referencing node v
or the removed loops are also invalidated. Other iterators remain valid.
|
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.
|
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.
InArcIt
iterators referencing the original arc are invalidated. Other iterators remain valid.
|
inline |
This function erases all nodes and arcs from the digraph.
|
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.
|
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.