MaxFractionalMatching

Declared in lemon/fractional_matching.h, in the group Matching Algorithms; the same class on the Doxygen site.

template< typename GR , typename TR >
class MaxFractionalMatching

Max cardinality fractional matching.

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:

GR – The undirected graph type the algorithm runs on.

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.

inline void init()

Initializes the internal data structures.

Initializes the internal data structures and sets the initial matching.

inline void start( bool postprocess = true )

Starts the algorithm and computes a fractional matching.

The algorithm computes a maximum fractional matching.

Parameters:

postprocess – The 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.

inline bool startPerfect( bool postprocess = true )

Starts the algorithm and computes a perfect fractional matching.

The algorithm computes a perfect fractional matching. If it does not exist, then the algorithm returns false, the matching is undefined, and barrier() gives a set of nodes with fewer neighbours than nodes, which proves that no perfect fractional matching exists.

Parameters:

postprocess – The 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.

inline void run( bool postprocess = true )

Runs the algorithm.

Just a shortcut for the next code:

init();
start();

inline bool runPerfect( bool postprocess = true )

Runs the algorithm to find a perfect fractional matching.

Just a shortcut for the next code:

init();
startPerfect();

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.

inline int matchingSize() const

Return the number of covered nodes in the matching.

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

Pre:

Either run() or start() must be called before using this function.

inline const MatchingMap & matchingMap() const

Returns a const reference to the matching map.

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

Pre:

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

inline int matching( const Edge & edge ) const

Return the value of the given edge in the matching.

This function returns the value of the given edge in the found matching, scaled by primal scale: 2 for an edge of value 1, 1 for an edge of an odd cycle (a loop included) and 0 for an edge not in the matching.

Pre:

Either run() or start() must be called before using this function.

inline Arc matching( const Node & node ) const

Return the fractional matching arc (or edge) incident to the given node.

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.

Pre:

Either run() or start() must be called before using this function.

inline bool barrier( const Node & node ) const

Returns true if the node is in the barrier.

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.

Public Types

typedef TR Traits

The traits class 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.

typedef MaxFractionalMatching Create

Public Functions

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

Constructor.

inline ~MaxFractionalMatching()
inline MaxFractionalMatching & matchingMap( MatchingMap & map )

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)

inline MaxFractionalMatching & elevator( Elevator & elevator )

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)

inline const Elevator & elevator() const

Returns a const reference to the elevator.

Pre:

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

Public Static Attributes

static const int primalScale = 2

Scaling factor for primal solution.

Protected Functions

inline MaxFractionalMatching()
template< typename T >
struct SetMatchingMapTraits : public Traits

Public Types

typedef T MatchingMap

Public Static Functions

static inline MatchingMap * createMatchingMap( const Graph & )
template< typename T >
struct SetMatchingMap : public MaxFractionalMatching< Graph , SetMatchingMapTraits< T > >

Named parameter for setting MatchingMap type.

Public Types

typedef MaxFractionalMatching< Graph , SetMatchingMapTraits< T > > Create
template< typename T >
struct SetElevatorTraits : public Traits

Public Types

typedef T Elevator

Public Static Functions

static inline Elevator * createElevator( const Graph & , int )
template< typename T >
struct SetElevator : public MaxFractionalMatching< Graph , SetElevatorTraits< T > >

Named parameter for setting Elevator type. If this named parameter is used, then an external elevator object must be passed to the algorithm using the elevator() function before calling run() or init().

Public Types

typedef MaxFractionalMatching< Graph , SetElevatorTraits< T > > Create
template< typename T >
struct SetStandardElevatorTraits : public Traits

Public Types

typedef T Elevator

Public Static Functions

static inline Elevator * createElevator( const Graph & graph , int max_level )
template< typename T >
struct SetStandardElevator : public MaxFractionalMatching< Graph , SetStandardElevatorTraits< T > >

Named parameter for setting Elevator type with automatic allocation. The Elevator should have standard constructor interface to be able to automatically created by the algorithm (i.e. the graph and the maximum level should be passed to it). However an external elevator object could also be passed to the algorithm with the elevator() function before calling run() or init().

See also

SetElevator

Public Types

typedef MaxFractionalMatching< Graph , SetStandardElevatorTraits< T > > Create