Package com.jgalgo.alg.match

Interface MatchingAlgo

All Known Implementing Classes:
MatchingAlgoAbstract, MatchingAlgoAbstractBasedMaximum, MatchingAlgoAbstractBasedMinimum, MatchingAlgoAbstractCardinality, MatchingCardinalityBipartiteHopcroftKarp, MatchingCardinalityGabow1976, MatchingWeightedBipartiteHungarianMethod, MatchingWeightedBipartiteSssp, MatchingWeightedBlossomV, MatchingWeightedGabow1990, MatchingWeightedGabow1990Simpler
public interface MatchingAlgo
Maximum/minimum matching algorithm.

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\). A maximum cardinality matching is a matching with the maximum number of edges in \(M\). A maximum/minimum weighted matching is a matching with the maximum/minimum edges weight sum with respect to some weight function. A perfect maximum/minimum weighted matching is a matching with the maximum/minimum edges weight sum out of all the matchings in which each vertex has an adjacent matched edge. Note that the weight of a perfect maximum matching is smaller or equal to the weight of a maximum weight matching.

Use newInstance() to get a default implementation of this interface. A builder obtained via builder() may support different options to obtain different implementations.

Author:
Barak Ugav
See Also:

  • Method Details

    • computeMaximumMatching

      <V, E> Matching<V,E> computeMaximumMatching(Graph<V,E> g, WeightFunction<E> w)
      Compute the maximum weighted matching of a weighted undirected graph.

      To compute the maximum cardinality (non weighted) matching, pass null instead of the weight function w.

      If g is IntGraph, the returned object is IMatching.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - an undirected graph
      w - an edge weight function
      Returns:
      the computed matching
      Throws:
      IllegalArgumentException - if g is a directed graph

    • computeMinimumMatching

      <V, E> Matching<V,E> computeMinimumMatching(Graph<V,E> g, WeightFunction<E> w)
      Compute the minimum weighted matching of a weighted undirected graph.

      If g is IntGraph, the returned object is IMatching.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - an undirected graph
      w - an edge weight function
      Returns:
      the computed matching
      Throws:
      IllegalArgumentException - if g is a directed graph

    • computeMaximumPerfectMatching

      <V, E> Matching<V,E> computeMaximumPerfectMatching(Graph<V,E> g, WeightFunction<E> w)
      Compute the maximum perfect matching of a weighted undirected graph.

      A perfect matching in which each vertex has an adjacent matched edge is assumed to exist in the input graph, and if no such matching exist the behavior is undefined.

      To compute the maximum cardinality (non weighted) perfect matching, pass null instead of the weight function w.

      If g is IntGraph, the returned object is IMatching.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - an undirected graph
      w - an edge weight function
      Returns:
      the computed perfect matching
      Throws:
      IllegalArgumentException - if g is a directed graph

    • computeMinimumPerfectMatching

      <V, E> Matching<V,E> computeMinimumPerfectMatching(Graph<V,E> g, WeightFunction<E> w)
      Compute the minimum perfect matching of a weighted undirected graph.

      A perfect matching in which each vertex has an adjacent matched edge is assumed to exist in the input graph, and if no such matching exist the behavior is undefined.

      To compute the maximum cardinality (non weighted) matching, pass null instead of the weight function w. Note that this is equivalent to computeMaximumPerfectMatching(Graph, WeightFunction).

      If g is IntGraph, the returned object is IMatching.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - an undirected graph
      w - an edge weight function
      Returns:
      the computed perfect matching
      Throws:
      IllegalArgumentException - if g is a directed graph

    • newInstance

      static MatchingAlgo newInstance()
      Create a new matching algorithm object.

      This is the recommended way to instantiate a new MatchingAlgo object. The MatchingAlgo.Builder might support different options to obtain different implementations.

      Returns:
      a default implementation of MatchingAlgo

    • builder

      static MatchingAlgo.Builder builder()
      Create a new matching algorithm builder.

      Use newInstance() for a default implementation.

      Returns:
      a new builder that can build MatchingAlgo objects