abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
StaticGraph Class Reference

A static undirected graph class. More...

#include <lemon/static_graph.h>

Public Member Functions

 StaticGraph ()
 Constructor.
template< typename Graph , typename NodeRefMap , typename EdgeRefMap >
void build (const Graph &graph, NodeRefMap &nodeRef, EdgeRefMap &edgeRef)
 Build the graph copying another graph.
template< typename EdgeListIterator >
void build (int n, EdgeListIterator begin, EdgeListIterator end)
 Build the graph from a list of edges.
void clear ()
 Clear the graph.

Static Public Member Functions

static Node node (int ix)
 The node with the given index.
static Edge edge (int ix)
 The edge with the given index.
static int index (Node node)
 The index of the given node.
static int index (Edge edge)
 The index of the given edge.

Private Member Functions

 StaticGraph (const StaticGraph &)
 Graphs are not copy constructible. Use GraphCopy instead.
void operator= (const StaticGraph &)
 Assignment of a graph to another one is not allowed. Use GraphCopy instead.

Detailed Description

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

Constructor & Destructor Documentation

◆ StaticGraph()

StaticGraph ( )
inline

Default constructor, of the empty graph.

Member Function Documentation

◆ build() [1/2]

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
graphAn existing graph to be copied.
nodeRefThe node references will be copied into this map, which must be readable and writable, with key type Graph::Node and value type StaticGraph::Node.
edgeRefThe 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.

◆ build() [2/2]

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.

◆ clear()

void clear ( )
inline

This function erases all the nodes and the edges of the graph.