Package org.graph4j.matching

Class GreedyWeightedMatching

java.lang.Object

org.graph4j.GraphAlgorithm

org.graph4j.matching.GreedyWeightedMatching

All Implemented Interfaces:

MatchingAlgorithm

public class GreedyWeightedMatching
extends GraphAlgorithm
implements MatchingAlgorithm

Greedy algorithm to create a weighted matching. The algorithm sorts descending the edges of the graph either by their weight or by their normalized weight (weigth / sum of endpoints degree) and then adds them to the matching as long as it is possible. Non-positive weighted edges are ignored so the matching is maximal with respect to the subgraph formed only by positive weighted edges. If the edges are sorted by their weight, the matching is guaranteed to be a 1/2-approximation of the meximum weighted matching.

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from class org.graph4j.GraphAlgorithm

directed, graph

Constructor Summary

Constructors

Constructor	Description
GreedyWeightedMatching(Graph graph)	Creates a maximal weighted matching algorithm that iterates over the edges of the graph in the descending order given by their normalized weight.
GreedyWeightedMatching(Graph graph, boolean normalized)	Creates a maximal weighted matching algorithm that iterates over the edges of the graph in the descending order given by theier wight or normalized weight.
GreedyWeightedMatching(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.

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

GreedyWeightedMatching

public GreedyWeightedMatching(Graph graph)

Creates a maximal weighted matching algorithm that iterates over the edges of the graph in the descending order given by their normalized weight. This method has O(m + m log n) time complexity.

Parameters:

graph - the input graph.

GreedyWeightedMatching

public GreedyWeightedMatching(Graph graph,
 boolean normalized)

Creates a maximal weighted matching algorithm that iterates over the edges of the graph in the descending order given by theier wight or normalized weight. This method has O(m + m log n) time complexity.

Parameters:

graph - the input graph.

normalized - if true, the edges are sorted by their normalized weight, otherwise they are sorted by their weight.

GreedyWeightedMatching

public GreedyWeightedMatching(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

getMatching

public Matching getMatching()

Returns a maximal matching.

Specified by:

getMatching in interface MatchingAlgorithm

Returns:

a maximal matching.