Approximate MCB

Undirected Approximate Minimum Cycle Basis

template<class W>

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

Compute an undirected approximate MCB of a weighted graph.

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

Compute an undirected approximate MCB of a graph.

Directed Approximate Minimum Cycle Basis

template<class W>

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

Compute a directed approximate MCB of a weighted graph.

template<class W>

W mcb::DMCB_APPROX (const graph &g, const edge_array< W > &len, const int k, array< mcb::spvecfp > &mcb, const mcb::edge_num &enumb, mcb::ptype prime)

Compute a directed approximate MCB of a weighted graph in $\mathcal{F}_p$ . Note that the minimum cycle basis in $\mathcal{F}_p$ might not be the minimum cycle basis of the graph.

Function Documentation

template<class W>

W mcb::DMCB_APPROX ( const graph & g,

const edge_array< W > & len,

const int k,

array< mcb::spvecfp > & mcb,

const mcb::edge_num & enumb,

mcb::ptype prime

)

Compute a directed approximate MCB of a weighted graph in $\mathcal{F}_p$ . Note that the minimum cycle basis in $\mathcal{F}_p$ might not be the minimum cycle basis of the graph.
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 returns the weight of the possibly approximate Minimum Cycle Basis or is undefined if there were any errors.

The running time is $O( mn^{1+1/k} + \min(m^3 + mn^2 \log n,n^{3+3/k}) )$ where $n$ are the number of nodes of $g$ , $m$ the number of edges and $k$ is an integer $\ge 1$ .

Parameters:

g An directed graph.

len A leda::edge_array for the edge lengths.

k How much to approximate?

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

enumb An edge numbering.

prime A leda::integer prime number in order to do the computation in $\mathcal{F}_p$ .

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

Precondition:
g is loopfree.
len is non-negative
k must be an integer greater than zero
prime is a prime number > 2

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

template<class W>

W mcb::DMCB_APPROX ( const graph & g,

const edge_array< W > & len,

const int k,

array< mcb::spvecfp > & mcb,

const mcb::edge_num & enumb,

double error = 0.375

)

Compute a directed approximate MCB of a weighted graph.
The function computes an $(2k-1)$ -approximate Minimum Cycle Basis $B$ of a graph $g$ . 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 $(2k-1)$ -approximate minimum cycle basis.
The function returns the weight of the approximate Minimum Cycle Basis or is undefined if there were any errors.

The running time is $O( mn^{1+1/k} + \min(m^3 + mn^2 \log n,n^{3+3/k}) )$ where $n$ are the number of nodes of $g$ , $m$ the number of edges and $k$ is an integer $\ge 1$ .

Parameters:

g An directed graph.

len A leda::edge_array for the edge lengths.

k How much to approximate?

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

enumb An edge numbering.

error The error probability

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

Precondition:
g is loopfree.
len is non-negative
k must be an integer greater than zero
error is positive and less than one

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

int mcb::UMCB_APPROX ( const graph & g,

const int k,

array< mcb::spvecgf2 > & mcb,

const mcb::edge_num & enumb

)

Compute an undirected approximate MCB of a graph.
The function computes an $(2k-1)$ -approximate Minimum Cycle Basis $B$ of a graph $g$ . The basis is returned as an array of sparse vectors, spvecgf2, 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 approximate Minimum Cycle Basis or is undefined if there were any errors.
Even if the graph is directed this function computes an approximate MCB of the underlying undirected graph.

The running time is $O( m n^{1+1/k} + \min( m^3 + mn^2 \log n, n^{3+3/k}) )$ where $n$ are the number of nodes of $g$ , $m$ the number of edges and $k$ is an integer $\ge 1$ .

Parameters:

g An undirected graph.

k How much to approximate?

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

enumb An edge numbering.

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

Precondition:
g is loopfree.
len is non-negative
k must be an integer greater than zero

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_APPROX ( const graph & g,

const edge_array< W > & len,

const int k,

array< mcb::spvecgf2 > & mcb,

const mcb::edge_num & enumb

)

Compute an undirected approximate MCB of a weighted graph.
The function computes an $(2k-1)$ -approximate Minimum Cycle Basis $B$ of a graph $g$ . The basis is returned as an array of sparse vectors, spvecgf2, 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 approximate Minimum Cycle Basis or is undefined if there were any errors.
Even if the graph is directed this function computes an approximate MCB of the underlying undirected graph.

The running time is $O( m n^{1+1/k} + \min( m^3 + mn^2 \log n, n^{3+3/k}) )$ where $n$ are the number of nodes of $g$ , $m$ the number of edges and $k$ is an integer $\ge 1$ .

Parameters:

g An graph.

len A leda::edge_array for the edge lengths.

k How much to approximate?

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

enumb An edge numbering.

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

Precondition:
g is loopfree.
len is non-negative
k must be an integer greater than zero

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

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

1.4.6


Undirected Approximate Minimum Cycle Basis
template<class W>
W	mcb::UMCB_APPROX (const graph &g, const edge_array< W > &len, const int k, array< mcb::spvecgf2 > &mcb, const mcb::edge_num &enumb)
	Compute an undirected approximate MCB of a weighted graph.
int	mcb::UMCB_APPROX (const graph &g, const int k, array< mcb::spvecgf2 > &mcb, const mcb::edge_num &enumb)
	Compute an undirected approximate MCB of a graph.
Directed Approximate Minimum Cycle Basis
template<class W>
W	mcb::DMCB_APPROX (const graph &g, const edge_array< W > &len, const int k, array< mcb::spvecfp > &mcb, const mcb::edge_num &enumb, double error=0.375)
	Compute a directed approximate MCB of a weighted graph.
template<class W>
W	mcb::DMCB_APPROX (const graph &g, const edge_array< W > &len, const int k, array< mcb::spvecfp > &mcb, const mcb::edge_num &enumb, mcb::ptype prime)
	Compute a directed approximate MCB of a weighted graph in $\mathcal{F}_p$ . Note that the minimum cycle basis in $\mathcal{F}_p$ might not be the minimum cycle basis of the graph.