Package org.jgrapht.alg.matching

Class GreedyMaximumCardinalityMatching<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    MatchingAlgorithm<V,​E>
    public class GreedyMaximumCardinalityMatching<V,​E>
extends Object
implements MatchingAlgorithm<V,​E>
    The greedy algorithm for computing a maximum cardinality matching. The algorithm can run in two modes: sorted or unsorted. When unsorted, the matching is obtained by iterating through the edges and adding an edge if it doesn't conflict with the edges already in the matching. When sorted, the edges are first sorted by the sum of degrees of their endpoints. After that, the algorithm proceeds in the same manner. Running this algorithm in sorted mode can sometimes produce better results, albeit at the cost of some additional computational overhead.

    Independent of the mode, the resulting matching is maximal, and is therefore guaranteed to contain at least half of the edges that a maximum cardinality matching has ($\frac{1}{2}$ approximation). Runtime complexity: $O(m)$ when the edges are not sorted, $O(m + m \log n)$ otherwise, where $n$ is the number of vertices, and $m$ the number of edges.

    Author:
    Joris Kinable

    • Constructor Detail

      • GreedyMaximumCardinalityMatching

        public GreedyMaximumCardinalityMatching​(Graph<V,​E> graph,
                                        boolean sort)
        Creates a new GreedyMaximumCardinalityMatching instance.
        Parameters:
        graph - graph
        sort - sort the edges prior to starting the greedy algorithm