The main package namespace. More...

Classes
class	edge_num
	An edge numbering class. More...

class	spvecfp
	A sparse vector with elements in . More...

class	spvecgf2
	A sparse vector with elements in GF2. More...

Typedefs
typedef int	indextype

typedef leda::integer	ptype

Functions
std::ostream &	operator<< (std::ostream &o, const spvecgf2 &v)

std::istream &	operator>> (std::istream &o, spvecgf2 &v)

std::ostream &	operator<< (std::ostream &o, const spvecfp &v)

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

template<class W >
W	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. More...

int	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. More...

Directed Minimum Cycle Basis
template<class W >
W	DMCB (const graph &g, const edge_array< W > &len, array< mcb::spvecfp > &mcb, array< mcb::spvecfp > &proof, const mcb::edge_num &enumb, ptype &p)

template<class W >
W	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. More...

template<class W >
W	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. More...

template<class W >
W	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. More...

Undirected Approximate Minimum Cycle Basis
template<class W >
W	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. More...

int	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. More...

Directed Approximate Minimum Cycle Basis
template<class W >
W	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. More...

template<class W >
W	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. More...


template<class Container >
void	cycle_matrix (const graph &g, const array< Container > &cb, const mcb::edge_num &enumb, integer_matrix &B)
	Compute the cycle matrix of a cycle basis. More...

std::ostream &	output_maple_format (std::ostream &out, const integer_matrix &B)
	Output a LEDA integer_matrix in a format compatible with maple. More...

template<class Container >
leda::integer	determinant (const graph &g, const array< Container > &cb, const mcb::edge_num &enumb)
	Compute the determinant of a cycle basis. More...

Detailed Description

The main package namespace.

Typedef Documentation

typedef int mcb::indextype

The index type used for the directed cycle basis algorithm.

typedef leda::integer mcb::ptype

The prime type used for the directed cycle basis algorithm.

Function Documentation

std::ostream& mcb::operator<<	(	std::ostream &	o,
		const spvecfp &	v
	)

Output a sparse vector to a stream.

Parameters

o	The stream to output to.
v	The sparse vector to output to.

Returns: The stream after outputing.

std::ostream& mcb::operator<<	(	std::ostream &	o,
		const spvecgf2 &	v
	)

Output a sparse vector.

Parameters

o	The stream to output to.
v	The sparse vector to output.

Returns: The stream after output.

Referenced by mcb::spvecgf2::inf().

std::istream& mcb::operator>>	(	std::istream &	o,
		spvecgf2 &	v
	)

Input a sparse vector.

Parameters

o	The stream to input from.
v	Where to store the sparse vector.

Returns: The stream after reading.

Referenced by mcb::spvecgf2::inf().

Classes

Typedefs

Functions

Detailed Description

Typedef Documentation

Function Documentation