org.openscience.cdk.graph

Class Matching

java.lang.Object

org.openscience.cdk.graph.Matching

public final class Matching
extends Object

A matching is an independent edge set of a graph. This is a set of edges that share no common vertices. A matching is perfect if every vertex in the graph is matched. Each vertex can be matched with exactly one other vertex. This class provides storage and manipulation of a matching. A new match is added with match(int, int), any existing match for the newly matched vertices is no-longer available. The status of a vertex can be queried with matched(int) and the matched vertex obtained with other(int).

Author:

John May

See Also:

Matching (graph theory), Wikipedia

Belongs to CDK module:

standard

Method Summary

Modifier and Type	Method and Description
void	match(int u, int v) Add the edge '{u,v}' to the matched edge set.
boolean	matched(int v) Determine if a vertex has a match.
int	other(int v) Access the vertex matched with 'v'.
boolean	perfect(int[][] graph, BitSet subset) Attempt to augment the matching such that it is perfect over the subset of vertices in the provided graph.
String	toString()
void	unmatch(int v) Remove a matching for the specified vertex.
boolean	unmatched(int v) Determine if a vertex is not matched.
static Matching	withCapacity(int capacity) Create an empty matching with the specified capacity.

Methods inherited from class java.lang.Object

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

Method Detail

match

public void match(int u,
                  int v)

Add the edge '{u,v}' to the matched edge set. Any existing matches for 'u' or 'v' are removed from the matched set.

Parameters:

u - a vertex

v - another vertex

other

public int other(int v)

Access the vertex matched with 'v'.

Parameters:

v - vertex

Returns:

matched vertex

Throws:

IllegalArgumentException - the vertex is currently unmatched

unmatch

public void unmatch(int v)

Remove a matching for the specified vertex.

Parameters:

v - vertex

matched

public boolean matched(int v)

Determine if a vertex has a match.

Parameters:

v - vertex

Returns:

the vertex is matched

unmatched

public boolean unmatched(int v)

Determine if a vertex is not matched.

Parameters:

v - a vertex

Returns:

the vertex has no matching

perfect

public boolean perfect(int[][] graph,
                       BitSet subset)

Attempt to augment the matching such that it is perfect over the subset of vertices in the provided graph.

Parameters:

graph - adjacency list representation of graph

subset - subset of vertices

Returns:

the matching was perfect

Throws:

IllegalArgumentException - the graph was a different size to the matching capacity

withCapacity

public static Matching withCapacity(int capacity)

Create an empty matching with the specified capacity.

Parameters:

capacity - maximum number of vertices

Returns:

empty matching

toString

public String toString()

Overrides:

toString in class Object