Satsuma.MaximumMatching Class Reference

Finds a maximum matching in a bipartite graph using the alternating path algorithm. More...

Inheritance diagram for Satsuma.MaximumMatching:

Public Member Functions
void	Add (Arc arc)
	Tries to add a specific arc to the current matching. More...
void	Clear ()
	Removes all arcs from the matching. More...
int	GreedyGrow (int maxImprovements=int.MaxValue)
	Grows the current matching greedily. More...
	MaximumMatching (IGraph graph, Func< Node, bool > isRed)
void	Run ()
	Grows the current matching to a maximum matching by running the whole alternating path algorithm. More...

Properties
IGraph	Graph [get, set]
Func< Node, bool >	IsRed [get, set]
	Describes a bipartition of the input graph by dividing its nodes into red and blue ones. More...
IMatching	Matching [get]
	The current matching. More...

Detailed Description

Finds a maximum matching in a bipartite graph using the alternating path algorithm.

See Also

MinimumCostMatching

Definition at line 33 of file MaximumMatching.cs.

Constructor & Destructor Documentation

Satsuma.MaximumMatching.MaximumMatching	(	IGraph	graph,
		Func< Node, bool >	isRed
	)

Definition at line 46 of file MaximumMatching.cs.

Member Function Documentation

void Satsuma.MaximumMatching.Add

(

Arc

arc

)

Tries to add a specific arc to the current matching.

If the arc is already present, does nothing.

Parameters

arc	An arc of Graph.

Exceptions

ArgumentException

Trying to add an illegal arc.

Definition at line 96 of file MaximumMatching.cs.

void Satsuma.MaximumMatching.Clear

(

)

Removes all arcs from the matching.

Implements Satsuma.IClearable.

Definition at line 57 of file MaximumMatching.cs.

int Satsuma.MaximumMatching.GreedyGrow

(

int

maxImprovements = int.MaxValue

)

Grows the current matching greedily.

Can be used to speed up optimization by finding a reasonable initial matching.

Parameters

maxImprovements

The maximum number of arcs to grow the current matching with.

Returns

The number of arcs added to the matching.

Definition at line 70 of file MaximumMatching.cs.

void Satsuma.MaximumMatching.Run

(

)

Grows the current matching to a maximum matching by running the whole alternating path algorithm.

Note

Calling GreedyGrow before Run may speed up operation.

Definition at line 140 of file MaximumMatching.cs.

Property Documentation

IGraph Satsuma.MaximumMatching.Graph

getset

Definition at line 35 of file MaximumMatching.cs.

Func<Node, bool> Satsuma.MaximumMatching.IsRed

getset

Describes a bipartition of the input graph by dividing its nodes into red and blue ones.

Definition at line 37 of file MaximumMatching.cs.

IMatching Satsuma.MaximumMatching.Matching

get

The current matching.

Definition at line 42 of file MaximumMatching.cs.

---

The documentation for this class was generated from the following file:

• src/MaximumMatching.cs