Various Utilities

template<class Container >
void	mcb::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 &	mcb::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	mcb::determinant (const graph &g, const array< Container > &cb, const mcb::edge_num &enumb)
	Compute the determinant of a cycle basis. More...

Detailed Description

Function Documentation

template<class Container >

void mcb::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.

Let be the dimension of the cycle space. The cycle matrix is an matrix. Each row corresponds to a cycle in the cycle basis. Each column corresponds to an edge of the graph among the edges that have numbering in mcb::edge_num from 0 to N-1. The remaining edges are the edges of a fixed spanning tree.

The edges have values either -1,0,1 based on an arbitrary orientation of traversing the cycle and based on the orientation of the edges of the graph.

The absolute value of the determinant of this matrix describes the cycle basis. If it is positive then the cycle basis is a directed cycle basis. If it is an odd numbers then the basis is an undirected cycle basis. If it is 1 then the basis is an integral cycle basis.

Parameters

g	The graph
cb	The cycle basis
enumb	An edge numbering
B	The matrix to output the cycle matrix.

Precondition

B has dimension .

References mcb::edge_num::dim_cycle_space(), and mcb::output_maple_format().

template<class Container >

leda::integer mcb::determinant	(	const graph &	g,
		const array< Container > &	cb,
		const mcb::edge_num &	enumb
	)

Compute the determinant of a cycle basis.

Parameters

g	A graph.
cb	A leda::array of Container with a cycle basis. Container can be either mcb::spvecgf2 and leda::d_int_set for undirected graphs or mcb::spvecfp for directed.
enumb	An edge numbering.

Returns

The determinant of the cycle basis, as a leda::integer.

Precondition

g is loopfree.

References mcb::edge_num::dim_cycle_space().

std::ostream& mcb::output_maple_format	(	std::ostream &	out,
		const integer_matrix &	B
	)

Output a LEDA integer_matrix in a format compatible with maple.

Parameters

out	The output stream
B	The matrix to output

Returns

The output stream after outputing.

Referenced by mcb::cycle_matrix().