Module org.jgrapht.core

Package org.jgrapht.alg.matching

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 java.lang.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 class	SparseEdmondsMaximumCardinalityMatching.Algorithm.Label	Even, odd and unlabeled labels.

Field Summary

Fields

Modifier and Type	Field	Description
private SparseEdmondsMaximumCardinalityMatching.VertexPartition	base
private Graph<V,E>	graph
private MatchingAlgorithm<V,E>	initializer
private SparseEdmondsMaximumCardinalityMatching.Algorithm.Label[]	label
private java.util.List<java.lang.Integer>	labeledNodes
private int[]	mate
private int	nodes
private static 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 java.util.Map<V,java.lang.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
java.util.Set<E>	computeMatching()
java.util.Map<V,java.lang.Integer>	computeOddSetCover()
private void	findPath(java.util.Deque<java.lang.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 java.lang.Object

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

Field Detail

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 java.util.Map<V,java.lang.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 java.util.List<java.lang.Integer> labeledNodes

Constructor Detail

Algorithm

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

Method Detail

initialize

private void initialize()

runInitializer

private void runInitializer()

findPath

private void findPath(java.util.Deque<java.lang.Integer> p,
                      int x,
                      int y)

shrinkPath

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

computeMatching

public java.util.Set<E> computeMatching()

computeOddSetCover

public java.util.Map<V,java.lang.Integer> computeOddSetCover()