All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
List of all members | Classes | Public Member Functions | Private Member Functions
ListBpGraph Class Reference

Detailed Description

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.

See Also
concepts::BpGraph
ListDigraph

#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 ()
 Constructor. More...
 
RedNode addRedNode ()
 Add a new red node to the graph. More...
 
BlueNode addBlueNode ()
 Add a new blue node to the graph. More...
 
Edge addEdge (RedNode u, BlueNode v)
 Add a new edge to the graph. More...
 
void erase (Node n)
 Erase a node from the graph. More...
 
void erase (Edge e)
 Erase an edge from the graph. More...
 
bool valid (Node n) const
 Node validity check. More...
 
bool valid (Edge e) const
 Edge validity check. More...
 
bool valid (Arc a) const
 Arc validity check. More...
 
void changeRed (Edge e, RedNode n)
 Change the red node of an edge. More...
 
void changeBlue (Edge e, BlueNode n)
 Change the blue node of an edge. More...
 
void clear ()
 Clear the graph. More...
 
void reserveNode (int n)
 Reserve memory for nodes. More...
 
void reserveEdge (int m)
 Reserve memory for edges. More...
 

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.
 

Constructor & Destructor Documentation

ListBpGraph ( )
inline

Constructor.

Member Function Documentation

RedNode addRedNode ( )
inline

This function adds a red new node to the graph.

Returns
The new node.
BlueNode addBlueNode ( )
inline

This function adds a blue new node to the graph.

Returns
The new node.
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.

Returns
The new edge.
void erase ( Node  n)
inline

This function erases the given node along with its incident arcs from the graph.

Note
All iterators referencing the removed node or the incident edges are invalidated, of course.
void erase ( Edge  e)
inline

This function erases the given edge from the graph.

Note
All iterators referencing the removed edge are invalidated, of course.
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.

Warning
A removed node could become valid again if new nodes are added to 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.

Warning
A removed edge could become valid again if new edges are added to 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.

Warning
A removed arc could become valid again if new edges are added to the graph.
void changeRed ( Edge  e,
RedNode  n 
)
inline

This function changes the red node of the given edge e to n.

Note
EdgeIt and ArcIt iterators referencing the changed edge are invalidated and all other iterators whose base node is the changed node are also invalidated.
Warning
This functionality cannot be used together with the Snapshot feature.
void changeBlue ( Edge  e,
BlueNode  n 
)
inline

This function changes the blue node of the given edge e to n.

Note
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.
Warning
This functionality cannot be used together with the Snapshot feature.
void clear ( )
inline

This function erases all nodes and arcs from the graph.

Note
All iterators of the graph are invalidated, of course.
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.

See Also
reserveEdge()
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.

See Also
reserveNode()