Package org.graph4j.matching

Class MaximalCardinalityMatching

java.lang.Object
org.graph4j.GraphAlgorithm
org.graph4j.matching.MaximalCardinalityMatching
All Implemented Interfaces:
MatchingAlgorithm
public class MaximalCardinalityMatching extends GraphAlgorithm implements MatchingAlgorithm
Creates a maximal cardinality matching either randomly or using a simple heuristic. A maximal cardinality matching has the property that no other edge can be added to it. A maximum cardinality matching is the largest possible matching. In any graph, any maximal matching has size at least 1/2 of the maximum matching.
Author:
Cristian Frăsinaru

  • Field Summary

    Fields inherited from class org.graph4j.GraphAlgorithm

    directed, graph

  • Constructor Summary

    Constructors
    Constructor
    Description
    MaximalCardinalityMatching(Graph graph)
    Creates a maximal matching algorithm that iterates over the edges of the graph in the order given by the sum of degrees of the edges endpoints.This method has O(m + m log n) time complexity and produces, in general, better results than the random version.
    MaximalCardinalityMatching(Graph graph, boolean random)
    Creates a maximal matching algorithm that iterates over the edges of the graph in a random order (random=true) or in the order in which the edges are internally stored (random=false).This method has O(m) time complexity.
    MaximalCardinalityMatching(Graph graph, Comparator<Edge> comparator)
    Creates a maximal matching algorithm that iterates over the edges of the graph in the order given by a specified comparator.This method has O(m + m log n) time complexity.

  • Method Summary

    Modifier and Type
    Method
    Description
    Matching
    getMatching()
    Returns a maximal matching.

    Methods inherited from class org.graph4j.GraphAlgorithm

    getGraph

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    Methods inherited from interface org.graph4j.matching.MatchingAlgorithm

    getGraph

  • Constructor Details

    • MaximalCardinalityMatching

      public MaximalCardinalityMatching(Graph graph)
      Creates a maximal matching algorithm that iterates over the edges of the graph in the order given by the sum of degrees of the edges endpoints.This method has O(m + m log n) time complexity and produces, in general, better results than the random version.
      Parameters:
      graph - the input graph.

    • MaximalCardinalityMatching

      public MaximalCardinalityMatching(Graph graph, boolean random)
      Creates a maximal matching algorithm that iterates over the edges of the graph in a random order (random=true) or in the order in which the edges are internally stored (random=false).This method has O(m) time complexity.
      Parameters:
      graph - the input graph.
      random - if true creates a random matching.

    • MaximalCardinalityMatching

      public MaximalCardinalityMatching(Graph graph, Comparator<Edge> comparator)
      Creates a maximal matching algorithm that iterates over the edges of the graph in the order given by a specified comparator.This method has O(m + m log n) time complexity.
      Parameters:
      graph - the input graph.
      comparator - a comparator for sorting the edges.

  • Method Details