org.jgrapht.alg.decomposition

Class DulmageMendelsohnDecomposition.Decomposition<V,E>

java.lang.Object

org.jgrapht.alg.decomposition.DulmageMendelsohnDecomposition.Decomposition<V,E>

Type Parameters:

V - vertex type

E - edge type

Enclosing class:

DulmageMendelsohnDecomposition<V,E>

public static class DulmageMendelsohnDecomposition.Decomposition<V,E>
extends Object

The output of a decomposition operation

Method Summary

Modifier and Type	Method and Description
Set<V>	getPartition1DominatedSet() Gets the subset dominated by partition1.
Set<V>	getPartition2DominatedSet() Gets the subset dominated by partition2.
List<Set<V>>	getPerfectMatchedSets() Gets the remaining subset, or subsets in the fine decomposition.

Methods inherited from class java.lang.Object

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

Method Detail

getPartition1DominatedSet

public Set<V> getPartition1DominatedSet()

Gets the subset dominated by partition1. Where $D$ is the set of vertices in $G$ that are not matched in the maximum matching of $G$, this set contains members of the first partition and vertices from the second partition that neighbour them.

Returns:

The vertices in $D \cap V_1$ and their neighbours

getPartition2DominatedSet

public Set<V> getPartition2DominatedSet()

Gets the subset dominated by partition2. Where $D$ is the set of vertices in $G$ that are not matched in the maximum matching of $G$, this set contains members of the second partition and vertices from the first partition that neighbour them.

Returns:

The vertices in $D \cap V_2$ and their neighbours

getPerfectMatchedSets

public List<Set<V>> getPerfectMatchedSets()

Gets the remaining subset, or subsets in the fine decomposition. This set contains vertices that are matched in the maximum matching of the graph $G$. If the fine decomposition was used, this will be multiple sets, each a strongly-connected-component of the matched subset of $G$.

Returns:

List of Sets of vertices in the subsets