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

## Detailed Description

StaticDigraph is a highly efficient digraph implementation, but it is fully static. It stores only two `int` values for each node and only four `int` values for each arc. Moreover it provides faster item iteration than ListDigraph and SmartDigraph, especially using `OutArcIt` iterators, since its arcs are stored in an appropriate order. However it only provides build() and clear() functions and does not support any other modification of the digraph.

Since this digraph structure is completely static, its nodes and arcs can be indexed with integers from the ranges [0..nodeNum()-1] and [0..arcNum()-1], respectively. The index of an item is the same as its ID, it can be obtained using the corresponding index() or id() function. A node or arc with a certain index can be obtained using node() or arc().

This type fully conforms to the Digraph concept. Most of its member functions and nested classes are documented only in the concept class.

This class provides constant time counting for nodes and arcs.

See also
  concepts::Digraph

`#include <lemon/static_graph.h>`

## Public Member Functions

| StaticDigraph ()
| Constructor.
int | nodeNum () const
| Number of nodes.
int | arcNum () const
| Number of arcs.
template<typename Digraph, typename NodeRefMap, typename ArcRefMap>
void | build (const Digraph &digraph, NodeRefMap &nodeRef, ArcRefMap &arcRef)
| Build the digraph copying another digraph.
template<typename ArcListIterator>
void | build (int n, ArcListIterator begin, ArcListIterator end)
| Build the digraph from an arc list.
void | clear ()
| Clear the digraph.

## Static Public Member Functions

static Node | node (int ix)
| The node with the given index.
static Arc | arc (int ix)
| The arc with the given index.
static int | index (Node node)
| The index of the given node.
static int | index (Arc arc)
| The index of the given arc.

## Constructor & Destructor Documentation

## StaticDigraph()

StaticDigraph | ( |  | ) |

inline

Default constructor.

## Member Function Documentation

## node()

Node node | ( | int | ix | ) |

inline static

This function returns the node with the given index.

See also
  index()

## arc()

Arc arc | ( | int | ix | ) |

inline static

This function returns the arc with the given index.

See also
  index()

## index() [1/2]

int index | ( | Node | node | ) |

inline static

This function returns the index of the the given node.

See also
  node()

## index() [2/2]

int index | ( | Arc | arc | ) |

inline static

This function returns the index of the the given arc.

See also
  arc()

## nodeNum()

int nodeNum | ( |  | ) | const

inline

This function returns the number of nodes.

## arcNum()

int arcNum | ( |  | ) | const

inline

This function returns the number of arcs.

## build() [1/2]

template<typename Digraph, typename NodeRefMap, typename ArcRefMap>

void build | ( | const Digraph & | digraph,
|  | NodeRefMap & | nodeRef,
|  | ArcRefMap & | arcRef )

inline

This function builds the digraph copying another digraph of any kind. It can be called more than once, but in such case, the whole structure and all maps will be cleared and rebuilt.

This method also makes possible to copy a digraph to a StaticDigraph structure using DigraphCopy.

Parameters

  digraph | An existing digraph to be copied.
  nodeRef | The node references will be copied into this map. Its key type must be `Digraph::Node` and its value type must be `StaticDigraph::Node`. It must conform to the ReadWriteMap concept.
  arcRef | The arc references will be copied into this map. Its key type must be `Digraph::Arc` and its value type must be `StaticDigraph::Arc`. It must conform to the WriteMap concept.

Note
  If you do not need the arc references, then you could use NullMap for the last parameter. However the node references are required by the function itself, thus they must be readable from the map.

## build() [2/2]

template<typename ArcListIterator>

void build | ( | int | n,
|  | ArcListIterator | begin,
|  | ArcListIterator | end )

inline

This function builds the digraph from the given arc list. It can be called more than once, but in such case, the whole structure and all maps will be cleared and rebuilt.

The list of the arcs must be given in the range [begin, end) specified by STL compatible itartors whose `value_type` must be std::pair<int,int>. Each arc must be specified by a pair of integer indices from the range [0..n-1]. The pairs must be in a non-decreasing order with respect to their first values. If the k-th pair in the list is (i,j), then arc(k-1) will connect node(i) to node(j).

Parameters

  n | The number of nodes.
  begin | An iterator pointing to the beginning of the arc list.
  end | An iterator pointing to the end of the arc list.

For example, a simple digraph can be constructed like this.

std::vector<std::pair<int,int> > arcs;
arcs.push_back(std::make_pair(0,1));
arcs.push_back(std::make_pair(0,2));
arcs.push_back(std::make_pair(1,3));
arcs.push_back(std::make_pair(1,2));
arcs.push_back(std::make_pair(3,0));
StaticDigraph gr;
gr.build(4, arcs.begin(), arcs.end());
lemon::StaticDigraph::build
void build(const Digraph &digraph, NodeRefMap &nodeRef, ArcRefMap &arcRef)
Build the digraph copying another digraph.
Definition static_graph.h:369
lemon::StaticDigraph::StaticDigraph
StaticDigraph()
Constructor.
Definition static_graph.h:308

## clear()

void clear | ( |  | ) |

inline

This function erases all nodes and arcs from the digraph.