Package com.jgalgo.alg.match

Class MatchingWeightedBipartiteSssp

java.lang.Object

com.jgalgo.alg.match.MatchingAlgoAbstract

com.jgalgo.alg.match.MatchingAlgoAbstractBasedMaximum

com.jgalgo.alg.match.MatchingWeightedBipartiteSssp

All Implemented Interfaces:

MatchingAlgo

public class MatchingWeightedBipartiteSssp
extends MatchingAlgoAbstractBasedMaximum

Maximum weighted matching algorithm using ShortestPathSingleSource for bipartite graphs.

The running time of this algorithm is \(O(m n + n^2 \log n)\) and it uses linear space. If a different ShortestPathSingleSource algorithm is provided using setSsspAlgo(ShortestPathSingleSource) the running time will be \(O(n)\) times the running time of the shortest path algorithm on a graph of size \(O(n)\).

Author:

Barak Ugav

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.match.MatchingAlgo

MatchingAlgo.Builder

Constructor Summary

Constructors

Constructor	Description
MatchingWeightedBipartiteSssp()	Create a new maximum weighted matching object.

Method Summary

Modifier and Type	Method	Description
void	setSsspAlgo(ShortestPathSingleSource algo)	Set the ShortestPathSingleSource algorithm used by this algorithm.

Methods inherited from class com.jgalgo.alg.match.MatchingAlgoAbstract

computeMaximumMatching, computeMaximumPerfectMatching, computeMinimumMatching, computeMinimumPerfectMatching

Methods inherited from class java.lang.Object

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

Constructor Detail

MatchingWeightedBipartiteSssp

public MatchingWeightedBipartiteSssp()

Create a new maximum weighted matching object.

Method Detail

setSsspAlgo

public void setSsspAlgo(ShortestPathSingleSource algo)

Set the ShortestPathSingleSource algorithm used by this algorithm.

The shortest path algorithm should support non negative floating points weights. The default implementation uses Dijkstra's algorithm.

Parameters:

algo - an shortest path algorithm