Class PCSTNU

java.lang.Object
it.univr.di.cstnu.algorithms.AbstractCSTN<CSTNUEdge>
it.univr.di.cstnu.algorithms.CSTNU
it.univr.di.cstnu.algorithms.PCSTNU
public class PCSTNU extends CSTNU
Simple class that extends CSTNU for representing and managing 'parameter nodes'. Parameter nodes have been introduced in the paper "Dynamic Controllability of Parameterized CSTNUs".
Author:
posenato

  • Field Details

    • VERSIONandDATE

      public static final String VERSIONandDATE
      Version of the class
      See Also:

    • LOG

      static final Logger LOG
      logger

    • parameterNodes

      it.unimi.dsi.fastutil.objects.ObjectArrayList<LabeledNode> parameterNodes
      The set of parameter nodes

  • Constructor Details

    • PCSTNU

      public PCSTNU(String graphXML) throws IOException, ParserConfigurationException, SAXException
      Parameters:
      graphXML - an XML description of a parameterized PCSTNU instance
      Throws:
      IOException - any problem in reading the XML
      ParserConfigurationException - any problem in the XML format
      SAXException - any problem in the XML format

    • PCSTNU

      public PCSTNU(TemporalConstraintGraph<CSTNUEdge> graph)
      Parameters:
      graph - a parameterized CSTNU, without copying or converting it

    • PCSTNU

      public PCSTNU(TemporalConstraintGraph<CSTNUEdge> graph, int giveTimeOut)
      Parameters:
      graph - a parameterized CSTNU, without copying or converting it
      giveTimeOut - maximum duration (in seconds) for the DC checking.

    • PCSTNU

      public PCSTNU()
      Creates a PCSTNU with an empty graph using the sparse backend by default.

    • PCSTNU

      public PCSTNU(boolean useDenseGraph)
      Creates a PCSTNU 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
      Reads a PCSTNU file and checks it.
      Parameters:
      args - an array of String objects.
      Throws:
      IOException - if any.
      ParserConfigurationException - if any.
      SAXException - if any.

    • initAndCheck

      public void initAndCheck() throws WellDefinitionException
      Checks and initializes the CSTN instance represented by graph g. The check is made by AbstractCSTN.coreCSTNInitAndCheck().

      Since many DC checking algorithms are complete if and only if the CSTN instance contains an upper bound to the distance from Z (the first node) for each node, this method also calls AbstractCSTN.addUpperBounds() for adding such bounds as constraints between Z and each node.

      Calls and then checks all contingent links. This method works only with streamlined instances!

      Calls and then checks all constraints about parameter nodes. This method works only with streamlined instances!

      Overrides:
      initAndCheck in class CSTNU
      Throws:
      WellDefinitionException - if the initial graph is not well-defined. We preferred to throw an exception instead of returning a negative status to stress that any further operation cannot be made on this instance.
      See Also:

    • oneStepDynamicControllability

      public CSTNU.CSTNUCheckStatus oneStepDynamicControllability(AbstractCSTN.EdgesToCheck<CSTNUEdge> edgesToCheck, Instant timeoutInstant)
      Description copied from class: CSTNU
      Executes one step of the dynamic controllability check.

      Before the first execution of this method, it is necessary to execute CSTNU.initAndCheck().

      Overrides:
      oneStepDynamicControllability in class CSTNU
      Parameters:
      edgesToCheck - set of edges that have to be checked.
      timeoutInstant - the time instant limit allowed for the computation.
      Returns:
      the updated status (for convenience, it is not necessary because it returns the same parameter status).

    • oneStepDynamicControllabilityLimitedToZ

      public CSTNU.CSTNUCheckStatus oneStepDynamicControllabilityLimitedToZ(AbstractCSTN.EdgesToCheck<CSTNUEdge> edgesToCheck, Instant timeoutInstant)
      Executes one step of the dynamic controllability check, considering only a pair of edges going to/from Z or parameter nodes.

      The name is limited to Z because it is inherited from CSTNU, but such a method also calls others that consider parameter nodes as Z nodes.

      Before the first execution of this method, it is necessary to execute initAndCheck().

      Note: this version is not optimized with respect to the number of times and edge is considered at each call. Future versions will improve this aspect.

      Overrides:
      oneStepDynamicControllabilityLimitedToZ in class CSTNU
      Parameters:
      edgesToCheck - set of edges that have to be checked.
      timeoutInstant - the time instant limit allowed for the computation.
      Returns:
      the updated status (for convenience, it is not necessary because it returns the same parameter status).

    • labelPropagation

      final boolean labelPropagation(LabeledNode nX, LabeledNode nY, LabeledNode nW, CSTNUEdge eXY, CSTNUEdge eYW, CSTNUEdge eXW)
      Apply A, A-Parameter, and C rules of the paper about Parameter-CSTNU. 
      1) CASE A
       ℵ:v,β           u,α
W==Z <------------ Y <------------ X
adds
    ℵ:u+v,𝛾
Z <------------------------------X
𝛾=αβ has to be consistent and u+v < 0.
ℵ can be empty.
If X is a parameter, set ℵ and 𝛾 empty in the generated edge

2) CASE A-Parameter
       v,β           ℵ:u,α
W==P <------------ Y <------------ X
adds
    ℵ:u+v,𝛾
P <------------------------------X
P is a parameter, 𝛾=αβ has to be consistent.
ℵ can be empty.
If X is a parameter or Z, set ℵ and 𝛾 empty in the generated edge

2) CASE C
    ℵ:v,β           C:u,α
Z <------------ Y <------------ C
adds
    Cℵ:u+v,αβ
Z <------------------------------C
if u+v < 0 and αβ is consistent
ℵ can be empty.
      Overrides:
      labelPropagation in class CSTNU
      Parameters:
      nX - node
      nY - node
      nW - node
      eXY - CANNOT BE NULL
      eYW - CANNOT BE NULL
      eXW - CANNOT BE NULL
      Returns:
      true if a reduction is applied at least

    • labeledCrossLowerCaseRule

      final boolean labeledCrossLowerCaseRule(LabeledNode nA, LabeledNode nC, LabeledNode nX, CSTNUEdge eAC, CSTNUEdge eCX, CSTNUEdge eAX)
      Apply B and B-parameter rules of the paper about Parameter-CSTNU.

      1) Case B 

          ℵ:v,β           c:u,α
Z <------------ C <------------ A
adds
            ℵ:u+v,αβ
Z <----------------------------A

Conditions: αβ∈P*, C ∉ ℵ, u+v < 0

      2) Case B-parameter 

          v,β             c:u,α
X <------------ C <------------ A
adds
            u+v,αβ
X <----------------------------A

X is a parameter node.
Conditions: αβ∈P*

      Since it is assumed that L(C) L (A)=α, there is only ONE lower-case labeled value u,c,α! The name is inherited from CSTNU.

      Overrides:
      labeledCrossLowerCaseRule in class CSTNU
      Parameters:
      nA - node
      nC - node
      nX - node
      eAC - CANNOT BE NULL
      eCX - CANNOT BE NULL
      eAX - CANNOT BE NULL
      Returns:
      true if the rule has been applied.