Loading...
Searching...
No Matches
ListDigraph Class Reference
Data Structures » Graph Structures

## Detailed Description

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.

See also
  concepts::Digraph
  ListGraph

`#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.

## Constructor & Destructor Documentation

## ListDigraph()

ListDigraph | ( |  | ) |

inline

Constructor.

## Member Function Documentation

## addNode()

Node addNode | ( |  | ) |

inline

This function adds a new node to the digraph.

Returns
  The new node.

## addArc()

Arc addArc | ( | Node | s,
|  | Node | t )

inline

This function adds a new arc to the digraph with source node `s` and target node `t`.

Returns
  The new arc.

## erase() [1/2]

void erase | ( | Node | n | ) |

inline

This function erases the given node along with its outgoing and incoming arcs from the digraph.

Note
  All iterators referencing the removed node or the connected arcs are invalidated, of course.

## erase() [2/2]

void erase | ( | Arc | a | ) |

inline

This function erases the given arc from the digraph.

Note
  All iterators referencing the removed arc are invalidated, of course.

## valid() [1/2]

bool valid | ( | Node | n | ) | const

inline

This function gives back `true` if the given node is valid, i.e. it is a real node of the digraph.

Warning
  A removed node could become valid again if new nodes are added to the digraph.

## valid() [2/2]

bool valid | ( | Arc | a | ) | const

inline

This function gives back `true` if the given arc is valid, i.e. it is a real arc of the digraph.

Warning
  A removed arc could become valid again if new arcs are added to the digraph.

## changeTarget()

void changeTarget | ( | Arc | a,
|  | Node | n )

inline

This function changes the target node of the given arc `a` to `n`.

Note
  `ArcIt` and `OutArcIt` iterators referencing the changed arc remain valid, but `InArcIt` iterators are invalidated.

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

## changeSource()

void changeSource | ( | Arc | a,
|  | Node | n )

inline

This function changes the source node of the given arc `a` to `n`.

Note
  `InArcIt` iterators referencing the changed arc remain valid, but `ArcIt` and `OutArcIt` iterators are invalidated.

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

## reverseArc()

void reverseArc | ( | Arc | a | ) |

inline

This function reverses the direction of the given arc.

Note
  `ArcIt`, `OutArcIt` and `InArcIt` iterators referencing the changed arc are invalidated.

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

## contract()

void contract | ( | Node | u,
|  | Node | v,
|  | bool | r = true )

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.

Note
  The moved arcs are joined to node `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.

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

## split() [1/2]

Node split | ( | Node | n,
|  | bool | connect = true )

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.

Returns
  The newly created node.

Note
  All iterators remain valid.

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

## split() [2/2]

Node split | ( | Arc | a | ) |

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.

Returns
  The newly created node.

Note
  `InArcIt` iterators referencing the original arc are invalidated. Other iterators remain valid.

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

## clear()

void clear | ( |  | ) |

inline

This function erases all nodes and arcs from the digraph.

Note
  All iterators of the digraph are invalidated, of course.

## reserveNode()

void reserveNode | ( | int | n | ) |

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.

See also
  reserveArc()

## reserveArc()

void reserveArc | ( | int | m | ) |

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.

See also
  reserveNode()