Package 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:

  • Method Summary

    Modifier and Type
    Method
    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 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 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