Class STNUAddSemiRigidCycles

java.lang.Object
it.univr.di.cstnu.util.STNUAddSemiRigidCycles
public class STNUAddSemiRigidCycles extends Object
Loads STNU instances previously generated by STNURandomGenerator using the add4or6NestedDiamond method (a chain of nested diamonds V(i) -> C(i) <= A(i) -> W, closed by a single Uxxx node) and adds, to each diamond of the chain, the one edge that is missing to turn its wait into a semi-rigid cycle: an ordinary path from A(i) back to V(i) whose length equals the magnitude of the wait generated by that diamond, so that the wait and the path form a tight cycle.

The generator already provides every other constraint the tight path needs (the nesting edges A(i+1) -> V(i) = -2 and, for the last diamond, Uxxx -> V(xxx) = -1); this class only supplies the complementary edge A(i) -> A(i+1) (or A(xxx) -> Uxxx for the last diamond) with the exact value that makes the path tight. A successfully processed instance also carries a DYNAMIC_CONTROLLABILITY CheckOutcome, recorded once the repaired graph has been confirmed controllable (see makeDynamicallyControllable(DenseTCGraph, Set)). Processing an instance means:

  1. Precondition: every node matching W\d+ must already have an outgoing non-derived edge (the invariant STNURandomGenerator establishes since r1144). If some W is still a sink, the diamond it belongs to would constrain nothing, and the file is skipped.
  2. Structure discovery: the unique Uxxx node is located, then the chain is walked backwards from xxx-1 requiring, at each step, the nodes A(i), V(i) and the nesting edge A(i+1) -> V(i); the walk stops at the first missing element, and the last index reached is the first (outermost) diamond. No fixed depth (4 or 6) is assumed.
  3. Value computation: for every diamond i of the discovered chain, the tight-path length need(i) = y(i) - vc(i) is computed from the graph itself, where vc(i) is the value of V(i) -> C(i) and y(i) is the upper bound of the contingent link (A(i), x, y, C(i)) (read from either the not-yet-initialized or the STNU.initAndCheck()-initialized representation). The added edge then gets value need(i) minus the already-present negative edge that closes the rest of the path.
  4. Repair: if adding these edges makes the instance not dynamically controllable, every negative requirement edge is relaxed by 1 and the check is repeated, except the specific edges the tight paths are made of: the nesting edges A(i+1) -> V(i), the edge Uxxx -> V(xxx), and the edges this class just added. Protection is by edge, not by node, so unrelated negative edges that happen to touch a Uxxx or A(i) node (both can carry ordinary random constraints from the surrounding network) remain relaxable.
  5. Verification: before saving, every tight path is re-measured on the repaired graph and compared against need(i); a mismatch aborts the save.
The result is a single output file per input, with suffix _withSRCycles. The suffix is inserted right before the input file's trailing instance index (the zero-padded _NNN counter STNURandomGenerator writes with %03d), if there is one, so the index stays the last thing before the extension (e.g. ..._withOne4NestedDiamond_027.stnu becomes ..._withOne4NestedDiamond_withSRCycles_027.stnu); otherwise the suffix is simply appended to the stem, as before. See computeOutputFileName(String, String).
Version:
$Rev: 1 $
Author:
posenato

  • Field Details

  • Constructor Details

    • STNUAddSemiRigidCycles

      public STNUAddSemiRigidCycles()

  • Method Details

    • main

      public static void main(String[] args) throws IOException, ParserConfigurationException, SAXException, WellDefinitionException
      Entry point.
      Parameters:
      args - command-line arguments (one or more STNU file paths)
      Throws:
      IOException - if a file cannot be read or written
      ParserConfigurationException - if the XML parser cannot be configured
      SAXException - if a file does not contain valid GraphML
      WellDefinitionException - if an STNU instance is not well-defined

    • addSemiRigidCycles

      public static STNUAddSemiRigidCycles.Result addSemiRigidCycles(DenseTCGraph<STNUEdge> graph) throws WellDefinitionException
      Graph-level entry point. Given a graph produced by STNURandomGenerator#add4or6NestedDiamond, adds one tightening edge per diamond of the discovered chain, repairs dynamic controllability if needed, and verifies that every tight path still measures what it should. The graph is mutated in place: edges are added, and, if a repair is needed, some existing negative requirement edges may be relaxed by 1 one or more times. Callers must not save the graph when a STNUAddSemiRigidCycles.Failure is returned.
      Parameters:
      graph - the graph to process
      Returns:
      a STNUAddSemiRigidCycles.Success describing what was added, or a STNUAddSemiRigidCycles.Failure with the reason to skip
      Throws:
      WellDefinitionException - if a dynamic-controllability check performed while repairing the graph finds it not well-defined

    • computeOutputFileName

      static String computeOutputFileName(String originalName, String suffix)
      Computes the output file name for originalName: suffix is inserted immediately before the name's trailing instance index (see insertSuffixBeforeTrailingIndex(String, String)), keeping the original extension last. Package-visible so the naming rule can be tested directly.
      Parameters:
      originalName - the input file's name, extension included
      suffix - the suffix identifying this tool's output (e.g. FILE_NAME_SUFFIX)
      Returns:
      the output file name