All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
List of all members | Classes | Public Types | Public Member Functions | Static Public Attributes
MaxFractionalMatching< GR, TR > Class Template Reference

Detailed Description

template<typename GR, typename TR>
class lemon::MaxFractionalMatching< GR, TR >

This class provides an implementation of fractional matching algorithm based on push-relabel principle.

The maximum cardinality fractional matching is a relaxation of the maximum cardinality matching problem where the odd set constraints are omitted. It can be formulated with the following linear program.

\[ \sum_{e \in \delta(u)}x_e \le 1 \quad \forall u\in V\]

\[x_e \ge 0\quad \forall e\in E\]

\[\max \sum_{e\in E}x_e\]

where $\delta(X)$ is the set of edges incident to a node in $X$. The result can be represented as the union of a matching with one value edges and a set of odd length cycles with half value edges.

The algorithm calculates an optimal fractional matching and a barrier. The number of adjacents of any node set minus the size of node set is a lower bound on the uncovered nodes in the graph. For maximum matching a barrier is computed which maximizes this difference.

The algorithm can be executed with the run() function. After it the matching (the primal solution) and the barrier (the dual solution) can be obtained using the query functions.

The primal solution is multiplied by 2.

Template Parameters
GRThe undirected graph type the algorithm runs on.

#include <lemon/fractional_matching.h>

Classes

struct  SetElevator
 Named parameter for setting Elevator type More...
 
struct  SetMatchingMap
 Named parameter for setting MatchingMap type More...
 
struct  SetStandardElevator
 Named parameter for setting Elevator type with automatic allocation More...
 

Public Types

typedef TR Traits
 The traitsclass" of the algorithm.
 
typedef TR::Graph Graph
 The type of the graph the algorithm runs on.
 
typedef TR::MatchingMap MatchingMap
 The type of the matching map.
 
typedef TR::Elevator Elevator
 The type of the elevator.
 

Public Member Functions

 MaxFractionalMatching (const Graph &graph, bool allow_loops=true)
 
MaxFractionalMatchingmatchingMap (MatchingMap &map)
 Sets the matching map.
 
MaxFractionalMatchingelevator (Elevator &elevator)
 Sets the elevator used by algorithm.
 
const Elevatorelevator () const
 Returns a const reference to the elevator.
 
Execution control

The simplest way to execute the algorithm is to use one of the member functions called run().
If you need more control on the execution, first you must call init() and then one variant of the start() member.

void init ()
 Initializes the internal data structures.
 
void start (bool postprocess=true)
 Starts the algorithm and computes a fractional matching.
 
bool startPerfect (bool postprocess=true)
 Starts the algorithm and computes a perfect fractional matching.
 
void run (bool postprocess=true)
 Runs the algorithm.
 
bool runPerfect (bool postprocess=true)
 Runs the algorithm to find a perfect fractional matching.
 
Query Functions

The result of the Matching algorithm can be obtained using these functions.
Before the use of these functions, either run() or start() must be called.

int matchingSize () const
 Return the number of covered nodes in the matching.
 
const MatchingMapmatchingMap () const
 Returns a const reference to the matching map.
 
int matching (const Edge &edge) const
 Return true if the given edge is in the matching.
 
Arc matching (const Node &node) const
 Return the fractional matching arc (or edge) incident to the given node.
 
bool barrier (const Node &node) const
 Returns true if the node is in the barrier.
 

Static Public Attributes

static const int primalScale = 2
 

Constructor & Destructor Documentation

MaxFractionalMatching ( const Graph graph,
bool  allow_loops = true 
)
inline

Constructor.

Member Function Documentation

MaxFractionalMatching& matchingMap ( MatchingMap map)
inline

Sets the matching map. If you don't use this function before calling run() or init(), an instance will be allocated automatically. The destructor deallocates this automatically allocated map, of course.

Returns
(*this)
MaxFractionalMatching& elevator ( Elevator elevator)
inline

Sets the elevator used by algorithm. If you don't use this function before calling run() or init(), an instance will be allocated automatically. The destructor deallocates this automatically allocated elevator, of course.

Returns
(*this)
const Elevator& elevator ( ) const
inline

Returns a const reference to the elevator.

Precondition
Either run() or init() must be called before using this function.
void init ( )
inline

Initializes the internal data structures and sets the initial matching.

void start ( bool  postprocess = true)
inline

The algorithm computes a maximum fractional matching.

Parameters
postprocessThe algorithm computes first a matching which is a union of a matching with one value edges, cycles with half value edges and even length paths with half value edges. If the parameter is true, then after the push-relabel algorithm it postprocesses the matching to contain only matching edges and half value odd cycles.
bool startPerfect ( bool  postprocess = true)
inline

The algorithm computes a perfect fractional matching. If it does not exists, then the algorithm returns false and the matching is undefined and the barrier.

Parameters
postprocessThe algorithm computes first a matching which is a union of a matching with one value edges, cycles with half value edges and even length paths with half value edges. If the parameter is true, then after the push-relabel algorithm it postprocesses the matching to contain only matching edges and half value odd cycles.
void run ( bool  postprocess = true)
inline

Just a shortcut for the next code:

init();
bool runPerfect ( bool  postprocess = true)
inline

Just a shortcut for the next code:

int matchingSize ( ) const
inline

This function returns the number of covered nodes in the matching.

Precondition
Either run() or start() must be called before using this function.
const MatchingMap& matchingMap ( ) const
inline

Returns a const reference to the node map storing the found fractional matching. This method can be called after running the algorithm.

Precondition
Either run() or init() must be called before using this function.
int matching ( const Edge &  edge) const
inline

This function returns true if the given edge is in the found matching. The result is scaled by primal scale.

Precondition
Either run() or start() must be called before using this function.
Arc matching ( const Node &  node) const
inline

This function returns one of the fractional matching arc (or edge) incident to the given node in the found matching or INVALID if the node is not covered by the matching or if the node is on an odd length cycle then it is the successor edge on the cycle.

Precondition
Either run() or start() must be called before using this function.
bool barrier ( const Node &  node) const
inline

The barrier is a subset of the nodes. If the nodes in the barrier have less adjacent nodes than the size of the barrier, then at least as much nodes cannot be covered as the difference of the two subsets.

Member Data Documentation

const int primalScale = 2
static

Scaling factor for primal solution.