org.metacsp.time

Class APSPSolver

java.lang.Object

org.metacsp.framework.ConstraintSolver

org.metacsp.time.APSPSolver

All Implemented Interfaces:

java.io.Serializable

public class APSPSolver
extends ConstraintSolver

Simple Temporal Problem solver which uses the Floyd-Warshall all-pairs shortest-path algorithm for constraint propagation. Derived from original implementation by the Planning and Scheduling Team (ISTC-CNR) under project APSI.

Author:

Federico Pecora and Planning and Scheduling Team

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class org.metacsp.framework.ConstraintSolver

ConstraintSolver.OPTIONS

Field Summary

Fields

Modifier and Type	Field and Description
static int	DEFAULT_MAX_TPS
static long	INF Public access class variable denoting the value infinity.

Fields inherited from class org.metacsp.framework.ConstraintSolver

autoprop, components, constraintTypes, IDs, logger, name, nesting, noPropOnVarCreation, numcalls, skipPropagation, spacing, theNetwork, variableType

Constructor Summary

Constructors

Constructor and Description
APSPSolver(long origin, long horizon) Create a new APSPSolver with given temporal horizon.
APSPSolver(long origin, long horizon, int maxTPs) Create a new APSPSolver with given temporal horizon and given maximum number of timepoints.

Method Summary

Modifier and Type	Method and Description
protected boolean	addConstraintsSub(Constraint[] con) This method must be implemented by the developer of the specific ConstraintSolver class.
int	bookmark()
boolean	changeHorizon(long val) Set a new horizon for this network.
protected Variable[]	createVariablesSub(int num) This method must be implemented by the developer of the specific ConstraintSolver class.
void	draw() Draw a graph representing this APSPSolver's ConstraintNetwork.
SimpleDistanceConstraint	getConstraint(TimePoint tpFrom, TimePoint tpTo) Get active constraint between two TimePoints.
Bounds	getDistanceBounds(TimePoint tpFrom, TimePoint tpTo) Gets the effective bounds between a pair of TimePoints.
TimePoint	getEqualTimePoint(TimePoint queryTp)
long	getH() Get the horizon of this APSPSolver.
int	getMaxTps()
long	getO() Get the time origin of this APSPSolver.
double	getRMSRigidity() This method computes the root mean square rigidity of a consistent STN (the inverse concept of flexibility of a STN).
TimePoint	getSink() Get the sink timepoint of the Simple Temporal Network (anchored to horizon).
TimePoint	getSource() Get the source timepoint of the Simple Temporal Network (anchored to origin of time).
TimePoint	getTimePoint(int Id) Get a timepoint given its ID.
int	numBookmarks()
java.lang.String	printDist()
java.lang.String	printDistHist()
static java.lang.String	printLong(long l) Class method for pretty-printing longs (substitutes +/-INF appropriately).
boolean	propagate() Perform complete propagation.
void	registerValueChoiceFunctions()
void	removeBookmark(int i)
protected void	removeConstraintsSub(Constraint[] con) This method must be implemented by the developer of the specific ConstraintSolver class.
protected void	removeVariablesSub(Variable[] ti) This method must be implemented by the developer of the specific ConstraintSolver class.
void	revert(int i)
void	setAddingIndependentConstraints()
java.lang.String	toString() Generates a String representation of the Simple Temporal Network (STN).

Methods inherited from class org.metacsp.framework.ConstraintSolver

addConstraint, addConstraintNoPropagation, addConstraints, addConstraintsDebug, addConstraintsNoPropagation, containsVariable, createVariable, createVariable, createVariables, createVariables, createVariablesSub, deplenish, getComponent, getComponents, getConstraintNetwork, getConstraints, getConstraints, getDescription, getID, getOption, getVariable, getVariables, getVariables, getVariables, isCompatible, maskConstraints, removeConstraint, removeConstraints, removeVariable, removeVariables, setComponent, setComponents, setConstraintNetwork, setName, setOptions, unmaskConstraints

Methods inherited from class java.lang.Object

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

Field Detail

INF

public static final long INF

Public access class variable denoting the value infinity.

See Also:

Constant Field Values

DEFAULT_MAX_TPS

public static final int DEFAULT_MAX_TPS

See Also:

Constant Field Values

Constructor Detail

APSPSolver

public APSPSolver(long origin,
                  long horizon)

Create a new APSPSolver with given temporal horizon.

Parameters:

origin - The start time of the horizon.

horizon - The end time of the horizon.

APSPSolver

public APSPSolver(long origin,
                  long horizon,
                  int maxTPs)

Create a new APSPSolver with given temporal horizon and given maximum number of timepoints.

Parameters:

origin - The start time of the horizon.

horizon - The end time of the horizon.

maxTPs - maximum number of timepoints in the network (excluding the Origin (O) and Horizon (H) timepoint) (propagation is O((maxTPs+2)^3)).

Method Detail

getTimePoint

public TimePoint getTimePoint(int Id)

Get a timepoint given its ID.

Parameters:

Id - The ID of the timepoint.

Returns:

The timepoint referenced by passed ID.

toString

public java.lang.String toString()

Generates a String representation of the Simple Temporal Network (STN).

Overrides:

toString in class ConstraintSolver

Returns:

A String describing the STN.

createVariablesSub

protected Variable[] createVariablesSub(int num)

Description copied from class: ConstraintSolver

This method must be implemented by the developer of the specific ConstraintSolver class. It should implement all operations necessary to create a batch of variable for the specific type of ConstraintSolver.

Specified by:

createVariablesSub in class ConstraintSolver

Parameters:

num - The number of variables to create.

Returns:

A batch of new Variable for this ConstraintSolver.

removeVariablesSub

protected void removeVariablesSub(Variable[] ti)

Description copied from class: ConstraintSolver

This method must be implemented by the developer of the specific ConstraintSolver class. It should implement all operations necessary to remove a batch of variables for the specific type of ConstraintSolver.

Specified by:

removeVariablesSub in class ConstraintSolver

Parameters:

ti - The Variables to remove.

setAddingIndependentConstraints

public void setAddingIndependentConstraints()

addConstraintsSub

protected boolean addConstraintsSub(Constraint[] con)

Description copied from class: ConstraintSolver

This method must be implemented by the developer of the specific ConstraintSolver class. It should implement all operations necessary to add multiple constraints, and should return true upon success, false otherwise.

Specified by:

addConstraintsSub in class ConstraintSolver

Parameters:

con - The constraints to add.

Returns:

true iff the constraints were added to the ConstraintNetwork.

removeConstraintsSub

protected void removeConstraintsSub(Constraint[] con)

Description copied from class: ConstraintSolver

This method must be implemented by the developer of the specific ConstraintSolver class. Should implement all operations necessary to remove a batch of constraints.

Specified by:

removeConstraintsSub in class ConstraintSolver

Parameters:

con - The constraints to remove.

propagate

public boolean propagate()

Perform complete propagation. Computational cost is O(n^3) where n is the number of timepoints in the Simple Temporal Network.

Specified by:

propagate in class ConstraintSolver

Returns:

True if propagation was successful, False otherwise.

getO

public long getO()

Get the time origin of this APSPSolver.

Returns:

The time origin of this APSPSolver.

getH

public long getH()

Get the horizon of this APSPSolver.

Returns:

The horizon of this APSPSolver.

changeHorizon

public boolean changeHorizon(long val)

Set a new horizon for this network.

Parameters:

val - The new horizon.

Returns:

True If the operation succeeded, False otherwise.

getSource

public TimePoint getSource()

Get the source timepoint of the Simple Temporal Network (anchored to origin of time).

Returns:

the source timepoint of the Simple Temporal Network.

getSink

public TimePoint getSink()

Get the sink timepoint of the Simple Temporal Network (anchored to horizon).

Returns:

the sink timepoint of the Simple Temporal Network.

printLong

public static java.lang.String printLong(long l)

Class method for pretty-printing longs (substitutes +/-INF appropriately).

Parameters:

l - The long value to pretty-print.

Returns:

a String representation of the given long value.

getConstraint

public SimpleDistanceConstraint getConstraint(TimePoint tpFrom,
                                              TimePoint tpTo)

Get active constraint between two TimePoints.

Parameters:

tpFrom - The source TimePoint.

tpTo - The destination TimePoint.

Returns:

The active SimpleDistanceConstraint between the two TimePoints (null if none exists).

getDistanceBounds

public Bounds getDistanceBounds(TimePoint tpFrom,
                                TimePoint tpTo)

Gets the effective bounds between a pair of TimePoints. (After propagation, considering all constraints in the network)

getMaxTps

public int getMaxTps()

Returns:

The maximum number of timepoints that can be added to this STP network (excluding the Origin (O) and Horizon (H) timepoint).

See Also:

APSPSolver(long, long, int)

draw

public void draw()

Draw a graph representing this APSPSolver's ConstraintNetwork. This method depends on the Prefuse library.

getRMSRigidity

public double getRMSRigidity()

This method computes the root mean square rigidity of a consistent STN (the inverse concept of flexibility of a STN). If the STN is completely rigid, then its rigidity is 1. If the STN has no constraints, its rigidity is 0. This measure in proposed in [Luke Hunsberger, 2002].

Returns:

Root mean square rigidity of a consistent STN.

bookmark

public int bookmark()

removeBookmark

public void removeBookmark(int i)

revert

public void revert(int i)

numBookmarks

public int numBookmarks()

getEqualTimePoint

public TimePoint getEqualTimePoint(TimePoint queryTp)

printDist

public java.lang.String printDist()

printDistHist

public java.lang.String printDistHist()

registerValueChoiceFunctions

public void registerValueChoiceFunctions()

Specified by:

registerValueChoiceFunctions in class ConstraintSolver