grph.algo.covering_packing

Class LPBasedMaximumMatchingAlgorithm

java.lang.Object

grph.GrphAlgorithm<R>

grph.algo.LPBasedAlgorithm<R>

grph.algo.StructuredLPBasedAlgorithm<it.unimi.dsi.fastutil.ints.IntSet>

grph.algo.covering_packing.LPBasedMaximumMatchingAlgorithm

All Implemented Interfaces:

java.io.Serializable

public class LPBasedMaximumMatchingAlgorithm
extends StructuredLPBasedAlgorithm<it.unimi.dsi.fastutil.ints.IntSet>

An algorithm to solve the maximum bipartite matching problem. It is based on the classical reduction to a network flow problem, described by a linear program and then solved by a solver.

See Also:

Serialized Form

Field Summary

Fields inherited from class grph.algo.LPBasedAlgorithm

SHOW_LP, SHOW_SOL

Constructor Summary

Constructors

Constructor and Description
LPBasedMaximumMatchingAlgorithm()

Method Summary

Modifier and Type	Method and Description
protected jalinopt.LP.OptimizationType	getOptimizationType()
protected jalinopt.Variable.TYPE	getVariableType(jalinopt.Variable v)
protected it.unimi.dsi.fastutil.ints.IntSet	processResult(jalinopt.Result r)
protected void	setConstraints(Grph g, jalinopt.LP p)
protected void	setObjective(jalinopt.LP lp, Grph g)

Methods inherited from class grph.algo.StructuredLPBasedAlgorithm

getLP

Methods inherited from class grph.algo.LPBasedAlgorithm

compute, computeResult, getSolver

Methods inherited from class grph.GrphAlgorithm

cacheResultForGraph, getSourceCode

Methods inherited from class java.lang.Object

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

Constructor Detail

LPBasedMaximumMatchingAlgorithm

public LPBasedMaximumMatchingAlgorithm()

Method Detail

getOptimizationType

protected jalinopt.LP.OptimizationType getOptimizationType()

Specified by:

getOptimizationType in class StructuredLPBasedAlgorithm<it.unimi.dsi.fastutil.ints.IntSet>

getVariableType

protected jalinopt.Variable.TYPE getVariableType(jalinopt.Variable v)

Specified by:

getVariableType in class StructuredLPBasedAlgorithm<it.unimi.dsi.fastutil.ints.IntSet>

setObjective

protected void setObjective(jalinopt.LP lp,
                            Grph g)

Specified by:

setObjective in class StructuredLPBasedAlgorithm<it.unimi.dsi.fastutil.ints.IntSet>

setConstraints

protected void setConstraints(Grph g,
                              jalinopt.LP p)

Specified by:

setConstraints in class StructuredLPBasedAlgorithm<it.unimi.dsi.fastutil.ints.IntSet>

processResult

protected it.unimi.dsi.fastutil.ints.IntSet processResult(jalinopt.Result r)

Specified by:

processResult in class LPBasedAlgorithm<it.unimi.dsi.fastutil.ints.IntSet>