Algorithms for approximate MCB in undirected and directed graphs. More...
#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 | |
| mcb | |
| The main package namespace. | |
Functions | |
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. More... | |
| 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. More... | |
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. More... | |
| 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. More... | |
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. More... | |
| 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. More... | |
Detailed Description
Algorithms for approximate MCB in undirected and directed graphs.
- See also
- mcb::edge_num mcb::spvecgf2 mcb::spvecfp
