Exact MCB

Undirected Minimum Cycle Basis

These functions implement the three main approaches for computing a minimum cycle basis. All these approaches are based on the Support Vector Approach. Their differences are on the way of finding the shortest non-orthogonal cycle:

mcb::UMCB_SVA finds the cycles by maintaining a signed graph
mcb::UMCB_HYBRID maintains a list of candidate cycles which is guarantied to contain an MCB,
mcb::UMCB_FH maintains the same list as above but in a more elaborate way in order to be able to compute faster the shortest non-orthogonal cycle.

In case you have no special preference try the mcb::UMCB function which uses the signed graph implementation and supports multigraphs.
The fastest algorithm is mcb::UMCB_SVA.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Directed Minimum Cycle Basis

template<class W>

W mcb::DMCB (const graph &g, const edge_array< W > &len, array< mcb::spvecfp > &mcb, array< mcb::spvecfp > &proof, const mcb::edge_num &enumb, double error=0.375)

Compute a minimum cycle basis of a weighted directed graph.

template<class W>

W mcb::DMCB (const graph &g, const edge_array< W > &len, array< mcb::spvecfp > &mcb, const mcb::edge_num &enumb, double error=0.375)

Compute a minimum cycle basis of a weighted directed graph.

template<class W>

W mcb::DMCB (const graph &g, const edge_array< W > &len, array< array< etype > > &mcb, const mcb::edge_num &enumb, double error=0.375)

Compute a minimum cycle basis of a weighted directed graph.

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 W>

W mcb::UMCB (const graph &g, const edge_array< W > &len, array< mcb::spvecgf2 > &mcb, const mcb::edge_num &enumb)

Compute an MCB of an undirected graph (possible a multigraph) using the most general implementation of this library.

int mcb::UMCB (const graph &g, array< mcb::spvecgf2 > &mcb, const mcb::edge_num &enumb)

Compute an MCB of an undirected graph (possible a multigraph) using the most general implementation of this library.

Function Documentation

template<class W>

W mcb::DMCB ( const graph & g,

const edge_array< W > & len,

array< array< etype > > & mcb,

const mcb::edge_num & enumb,

double error = 0.375

)

Compute a minimum cycle basis of a weighted directed graph.
The function computes a directed Minimum Cycle Basis $B$ of $g$ , that is a cycle basis of $g$ with the smallest length (sum of lengths of cycles). The basis is returned as an array of arrays of integers. Each such array if indexed on $1 \dots m$ and its entry can be $0$ or $\pm 1$ . Which edge corresponds to which index in this array can be found by the edge numbering, enumb. Note that the edge numbering using an indexing from $0$ to $m-1$ .
Since the algorithm is a randomized Monte-Carlo algorithm, the error argument which should be less that 1 represents the acceptable error probability that the returned cycle basis is not a minimum cycle basis.
The function returns the weight of the Minimum Cycle Basis or is undefined if there were any errors.
The running time is $O( m^3 )$ where $m$ are the number of edges of $g$ .

Parameters:

g A directed graph.

len The edge lengths.

mcb A leda::array of leda::arrays of ints to return the MCB.

enumb An edge numbering.

error The error probability.

Precondition:
g is simple and loop-free
len is positive
enumb is already initialized with g
error is positive and less than one

template<class W>

W mcb::DMCB ( const graph & g,

const edge_array< W > & len,

array< mcb::spvecfp > & mcb,

const mcb::edge_num & enumb,

double error = 0.375

)

Compute a minimum cycle basis of a weighted directed graph.
The function computes a directed Minimum Cycle Basis $B$ of $g$ , that is a cycle basis of $g$ with the smallest length (sum of lengths of cycles). The basis is returned as an array of sparse vectors spvecfp, called mcb.
Every edge is represented by some integer, by a fixed and arbitrary numbering. This numbering is represented by enumb.
Since the algorithm is a randomized Monte-Carlo algorithm, the error argument which should be less that 1 represents the acceptable error probability that the returned cycle basis is not a minimum cycle basis.
The function returns the weight of the Minimum Cycle Basis or is undefined if there were any errors.
The running time is $O( m^3 )$ where $m$ are the number of edges of $g$ .

Parameters:

g A directed graph.

len The edge lengths.

mcb A leda::array of spvecfp to return the MCB.

enumb An edge numbering.

error The error probability.

Precondition:
g is simple and loop-free
len is positive
enumb is already initialized with g
error is positive and less than one

template<class W>

W mcb::DMCB ( const graph & g,

const edge_array< W > & len,

array< mcb::spvecfp > & mcb,

array< mcb::spvecfp > & proof,

const mcb::edge_num & enumb,

double error = 0.375

)

Compute a minimum cycle basis of a weighted directed graph.
The function computes a directed Minimum Cycle Basis $B$ of $g$ , that is a cycle basis of $g$ with the smallest length (sum of lengths of cycles). The basis is returned as an array of sparse vectors spvecfp, called mcb.
Every edge is represented by some integer, by a fixed and arbitrary numbering. This numbering is represented by enumb.
The function also returns a certificate of optimality of the minimum cycle basis. More precisely a set of linearly independent vectors for which cycle $i$ is the shortest cycle in $g$ with non-zero intersection with the proof vector $i$ .
Since the algorithm is a randomized Monte-Carlo algorithm, the error argument which should be less that 1 represents the acceptable error probability that the returned cycle basis is not a minimum cycle basis.
The function returns the weight of the Minimum Cycle Basis or is undefined if there were any errors.
The running time is $O( m^3 )$ where $m$ are the number of edges of $g$ .

Parameters:

g A directed graph.

len The edge lengths.

mcb A leda::array of spvecfp to return the MCB.

proof A leda::array of spvecfp to return the proof.

enumb An edge numbering.

error The error probability.

Precondition:
g is simple and loop-free
len is positive
enumb is already initialized with g
error is positive and less than one

int mcb::UMCB ( const graph & g,

array< mcb::spvecgf2 > & mcb,

const mcb::edge_num & enumb

)

Compute an MCB of an undirected graph (possible a multigraph) using the most general implementation of this library.
The function computes a Minimum Cycle Basis $B$ of a graph $g$ , that is a cycle basis of $g$ with the smallest length (sum of lengths of cycles). The basis is returned as an array of mcb:spvecgf2 objects.
Every edge is represented by some integer, by a fixed and arbitrary numbering. This numbering is represented by enumb.
The function returns the weight of the Minimum Cycle Basis or is undefined if there were any errors.
The running time is $O( m^3 )$ where $m$ are the number of edges of $g$ .

Parameters:

g An undirected graph.

mcb A leda::array of mcb::spvecgf2 to return the MCB.

enumb An edge numbering.

Returns:
The length of the MCB or undefined if some error occured.

Precondition:
g is undirected

Remarks:
Care must be taken when the template parameter is instantiated with a data type which has rounding errors.

template<class W>

W mcb::UMCB ( const graph & g,

const edge_array< W > & len,

array< mcb::spvecgf2 > & mcb,

const mcb::edge_num & enumb

)

Compute an MCB of an undirected graph (possible a multigraph) using the most general implementation of this library.
The function computes a Minimum Cycle Basis $B$ of a graph $g$ , that is a cycle basis of $g$ with the smallest length (sum of lengths of cycles). The basis is returned as an array of mcb:spvecgf2 objects.
Every edge is represented by some integer, by a fixed and arbitrary numbering. This numbering is represented by enumb.
The function returns the weight of the Minimum Cycle Basis or is undefined if there were any errors.
The running time is $O( m^3 )$ where $m$ are the number of edges of $g$ .

Parameters:

g An undirected graph.

len The edge lengths function.

mcb A leda::array of mcb::spvecgf2 to return the MCB.

enumb An edge numbering.

Returns:
The length of the MCB or undefined if some error occured.

Precondition:
g is undirected

Remarks:
Care must be taken when the template parameter is instantiated with a data type which has rounding errors.

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.
The function computes a Minimum Cycle Basis $B$ of a graph $g$ , that is a cycle basis of $g$ with the smallest length (sum of lengths of cycles). It accepts the length type as a template parameter. The basis is returned as an array of mcb::spvecgf2 objects.

Every edge is represented by some integer, by a fixed and arbitrary numbering. This numbering is represented by enumb.
The function returns the weight of the Minimum Cycle Basis or is undefined if there were any errors.
The running time is $O( m^3 )$ where $m$ are the number of edges of $g$ .

Parameters:

g An undirected graph.

len A leda::edge_array for the edge lengths.

mcb A leda::array of mcb::spvecgf2 to return the MCB.

enumb An edge numbering.

Returns:
The length of the MCB or undefined if some error occured.

Precondition:
g is undirected, simple and loopfree.
len is non-negative

Remarks:
Care must be taken when the template parameter is instantiated with a data type which has rounding errors.

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.
The function computes a Minimum Cycle Basis $B$ of a graph $g$ , that is a cycle basis of $g$ with the smallest length (sum of lengths of cycles). It accepts the length type as a template parameter. The basis is returned as an array of mcb::spvecgf2 objects.

Every edge is represented by some integer, by a fixed and arbitrary numbering. This numbering is represented by enumb. The function also returns a certificate of optimality of the minimum cycle basis. More precisely a set of linearly independent vectors for which cycle $i$ is the shortest cycle in $g$ with odd intersection with the proof vector $i$ .

The function returns the weight of the Minimum Cycle Basis or is undefined if there were any errors.
The running time is $O( m^3 )$ where $m$ are the number of edges of $g$ .

Parameters:

g An undirected graph.

len A leda::edge_array for the edge lengths.

mcb A leda::array of mcb::spvecgf2 to return the MCB.

proof A leda::array of mcb::spvecgf2 to return the proof.

enumb An edge numbering.

Returns:
The length of the MCB or undefined if some error occured.

Precondition:
g is undirected, simple and loopfree.
len is non-negative

Remarks:
Care must be taken when the template parameter is instantiated with a data type which has rounding errors.

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.
The function computes a minimum cycle basis of an undirected weighted graph $g$ , that is a cycle basis of $g$ with the smallest length (sum of lengths of cycles). The basis is returned as an array of dynamic integer sets, d_int_set, called mcb.
Every edge is represented by some integer, by a fixed and arbitrary numbering. This numbering is represented by enumb.
The function returns the weight of the Minimum Cycle Basis or is undefined if there were any errors.
The running time is $O( m^2 n^2 )$ where $m$ are the number of edges of $g$ and $n$ the number of vertices.
Parameters:

g An undirected graph.

len A leda::edge_array for the edge lengths.

mcb A leda::array of leda::d_int_set to return the MCB.

enumb An edge numbering.

Returns:
The length of the MCB or undefined if some error occured.

Precondition:
g is undirected, simple and loopfree
len is non-negative

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.
The function computes a minimum cycle basis of an undirected weighted graph $g$ , that is a cycle basis of $g$ with the smallest length (sum of lengths of cycles). The basis is returned as an array of dynamic integer sets, d_int_set, called mcb.
Every edge is represented by some integer, by a fixed and arbitrary numbering. This numbering is represented by enumb.
The function also returns a certificate of optimality of the minimum cycle basis. More precisely a set of linearly independent vectors for which cycle $i$ is the shortest cycle in $g$ with odd intersection with the proof vector $i$ .
The function returns the weight of the Minimum Cycle Basis or is undefined if there were any errors.
The running time is $O( m^2 n^2 )$ where $m$ are the number of edges of $g$ and $n$ the number of vertices.
Parameters:

g An undirected graph.

len A leda::edge_array for the edge lengths.

mcb A leda::array of leda::d_int_set to return the MCB.

proof A leda::array of leda::d_int_set to return the proof.

enumb An edge numbering.

Returns:
The length of the MCB or undefined if some error occured.

Precondition:
g is undirected, simple and loopfree
len is non-negative

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.
The function computes a minimum cycle basis of an undirected graph $g$ , that is a cycle basis of $g$ with the smallest length (sum of lengths of cycles). The basis is returned as an array of dynamic integer sets, d_int_set, called mcb.
Every edge is represented by some integer, by a fixed and arbitrary numbering. This numbering is represented by enumb.
The function returns the weight of the Minimum Cycle Basis or is undefined if there were any errors.
The running time is $O( m^2 n^2 )$ where $m$ are the number of edges of $g$ and $n$ the number of vertices.
Parameters:

g An undirected graph.

mcb A leda::array of leda::d_int_set to return the MCB.

enumb An edge numbering.

Returns:
The length of the MCB or undefined if some error occured.

Precondition:
g is undirected, simple and loopfree

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.
The function computes a minimum cycle basis of an undirected graph $g$ , that is a cycle basis of $g$ with the smallest length (sum of lengths of cycles). The basis is returned as an array of dynamic integer sets, d_int_set, called mcb.
Every edge is represented by some integer, by a fixed and arbitrary numbering. This numbering is represented by enumb.
The function also returns a certificate of optimality of the minimum cycle basis. More precisely a set of linearly independent vectors for which cycle $i$ is the shortest cycle in $g$ with odd intersection with the proof vector $i$ .
The function returns the weight of the Minimum Cycle Basis or is undefined if there were any errors.
The running time is $O( m^2 n^2 )$ where $m$ are the number of edges of $g$ and $n$ the number of vertices.
Parameters:

g An undirected graph.

mcb A leda::array of leda::d_int_set to return the MCB.

proof A leda::array of leda::d_int_set to return the proof.

enumb An edge numbering.

Returns:
The length of the MCB or undefined if some error occured.

Precondition:
g is undirected, simple and loopfree

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.
The function computes a Minimum Cycle Basis $B$ of a graph $g$ , that is a cycle basis of $g$ with the smallest length (sum of lengths of cycles). It accepts two template parameters. The first is length type and the second is the container to use for recording the cycles. Currently two options are accepted, leda::d_int_set and mcb::spvecgf2. The basis is returned as an array of Container objects.

Every edge is represented by some integer, by a fixed and arbitrary numbering. This numbering is represented by enumb.
The function returns the weight of the Minimum Cycle Basis or is undefined if there were any errors.
The running time is $O( m^3 )$ where $m$ are the number of edges of $g$ .

Parameters:

g An undirected graph.

len A leda::edge_array for the edge lengths.

mcb A leda::array of Container to return the MCB.

enumb An edge numbering.

Returns:
The length of the MCB or undefined if some error occured.

Precondition:
g is undirected, simple and loopfree.
len is non-negative

Remarks:
Care must be taken when the template parameter is instantiated with a data type which has rounding errors.

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.
The function computes a Minimum Cycle Basis $B$ of a graph $g$ , that is a cycle basis of $g$ with the smallest length (sum of lengths of cycles). It accepts two template parameters. The first is length type and the second is the container to use for recording the cycles. Currently two options are accepted, leda::d_int_set and mcb::spvecgf2. The basis is returned as an array of Container objects.

Every edge is represented by some integer, by a fixed and arbitrary numbering. This numbering is represented by enumb. The function also returns a certificate of optimality of the minimum cycle basis. More precisely a set of linearly independent vectors for which cycle $i$ is the shortest cycle in $g$ with odd intersection with the proof vector $i$ .

The function returns the weight of the Minimum Cycle Basis or is undefined if there were any errors.
The running time is $O( m^3 )$ where $m$ are the number of edges of $g$ .

Parameters:

g An undirected graph.

len A leda::edge_array for the edge lengths.

mcb A leda::array of Container to return the MCB.

proof A leda::array of Container to return the proof.

enumb An edge numbering.

Returns:
The length of the MCB or undefined if some error occured.

Precondition:
g is undirected, simple and loopfree.
len is non-negative

Remarks:
Care must be taken when the template parameter is instantiated with a data type which has rounding errors.

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.
The function computes a Minimum Cycle Basis $B$ of a graph $g$ , that is a cycle basis of $g$ with the smallest length (sum of lengths of cycles). It accepts one template parameters which is the container to use for recording the cycles. Currently two options are accepted, leda::d_int_set and mcb::spvecgf2. The basis is returned as an array of Container objects.

Every edge is represented by some integer, by a fixed and arbitrary numbering. This numbering is represented by enumb.

The function returns the weight of the Minimum Cycle Basis or is undefined if there were any errors.
The running time is $O( m^3 )$ where $m$ are the number of edges of $g$ .

Parameters:

g An undirected graph.

mcb A leda::array of Container to return the MCB.

enumb An edge numbering.

Returns:
The length of the MCB or undefined if some error occured.

Precondition:
g is undirected, simple and loopfree.

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.
The function computes a Minimum Cycle Basis $B$ of a graph $g$ , that is a cycle basis of $g$ with the smallest length (sum of lengths of cycles). It accepts one template parameter which is the container to use for recording the cycles. Currently two options are accepted, leda::d_int_set and mcb::spvecgf2. The basis is returned as an array of Container objects.

Every edge is represented by some integer, by a fixed and arbitrary numbering. This numbering is represented by enumb. The function also returns a certificate of optimality of the minimum cycle basis. More precisely a set of linearly independent vectors for which cycle $i$ is the shortest cycle in $g$ with odd intersection with the proof vector $i$ .

The function returns the weight of the Minimum Cycle Basis or is undefined if there were any errors.
The running time is $O( m^3 )$ where $m$ are the number of edges of $g$ .

Parameters:

g An undirected graph.

mcb A leda::array of Container to return the MCB.

proof A leda::array of Container to return the proof.

enumb An edge numbering.

Returns:
The length of the MCB or undefined if some error occured.

Precondition:
g is undirected, simple and loopfree.

Generated on Tue Apr 22 13:40:09 2008 for mcb LEDA Extension Package by

1.4.6


Undirected Minimum Cycle Basis
These functions implement the three main approaches for computing a minimum cycle basis. All these approaches are based on the Support Vector Approach. Their differences are on the way of finding the shortest non-orthogonal cycle: mcb::UMCB_SVA finds the cycles by maintaining a signed graph mcb::UMCB_HYBRID maintains a list of candidate cycles which is guarantied to contain an MCB, mcb::UMCB_FH maintains the same list as above but in a more elaborate way in order to be able to compute faster the shortest non-orthogonal cycle. In case you have no special preference try the mcb::UMCB function which uses the signed graph implementation and supports multigraphs. The fastest algorithm is mcb::UMCB_SVA.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Directed Minimum Cycle Basis
template<class W>
W	mcb::DMCB (const graph &g, const edge_array< W > &len, array< mcb::spvecfp > &mcb, array< mcb::spvecfp > &proof, const mcb::edge_num &enumb, double error=0.375)
	Compute a minimum cycle basis of a weighted directed graph.
template<class W>
W	mcb::DMCB (const graph &g, const edge_array< W > &len, array< mcb::spvecfp > &mcb, const mcb::edge_num &enumb, double error=0.375)
	Compute a minimum cycle basis of a weighted directed graph.
template<class W>
W	mcb::DMCB (const graph &g, const edge_array< W > &len, array< array< etype > > &mcb, const mcb::edge_num &enumb, double error=0.375)
	Compute a minimum cycle basis of a weighted directed graph.
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 W>
W	mcb::UMCB (const graph &g, const edge_array< W > &len, array< mcb::spvecgf2 > &mcb, const mcb::edge_num &enumb)
	Compute an MCB of an undirected graph (possible a multigraph) using the most general implementation of this library.
int	mcb::UMCB (const graph &g, array< mcb::spvecgf2 > &mcb, const mcb::edge_num &enumb)
	Compute an MCB of an undirected graph (possible a multigraph) using the most general implementation of this library.