umcb.h File Reference

---

Detailed Description

Algorithms for undirected MCB.

Given an undirected graph and a non-negative length function on the edges , a minimum cycle basis is a set of cycles which can generate the cycle space and at the same time has minimum total length.

Each cycle of the graph is assumed to be a 0-1 vector indexed on the edge set, and operations between cycles is performed in GF(2). The length of a cycle basis is the sum of the length of its cycles and the length of a cycle is the sum of the length of its edges.

The solution of a minimum cycle basis problem can be in the following two forms.

• A pair (mcb, proof) where both are arrays of mcb::spvecgf2, array< mcb::spvecgf2 >. Each mcb::spvecgf2 represents a cycle or some edge set. Each edge of the graph is represented by a unique number provided by an edge numbering, mcb::edge_num.
• A pair (mcb, proof) where both are arrays of compressed integer sets, array< d_int_set >. Each integer sets represents a cycle. In these integer sets, each edge of the graph is represented by a unique number provided by the edge numbering, mcb::edge_num.

Most functions of this section are templates functions. The template parameter W can be instantiated with any number type. Attention must be paid in order to avoid overflow of values.

The whole package is protected using a namespace called "mcb", and therefore using anything requires mcb::xx or the using namespace mcb directive.

See also:

mcb::edge_num mcb::spvecgf2

#include <LEP/mcb/config.h>
#include <LEDA/graph.h>
#include <LEDA/d_int_set.h>
#include <LEDA/edge_array.h>
#include <LEDA/node_array.h>
#include <LEDA/array.h>
#include <LEDA/list.h>
#include <LEP/mcb/spvecgf2.h>
#include <LEP/mcb/signed.h>
#include <LEP/mcb/superset.h>
#include <LEP/mcb/sptrees.h>
#include <LEP/mcb/transform.h>
#include <LEP/mcb/verify.h>

Include dependency graph for umcb.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

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

---