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

A static directed graph class. More...

#include <lemon/compact_graph.h>

Public Member Functions

 CompactDigraph ()
 Constructor.
Arc arc (int ix) const
 The arc with the given index.
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 int index (Node node)
 The index of the given node.
static int index (Arc arc)
 The index of the given arc.

Private Member Functions

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

Detailed Description

CompactDigraph is a highly efficient digraph implementation similar to StaticDigraph. It is more memory efficient but does not provide efficient iteration over incoming arcs.

It stores only one int value for each node and one int value for each arc. Its InArcIt is provided only for compatibility with the Digraph concept: with no index of the incoming arcs, it scans the arcs, so that visiting the incoming arcs of one node takes \(O(m)\) time, and of all nodes \(O(nm)\). An algorithm that visits them (e.g., one on the reverse digraph) should use StaticDigraph, which stores the incoming arcs too.

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

See also
concepts::Digraph

Constructor & Destructor Documentation

◆ CompactDigraph()

CompactDigraph ( )
inline

Default constructor.

Member Function Documentation

◆ node()

Node node ( int ix)
inlinestatic

This function returns the node with the given index.

See also
index()

◆ arc()

Arc arc ( int ix) const
inline

This function returns the arc with the given index.

See also
index()

◆ index() [1/2]

int index ( Node node)
inlinestatic

This function returns the index of the the given node.

See also
node()

◆ index() [2/2]

int index ( Arc arc)
inlinestatic

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 CompactDigraph structure using DigraphCopy.

Parameters
digraphAn existing digraph to be copied.
nodeRefThe node references will be copied into this map. Its key type must be Digraph::Node and its value type must be CompactDigraph::Node. It must conform to the ReadWriteMap concept.
arcRefThe arc references will be copied into this map. Its key type must be Digraph::Arc and its value type must be CompactDigraph::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
nThe number of nodes.
beginAn iterator pointing to the beginning of the arc list.
endAn 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 ) );
gr.build( 4 , arcs.begin() , arcs.end() );
void build( const Digraph & digraph , NodeRefMap & nodeRef , ArcRefMap & arcRef )
Build the digraph copying another digraph.
Definition compact_graph.h:370
CompactDigraph( const CompactDigraph & )
Graphs are not copy constructible. Use DigraphCopy instead.
Definition compact_graph.h:297

◆ clear()

void clear ( )
inline

This function erases all nodes and arcs from the digraph.