Class CSTN2CSTN0

java.lang.Object

it.univr.di.cstnu.algorithms.AbstractCSTN<CSTNEdge>

it.univr.di.cstnu.algorithms.CSTN

it.univr.di.cstnu.algorithms.CSTNEpsilon

it.univr.di.cstnu.algorithms.CSTNEpsilonwoNodeLabels

it.univr.di.cstnu.algorithms.CSTN2CSTN0

public class CSTN2CSTN0
extends CSTNEpsilonwoNodeLabels

Simple class to represent and check Conditional Simple Temporal Network, assuming epsilon semantics and reducing an instance to an appropriate CSTN where DC checking is made, assuming instantaneous reaction semantics.

Version:

$Rev: 1154 $

Author:

Roberto Posenato

Nested Class Summary

Nested classes/interfaces inherited from class AbstractCSTN

AbstractCSTN.CheckAlgorithm, AbstractCSTN.CSTNCheckStatus, AbstractCSTN.DCSemantics, AbstractCSTN.EdgesToCheck<E>, AbstractCSTN.NodesToCheck

Modifier and Type	Class	Description
static enum	AbstractCSTN.CheckAlgorithm	Only for stating which kind of DC checking algorithms have been implemented so far.
static class	AbstractCSTN.CSTNCheckStatus	Represents the status of a CSTN-checking algorithm during an execution.
static enum	AbstractCSTN.DCSemantics	Value for dcSemantics
static class	AbstractCSTN.EdgesToCheck<E extends Edge>	A simple class to maintain the set of edges to check in the following phase.
static class	AbstractCSTN.NodesToCheck	Acts as a queue and a set.

Field Summary

Fields

Modifier and Type	Field	Description
static final String	VERSIONandDATE	Version of the class

Fields inherited from class CSTNEpsilon

epsilon

Modifier and Type	Field	Description
(package private) int	epsilon	Reaction time for CSTN

Fields inherited from class AbstractCSTN

checkStatus, cleanCheckedInstance, FILE_NAME_SUFFIX, fInput, fOutput, g, gCheckedCleaned, horizon, maxWeight, propagationOnlyToZ, reactionTime, timeOut, versionReq, withNodeLabels, ZERO_NODE_NAME

Modifier and Type	Field	Description
(package private) AbstractCSTN.CSTNCheckStatus	checkStatus	Check status
(package private) boolean	cleanCheckedInstance	If true, after a check, the resulting graph is cleaned: all empty edges or labeled values containing unknown literals are removed.
(package private) static String	FILE_NAME_SUFFIX	Suffix for file name
(package private) File	fInput	The input file containing the CSTN graph in GraphML format.
(package private) File	fOutput	Output file where to write the XML representing the CSTN graph after a check.
(package private) TemporalConstraintGraph<CSTNEdge>	g	Input graph.
(package private) TemporalConstraintGraph<CSTNEdge>	gCheckedCleaned	The graph obtained by a check and the cleaning action.
(package private) int	horizon	Horizon value.
(package private) int	maxWeight	The absolute value of the max negative weight was determined during the initialization phase.
(package private) boolean	propagationOnlyToZ	Check using the full set of rules R0, qR0, R3, qR3, LP, qLP or the reduced set qR0, qR3, LP.
(package private) int	reactionTime	WD2.2 epsilon value, also called `reaction time` in ICAPS 18.
(package private) int	timeOut	Timeout in seconds for the check.
(package private) boolean	versionReq	Software Version.
(package private) boolean	withNodeLabels	If false, node labels are ignored during the check.
static final String	ZERO_NODE_NAME	The name for the initial node.

Constructor Summary

Constructors

Constructor	Description
CSTN2CSTN0()	Creates a CSTN2CSTN0 with an empty graph using the sparse backend by default.
CSTN2CSTN0(boolean useDenseGraph)	Creates a CSTN2CSTN0 with an empty, newly created graph.
CSTN2CSTN0(int givenReactionTime, TemporalConstraintGraph<CSTNEdge> graph)
CSTN2CSTN0(int givenReactionTime, TemporalConstraintGraph<CSTNEdge> graph, int givenTimeOut)

Method Summary

Modifier and Type	Method	Description
final AbstractCSTN.CSTNCheckStatus	dynamicConsistencyCheck()	Checks the dynamic consistency (DC) of a CSTN instance within timeout seconds.
static void	main(String[] args)
(package private) final TemporalConstraintGraph<CSTNEdge>	transform()	Returns the corresponding CSTN having each observation node 'P?'

Methods inherited from class CSTNEpsilon

getEpsilonReactionTime, lpMustRestricted2ConsistentLabel, mainConditionForSkippingInR0qR0, mainConditionForSkippingInR3qR3, newValueInR3qR3

Modifier and Type	Method	Description
final int	getEpsilonReactionTime()
(package private) boolean	lpMustRestricted2ConsistentLabel(int u, int v)	Returns true if label propagation rule (for example, CSTN.labelPropagation(LabeledNode, LabeledNode, LabeledNode, CSTNEdge, CSTNEdge, CSTNEdge) method) has to apply only for consistent labels.
(package private) final boolean	mainConditionForSkippingInR0qR0(int w)	Returns true if AbstractCSTN.labelModificationR0qR0(LabeledNode, LabeledNode, E) method has to not apply.
(package private) final boolean	mainConditionForSkippingInR3qR3(int w, LabeledNode nD)	Returns true if CSTN.labelModificationR3qR3(LabeledNode, LabeledNode, CSTNEdge) method has to not apply.
(package private) final int	newValueInR3qR3(int edgeValue, int obsEdgeValue)	According to Table 2 paper ICAPS16, it returns max(edgeValue, obsEdgeValue-ɛ).

Methods inherited from class CSTN

defaultMain, dynamicConsistencyCheckWOInit, labelModificationR3qR3, labelPropagation, oneStepDynamicConsistencyByEdges, oneStepDynamicConsistencyByEdgesLimitedToZ, oneStepDynamicConsistencyByNode

Modifier and Type	Method	Description
(package private) static void	defaultMain(String[] args, CSTN cstn, String kindOfChecking)
(package private) AbstractCSTN.CSTNCheckStatus	dynamicConsistencyCheckWOInit()	Checks the dynamic consistency of a CSTN instance without initializing the network.
(package private) boolean	labelModificationR3qR3(LabeledNode nS, LabeledNode nD, CSTNEdge eSD)	Rule R3*
(package private) boolean	labelPropagation(LabeledNode nA, LabeledNode nB, LabeledNode nC, CSTNEdge eAB, CSTNEdge eBC, CSTNEdge eAC)	Applies the labeled propagation rule:
(package private) AbstractCSTN.CSTNCheckStatus	oneStepDynamicConsistencyByEdges(AbstractCSTN.EdgesToCheck<CSTNEdge> edgesToCheck, Instant timeoutInstant)	Executes one step of the dynamic consistency check.
(package private) AbstractCSTN.CSTNCheckStatus	oneStepDynamicConsistencyByEdgesLimitedToZ(AbstractCSTN.EdgesToCheck<CSTNEdge> edgesToCheck, Instant timeoutInstant)	Executes one step of the dynamic consistency check.
AbstractCSTN.CSTNCheckStatus	oneStepDynamicConsistencyByNode()	Executes one step of the dynamic consistency check.

Methods inherited from class AbstractCSTN

addUpperBounds, checkWellDefinitionProperties, checkWellDefinitionProperty1and3, coreCSTNInitAndCheck, getCheckedGraph, getCheckStatus, getEdgeFromObserversToNode, getfOutput, getG, getGChecked, getGCheckedAsGraphML, getGraph, getMaxWeight, getReactionTime, getVersionAndCopyright, initAndCheck, isOutputCleaned, isWithNodeLabels, labelModificationR0qR0, labelModificationR0qR0Core, makeAlphaBetaGammaPrime4R3, makeAlphaPrime, makeBetaGammaDagger4qR3, makeNewEdge, manageParameters, pairAsString, recordCheckOutcome, removeChildrenOfUnknown, reset, saveGraphToFile, setfOutput, setG, setOutputCleaned, setPropagationOnlyToZ, setWithNodeLabels

Modifier and Type	Method	Description
(package private) final void	addUpperBounds()	The upper bounds from Z to each node have to be set after the horizon is determined.
(package private) final boolean	checkWellDefinitionProperties()	checkWellDefinitionProperties.
(package private) boolean	checkWellDefinitionProperty1and3(LabeledNode nS, LabeledNode nD, CSTNEdge eSN, boolean hasToBeFixed)	Checks whether the constraint represented by an edge 'e' satisfies the well-defined first property (WD1): any labeled value of the edge has a label that subsumes both labels of the two endpoints. In case a label is not WD1 and hasToBeFixed, then it is fixed.
(package private) final void	coreCSTNInitAndCheck()	Makes the CSTN well-definedness check and initialization.
final TemporalConstraintGraph<CSTNEdge>	getCheckedGraph()	Getter for the resulting checked graph, without copying or converting it.
AbstractCSTN.CSTNCheckStatus	getCheckStatus()	Getter for the field checkStatus, the status of a checking algorithm.
(package private) final it.unimi.dsi.fastutil.objects.ObjectList<CSTNEdge>	getEdgeFromObserversToNode(LabeledNode nX)	Determines the set of edges P?
File	getfOutput()	Getter for the field fOutput.
DenseTCGraph<CSTNEdge>	getG()	Deprecated. use AbstractCSTN.getGraph() in algorithms; this adapter is only for JUNG/GraphML boundaries.
DenseTCGraph<CSTNEdge>	getGChecked()	Deprecated. use AbstractCSTN.getCheckedGraph() in algorithms; this adapter is only for JUNG/GraphML boundaries.
String	getGCheckedAsGraphML()	Helper method for having the graph obtained by AbstractCSTN.getCheckedGraph() in GraphML format.
final TemporalConstraintGraph<CSTNEdge>	getGraph()	Getter for the field g, the input graph, without copying or converting it.
final int	getMaxWeight()	Getter for the field maxWeight.
final int	getReactionTime()	Getter for the field reactionTime.
final String	getVersionAndCopyright()
void	initAndCheck()	Checks and initializes the CSTN instance represented by graph g.
boolean	isOutputCleaned()
boolean	isWithNodeLabels()
(package private) final boolean	labelModificationR0qR0(LabeledNode nObs, LabeledNode nX, CSTNEdge eObsX)	Applies rule R0/qR0: label containing a proposition that can be decided only in the future is simplified by removing such a proposition.
(package private) final Label	labelModificationR0qR0Core(LabeledNode nP, LabeledNode nX, Label alpha, int w)	Execute the core of AbstractCSTN.labelModificationR0qR0(LabeledNode, LabeledNode, CSTNEdge).
(package private) final Label	makeAlphaBetaGammaPrime4R3(LabeledNode nS, LabeledNode nD, LabeledNode nObs, char observed, Label labelFromObs, Label labelToClean)	A simple method to determine the label "αβγ" for the rule CSTN.labelModificationR3qR3(LabeledNode, LabeledNode, CSTNEdge).
(package private) final Label	makeAlphaPrime(LabeledNode nX, LabeledNode nObs, char observed, Label labelFromObs)	Simple method to determine the α' to use in rules R0 and in rule qR0.
(package private) final Label	makeBetaGammaDagger4qR3(LabeledNode nS, LabeledNode nObs, char observed, Label labelFromObs, Label labelToClean)	Simple method to determine the label (β*γ)† to use in rules qR3* CSTN.labelModificationR3qR3(LabeledNode, LabeledNode, CSTNEdge).
(package private) final CSTNEdge	makeNewEdge(String name, Edge.ConstraintType type)	Create an edge, ensuring that its name is unique in the graph 'g'.
(package private) final boolean	manageParameters(String[] args)	Simple method to manage command line parameters using the "args4j" library.
(package private) static String	pairAsString(Label label, int value)
protected final void	recordCheckOutcome(CheckOutcome.Kind kind, boolean successful)	Records the verdict of a completed check on both AbstractCSTN.g and, when it exists and is not g itself, on AbstractCSTN.gCheckedCleaned.
(package private) final Label	removeChildrenOfUnknown(Label l)	Returns a new label removing all children of possibly present unknown literals in l.
void	reset()	Resets all internal structures but not g.
final void	saveGraphToFile()	Helper method to make it easier to store the resulting graph during a check.
final void	setfOutput(File fileOutput)
final void	setG(TemporalConstraintGraph<CSTNEdge> graph)	Considers the given graph as the graph to check, without copying or converting it (the graph will be modified).
final void	setOutputCleaned(boolean clean)	Set to true for having the result graph cleaned of empty edges and labeled values having unknown literals.
final void	setPropagationOnlyToZ(boolean propagationOnlyToZ1)	Setter for the field propagationOnlyToZ.
final void	setWithNodeLabels(boolean withNodeLabels1)

Methods inherited from class Object

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

Field Details

VERSIONandDATE

public static final String VERSIONandDATE

Version of the class

See Also:

• Constant Field Values

Constructor Details

CSTN2CSTN0

public CSTN2CSTN0(int givenReactionTime,
 TemporalConstraintGraph<CSTNEdge> graph)

Parameters:

givenReactionTime - the reaction time of the network

graph - graph to check, without copying or converting it

CSTN2CSTN0

public CSTN2CSTN0(int givenReactionTime,
 TemporalConstraintGraph<CSTNEdge> graph,
 int givenTimeOut)

Parameters:

givenReactionTime - the reaction time of the network.

graph - graph to check, without copying or converting it

givenTimeOut - the timeout for the check in seconds.

CSTN2CSTN0

public CSTN2CSTN0()

Creates a CSTN2CSTN0 with an empty graph using the sparse backend by default.

CSTN2CSTN0

public CSTN2CSTN0(boolean useDenseGraph)

Creates a CSTN2CSTN0 with an empty, newly created graph.

Parameters:

useDenseGraph - true to use the dense backend (DenseTCGraph); false to use the sparse backend (SparseTCGraph).

Method Details

main

public static void main(String[] args)
                 throws IOException,
ParserConfigurationException,
SAXException

Parameters:

args - an array of String objects.

Throws:

IOException - if any.

ParserConfigurationException - if any.

SAXException - if any.

dynamicConsistencyCheck

public final AbstractCSTN.CSTNCheckStatus dynamicConsistencyCheck()
                                                           throws WellDefinitionException

Checks the dynamic consistency (DC) of a CSTN instance within timeout seconds. During the execution of this method, the given network is modified.

If the check is successful, all constraints to node Z in the network are minimized; otherwise, the network contains at least one negative loop.

After a check, AbstractCSTN.getGChecked() returns the network determined by the check and AbstractCSTN.getCheckStatus() the result of the checking action with some statistics, and the node having a negative loop if the network is NOT DC.

In any case, before returning, this method call AbstractCSTN.saveGraphToFile() for saving the computed graph.

Checks the controllability of a CSTNU instance. This method transforms the given CSTNU instance into a corresponding CSTN instance such that the original instance is dynamic controllable iff the corresponding CSTN is dynamic consistent.

Overrides:

dynamicConsistencyCheck in class CSTN

Returns:

the final status of the checking with some statistics.

Throws:

WellDefinitionException - if any.

transform

final TemporalConstraintGraph<CSTNEdge> transform()

Returns the corresponding CSTN having each observation node 'P?' replaced with a pair of nodes 'P?' and 'P?0'. 'P?' is the standard node, while 'P?0' is a new observation node that observes 'p'.

'P?0' is set to be at distance epsilon after 'P?', exactly.

Returns:

g represented as a CSTN0. To minimize name conflicts, the new name associated with 'P?' is 'P?^0'.