StaticGraph is the undirected counterpart of StaticDigraph: a graph whose structure is built once, with build(), and cannot be modified after that (but it can be built again), in exchange for arrays that hold the arcs out of each node one after the other, with no pointer to follow. It takes less memory than SmartGraph and ListGraph, and the incidences of a node are scanned contiguously.
The nodes and the edges are numbered from 0, in the order in which build() is given them, and node() and edge() find them from their index; the edges and the arcs are related as in SmartGraph.
This type fully conforms to the Graph concept. Most of its member functions and nested classes are documented only in the concept class.
This class provides constant time counting for nodes, edges and arcs.
- See also
- concepts::Graph
-
StaticDigraph
template< typename Graph , typename NodeRefMap , typename EdgeRefMap >
| void build |
( |
const Graph & | graph, |
|
|
NodeRefMap & | nodeRef, |
|
|
EdgeRefMap & | edgeRef ) |
|
inline |
This function builds the graph copying another undirected graph of any kind, with its nodes and edges in the order of their iterators. It can be called more than once, in which case the whole structure and all the maps are cleared and rebuilt. It also makes it possible to copy a graph to a StaticGraph with GraphCopy.
- Parameters
-
| graph | An existing graph to be copied. |
| nodeRef | The node references will be copied into this map, which must be readable and writable, with key type Graph::Node and value type StaticGraph::Node. |
| edgeRef | The edge references will be copied into this map, which must be writable, with key type Graph::Edge and value type StaticGraph::Edge; NullMap if they are not needed. |
template< typename EdgeListIterator >
| void build |
( |
int | n, |
|
|
EdgeListIterator | begin, |
|
|
EdgeListIterator | end ) |
|
inline |
This function builds the graph with n nodes and the edges in the range [begin, end), given by STL compatible iterators whose value_type is std::pair< int , int >: if the k-th pair is (i,j), then edge(k-1) joins node(i), its u(), and node(j), its v(). Unlike in StaticDigraph::build(), the pairs may come in any order. It can be called more than once, in which case the whole structure and all the maps are cleared and rebuilt.