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:

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    containsEdge(E edge)
    Check whether an edge is part of the matching.
    Set<E>
    edges()
    The collection of edges forming this matching.
    E
    getMatchedEdge(V vertex)
    Get the only matched edge adjacent to a given vertex.
    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.
    boolean
    isPerfect()
    Check whether this matching is perfect.
    boolean
    isVertexMatched(V vertex)
    Check whether a vertex is matched by the matching.
    Set<V>
    matchedVertices()
    Get all the vertices matched by the matching.
    Set<V>
    unmatchedVertices()
    Get all the vertices that are not matched by the matching.

  • Method Details

    • 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