Algorithms for undirected MCB. More...

#include <LEP/mcb/config.h>
#include <LEDA/graph.h>
#include <LEDA/d_int_set.h>
#include <LEDA/edge_array.h>
#include <LEDA/node_array.h>
#include <LEDA/array.h>
#include <LEDA/list.h>
#include <LEP/mcb/spvecgf2.h>
#include <LEP/mcb/signed.h>
#include <LEP/mcb/superset.h>
#include <LEP/mcb/sptrees.h>
#include <LEP/mcb/transform.h>
#include <LEP/mcb/verify.h>

Include dependency graph for umcb.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces
	mcb
	The main package namespace.

Functions
Undirected Minimum Cycle Basis
The functions below are the more general implementation for undirected graphs. They also support multigraphs. As an underlying implementation they use the Support Vector approach (mcb::UMCB_SVA). They should be the first choice of use unless some special requirements exist.
template<class Container >
int	mcb::UMCB_SVA (const graph &g, array< Container > &mcb, array< Container > &proof, const mcb::edge_num &enumb)
	Compute a MCB of an undirected graph using the Support Vector Approach (de Pina's PhD thesis) algorithm. More...

template<class Container >
int	mcb::UMCB_SVA (const graph &g, array< Container > &mcb, const mcb::edge_num &enumb)
	Compute a MCB of an undirected weighted graph using the Support Vector Approach (de Pina's PhD thesis) algorithm. More...

template<class W , class Container >
W	mcb::UMCB_SVA (const graph &g, const edge_array< W > &len, array< Container > &mcb, array< Container > &proof, const mcb::edge_num &enumb)
	Compute a MCB of an undirected weighted graph using the Support Vector Approach (de Pina's PhD thesis) algorithm. More...

template<class W , class Container >
W	mcb::UMCB_SVA (const graph &g, const edge_array< W > &len, array< Container > &mcb, const mcb::edge_num &enumb)
	Compute a MCB of an undirected weighted graph using the Support Vector Approach (de Pina's PhD thesis) algorithm. More...

int	mcb::UMCB_HYBRID (const leda::graph &g, leda::array< leda::d_int_set > &mcb, leda::array< leda::d_int_set > &proof, const mcb::edge_num &enumb)
	Compute a minimum cycle basis of an undirected graph using a hybrid algorithm. More...

int	mcb::UMCB_HYBRID (const leda::graph &g, leda::array< leda::d_int_set > &mcb, const mcb::edge_num &enumb)
	Compute a minimum cycle basis of an undirected graph using a hybrid algorithm. More...

template<class W >
W	mcb::UMCB_HYBRID (const graph &g, const edge_array< W > &len, array< d_int_set > &mcb, array< d_int_set > &proof, const mcb::edge_num &enumb)
	Compute a minimum cycle basis of a weighted undirected graph using a hybrid algorithm. More...

template<class W >
W	mcb::UMCB_HYBRID (const graph &g, const edge_array< W > &len, array< d_int_set > &mcb, const mcb::edge_num &enumb)
	Compute a minimum cycle basis of a weighted undirected graph using a hybrid algorithm. More...

template<class W >
W	mcb::UMCB_FH (const graph &g, const edge_array< W > &len, array< mcb::spvecgf2 > &mcb, array< mcb::spvecgf2 > &proof, const mcb::edge_num &enumb)
	Compute a MCB of an undirected weighted graph using a Fast variant of the Hybrid algorithm. More...

template<class W >
W	mcb::UMCB_FH (const graph &g, const edge_array< W > &len, array< mcb::spvecgf2 > &mcb, const mcb::edge_num &enumb)
	Compute a MCB of an undirected weighted graph using a Fast variant of the Hybrid algorithm. More...

Detailed Description

Algorithms for undirected MCB.

Given an undirected graph $G(V,E)$ and a non-negative length function on the edges $w: E \mapsto \mathcal{R}_{\ge 0}$ , a minimum cycle basis is a set of cycles which can generate the cycle space and at the same time has minimum total length.

Each cycle of the graph is assumed to be a 0-1 vector indexed on the edge set, and operations between cycles is performed in GF(2). The length of a cycle basis is the sum of the length of its cycles and the length of a cycle is the sum of the length of its edges.

The solution of a minimum cycle basis problem can be in the following two forms.

A pair (mcb, proof) where both are arrays of mcb::spvecgf2, array< mcb::spvecgf2 >. Each mcb::spvecgf2 represents a cycle or some edge set. Each edge of the graph is represented by a unique number provided by an edge numbering, mcb::edge_num.
A pair (mcb, proof) where both are arrays of compressed integer sets, array< d_int_set >. Each integer sets represents a cycle. In these integer sets, each edge of the graph is represented by a unique number provided by the edge numbering, mcb::edge_num.

Most functions of this section are templates functions. The template parameter W can be instantiated with any number type. Attention must be paid in order to avoid overflow of values.

The whole package is protected using a namespace called "mcb", and therefore using anything requires mcb::xx or the using namespace mcb directive.

See also: mcb::edge_num mcb::spvecgf2

Namespaces

Functions

Detailed Description