choco.global.matching
Class AbstractBipartiteMatching

java.lang.Object
  choco.AbstractEntity
      choco.AbstractConstraint
          choco.integer.constraints.AbstractIntConstraint
              choco.integer.constraints.AbstractLargeIntConstraint
                  choco.global.matching.AbstractBipartiteGraph
                      choco.global.matching.AbstractBipartiteMatching

All Implemented Interfaces:

Constraint, Entity, IntConstraint, IntVarEventListener, VarEventListener, Propagator, java.lang.Cloneable, java.util.EventListener

Direct Known Subclasses:

AllDifferent

public abstract class AbstractBipartiteMatching
extends AbstractBipartiteGraph

A subclass of AbtractBipartiteGraph restricted only to matchings (and not flows).

Nested Class Summary

Nested classes/interfaces inherited from class choco.global.matching.AbstractBipartiteGraph

AbstractBipartiteGraph.IntQueue

Field Summary

protected IStateIntVector

refInverseMatch Vector with the reverse matching.

Fields inherited from class choco.global.matching.AbstractBipartiteGraph

component, componentOrder, currentComponent, currentNode, finishDate, left2rightArc, logger, matchingSize, maxValue, minValue, nbLeftVertices, nbRightVertices, nbVertices, queue, refMatch, right2leftArc, seen, source, time

Fields inherited from class choco.integer.constraints.AbstractLargeIntConstraint

cIndices, cste, vars

Fields inherited from class choco.AbstractConstraint

active, constAwakeEvent, hook, priority

Fields inherited from class choco.AbstractEntity

problem

Constructor Summary

AbstractBipartiteMatching(IntDomainVar[] vars, int nbLeft, int nbRight)
Builds a new instance for the specified vars.

Method Summary

java.lang.Object	clone() Builds a copy of this contraint.
void	decreaseMatchingSize(int j) Matching size has been decrease by 1.
void	deleteMatch(int i, int j) Removing the arc i-j from the reference matching.
void	increaseMatchingSize(int j) Matching size has been increase by 1.
void	initAbstractBipartiteMatching() Initializes the matching by building the backtrackable vector for the right vertices values.
int	inverseMatch(int j) Accessing the left vertex matched to j.
boolean	mayDiminishFlowFromSource(int j) Checks if the flow can be decreased between source and a vertex.
boolean	mayGrowFlowFromSource(int j) Checks if the flow can be increased between source and a vertex.
boolean	mustGrowFlowFromSource(int j) Checks if the flow must be increased between the source and a vertex.
void	putRefMatch(int i, int j) Adding the arc i-j in the reference matching without any updates.
void	setMatch(int i, int j) Adding the arc i-j in the reference matching.

Methods inherited from class choco.global.matching.AbstractBipartiteGraph

addComponentEdge, addComponentVertex, augment, augmentFlow, deleteEdgeAndPublish, findAlternatingPath, firstDFSearch, firstPassDFS, getPriority, init, initSCCGraph, match, mayDiminishFlowBetween, mayGrowFlowBetween, mayGrowFlowToSink, mayInverseMatch, mayMatch, propagate, removeUselessEdges, secondDFSearch, secondPassDFS

Methods inherited from class choco.integer.constraints.AbstractLargeIntConstraint

assignIndices, getConstraintIdx, getIntVar, getNbVars, getVar, isCompletelyInstantiated, setConstraintIndex, setVar

Methods inherited from class choco.integer.constraints.AbstractIntConstraint

awakeOnBounds, awakeOnInf, awakeOnInst, awakeOnRem, awakeOnRemovals, awakeOnSup, getSelfIndex, isConsistent

Methods inherited from class choco.AbstractConstraint

addListener, awake, awakeOnVar, connectVar, constAwake, delete, fail, getEvent, getPlugIn, getProblem, getVarIdxInOpposite, isActive, isEntailed, isEquivalentTo, opposite, setActive, setEntailed, setPassive, setPlugIn, substituteVar

Methods inherited from class choco.AbstractEntity

pretty

Methods inherited from class java.lang.Object

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

Methods inherited from interface choco.Propagator

awake, awakeOnVar, constAwake, delete, getEvent, getPlugIn, isEntailed

Methods inherited from interface choco.prop.VarEventListener

addListener, isActive, setActive, setPassive

Methods inherited from interface choco.prop.VarEventListener

addListener, isActive, setActive, setPassive

Field Detail

refInverseMatch

protected IStateIntVector refInverseMatch

Vector with the reverse matching.

Constructor Detail

AbstractBipartiteMatching

public AbstractBipartiteMatching(IntDomainVar[] vars,
                                 int nbLeft,
                                 int nbRight)

Builds a new instance for the specified vars.

Parameters:

vars - the variables

nbLeft - number of nodes in the first part of the bipartite matching

nbRight - number of nodes in the second part

Method Detail

clone

public java.lang.Object clone()
                       throws java.lang.CloneNotSupportedException

Builds a copy of this contraint.

Specified by:

clone in interface Constraint

Overrides:

clone in class AbstractBipartiteGraph

Returns:

a clone of this constraint

Throws:

java.lang.CloneNotSupportedException - if an error occurs during cloning

initAbstractBipartiteMatching

public void initAbstractBipartiteMatching()

Initializes the matching by building the backtrackable vector for the right vertices values.

inverseMatch

public int inverseMatch(int j)

Accessing the left vertex matched to j.

Parameters:

j - the vertex

Returns:

the left vertex matched to j

increaseMatchingSize

public void increaseMatchingSize(int j)

Matching size has been increase by 1.

Specified by:

increaseMatchingSize in class AbstractBipartiteGraph

Parameters:

j - useless here

decreaseMatchingSize

public void decreaseMatchingSize(int j)

Matching size has been decrease by 1.

Specified by:

decreaseMatchingSize in class AbstractBipartiteGraph

Parameters:

j - useless here

deleteMatch

public void deleteMatch(int i,
                        int j)

Removing the arc i-j from the reference matching.

Specified by:

deleteMatch in class AbstractBipartiteGraph

Parameters:

i - the left vertex

j - the right vertex

putRefMatch

public void putRefMatch(int i,
                        int j)

Adding the arc i-j in the reference matching without any updates.

Specified by:

putRefMatch in class AbstractBipartiteGraph

Parameters:

i - the left vertex

j - the right vertex

setMatch

public void setMatch(int i,
                     int j)

Adding the arc i-j in the reference matching.

Specified by:

setMatch in class AbstractBipartiteGraph

Parameters:

i - the left vertex

j - the right vertex

mayDiminishFlowFromSource

public boolean mayDiminishFlowFromSource(int j)

Checks if the flow can be decreased between source and a vertex.

Specified by:

mayDiminishFlowFromSource in class AbstractBipartiteGraph

Parameters:

j - the vertex

Returns:

whether the flow from the source to j (a right vertex) may be decreased

mayGrowFlowFromSource

public boolean mayGrowFlowFromSource(int j)

Checks if the flow can be increased between source and a vertex.

Specified by:

mayGrowFlowFromSource in class AbstractBipartiteGraph

Parameters:

j - the vertex

Returns:

whether the flow from the source to j (a right vertex) may be increased

mustGrowFlowFromSource

public boolean mustGrowFlowFromSource(int j)

Checks if the flow must be increased between the source and a vertex.

Specified by:

mustGrowFlowFromSource in class AbstractBipartiteGraph

Parameters:

j - the vertex

Returns:

whether the flow from the source to j (a right vertex) must be increased in order to get a maximal (sink/left vertex set saturating) flow