Package org.openscience.cdk.graph
Class Matching
java.lang.Object
org.openscience.cdk.graph.Matching
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:
- Belongs to CDK module:
- standard
-
Method Summary
Modifier and TypeMethodDescriptionvoid
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
Attempt to augment the matching such that it is perfect over the subset of vertices in the provided graph.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.
-
Method Details
-
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 vertexv
- 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
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 graphsubset
- subset of vertices- Returns:
- the matching was perfect
- Throws:
IllegalArgumentException
- the graph was a different size to the matching capacity
-
withCapacity
Create an empty matching with the specified capacity.- Parameters:
capacity
- maximum number of vertices- Returns:
- empty matching
-
toString
-