mcb_approx.h File Reference

---

Detailed Description

Algorithms for approximate MCB in undirected and directed graphs.

See also:

mcb::edge_num mcb::spvecgf2 mcb::spvecfp

#include <LEP/mcb/config.h>
#include <LEP/mcb/umcb.h>
#include <LEP/mcb/spanner.h>
#include <LEP/mcb/ushortpath.h>
#include <LEP/mcb/dmcb.h>
#include <LEDA/edge_map.h>
#include <LEDA/node_map.h>

Include dependency graph for mcb_approx.h:

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

Go to the source code of this file.

Namespaces
namespace	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 . Note that the minimum cycle basis in might not be the minimum cycle basis of the graph.
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 W>
W	mcb::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.
int	mcb::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.

---