org.openscience.cdk.graph

## Class 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
Matching (graph theory), Wikipedia
Belongs to CDK module:
standard
• ### Method Summary

Methods
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`