choco.global.matching
Class AbstractBipartiteGraph

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

All Implemented Interfaces:

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

Direct Known Subclasses:

AbstractBipartiteFlow, AbstractBipartiteMatching

public abstract class AbstractBipartiteGraph
extends AbstractLargeIntConstraint

An abstract class encoding assignment graphs (matching each left vertex with one single right vertex) We consider a flow in the graph by adding a source linked to all right vertices and a sink linked to all left vertices

It is based on computing the strongly connected components of the residual graph, then remove arcs connecting two different strongly connected components

Computing the strongly connected components is done by an algorithm of Aho, Hopcroft, Ullman using depth first search (Cormen, Leiserson, p. 478, p. 489)

Note (EGA) on ice traduction from claire to java : class StrongConnectionDecomposition have been included in this one

Nested Class Summary

protected class

AbstractBipartiteGraph.IntQueue

Field Summary

protected int[]	component
protected boolean[][]	componentOrder
protected int	currentComponent
protected int	currentNode
protected int[]	finishDate
protected int[]	left2rightArc
protected java.util.logging.Logger	logger
protected IStateInt	matchingSize
protected int	maxValue
protected int	minValue
protected int	nbLeftVertices
protected int	nbRightVertices
protected int	nbVertices
protected AbstractBipartiteGraph.IntQueue	queue
protected IStateIntVector	refMatch
protected int[]	right2leftArc
protected boolean[]	seen
protected int	source
protected int	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

AbstractBipartiteGraph(IntDomainVar[] vars, int nbLeft, int nbRight)
Constructor

Method Summary

void	addComponentEdge(int compi, int compj) add an edge in the component graph between compi and compj: componentOrder stores the transitive closure of that graph
void	addComponentVertex() adds a new vertex to the component graph (= a component = a set of s. connected vertices in the original graph)
void	augment(int x) augment the matching along one alternating path note: throughout the following code, we assume (1 <= x <= c.nbLeftVertices), (1 <= y <= c.nbRightVertices)
void	augmentFlow() keeps augmenting the flow until a maximal flow is reached
java.lang.Object	clone() returns a copy of the constraint.
abstract void	decreaseMatchingSize(int j) updates the matching size when one more left vertex is de-matched with j
abstract void	deleteEdgeAndPublish(int i, int j) two methods used for detecting that an edge should be removed from the bipartite assignment graph deleteMatch -> removes it from the graph data strutures deleteEdgeAndPublish -> same + publishes the information outside the constraint
abstract void	deleteMatch(int i, int j) removing the arc i-j from the reference matching & update matchingSize
int	findAlternatingPath() First pass: use Ford & Fulkerson algorithm to compute a reference flow (assignment) finds an augmenting path using a fifo queue
void	firstDFSearch(int i) the first search explores (DFS) the reduced graph
void	firstPassDFS() seen[i] = false <=> color[i] = white (in book) = true % {gray, black}
int	getPriority() Returns the priority.
abstract void	increaseMatchingSize(int j) updates the matching size when one more left vertex is matched with j
protected void	init(int nbLeft, int nbRight)
void	initSCCGraph() initialize the graph data structure storing the SCC decomposition
int	match(int i)
boolean	mayDiminishFlowBetween(int j, int i) whether the flow from j (a right vertex) to i (a left vertex) may be increased
abstract boolean	mayDiminishFlowFromSource(int j) whether the flow from the source to j (a right vertex) may be decreased
boolean	mayGrowFlowBetween(int j, int i) whether the flow from j (a right vertex) to i (a left vertex) may be increased (the additional flow is able to arrive to j, we don't care yet whether it will be able to leave i)
abstract boolean	mayGrowFlowFromSource(int j) whether the flow from the source to j (a right vertex) may be increased
boolean	mayGrowFlowToSink(int i) whether the flow from i (a left vertex) to the sink may be increased
int[]	mayInverseMatch(int j) reverse, access from the right vertex set: iterating over the variables (left vertex set) and reading their domains TODO abstract in claire ice
int[]	mayMatch(int i) Accessing the edges of the bipartite graph access from the left vertex set: reading domains of modeling variables TODO abstract in claire ice
abstract boolean	mustGrowFlowFromSource(int j) 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
void	propagate() Achieves generalized arc consistency in one call
abstract void	putRefMatch(int i, int j) adding the arc i-j in the reference matching without any updates
protected void	removeUselessEdges() remove arcs connecting two different strongly connected components the event generated by the flow algorithm: discovering that an edge is no longer valid, and posting this event to the constraint solver: since we are already achieving GAC consistency in one single loop, there is no need to post a constAwake
void	secondDFSearch(int i) the second search explores (DFS) the inverse of the reduced graph
void	secondPassDFS()
abstract void	setMatch(int i, int j) adding the arc i-j in the reference matching & update matchingSize

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

logger

protected java.util.logging.Logger logger

nbLeftVertices

protected int nbLeftVertices

nbRightVertices

protected int nbRightVertices

nbVertices

protected int nbVertices

minValue

protected int minValue

maxValue

protected int maxValue

source

protected int source

refMatch

protected IStateIntVector refMatch

matchingSize

protected IStateInt matchingSize

left2rightArc

protected int[] left2rightArc

right2leftArc

protected int[] right2leftArc

queue

protected AbstractBipartiteGraph.IntQueue queue

time

protected int time

finishDate

protected int[] finishDate

seen

protected boolean[] seen

currentNode

protected int currentNode

currentComponent

protected int currentComponent

component

protected int[] component

componentOrder

protected boolean[][] componentOrder

Constructor Detail

AbstractBipartiteGraph

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

Constructor

Parameters:

vars - the graph, a left vextex per vars, a right vertex per domain value

nbLeft - number of left nodes, = vars.length

nbRight - number of right nodes, domain values of vars

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 AbstractLargeIntConstraint

Returns:

Throws:

java.lang.CloneNotSupportedException

init

protected void init(int nbLeft,
                    int nbRight)

mayMatch

public int[] mayMatch(int i)

Accessing the edges of the bipartite graph access from the left vertex set: reading domains of modeling variables TODO abstract in claire ice

Parameters:

i -

Returns:

mayInverseMatch

public int[] mayInverseMatch(int j)

reverse, access from the right vertex set: iterating over the variables (left vertex set) and reading their domains TODO abstract in claire ice

Parameters:

j -

Returns:

match

public int match(int i)

Parameters:

i - left vextex index

Returns:

accessing the right vertex matched to i

mayGrowFlowToSink

public boolean mayGrowFlowToSink(int i)

whether the flow from i (a left vertex) to the sink may be increased

Parameters:

i -

Returns:

mayGrowFlowBetween

public boolean mayGrowFlowBetween(int j,
                                  int i)

whether the flow from j (a right vertex) to i (a left vertex) may be increased (the additional flow is able to arrive to j, we don't care yet whether it will be able to leave i)

Parameters:

j -

i -

Returns:

mayDiminishFlowBetween

public boolean mayDiminishFlowBetween(int j,
                                      int i)

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

Parameters:

j -

i -

Returns:

increaseMatchingSize

public abstract void increaseMatchingSize(int j)

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

Parameters:

j -

decreaseMatchingSize

public abstract void decreaseMatchingSize(int j)

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

Parameters:

j -

deleteMatch

public abstract void deleteMatch(int i,
                                 int j)

removing the arc i-j from the reference matching & update matchingSize

Parameters:

i -

j -

putRefMatch

public abstract void putRefMatch(int i,
                                 int j)

adding the arc i-j in the reference matching without any updates

Parameters:

i - left node index

j - right node index

setMatch

public abstract void setMatch(int i,
                              int j)

adding the arc i-j in the reference matching & update matchingSize

Parameters:

i -

j -

mayDiminishFlowFromSource

public abstract boolean mayDiminishFlowFromSource(int j)

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

Parameters:

j -

Returns:

mayGrowFlowFromSource

public abstract boolean mayGrowFlowFromSource(int j)

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

Parameters:

j -

Returns:

mustGrowFlowFromSource

public abstract boolean mustGrowFlowFromSource(int j)

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

Parameters:

j -

Returns:

deleteEdgeAndPublish

public abstract void deleteEdgeAndPublish(int i,
                                          int j)
                                   throws ContradictionException

two methods used for detecting that an edge should be removed from the bipartite assignment graph deleteMatch -> removes it from the graph data strutures deleteEdgeAndPublish -> same + publishes the information outside the constraint

Parameters:

i -

j -

Throws:

ContradictionException

findAlternatingPath

public int findAlternatingPath()

First pass: use Ford & Fulkerson algorithm to compute a reference flow (assignment) finds an augmenting path using a fifo queue

Returns:

0 if none found, otherwise the end of the path

augment

public void augment(int x)

augment the matching along one alternating path note: throughout the following code, we assume (1 <= x <= c.nbLeftVertices), (1 <= y <= c.nbRightVertices)

Parameters:

x -

augmentFlow

public void augmentFlow()
                 throws ContradictionException

keeps augmenting the flow until a maximal flow is reached

Throws:

ContradictionException

initSCCGraph

public void initSCCGraph()

initialize the graph data structure storing the SCC decomposition

addComponentVertex

public void addComponentVertex()

adds a new vertex to the component graph (= a component = a set of s. connected vertices in the original graph)

addComponentEdge

public void addComponentEdge(int compi,
                             int compj)

add an edge in the component graph between compi and compj: componentOrder stores the transitive closure of that graph

Parameters:

compi -

compj -

firstPassDFS

public void firstPassDFS()

seen[i] = false <=> color[i] = white (in book) = true % {gray, black}

firstDFSearch

public void firstDFSearch(int i)

the first search explores (DFS) the reduced graph

Parameters:

i -

secondPassDFS

public void secondPassDFS()

secondDFSearch

public void secondDFSearch(int i)

the second search explores (DFS) the inverse of the reduced graph

Parameters:

i -

removeUselessEdges

protected void removeUselessEdges()
                           throws ContradictionException

remove arcs connecting two different strongly connected components the event generated by the flow algorithm: discovering that an edge is no longer valid, and posting this event to the constraint solver: since we are already achieving GAC consistency in one single loop, there is no need to post a constAwake

Throws:

ContradictionException

propagate

public void propagate()
               throws ContradictionException

Achieves generalized arc consistency in one call

Specified by:

propagate in interface Propagator

Overrides:

propagate in class AbstractLargeIntConstraint

Throws:

ContradictionException

getPriority

public int getPriority()

Description copied from class: AbstractConstraint

Returns the priority.

Specified by:

getPriority in interface Propagator

Overrides:

getPriority in class AbstractConstraint