Class SparseEdmondsMaximumCardinalityMatching.Algorithm<V,E>

java.lang.Object

org.jgrapht.alg.matching.SparseEdmondsMaximumCardinalityMatching.Algorithm<V,E>

Type Parameters:

V - the vertex type

E - the edge type

Enclosing class:

SparseEdmondsMaximumCardinalityMatching<V,E>

private static class SparseEdmondsMaximumCardinalityMatching.Algorithm<V,E>
extends Object

The actual implementation as an inner class. We use this pattern in order to free the work memory after computation. The outer class can cache the result but can also release all the auxiliary memory.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private static enum	SparseEdmondsMaximumCardinalityMatching.Algorithm.Label	Even, odd and unlabeled labels.

Field Summary

Fields

Modifier and Type	Field	Description
private SparseEdmondsMaximumCardinalityMatching.VertexPartition	base
private final Graph<V,E>	graph
private MatchingAlgorithm<V,E>	initializer
private SparseEdmondsMaximumCardinalityMatching.Algorithm.Label[]	label
private List<Integer>	labeledNodes
private int[]	mate
private int	nodes
private static final int	NULL
private double[]	path1
private double[]	path2
private int[]	pred
private FixedSizeIntegerQueue	queue
private int[]	sourceBridge
(package private) double	strue
private int[]	targetBridge
private Map<V,Integer>	vertexIndexMap
private V[]	vertexMap

Constructor Summary

Constructors

Constructor	Description
Algorithm(Graph<V,E> graph, MatchingAlgorithm<V,E> initializer)

Method Summary

Modifier and Type	Method	Description
Set<E>	computeMatching()
Map<V,Integer>	computeOddSetCover()
private void	findPath(Deque<Integer> p, int x, int y)
private void	initialize()
private void	runInitializer()
private void	shrinkPath(int b, int v, int w)

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

NULL

private static final int NULL

See Also:

• Constant Field Values

graph

private final Graph<V,E> graph

initializer

private MatchingAlgorithm<V,E> initializer

nodes

private int nodes

vertexIndexMap

private Map<V,Integer> vertexIndexMap

vertexMap

private V[] vertexMap

mate

private int[] mate

label

private SparseEdmondsMaximumCardinalityMatching.Algorithm.Label[] label

pred

private int[] pred

strue

double strue

path1

private double[] path1

path2

private double[] path2

sourceBridge

private int[] sourceBridge

targetBridge

private int[] targetBridge

base

private SparseEdmondsMaximumCardinalityMatching.VertexPartition base

queue

private FixedSizeIntegerQueue queue

labeledNodes

private List<Integer> labeledNodes

Constructor Details

Algorithm

public Algorithm(Graph<V,E> graph,
 MatchingAlgorithm<V,E> initializer)

Method Details

initialize

private void initialize()

runInitializer

private void runInitializer()

findPath

private void findPath(Deque<Integer> p,
 int x,
 int y)

shrinkPath

private void shrinkPath(int b,
 int v,
 int w)

computeMatching

public Set<E> computeMatching()

computeOddSetCover

public Map<V,Integer> computeOddSetCover()