ListBpGraph is a versatile and fast undirected graph implementation based on linked lists that are stored in std::vector
structures.
This type fully conforms to the BpGraph 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, edges and arcs.
#include <lemon/list_graph.h>
Inherits BpGraphExtender< Base >.
Classes | |
class | Snapshot |
Class to make a snapshot of the graph and restore it later. More... | |
Public Member Functions | |
ListBpGraph () | |
RedNode | addRedNode () |
Add a new red node to the graph. | |
BlueNode | addBlueNode () |
Add a new blue node to the graph. | |
Edge | addEdge (RedNode u, BlueNode v) |
Add a new edge to the graph. | |
void | erase (Node n) |
Erase a node from the graph. | |
void | erase (Edge e) |
Erase an edge from the graph. | |
bool | valid (Node n) const |
Node validity check. | |
bool | valid (Edge e) const |
Edge validity check. | |
bool | valid (Arc a) const |
Arc validity check. | |
void | changeRed (Edge e, RedNode n) |
Change the red node of an edge. | |
void | changeBlue (Edge e, BlueNode n) |
Change the blue node of an edge. | |
void | clear () |
Clear the graph. | |
void | reserveNode (int n) |
Reserve memory for nodes. | |
void | reserveEdge (int m) |
Reserve memory for edges. | |
Private Member Functions | |
ListBpGraph (const ListBpGraph &) | |
BpGraphs are not copy constructible. Use BpGraphCopy instead. | |
void | operator= (const ListBpGraph &) |
Assignment of a graph to another one is not allowed. Use BpGraphCopy instead. |
ListBpGraph | ( | ) | [inline] |
Constructor.
RedNode addRedNode | ( | ) | [inline] |
This function adds a red new node to the graph.
BlueNode addBlueNode | ( | ) | [inline] |
This function adds a blue new node to the graph.
Edge addEdge | ( | RedNode | u, |
BlueNode | v | ||
) | [inline] |
This function adds a new edge to the graph between nodes u
and v
with inherent orientation from node u
to node v
.
void erase | ( | Node | n | ) | [inline] |
This function erases the given node along with its incident arcs from the graph.
void erase | ( | Edge | e | ) | [inline] |
This function erases the given edge from the graph.
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 graph.
bool valid | ( | Edge | e | ) | const [inline] |
This function gives back true
if the given edge is valid, i.e. it is a real edge of the graph.
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 graph.
void changeRed | ( | Edge | e, |
RedNode | n | ||
) | [inline] |
This function changes the red node of the given edge e
to n
.
EdgeIt
and ArcIt
iterators referencing the changed edge are invalidated and all other iterators whose base node is the changed node are also invalidated.void changeBlue | ( | Edge | e, |
BlueNode | n | ||
) | [inline] |
This function changes the blue node of the given edge e
to n
.
EdgeIt
iterators referencing the changed edge remain valid, but ArcIt
iterators referencing the changed edge and all other iterators whose base node is the changed node are also invalidated.void clear | ( | ) | [inline] |
This function erases all nodes and arcs from the graph.
void reserveNode | ( | int | n | ) | [inline] |
Using this function, it is possible to avoid superfluous memory allocation: if you know that the graph you want to build will be large (e.g. it will contain millions of nodes and/or edges), then it is worth reserving space for this amount before starting to build the graph.
void reserveEdge | ( | int | m | ) | [inline] |
Using this function, it is possible to avoid superfluous memory allocation: if you know that the graph you want to build will be large (e.g. it will contain millions of nodes and/or edges), then it is worth reserving space for this amount before starting to build the graph.