Package com.jgalgo.alg.match

Class MatchingAlgoAbstract

java.lang.Object
com.jgalgo.alg.match.MatchingAlgoAbstract
All Implemented Interfaces:
MatchingAlgo
Direct Known Subclasses:
MatchingAlgoAbstractBasedMaximum, MatchingAlgoAbstractBasedMinimum, MatchingAlgoAbstractCardinality
public abstract class MatchingAlgoAbstract extends Object implements MatchingAlgo
Abstract class for computing matchings in graphs.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:
Barak Ugav

  • Constructor Details

    • MatchingAlgoAbstract

      public MatchingAlgoAbstract()
      Default constructor.

  • Method Details

    • computeMaximumMatching

      public <V, E> Matching<V,E> computeMaximumMatching(Graph<V,E> g, WeightFunction<E> w)
      Description copied from interface: MatchingAlgo
      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.

      Specified by:
      computeMaximumMatching in interface MatchingAlgo
      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - an undirected graph
      w - an edge weight function
      Returns:
      the computed matching

    • computeMinimumMatching

      public <V, E> Matching<V,E> computeMinimumMatching(Graph<V,E> g, WeightFunction<E> w)
      Description copied from interface: MatchingAlgo
      Compute the minimum weighted matching of a weighted undirected graph.

      If g is IntGraph, the returned object is IMatching.

      Specified by:
      computeMinimumMatching in interface MatchingAlgo
      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - an undirected graph
      w - an edge weight function
      Returns:
      the computed matching

    • computeMaximumPerfectMatching

      public <V, E> Matching<V,E> computeMaximumPerfectMatching(Graph<V,E> g, WeightFunction<E> w)
      Description copied from interface: MatchingAlgo
      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.

      Specified by:
      computeMaximumPerfectMatching in interface MatchingAlgo
      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

    • computeMinimumPerfectMatching

      public <V, E> Matching<V,E> computeMinimumPerfectMatching(Graph<V,E> g, WeightFunction<E> w)
      Description copied from interface: MatchingAlgo
      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 MatchingAlgo.computeMaximumPerfectMatching(Graph, WeightFunction).

      If g is IntGraph, the returned object is IMatching.

      Specified by:
      computeMinimumPerfectMatching in interface MatchingAlgo
      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