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.
std::ostream & mcb::output_maple_format (std::ostream &out, const integer_matrix &B)
 Output a LEDA integer_matrix in a format compatible with maple.
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.

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 $N$ be the dimension of the cycle space. The cycle matrix is an $N \times N$ 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 $N \times N$.

$N>0$

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.

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.

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