Package 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
    See Also:
    Matching (graph theory), Wikipedia
    Belongs to CDK module:
    standard

    • 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