Package com.jgalgo

Interface Matching

  • public interface Matching
    A matching in a graph.

    Given a graph \(G=(V,E)\), a matching is a sub set of edges \(M\) such that any vertex in \(V\) has at most one adjacent edge in \(M\). Its a common problem to compute the maximum (cardinality) matching, namely the matching with the greatest number of edges. Another variant is to compute the maximum weighted matching with respect to some weight function.

    Author:
    Barak Ugav
    See Also:
    MatchingAlgorithm, Wikipedia

    • Method Detail

      • isVertexMatched

        boolean isVertexMatched​(int vertex)
        Check whether a vertex is matched by the matching.

        A vertex \(v\) is said to be matched if the matching contains an edge \((v,w)\) for some other vertex \(w\).

        Parameters:
        vertex - a vertex
        Returns:
        true if vertex has an adjacent edge in the matching, else false

      • getMatchedEdge

        int getMatchedEdge​(int vertex)
        Get the only matched edge adjacent to a given vertex.
        Parameters:
        vertex - a vertex
        Returns:
        the edge adjacent to vertex in the matching, or -1 if vertex is not matched

      • matchedVertices

        IntCollection matchedVertices()
        Get all the vertices matched by the matching.

        A vertex \(v\) is said to be matched if the matching contains an edge \((v,w)\) for some other vertex \(w\).

        Returns:
        all the matched vertices

      • unmatchedVertices

        IntCollection unmatchedVertices()
        Get all the vertices that are not matched by the matching.

        A vertex \(v\) is said to be matched if the matching contains an edge \((v,w)\) for some other vertex \(w\).

        Returns:
        all the unmatched vertices

      • containsEdge

        boolean containsEdge​(int edge)
        Check whether an edge is part of the matching.

        A matching \(M\) is a sub set of \(E\), the edge set of the graph. This method check whether a given edge is in \(M\).

        Parameters:
        edge - an edge
        Returns:
        true if the edge is part of the matching, else false

      • edges

        IntCollection edges()
        The collection of edges forming this matching.
        Returns:
        collection containing all the edges that are part of this matching

      • weight

        double weight​(WeightFunction w)
        Get the weight of the matching with respect to some weight function.

        The weight of a matching is defined as the sum of its edges weights.

        Parameters:
        w - an edge weight function
        Returns:
        the sum of this matching edges weights

      • isPerfect

        boolean isPerfect()
        Check whether this matching is perfect.

        A perfect matching is a matching in which all the vertices are matched.

        Returns:
        true if this matching is perfect, else false.