Package com.jgalgo.alg.match

Interface Matching<V,​E>

  • Type Parameters:
    V - the vertices type
    E - the edges type
    All Known Subinterfaces:
    IMatching
    public interface Matching<V,​E>
    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:
    MatchingAlgo, Wikipedia

    • Method Detail

      • isVertexMatched

        boolean isVertexMatched​(V 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

        E getMatchedEdge​(V 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

        Set<V> 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

        Set<V> 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​(E 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

        Set<E> edges()
        The collection of edges forming this matching.
        Returns:
        collection containing all the edges that are part of this matching

      • 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.

      • isMatching

        static <V,​E> boolean isMatching​(Graph<V,​E> g,
                                      Collection<E> edges)
        Check whether the given collection of edges form a valid matching in the graph.

        A matching \(M\) is a sub set of \(E\), the edge set of the graph, in which for each vertex of the graph, no more than one adjacent edge is in \(M\). This method check whether a given collection of edges form a valid matching.

        If g is an IntGraph, its better to pass a IntCollection as edges to avoid boxing/unboxing.

        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - a graph
        edges - a collection of edges
        Returns:
        true if edges form a valid matching in g, else false