choco.global.matching
Class AbstractBipartiteFlow

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

All Implemented Interfaces:

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

Direct Known Subclasses:

GlobalCardinality

public abstract class AbstractBipartiteFlow
extends AbstractBipartiteGraph

A general assignment constraint with constraints on the flow bounds

Nested Class Summary

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

AbstractBipartiteGraph.IntQueue

Field Summary

protected boolean	compatibleFlow
protected IStateIntVector	flow
protected int[]	maxFlow
protected int[]	minFlow

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

AbstractBipartiteFlow(IntDomainVar[] vars, int nbLeft, int nbRight)
Constructor for AbstractBipartiteFlow

Method Summary

void	augment(int x) Augment flow on the current matching
java.lang.Object	clone() returns a copy of the constraint.
void	decreaseMatchingSize(int j) updates the matching size when the matching is rebuilt
void	deleteMatch(int i, int j) remove the assignment of j to the ith variable
int	findAlternatingPath() Search for an augmenting path
void	increaseMatchingSize(int j) updates the matching size when one more left vertex is matched with j
protected void	initAbstractBipartiteFlow()
boolean	mayDiminishFlowFromSource(int j) check unassignement
boolean	mayGrowFlowFromSource(int j) check assignement
boolean	mustGrowFlowFromSource(int j) check if j should be assigned to other variables
void	putRefMatch(int i, int j) Assignment of j to the ith variable
void	setMatch(int i, int j) match the ith variable to value j

Methods inherited from class choco.global.matching.AbstractBipartiteGraph

addComponentEdge, addComponentVertex, augmentFlow, deleteEdgeAndPublish, 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

minFlow

protected int[] minFlow

maxFlow

protected int[] maxFlow

flow

protected IStateIntVector flow

compatibleFlow

protected boolean compatibleFlow

Constructor Detail

AbstractBipartiteFlow

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

Constructor for AbstractBipartiteFlow

Parameters:

vars - nbLeft domain variables

nbLeft - number of domain variables to assign

nbRight - number of values for assignment

Method Detail

clone

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

Description copied from interface: Constraint

returns a copy of the constraint. This copy is a new object, may be a recursive copy in case of composite constraints. The original and the copy share the same variables & plugins

Specified by:

clone in interface Constraint

Overrides:

clone in class AbstractBipartiteGraph

Returns:

Throws:

java.lang.CloneNotSupportedException

initAbstractBipartiteFlow

protected void initAbstractBipartiteFlow()

setMatch

public void setMatch(int i,
                     int j)

match the ith variable to value j

Specified by:

setMatch in class AbstractBipartiteGraph

Parameters:

i - the variable to match

j - the value to assign

deleteMatch

public void deleteMatch(int i,
                        int j)

remove the assignment of j to the ith variable

Specified by:

deleteMatch in class AbstractBipartiteGraph

Parameters:

i - the variable to unmatch

j - the value to remove

putRefMatch

public void putRefMatch(int i,
                        int j)

Assignment of j to the ith variable

Specified by:

putRefMatch in class AbstractBipartiteGraph

Parameters:

i - the variable to assign

j - the value

mayDiminishFlowFromSource

public boolean mayDiminishFlowFromSource(int j)

check unassignement

Specified by:

mayDiminishFlowFromSource in class AbstractBipartiteGraph

Parameters:

j - the jth value

Returns:

true if a variable assigned to j could be unassigned

mayGrowFlowFromSource

public boolean mayGrowFlowFromSource(int j)

check assignement

Specified by:

mayGrowFlowFromSource in class AbstractBipartiteGraph

Parameters:

j - the jth value

Returns:

true if a variable could be assigned to j

mustGrowFlowFromSource

public boolean mustGrowFlowFromSource(int j)

check if j should be assigned to other variables

Specified by:

mustGrowFlowFromSource in class AbstractBipartiteGraph

Parameters:

j - the jth value

Returns:

true if j has not been assigned to enough variables

increaseMatchingSize

public void increaseMatchingSize(int j)

updates the matching size when one more left vertex is matched with j

Specified by:

increaseMatchingSize in class AbstractBipartiteGraph

Parameters:

j - indice of the assigned value

decreaseMatchingSize

public void decreaseMatchingSize(int j)

updates the matching size when the matching is rebuilt

Specified by:

decreaseMatchingSize in class AbstractBipartiteGraph

Parameters:

j - indice of the removed assignement

findAlternatingPath

public int findAlternatingPath()

Search for an augmenting path

Overrides:

findAlternatingPath in class AbstractBipartiteGraph

Returns:

augment

public void augment(int x)

Augment flow on the current matching

Overrides:

augment in class AbstractBipartiteGraph

Parameters:

x - left extremity of one of the matching arc