v7.2

Date: not released yet; in development.

SVN revisions: r1181–TBD (r1181 is the first revision of this cycle, the one that opened it by moving the version in pom.xml to 7.2; the final revision will be the release commit).

The version in pom.xml moved to 7.2 as the first act of the cycle so that the artefacts of the work that follows — CSTNU-Tool-7.2.jar and CstnuTool-7.2.tgz, both named after ${project.version} — cannot overwrite the 7.1 ones, which stay the published reference until the next release. codemeta.json still describes 7.1, the released version, and moves at release time.

Updated the following classes:

• STNU:
  • applySRNCycleFinder no longer stores a generating path per node; a check of a non-controllable network costs 31% less (r1187). The back-propagation kept, for every node, the whole path towards the upper-case edge being bypassed, and copied it on every improving relaxation. Over the 1599 sparse non-controllable instances of the 2020 STNU benchmarks: 160 084 relaxations per instance, each copying a path of 44.2 edges on average (median 34, longest 632), about 7.1 million edge copies per instance, each discarded by the next relaxation. The path is now one (edge, node) pair per node — the representation SRNCycleFinderUpdatePotential has used since r1174 — materialised only at the five points that consume it, by the new SRNCycleFinderPathTo. A relaxation costs O(1); the memory per contingent link is O(n) instead of O(n × path length). Three further changes on the same loop: SRNCycleFinderApplyRL returns the source node it already holds, in the new record SRNCRelaxedEdge, instead of leaving the caller to recover it from the graph (441 022 lookups per instance); an unreachable early return is removed, together with the DeltaC parameter that only it used; one queue look-up replaces two, through ExtendedPriorityQueue.getStatusAndPriority.
  • Timings on vega, one process at a time, 50 instances per family, three repetitions, both jars built without instrumentation: the sum of the SRNCycleFinder times over 399 instances falls from 46.23 s to 31.79 s, −31.2%; the ratio to applyRul2021 on the same instances falls from 1.475 to 0.997. Per family the reduction is between −22.7% (1000 nodes) and −38.7% (2500 nodes); above 350 contingents SRNCycleFinder is the faster of the two. Drift control: applyRul2021, whose code did not change, measured +1.8% overall and between −7.1% and +7.6% per family, so the bench noise is about ±7%. Per-instance distribution of the post/pre ratio: median 0.924, 25th percentile 0.736, 10th percentile 0.596, 75th percentile 1.010, 90th percentile 1.079; 70% of the instances are faster, the slowest quartile is up to 8% slower, within that noise. The reduction is concentrated on the instances with long stored paths, the large and dense ones: mean path length is 19.5 edges in the densest family and 109.2 at 2500 nodes.
  • Output equivalence of that change: the suite asserts properties of the reported cycle, not the cycle itself. Before the change, a temporary instrumentation rebuilt every consumed path from the predecessor chain and compared it with the stored path: 1 959 685 rebuilds over the 1599 instances, zero divergences. After the change, the corpus was run again with the cycle recorded as an ordered list of edge names: the post-change run matches a pre-change run on 1599 of 1599 instances, on the verdict and on the whole cycle, edge by edge.
  • The cycle reported by applySRNCycleFinder no longer depends on the memory layout. The loop of SRNCycleFinderBackPropagation that generates the edges X -> A iterated localInfo.distanceFromNodeToContingent, an open hash map keyed by LabeledNode, whose hashCode is the JVM identity hash. The adjacency of a node is insertion-ordered, so the order of that iteration became the order in which getInEdgesAndSources returns those edges, and SRNCycleFinderUpdatePotential, called once after the loop, walks them and reports the first negative loop it meets. On notDC_1000nodes_100ctgs_150maxWeight_20maxCtgWeight_5lanes__093.stnu the same network reported a cycle of value −1 under -XX:hashCode= 0, 1, 2, 3 and 4 and one of value −18 under 5, both semi-reducible negative cycles of length 9; forcing the order of that single iteration swapped the two. The nodes that generate an edge are now collected first and walked in name order, which leaves the map unchanged: RULLocalInfo is shared with applyRul2021 and fd_STNUgenerateBypasses, which report no witness. Only the nodes that reach the graph are ordered, not every node the back-propagation touched. After the change the six forced layouts, and three runs without them, all report the same cycle. For a given network the reported witness can differ from the one 7.1 reported; every cycle reported is a semi-reducible negative cycle of the network, and the witness is not part of any published result.
  • STNUCheckStatus.SRNCInfo reports the number of occurrences of each ordinary edge in the expanded negative cycle. getNegativeSTNUCycleInfo computed the multiplicity of every edge of the expansion in a local map and returned only its maximum, as maxEdgeRepetition; the multiplicity of the edges of a contingent link was available from lowerCaseCount/upperCaseCount, that of the ordinary edges was not. PSTN uses the contingent counts as the coefficients of its optimisation problem. The new component ordinaryEdgeCount maps each ordinary edge of srnExpanded to its number of occurrences. On magicLoop.stnu, whose 7-edge cycle expands to 22 occurrences over 12 distinct edges, it is {eC1-C2: 2, eC2-C1: 2, eC1-C3: 1, eC1-X: 1, eC3-C1: 1, eX-C1: 1}. Adding a component to the record breaks a positional construction of SRNCInfo; the only one is in STNU, the other consumers use the accessors.
  • Counting in SRNCInfo: the counter was fed from the unexpanded cycle, derived edges included, and from the expanded sub-edges, so the map was not the multiset of srnExpanded. A derived edge present k times forces each of its sub-edges to be present at least k times, and the maximum agreed with an independent recount of the expansion on every non-controllable instance of the corpus. An edge is now counted when it is appended to the expansion, so ordinaryEdgeCount and maxEdgeRepetition are functions of srnExpanded. maxEdgeRepetition is 0 when the report is requested without expansion, where it described the unexpanded cycle before; SRNCFinderBenchmarkRunner, the only consumer that reads it, requests the expansion.
  • Edge classification in SRNCInfo: isWait() is !isContingentEdge() && caseLabel.isUpper(), so a wait edge satisfies isUpperCase(). The if (edge.isWait()) arm was unreachable, and a wait edge was counted in upperCaseCount under the key g.getSource(edge), which for a wait is not the contingent time point of a contingent link. Classification uses isOrdinaryEdge(), and an upper-case edge is counted only when it is also contingent. The kind of the edges of the cycle was decided, inside the expansion loop, by the flag of the enclosing edge instead of the edge examined; a cycle whose lower-case edges occur only inside derivations and which has no upper-case edge was reported as containing every kind. The reported kind agrees with a recount of the expansion on the 7 non-controllable instances available.
  • Cost of the SRNCInfo report: getEdgePathAnnotation() rebuilds a copy of all the annotations on every call, and was called once per edge of the cycle plus once per level of recursion of resolveEdgeDerivation. One rebuild takes 34 µs on notDC002 (384 annotations, 3231 path edges), and the loop performed sixteen of them. The accessor is called once per report and the result is passed down; resolveEdgeDerivation memoises its resolutions, which makes resolving a cycle O(distinct derived edges × derivation size) instead of O(occurrences × derivation size). Times for the report alone, best of five rounds of 200 calls after warm-up, 7.2 jar against the new classes: notDC002 204 815 → 23 103 ns, notDC033 64 544 → 9 398 ns, magicLoop 10 727 → 5 358 ns. resolveEdgeDerivation returns an immutable list, and on a cyclic set of annotations it throws IllegalStateException naming the edge instead of exhausting the stack.
  • Iteration order of the three multiplicity maps of SRNCInfo: they are returned to the caller and their keys inherit the JVM identity hash, so they iterated in an order that depended on the memory layout of the run, and PSTN builds from lowerCaseCount.keySet() the order of the variables it passes to the optimiser. All three are Object2IntLinkedOpenHashMap and iterate in order of first occurrence in the cycle, which the traversal supplies; the by-name order that r1178 imposed in SRNCycleFinderBackPropagation cost 4%. The maps remain mutable — PSTN removes entries from them — and a removal preserves the order of the remaining entries. The key sequences of the three maps are equal across two runs on 4 instances, and under -XX:hashCode= 0, 1, 3, 4 and 5.
  • Tests: ten cases in STNUTest for SRNCInfo, with assertNegativeSRNCInfo checking the invariants of the three maps at every existing call site, and STNUTest#srncGeneratingPathsMatchTheEdgesTheyAnnotate for the path rebuilt by SRNCycleFinderPathTo, which must sum to the value of the edge it annotates. src/test/resources/magicLoop.stnu was added: notDC002, notDC020 and notDC033 contain derived edges and report maxEdgeRepetition == 1. PSTN is not run — it calls an external optimisation engine and the repository has no probabilistic instance — so the order of its variables is verified on the mechanism it uses, an ObjectArraySet built from lowerCaseCount.keySet() and completed with upperCaseCount.keySet(), on 3 instances under -XX:hashCode= 0 and 5.
• SRNCFinderBenchmarkRunner: one CSV column added, srncEdges, the reported cycle as an ordered list of edge names joined by |. Code that reads those CSVs by column position must account for one more field per row.

v7.1

Date: 2026-09-08

SVN revisions: r1164–r1179 (r1164 opened the cycle by moving the version in pom.xml to 7.1, r1179 is the release commit).

The release extends the set of algorithms that report the negative cycle behind an inconsistent answer, and removes from LabeledNode the working state of four of them: a node goes from 1430 to 156 bytes.

Updated the following classes:

• GraphAlgs:

  • SSSP_BFCT — Bellman-Ford with Tarjan's subtree disassembly — moved here from STN, with its helpers SUBTREE_DISASSEMBLY and PRINT_STATUS_NODES_BFCT and with REMOVE_INTERNAL_EDGES_WITH_PREFIX, which was private in STN. STNU calls it to extract the negative cycle of the LO graph. Migration: call GraphAlgs.SSSP_BFCT instead of STN.SSSP_BFCT; the signature is unchanged.

  • The search state of SSSP_BFCT — predecessor tree, sibling lists, reached/labeled/scanned mark — is in local arrays indexed by a dense node id instead of in the fields of LabeledNode. The method is re-entrant: two checks on the same graph cannot interfere, and a repaint during a check cannot render a half-built search tree. The distances are returned through an optional out parameter on a new overload; the five-argument form delegates with null. The three node states are the enum BFCTNodeStatus rather than bare ints; BFCT_NONE stays an int, being the absent index in the parent and sibling arrays and not a state.

  • New GET_NEGATIVE_CYCLE(int[]): from a parent array it returns the cycle it contains, in the convention SSSP_BFCT uses — a closed list of nodes in traversal order, consecutive pairs being edges. It is not a verdict: IS_NEGATIVE_CYCLE remains the verdict.

  • GET_SSSP_BellmanFord loses the setNodePotential parameter, its returned map being the authoritative state.

  • GET_BellmanFord_Potential uses a queue with Tarjan's subtree disassembly instead of a round-based scan. On a network whose LO graph has a negative cycle the updates never cease, so the scan could not stop early and ran its whole budget of n rounds over m edges before answering. The queue is mirrored to the inverted update the method performs: it holds the nodes whose potential grew, and popping one rescans the edges whose destination it is. Same fixpoint, same map, same null on a negative cycle. When the potential fails, the parent chain holds the cycle, which the method publishes in STNCheckStatus.negativeCycle after validating it: every consecutive pair must be an edge of the graph and the weights must sum negative, or nothing is published. Measured on the 2020 non-controllable benchmarks, in one JVM, the RUL2021 check and its potential side by side:

    	whole RUL2021 check	of which the potential	with BFCT the check would be
    2000 nodes, 10 instances	54.4 ms	45.8 ms (84%)	9.0 ms —6.0×
    1000 nodes, 10 instances	16.3 ms	6.4 ms (39%)	10.2 ms — 1.6×

    Per instance the gain ranged from 5× to 102×, and it grows with the network because the term that disappears is Θ(n·m). On a controllable network nothing changes end to end: the potential is about 1.6% of a RUL2021 check and 0.5% of an MDE run.

• STN:

  • Yen's algorithm returns the negative cycle, in all three variants (Yen, YenSingleSink, BannisterEppstein). It already maintained the parent array and walked it to detect the cycle, and then discarded it; the cycle now reaches the caller in STNCheckStatus.negativeCycle, validated before publication. The verdict still comes from IS_NEGATIVE_CYCLE, unchanged, so no network changes its answer. Yen keeps its distances in a local array instead of in the nodes; the random variant shuffles the node order with Fisher-Yates instead of writing random values into the node potentials.

  • New CheckAlgorithm.canGiveTheNegativeCycle(): true for BFCT and the Yen family. The two Bellman-Ford entry points report only the node where the network failed (negativeLoopNode), Floyd-Warshall and Johnson report neither, and Dijkstra does not detect negative cycles at all. For an STN the cycle is therefore always within reach: when the check ran with one of the others, one further call to SSSP_BFCT produces one, at the 8 to 10 ms measured below, paid only on the negative answer.

  • MAKE_NODES_REACHABLE_BY becomes public, so GraphAlgs can reach it, and SSSP_BFCT moves out (see GraphAlgs).

  • Measured on an STN of 2001 nodes and 6328 constraints (release build, best of six runs in a warm JVM, three alternating rounds against the revision before this work):

    	before	after
    graph load	25.0–26.3 ms	25.0–25.6 ms
    BFCT	72.1–74.1 ms	7.8–10.2 ms
    Yen	73.3–79.8 ms	71.2–76.6 ms
    Yen single-sink	67.0–72.4 ms	62.7–71.9 ms
    Bellman-Ford	1.8–2.2 ms	2.0–2.2 ms

    BFCT is about eight times faster, its search state being in local arrays instead of in the nodes. Yen cost 5% more at first, an array indexed by a scattered index being less cache-friendly than a field of an object the loop already touches; removing the index lookup it performed per node per round, asking a map for a value that was the loop variable, more than paid for it.

• STNU:

  • The first step of RUL2021, RUL2018 and the FD algorithms is the potential of the LO graph, now computed with BFCT (see GraphAlgs.GET_BellmanFord_Potential): a non-controllable network is refused sooner, and STNCheckStatus.negativeCycle is filled by those checks too. 55% of the non-controllable instances at 1000 nodes and 68% at 2000 and 2500 are refused there, by the potential, before any upper-case edge is bypassed. The remaining refusals come from the upper-case bypass and their witness is a semi-reducible cycle involving contingent links, which is not a negative cycle of any static weighted graph: SRNCycleFinder is the only way to obtain those. Measured on STNU networks of 2001 nodes: RUL2021 0.270–0.273 s before against 0.271–0.277 s after, SRNCycleFinder 0.412–0.432 s against 0.398–0.403 s, MDE 6.73–6.77 s against 6.57–6.71 s.

  • findSRNCycleInLOGraph reuses the cycle the potential has already found, and keeps its own SSSP_BFCT call only as a fallback.

  • SRNCycleFinderUpdatePotential keeps one edge per node instead of a whole path. It recorded, for every node whose potential it raised, the entire generating path, rebuilt by copying the path of the node the value came from, so every relaxation cost a copy of everything found so far. It records the edge that raised the node and where that edge leads, and walks that chain back only when a negative loop is detected. The cycles produced are identical over ten instances at 2000 nodes; the gain is 2 to 4% at 2000 nodes and nothing at 1000. The premium this was meant to recover — SRNCycleFinder against RUL2021, +44% at 1000 nodes and +114% at 2000 — was mostly the round-based potential, which the change above removed; what remains is +22% and +30%.

  • Fixed: applySRNCycleFinder could report a different negative cycle on different runs of the same network. The verdict was never in doubt, only which of the network's negative cycles came back, and five consecutive runs agree; it takes forcing different memory layouts with -XX:+UnlockExperimentalVMOptions -XX:hashCode=N to see it. Over thirty non-controllable instances of the 2020 benchmarks, one answered with two different cycles; none does after the fix. The cause was unStartedUCEdges, keyed by LabeledNode, which inherits the identity hash: iterating it visited the nodes in the order the objects happened to occupy in memory, and that order decides which upper-case edge is bypassed first. SRNCycleFinderBackPropagation iterates it in order of node name, the one place where the order is observable; rul2021BackPropagation, which iterates the same map, does not sort, reporting a verdict and no cycle. Fifty non-controllable instances per size, two rounds, minimum per instance, against the map iterated as it comes:

    	1000 nodes RUL2021 / SRNCycleFinder	2000 nodes RUL2021 / SRNCycleFinder
    map, no order (reference)	1.418 s / 1.732 s	2.394 s / 3.269 s
    insertion order everywhere	+0.0% / +7.3%	+8.5% / +11.1%
    name order, only where observable	−0.4% / +3.9%	−0.4% / +4.2%

    The cost is not the container and not the sort — a few hundred names are nothing — but which order the algorithm walks, since that changes how soon a cycle closes: the order the identity hash produced was lucky on this corpus, and of the two deterministic orders, name order recovers about half of what insertion order lost. Per instance the penalty has median +1.3% and +0.4%, and at 2000 nodes 22 instances out of 43 are faster: the aggregate is a tail, not a shift. Scoping matters: an earlier version made the collection insertion-ordered for both algorithms and cost RUL2021 8.5% at 2000 nodes for a determinism it does not need. That 4% is measured on one corpus and is not a property; another corpus could invert the ranking of the two deterministic orders. What is structural is that RUL2021 pays nothing, and that name order is reproducible across releases, which insertion order is not — it follows the traversal, and the traversal changes when the code does.

  • MDELocalInfo keeps the same collection as an ObjectArrayList rather than the ObjectArraySet it was: nothing looks a node up in it, and a duplicate cannot arrive there because rigid components partition the nodes, so the array set paid a linear scan on every add to exclude something impossible. Its insertion order is already deterministic.

  • distanceFromNodeToContingent keeps the same exposure in principle, being iterated by keySet() in the twin loops of SRNCycleFinderBackPropagation and rul2021BackPropagation. No instance of the corpus was seen to depend on it, and closing it costs a further 6%, so it is documented rather than paid for blind. (Fixed in 7.2, for SRNCycleFinderBackPropagation, where an instance was found that does depend on it.)

  • A checking algorithm no longer writes into the network it was given: collapsing a rigid component adjusted the log-normal distribution of a contingent duration with setShift on the object read from the node, and the clone constructors of LabeledNode share that object, so the shift reached through every copy of the node, including the one in the caller's own network. The representative gets a new parameter object (see LogNormalDistributionParameter).

• LabeledNode: a node goes from 1430 to 156 bytes, measured over 20 000 nodes; construction is about four times faster.
  • predecessor, before, after, status and the Status enum are removed. They were the search state of SSSP_BFCT, used in thirty-two places, all inside GraphAlgs, which now keeps them in local arrays.
  • potential is removed, with its getPotential/setPotential and its line in toString(). It was working state of Yen and of BFCT, an output channel for the distances, and something the editor displayed. Migration: ask the algorithm for the distances instead of reading them off the nodes.
  • labeledUpperPotential and labeledPotentialCount are removed: they were the working state of CSTNPotential and of nothing else, neither persisted nor part of NetworkFingerprint nor displayed.
  • labeledPotential stays — the writer saves it, the fingerprint includes it, the editor shows it — but it is allocated on the first write and dropped by clearPotential(), and reads answer from a shared empty view. A node with a labeled potential still costs about 1200 bytes: only the nodes that need the map pay for it.
• CSTNPotential: owns the two labeled maps that LabeledNode used to hold, per node, allocated on first use and cleared in initAndCheck, reachable through the new getUpperPotential/putUpperPotential. updatePotentialCount is no longer static.
• LabeledALabelIntTreeMap: fixed — every read-only view reported size 0. The view shares the map of the object it views but not its cached count, and size() returned that count, so isEmpty() answered true whatever the view contained, and node.getULCaseLabeledPotential().isEmpty() lied about every node that had a potential. The view computes its size from the map it shares, which also keeps the answer live. The sister view of the plain labeled map was never affected, which is why the GraphML writer and the fingerprint, which ask that one, have always saved potentials correctly.
• LogNormalDistributionParameter: immutable. setShift is gone — it had exactly one caller, the rigid-component collapsing in STNU — and shift is final. Migration: build a shifted parameter with the three-argument constructor.
• DenseTCGraph: setAllPotential removed, no callers.
• EditorController: when an STN check fails and no cycle is available, the message adds that running BFCT or Yen would produce one. For an STNU it shows the cycle when the check published one, and otherwise states that the network is not controllable because of a cycle involving the contingent links and that SRNCycleFinder is the algorithm that produces those.
• EditorView: the node tooltip no longer shows a scalar potential, LabeledNode.potential being removed.

v7.0

Date: 2026-08-31

SVN revisions: r1032–r1162 (r1162 is the release commit).

This release removes JUNG from the project and introduces two interchangeable backends behind TemporalConstraintGraph: SparseTCGraph, the default for every kind of network, and DenseTCGraph, for the dense-specific operations and for callers that ask for it explicitly. Algorithms that need only the common graph API preserve the concrete backend of their input. Nothing in the library depends on JUNG any longer — not the graph model, not GraphML I/O, not the algorithms, and not the editor, which draws through plain Java2D.

The Swing editor has been rewritten from scratch in the new it.univr.di.cstnu.gui package, replacing the JUNG-based one. It is backend-agnostic, it draws and interacts through plain Java2D, and its controller is headless-testable, so the editor is covered by the ordinary test suite instead of being exercised by hand.

Public API migration notes:

• The following public class names were renamed to make the representation explicit: TNGraph → DenseTCGraph, TCNGraph → SparseTCGraph, TNPredecessorGraph → TCPredecessorGraph, TNGraphMLReader → TCGraphMLReader, TNGraphMLWriter → TCGraphMLWriter, and TNGraphBaselineRunner → TCGraphBaselineRunner (with the corresponding test classes). The nested TNGraph.NetworkType enumeration is now the top-level TemporalConstraintNetworkType. This is a source-incompatible API change.
• Algorithms that formerly accepted a concrete dense graph now take TemporalConstraintGraph in their constructors and methods. The dense-only overloads survived for a while as deprecated adapters that only cast their argument, and have been removed before the release, this version being the one that introduces the distinction: pass a TemporalConstraintGraph everywhere, STN.MAKE_MINIMAL_DISPATCHABLE(TemporalConstraintGraph) included. A dense graph is one, so a caller holding a DenseTCGraph needs no change.
• Use getGraph() and getCheckedGraph() on the migrated algorithm classes instead of the deprecated dense-only getG() and getGChecked() accessors. These, unlike the constructors, are still there: they narrow the returned graph to the dense backend, which the JUNG editor and the GraphML writer still require.
• Use graph.renameNode(node, name) and graph.renameEdge(edge, name) instead of changing the name of a graph-owned node or edge through setName.
• newInstance(...) replaces ad-hoc construction of auxiliary graphs in generic code: it creates a graph of the receiver's concrete backend, while target.newInstance(source) creates a faithful copy of any source graph in the backend chosen by target.
• Every algorithm class has an XXX() constructor that builds a sparse network and an XXX(boolean useDenseGraph) one for asking the dense backend. Code that relied on CSTNPSU(), OSTNU() or PCSTNU() returning a dense graph must now say so: new OSTNU(true). No kind of network is dense-only any more: CSTNPSU/FTNU, OSTNU and PCSTNU, documented as dense-only in the first part of this release cycle, work on both backends and default to sparse like their siblings. In STN, STNU and the CSTN-family algorithms the graph fields and the auxiliary paths use TemporalConstraintGraph, and fresh working graphs are created through newInstance, which preserves the selected backend.
• Use equalsByName instead of equals to compare two nodes or edges by name. Component.equals is deprecated: it is identity comparison, inherited from Object, which is what a graph needs internally but rarely what a caller means. The name is the identity of a component within its graph, and equalsByName says so explicitly.

Removed the following dependencies:

• JUNG 2.1.1 (net.sf.jung:jung-*) and Guava: no class of the library uses them any more. The it.univr.di.cstnu.visualization package, which held the old JUNG-based editor together with JungGraphAdapter, TNEditorApi, the graph-mouse plugins and SpringLayoutRunner, has been deleted; the new editor in it.univr.di.cstnu.gui replaces it. Guava came in only through JUNG and through two uses of its own (com.google.common.base.Supplier and Lists.cartesianProduct), both replaced by java.util.function.Supplier and by explicit enumeration. The distribution archive shrank from 9.0 MB to 6.9 MB, and the project no longer carries Guava's known vulnerabilities. Users who imported anything from it.univr.di.cstnu.visualization, or who relied on the JUNG graph interfaces being implemented by the graph classes, must migrate: the graph classes now implement only TemporalConstraintGraph. Luke2GraphML, which used the JUNG spring layout to give coordinates to a format that carries none, uses the new FruchtermanReingoldLayout instead, so its output still opens in the editor with a sensible layout.
• net.openhft:affinity and the --nCPUs option of Checker, CSTNU2CSTNPSU, and STNUDensifier: the tools now process their input files sequentially. --nCPUs parallelized only independent files, never an algorithm on one graph; measurements and verification found no real throughput gain, while concurrent jobs contend for memory bandwidth, caches, garbage collection, and possibly NUMA memory. CPU pinning does not remove that contention, and a standard Java pool would retain both it and needless complexity. Removing Affinity also eliminates its transitive JNA native-access dependencies from the distribution.

Added the following classes:

• AbstractBenchmarkRunner: shared base for the benchmark runners. It holds the common command-line options (input files, output CSV, number of repetitions, timeout, save, version), the output-stream management, and the repeatMeasure engine that executes an algorithm on a fresh instance for a given number of repetitions and collects the execution-time statistics.

• CheckOutcome and DispatchabilityOutcome: the two stored assertions, each a record with its own textual form. CheckOutcome.currentToolVersion() reads Implementation-Version from the manifest and answers dev when there is none, which is the answer for a run from a build tree or from the test suite.

  • A network carries the outcome of a check into its file through them. The two properties are persisted, and they are independent, because a network can be controllable and only afterwards be made dispatchable: CheckOutcome records the kind of check — consistency for the STNs, dynamic consistency for the CSTNs, dynamic controllability for the STNUs, the CSTNUs and the CSTNPSUs, agile controllability for the OSTNUs — its result, the algorithm that produced it and the version of the tool; DispatchabilityOutcome records whether the network is in dispatchable or in minimal form, and by which algorithm.
  • An outcome read from a file is an assertion by whoever wrote it, so it is stored together with the fingerprint of the network and is believed only while that fingerprint still matches (see NetworkFingerprint). When the fingerprint is missing, or of a version this tool cannot compare, or simply different, both properties are dropped in silence and the network loads normally: a stale verdict is not a malformed file.
  • What writes them is every checker: every check entry point, and every initAndCheck, clears the two stored outcomes before touching the network, and every check records its verdict when it ends, the negative one too, while a check that is cancelled or that exhausts its cycle budget records nothing, because the absence of an outcome is how “not known” is represented. Which check records what is under STN, STNU and CSTN.
  • Everything that mutates a network drops the two properties before starting: a claim belongs to the network it was established on, and the fingerprint cannot catch a claim attached to a network that has changed since, precisely because it is computed when the file is written, so it would match. What a copy and a content move do with them is under DenseTCGraph, and what an edit in the editor does is under EditorDocument.

• CurvaturePolicy: the automatic edge routing is decided in one place for both the screen and the exported figures, which previously disagreed: antiparallel edges were drawn apart on screen and superimposed in the exported TikZ.

• DenseTCGraph: JUNG-independent dense implementation of TemporalConstraintGraph. It retains the adjacency matrix needed by dense-specific operations (findEdge remains O(1)) and its incrementally maintained incidence indexes.

• EdgeRoute: an edge can carry an explicit routing: up to two control points, expressed relative to the chord joining the endpoints, which the user drags to lay out bundles of nearby edges so that they do not overlap, and optionally the angles at which the edge leaves its source and reaches its destination, dragged through two further handles constrained to the node circles. The routing is part of the document and is persisted in GraphML under the new per-edge key Route (see TCGraphMLWriter); its absence means automatic routing (see CurvaturePolicy), so every existing file keeps opening and saving exactly as before.

• GraphAnnotation: a network can carry annotations: free text placed on the drawing, which belongs to the document, is persisted in GraphML, and is reproduced by the SVG and TikZ exporters, so a figure prepared in the editor needs no retouching afterwards. An annotation is left out of NetworkFingerprint.

• MDEBenchmarkRunner: benchmark runner for the MDE family on DC STNUs (the inputs need not already be dispatchable). At least one algorithm-selection option is required: --MDE (or -MDE) executes MDE, whereas --MDE2 (or -MDE2) is accepted as a forward-compatible placeholder but is not implemented and reports method not yet implemented. in its CSV columns. For every input graph and selected implementation, the runner executes --numRepetitionDCCheck repetitions (30 by default), each on a fresh copy of the original STNU; it records mean and standard-deviation execution time, resulting edge count, and status. A timed-out or failed execution contributes neither time nor edge count to the global summary. The shared options are positional GraphML STNU input files, -o/--output for an append-mode CSV output, --timeOut (1800 seconds by default), --save to write successful checked networks, and -v/--version.

• NetworkFingerprint: the canonical semantic form of a network and its digest, written as sha256:v1:<hex>. The form holds the kind of the network, the nodes in name order with what the algorithms read from them, and the edges ordered by their endpoints with constraint type, ordinary value, labeled values and case label. An A-Label is written with its letters in lexicographic order rather than through ALabel.toString(), which orders them by position in the global registry: otherwise the digest would have depended on what had been loaded earlier in the same JVM. The version in the prefix lets a future change of the form make an old fingerprint unknown instead of mismatched, which isVersionComparable tells apart.

  • The SHA-256 digest is of that semantic form and not of the file: were it computed on the GraphML, adding a key — as the new Route key just did — would invalidate every fingerprint already stored. Coordinates, routing, annotations, the graph name and the name of an edge are left out of the form, so moving a node keeps a verdict while changing a weight drops it.

• PhaseStatsBenchmarkRunner: temporary, study-only runner for a focused comparison of the phase statistics of MDE (-MDE), SIMP-SEQ (-SimpSeq), and SIMP-SEQ-MINUS (-SimpSeqMinus) on DC STNU GraphML inputs. It repeats each selected algorithm through --numRepetitionDCCheck (10 by default) to average phase times, retains deterministic edge counts, aggregates the final values over the complete input set, and emits two \pgfplotstableread{...} blocks ready for the experimental article. It is not a production API: it and the associated PHASE-STATS instrumentation in STNU may be removed once the study is complete.

• SparseTCGraph: JUNG-independent sparse implementation of TemporalConstraintGraph, optimized for the project's usual sparse temporal-constraint networks. It stores only existing edges and maintains indexes by edge name, ordered endpoint pair, and incoming/outgoing incidence. Endpoint and edge lookup are expected O(1), incidence enumeration is O(degree), and transpose() is O(|E|).

• TCGraphBaselineRunner: command-line, non-JUnit benchmark for a reproducible comparison of DenseTCGraph and SparseTCGraph on external GraphML STNU files. --backend DenseTCGraph|SparseTCGraph|both selects the measured representation (both by default). It writes individual and mean CSV rows; its JVM used-memory deltas are marked approximate, because they are informative only and not reliable allocation metrics. The checked-in TNGRAPH_BENCHMARK_BASELINE.md records the initial 500–2500-node sparse and dense comparison.

• TCPredecessorGraph, TCGraphMLReader, and TCGraphMLWriter: backend-neutral predecessor-graph and GraphML services. The reader/writer operate through TemporalConstraintGraph, allowing GraphML networks and algorithm-produced copies to remain dense or sparse as requested by the caller.

• TemporalConstraintGraph: JUNG-independent data-structure API for temporal-constraint graphs. Besides basic graph operations, it now provides backend-preserving factories (newInstance), generic GraphML-facing mutation operations, safe graph-owned node/edge renaming (renameNode, renameEdge), and faithful copying. Direct setName is rejected after insertion into a graph, preventing stale name indexes without per-component listeners or overhead on ordinary graph construction/removal.

  • ownsEdge and ownsNode. Within a graph an element is identified by its name, so containsEdge and getSource/getDest answer by name and resolve a foreign but homonymous element to the local one; the two new methods answer by identity, for the callers that need actual membership. The documentation of the name-based methods was corrected accordingly. Their first use inside the library is STNU.minDEremoveStandInEdges (see STNU).
  • clearOutcomes, recordCheckOutcome and recordDispatchabilityOutcome, through which a check stores its verdict on the graph (see CheckOutcome), and addAnnotation, getAnnotations, removeAnnotation and clearAnnotations for the free text placed on the drawing (see GraphAnnotation).

Updated the following classes:

• CSTN: the CSTN family — CSTN, CSTNU, CSTNPSU, OSTNU and their subclasses — writes the verdict of a check on the checked graph and on the cleaned copy that getCheckedGraph() returns, since there the two are different objects (see CheckOutcome).
• CSTN2CSTN0: took its own consistency from the finished flag of the transformed check instead of from its consistency, so it declared consistent every instance whose inner check ran to the end, which also made Checker print that an inconsistent instance is DC. Corrected because that verdict now reaches a file, where a wrong one would be believed.
• DenseTCGraph:
  • Safe, atomic node and edge renaming through TemporalConstraintGraph.renameNode and renameEdge, in this backend and in SparseTCGraph. A node rename updates structural indexes, name-keyed caches, A-label references, case labels, upper/lower-case values, and labeled potentials; collisions are merged by the established minimum-value semantics. A graph-owned component can no longer be renamed directly with setName, preventing corrupt indexes. The editor uses these operations and reports a failed rename without invalidating its checked graph.
  • A graph that receives a parameter node now calls itself a PCSTNU, in this backend and in SparseTCGraph, so that the kind of a network follows its content instead of staying whatever it was when the graph was created.
  • Assigning an observed proposition, or an oracle, to a node already inserted in a graph updates the graph's observer index (see SparseTCGraph, whose defect it was). This backend was already correct here, apart from one point: on the duplicate branch it restored the node's previous proposition only inside if (Debug.ON), so a release build detected the duplicate, kept it on the node and skipped the invalidation of its index, while a build with debug enabled restored it. The behaviour no longer depends on that constant; only the log message does.
  • A fresh copy carries no stored outcome, in this backend and in SparseTCGraph, because it is a different network and starts without claims about itself, while takeFrom and replaceContentsFrom — which move a finished content into another object and keep its identity, as the editor does to keep the result's object stable after a check — carry both, since dropping them there would lose a verdict just established, immediately before the file is saved. DenseTCGraph.copy used to copy the two properties by reference into a deep clone, so a cloned network was born asserting something about another one.
• DispatchabilityBenchmarkRunner: refactored onto the new AbstractBenchmarkRunner base (single repetition/measurement engine, shared option validation). Dropped the --MDE option and its CSV columns: the MDE family is now benchmarked by the dedicated MDEBenchmarkRunner. Fixed a minimization repetition that failed but still contributed to the timing statistics, and unified the timeout accounting across the two testers.
• EditorDocument: two behaviours of the old editor were corrected.
  • An element of the computed network is now shown read-only, because editing it used to mark the document dirty and silently discard the result of the check while leaving the input network untouched.
  • A document edit that changes only how the network is drawn — node coordinates, edge routing — no longer invalidates the result of the check, which it has no reason to affect. A structural edit removes the verdict stored on the network; moving a node or rerouting an edge does not. A completed check leaves its verdict on the network shown as the result and on the input network as well — consistency and controllability are properties of the network, and a check preserves equivalence — so an ordinary Save records it, while the dispatchable form, which is a property of the result alone, stays with the result.
• FTNU: the no-argument constructor installed no graph, so FTNU.main died with a NullPointerException while reading the input file, before the check could start; the class now installs a graph like its siblings. FTNU.main parsed no argument at all and checked nothing, so the class was reachable only from code; it now behaves like the other mains.
• GraphAlgs: rewrote the strongly-connected-components routines (GET_STRONG_CONNECTED_COMPONENTS and GET_STRONG_CONNECTED_COMPONENTS_OL) from recursion to an explicit iterative Tarjan, so that graphs with thousands of nodes can no longer overflow the JVM call stack (component and emission orders are unchanged). Simplified getDepthFirstOrder by removing the redundant isVisited map (a node is visited iff its DFS status is finished). Optimized the graph-based GET_BellmanFord_Potential by extracting the significant edge weights once into parallel int arrays and by keeping node potentials in a dense int[] indexed by node id instead of a hash map. Hoisted loop-invariant lookups out of UPDATE_DISTANCES and pre-sized internal maps. Its migrated routines, including predecessor-subgraph construction, SCC, Floyd-Warshall, Bellman-Ford, reweighting, and the generic minimal-dispatchable path, now accept TemporalConstraintGraph and preserve the input backend. APSP_Johnson remains explicitly dense-only.
• GraphML2Luke: in stnuPlainWriter, the Num Ordinary Edges header is now the actual number of ordinary constraints written (counting the ordinary value carried by contingent/wait edges too), instead of an incorrect formula based on edge, contingent, and wait counts. Removed a redundant anonymous block.
• Luke2GraphML: accepts an ESTNU header and its optional # Waits section, converting each wait into the corresponding upper-case edge. It gives coordinates through FruchtermanReingoldLayout instead of the JUNG spring layout (see Removed the following dependencies).
• OSTNU: the no-argument constructor installed no graph, with the same effect on OSTNU.main as in FTNU; the class now installs a graph, and OSTNU() became public.
• PCSTNU: the no-argument constructor installed no graph, with the same effect on PCSTNU.main as in FTNU; the class now installs a graph.
• SparseTCGraph: assigning an observed proposition, or an oracle, to a node already inserted in a graph now updates the graph's observer index. This backend used to record observers only when the node was added, so a proposition assigned afterwards — the normal order of events in the editor, and in any code that builds a node and then makes it an observer — stayed invisible: getObserver returned null, getPropositions did not list it, and a second node could take a proposition that was already taken. Clearing a proposition left a stale entry behind. Renaming, the PCSTNU kind on a parameter node, and what a copy and a content move do with a stored outcome are shared with DenseTCGraph.
• STN:
  • MINIMAL is recorded for makeDispatchable and makeMinimalDispatchable, which for a network without waits are the same thing (see CheckOutcome).
  • An interrupted consistencyCheck was indistinguishable from a completed one, since the method overwrote the finished flag that APSP_FloydWarshall sets to false when the thread is interrupted — and the editor cancels a check exactly by interrupting its thread, so a cancelled check would have recorded a verdict it never established.
• STNU:

  • Replaced the previous two-pass minimal-dispatchability workflow with the current MDE implementation, which converts a DC STNU into its minimal-dispatchable ESTNU form in a single integrated pass. Compared with the previous FD plus minimal-dispatchability sequence, worst-case O(n^3), the current MDE algorithm costs O(mn + kn^2 + n^2 log n), strictly better than O(n^3) on sparse networks, and, by keeping special stand-in edges, it handles semi-rigid cycles (a cycle in the ordinary+wait graph formed by a wait edge (V, C:-v, A) and an ordinary path (A, v, V)): a case for which prior algorithms can produce a non-equivalent dispatchable network. All the mde* methods implementing MDE were added:

    • mdeM1: Step M1 entry — back-propagates from every UC edge to generate the undominated UC-bypass edges; returns the LO-graph potential.
    • mdeM1BpPlus: back-propagates from one UC edge, resuming recursively through still-unstarted UC edges.
    • mdeM1TryBpPlus: for a contingent node, back-propagates the mdd values along the incoming LO edges and decides which bypass edges/waits to add.
    • mdeM2: Step M2 — for each LC edge, forward-propagates from the contingent node to generate the undominated LC-bypass edges.
    • mdeM3: Step M3 entry — computes the ordinary+wait-graph potential, builds the AllMax reverse-predecessor graph, marks semi-rigid cycles, and generates the stand-in edges.
    • mdeM3buildMultiRevPredGraph: builds the reverse-predecessor graph of the AllMax projection (tight ordinary/UC/wait arcs).
    • mdeM3AddSucc: appends an arc to a node's successor list in that graph.
    • mdeM3fasterBetterGenStandIns: back-propagates from each target W, generating the undominated (and special) stand-in edges while tracking non-negative descendants.
    • mdeM3backPropOrds: the back-propagation step along ordinary edges, updating distances and non-negative-descendant sets.
    • mdeM3processWaits: projects a contingent link's waits during the back-propagation and records regular/special stand-in needs.
    • mdeM4: Step M4 entry — collapses the rigid components and runs the STNU-adapted dispatchable-STN minimization on the collapsed graph.
    • mdeM4b4ManageRCsForStnDisp: preprocessing — finds and collapses the rigid components of the tight ordinary graph into representatives and builds the collapsed graph g'.
    • mdeM4buildRPG: builds the reweighted reverse-predecessor tree/DAG used to find undominated predecessors.
    • mdeM4accUndomPreds: forward-propagates the need / non-negative-descendant statistics to accumulate the undominated predecessors of a target.
    • mdeM4stnDispESTNU: runs the adapted stnDisp over all targets to classify edges as dominated/undominated.
    • mdeM4processSpecialStandins: decides which special stand-in edges (those derived from semi-rigid cycles) must be preserved.
    • mdeM4representativeOf: returns the representative of a node after rigid-component collapse.
    • mdeM4resetRpgi: resets the per-target reverse-predecessor-graph scratch structure.
    • mdeM4addOrUpdateOrdinary: adds or updates an ordinary edge in g'.
    • mdeM4addOrUpdateLabeled: adds or updates an LC/UC/wait labeled edge in g'.
    • mdeM4addOrReplaceAdjacency: adds or replaces an adjacency entry in the working adjacency maps.
    • mdeM4putUndomPred: records an undominated predecessor together with its distance.
    • mdeM4putMinStandIn: keeps the minimum stand-in value for a (source, dest) pair.
    • mdeM4oreO: combines two “need” values (the ⊕ operator on the need markers/sets).
    • mdeM4mergeNeed: merges a need value into a node's current need value.
    • mdeM4copyNeedSet: copies a need-set value.
    • mdeM4isEmptyNeed: tests whether a need value is empty.
    • mdeM4firstByName: picks a deterministic node from a set (the first by name).
    • mdeM5: Step M5 — removes the dominated stand-in edges, restores the rigid components, and builds the final minimal dispatchable ESTNU.

    The supporting data structures were introduced as well (MDELocalInfo, MDELocalInfoM2, MDELocalInfoM3, and the MDEM4RCInfo/MDEM4* records); MDELocalInfo uses pre-sized maps and a reused priority queue across its per-update scans. The mde* methods are not optimized with respect to memory usage and running time.

  • applyMDE() returns a boolean (was void): true when the network was successfully turned into its minimal dispatchable form, false when the computation could not complete because the network is null (empty), not DC, or a timeout occurred (the detailed reason is always in getCheckStatus()); a @see #applyMDE() was added to every mde* auxiliary method. The obsolete earlier minimal-dispatchability implementation (mdeRUL2021Plus, mdeRUL2021BpPlus, mdeTryBackPropPlus, mdeGetWaitsMarkedToRemove, and the nested support types used only by that implementation) has been removed. CheckAlgorithm.MDE is now the only MDE-family algorithm exposed by STNU; MDEBenchmarkRunner measures --MDE and keeps --MDE2 only as a not-yet-implemented placeholder.

  • Fixed a bug in Step M3 (mdeM3fasterBetterGenStandIns): the removal of the dominated waits terminating at an activation node (pseudocode E_w.delete) identified the correct waits (distToW[V] <= -v) but deleted them only from an internal bookkeeping set that is never read again, so the dominated waits survived into the final network. They are now actually removed from the graph (the wait value is reset on the edge, and the edge is dropped if nothing else remains on it), producing the correct minimal number of wait edges. Removed the now-unused field waitEdges from MDELocalInfoM3.

  • Step M3 follows the revised pseudocode — the potential function is computed on the ordinary+wait graph instead of the ordinary+wait+upper-case one, the reverse predecessor graph no longer holds the upper-case edges, and srHash is filled by comparing the rigid-component representatives of the two endpoints of every wait instead of walking the components in search of tight waits. It was adopted after measuring that it changes nothing: networks identical edge by edge on the sixty 1000-node instances, with and without semi-rigid cycles, and on the twenty-four test fixtures; it is not faster either. Step M3 also skips a wait whose source is the destination being processed, whose stand-in edge would be a useless self-loop.

  • The representative of a rigid component is now chosen the same way at every site that chooses one, through two shared helpers, mdeAssignReps (selection, tie-break and offsets) and mdeReOrientEdgeWeight (the re-orientation weight delta + offset[measured] - offset[other]). The tie-break is part of the specification rather than of the implementation: an ordered preference list whose last element is the total order on names, so the representative is a function of the input and never of the iteration order of a hash map. One behaviour changed: in GET_REPRESENTATIVE_RIGID_COMPONENTS, used by makeOrdinaryConstraintMinimalDispatchable and hence by the minimization of the FD phase 5 as well as by MDE, the zero time point Z was taken as representative as soon as it was met, whatever its distance; it is now preferred only among the time points that attain the minimum. An unconditional preference contradicts that minimum and can make some offsets negative, and their non-negativity is what the argument x' = offset[A] + x >= x > 0 of Step M4 rests on.

  • Fixed two rigid-component bugs in collapseRigidComponents (used by makeOrdinaryConstraintMinimalDispatchable, hence by both MDE/applyBetterMinDispESTNU and the FD phase-5 minimization) that could corrupt a contingent link or drop a required constraint when a contingent time-point falls inside a rigid component. (1) When a rerouted wait (an upper-case value on a non-contingent edge, for which isWait() is true) was merged onto an edge that happened to be the genuine upper-case edge of a contingent link, the code called resetLabeledValue() on it, stripping the UC label and demoting the edge from contingent to requirement (destroying the contingent upper bound). The wait merge is now skipped when the target edge is contingent. (2) When a dominated weak stand-in edge was rerouted onto a pre-existing genuine (non-weak) edge whose ordinary value was not updated by the merge, the weakEdges bookkeeping wrongly marked the genuine edge as a stand-in, so it was later dropped by minDEremoveStandInEdges; a pre-existing genuine edge now stays a real constraint (a newOutEdge/newInEdge is treated as weak only if it was itself weak or was freshly created for the reroute). In addition, applyBetterMinDispESTNU now re-types any surviving internal stand-in edge (e.g., a repurposed VAC-companion whose value became undominated) as derived, so the final minimal dispatchable network no longer contains internal-typed real constraints (which GET_SPFromActivations_JohnsonO would otherwise skip as stand-ins).

  • upperContingentEdge became a linked hash map, and with it the algorithm became a function of its input. Keyed by LabeledNode, whose hashCode is the identity hash of the JVM by design — a node can be renamed, so the hash cannot depend on the name — a plain open hash map iterated in an order that depended on the heap, and the recursive mdeM1 used that order to decide which contingent link to process out of turn: the same network could therefore produce different, equally correct results in different runs of the same JVM. The same map is iterated by applySRNCycleFinder, whose negative cycles were affected in the same way.

  • MDE requires a dynamically controllable input and does not verify it – its own javadoc says so – and a network that is not controllable made it produce a contingent link with a negative minimum duration, silently. Two things now prevent that. Step M4 checks, for every contingent link it re-expresses between the representatives of the collapsed rigid components, that the offset of the contingent time point is zero and that of the activation time point is non-negative; those two facts are what makes the translated link legal, and they hold because a contingent time point is always the earliest member of its own rigid component – a time point rigidly tied to it and occurring earlier would have to be scheduled by the agent before the contingent duration is observed, which no dynamically controllable strategy can do. The check is not conditioned on Debug.ON: a release build is exactly where a silently illegal network must become a loud failure. And the public entry point now refuses MDE unless the controllability of the network has been established: either the graph carries a stored CheckOutcome saying so – captured before the check clears it, since a check establishes a new verdict – or a check already completed on that same object. A network whose file declares it not controllable gets a message saying so, rather than the generic one. A freshly built check status reports isControllable() as true before any check has run, so the condition also requires that a check actually finished and named its algorithm.

  • In the editor, asking for the dispatchable form with MDE selected on a network with no verdict does not fail with an exception and does not manufacture the verdict behind the user's back by checking a hidden copy: it reports that a dynamic-controllability algorithm other than MDE must be selected, the check run, and the network saved – because the outcome is saved with it, and MDE then starts without re-verifying anything. A verdict the user did establish is honoured: it is transferred explicitly from the input network onto the working copy, since a copy is born without claims and this is the one place that re-derives that conclusion for itself.

  • The form the class produces is recorded with the verdict (see CheckOutcome): MINIMAL for MDE and for applyBetterMinDispESTNU, DISPATCHABLE for FD_STNU, FD_STNU_IMPROVED and Morris2014Dispatchable. CheckAlgorithm.FD_STNU_IMPROVED was assigned nowhere, so the improved variant reported itself as FD_STNU.

  • minDEremoveStandInEdges uses the identity check (see TemporalConstraintGraph.ownsEdge), since it mutates and removes the very object it is given.

• STNUAddSemiRigidCycles: the tool that completes an instance built with nested diamonds by adding the constraints that close a semi-rigid cycle on each diamond. It no longer connects the W nodes, because the generator now does it itself, and it therefore requires that work to be already done: an instance where some W is still a sink is refused, since a diamond whose W constrains nothing makes a useless benchmark instance. With the W-connection go the --addEdges4WU option, the random choice of the target nodes, the retry loop over those choices and the intermediate _connectedW output; the single remaining output carries the suffix _withSRCycles, placed before the index of the instance so that the index stays last: dc_500nodes_..._withOne4NestedDiamond_027.stnu becomes dc_500nodes_..._withOne4NestedDiamond_withSRCycles_027.stnu.
  • It now works on the 4-nested structure as well, and not by counting indexes: the chain of diamonds is discovered by walking the nesting edges A(i+1) -> V(i) downwards from the U node. That is necessary, because the diamond gadget is inserted into a random lane network, and the contingent nodes created before it shift the whole numbering – for the same option the chain was observed to start at 1, at 2 and at 3. The value of each added edge is computed instead of written down: a semi-rigid cycle needs an ordinary path from A to V whose length equals the magnitude of the wait the gadget generates, that is y - vc, where y is the upper bound of the contingent link and vc the value of V -> C, so the tool reads both from the graph and subtracts the edge the generator already provides – the nesting edge, or U -> V for the last diamond, which has no nesting edge of its own. With the generator's current constants this yields the same 5 and 4 that the previous version had hardcoded, and it stays tight if those constants ever change.
  • The added constraints are requirement edges. They used to be typed internal, which inside STNU denotes a stand-in edge: applyBetterMinDispESTNU re-typed them as derived, so an instance presented its own constraints as produced by the checker. The step that restores dynamic controllability now protects the edges the tightness depends on rather than their endpoint nodes, which frees the unrelated lane constraints incident to the activation time points, and a final check refuses to save an instance whose paths are no longer tight – the relaxation being the one thing that could break a tightness the protection was meant to preserve. Measured over 200 generated instances, 196 are completed. The four that are not have an interruption cycle whose only negative contributions are case values of contingent links and zero-valued lane constraints, so no requirement edge is left to relax; the tool reports them and moves on.
  • An instance it writes carries the name of its own file and the outcome of the check that accepted it (see STNURandomGenerator).
• STNUEdge: fixed the Javadoc of GET_MIN_VALUE_BETWEEN_ORDINARY_AND_WAIT; added GET_MIN_VALUE_BETWEEN_ORDINARY_AND_WAIT_UPPER, which returns the minimum among the ordinary value, the wait value, and the upper-case value.
• STNURandomGenerator:
  • The W node of a diamond gadget was a sink, so the gadget constrained nothing outside itself and the instances of the 2025 benchmark were sound only because a separate tool connected W afterwards. The generator now adds three requirement edges from W itself and restores dynamic controllability around them, inside buildAPairRndTNInstances, so an instance obtained through the API carries the invariant too, and one that cannot is discarded rather than handed over. --withDiamonds could produce nothing at all: two int arguments were passed in the wrong order, where the compiler could not see it, and the per-slot bound for the ordinary nodes ignored the nodes each diamond adds.
  • An instance written by this generator and by STNUAddSemiRigidCycles now carries the name of its own file and the outcome of the check that accepted it. Neither was the case before, for a mechanical reason: both tools run the controllability check on a copy of the network – the instance has to remain the un-propagated one, without the derived edges the check adds – so the verdict was recorded on the copy and thrown away with it, while a fresh copy carries no claim of its own. The verdict is now written onto the graph that is actually saved, with the algorithm taken from the check status, at the three points where a network has just been accepted as controllable and is not mutated afterwards; no dispatchability outcome is recorded, since these instances are not in dispatchable form. makeDenseInstance is left alone: it runs no check of its own, so it has no verified fact to assert. The name was empty for a subtler reason: the generator created the graph without one and wrote an empty Name element, and the reader, finding the element present but empty, returns that empty string rather than falling back to the file name – so the emptiness survived every read-and-resave. Both tools now set the name of the file they are writing, extension included. The two additions are independent by construction, because NetworkFingerprint leaves the graph name out of its canonical form: setting the name cannot invalidate the verdict stored beside it.
  • The Benchmarks page of the website (src/site/tex/benchmarks.tex) declares STNUw4DiamondsBenchmark2025 and STNUw6DiamondsBenchmark2025 obsolete and no longer distributed, and drops the links to them. The reason is the W sink above: the node W of a diamond gadget receives the stand-in edge of every diamond of the structure and has no edge leaving it, so the structure takes constraints and propagates none, and does not constrain the rest of the network at all – verified on the published files, where not one of the 240 instances has an edge leaving a W. The tables and figures of that section are kept, because they document the evaluation published for TIME 2025, which was run on those instances. A new section describes the four archives that replace them – STNUw4DiamondsBenchmark2026 and STNUw6DiamondsBenchmark2026, plus the two WithSRCycles companions – with their generation parameters, what a semi-rigid cycle is and how many each instance carries, the fact that the two halves match one to one so that a measurement can be repeated on the same network with and without the cycles, and the two pieces of information every instance now carries about itself.
• TCGraphMLReader:
  • It honours the NetworkType declared in the file instead of inferring the kind from the edge classes and ignoring the declaration in silence; a file that contradicts itself — a CSTNU holding a parameter node — is rejected rather than read as something else, and six instances of the repository that declared a kind which was not theirs were corrected.
  • It reads the per-edge Route key (see EdgeRoute), the graph annotations (see GraphAnnotation) and the two stored outcomes, which it drops when the stored fingerprint does not match the network (see CheckOutcome).
• TCGraphMLWriter:
  • The project website gains a File format page, under Overview, that documents the GraphML dialect the tool reads and writes: the keys of the graph, of the nodes and of the edges, which of them exist for which kind of network, the format of each value, and complete examples. It also states how a contingent link is represented — the lower-case value on A → C and the upper-case one on C → A, in two edges — which is the most common source of malformed files. A test fails if a key emitted by TCGraphMLWriter is missing from that page, so the documentation cannot fall behind the format without the build noticing.
  • It emits the new per-edge Route key (see EdgeRoute), the graph annotations (see GraphAnnotation) and the two stored outcomes with the fingerprint of the network (see CheckOutcome).
• TikzExporter: the LaTeX escaping now covers every non-ASCII domain symbol that can reach an exported label — the empty label ⊡, the empty upper-case label ◇, the unknown-literal marker ¿, the contingency symbol ↕, the tuple delimiters ❮/❯, and the Greek Ω used as the horizon-node name in some instances — so an exported figure compiles under pdflatex (previously the raw ⊡/Ω in labels made the document fail with «Unicode character not set up»). Both the standalone document and the fragment's required-packages comment now load amssymb alongside tikz, which the emitted math symbols (\boxdot, \Diamond, \bowtie) need.
• TNEditor: replaced with a restructured implementation. All per-network-type knowledge (edge implementation, file extensions, help text) now lives in a single static registry; all check/init buttons go through one generic execution engine instead of ~20 duplicated listener classes; checking algorithms run in a background SwingWorker so the GUI stays responsive; the command row is rebuilt on demand for the current network type.
  • The editing and transforming mouse modes of the old editor are gone: there is a single interaction mode. The window shows the input network and the result of a computation side by side, each with its own view controls, a single status bar, and an attribute inspector.
  • The editor is what java -jar CSTNU-Tool-7.0.jar and the tnEditor.sh script start: both used to launch the old JUNG-based editor, which is no longer the one being maintained. The editor accepts no command-line options: -cleaned, -ctgAsOrdinary and -extraButtons are gone. Managing contingent links also as ordinary constraints remains available, as a setting of the window rather than a switch chosen before startup. On macOS the menu bar is drawn inside the window; -Dapple.laf.useScreenMenuBar=true asks for the system menu bar instead, at the price of a defect of the native menu, which keeps the entries of the File menu greyed out after a file dialog is dismissed with Cancel.
  • It can import Luke plain STNU files and export an STNU as plainStnu, without changing the document's associated GraphML file (see Luke2GraphML for the conversion). Long-running checks show their elapsed time and can be cancelled; the completed elapsed time remains visible until another network is opened or imported. The resulting graph permits deletion of selected nodes without changing the input network, and its automatic edge routing is already correct after the first MDE check.
  • A contingent link is entered by its ordinary bounds alone for CSTNU, OSTNU and PCSTNU. The extended form, which also accepts upper- and lower-case values differing from the ordinary bounds, is offered only for the network kind where such a difference is meaningful, CSTNPSU/FTNU. Contingent nodes of an OSTNU carry their oracle in the same inspector, validated against the propositions already in use. Drawing on a window where no network kind has been chosen is no longer possible: it used to produce a document that belonged to no kind and could not be saved, losing the work.
  • A {@link} in the editor's NetworkTypeRegistry, which named a class the file does not import and so resolved to nothing and left a diagnostic marker in the published documentation, is now fully qualified.
  • An element of the computed network is shown read-only, and an edit that changes only the drawing does not invalidate the result of a check (see EditorDocument).
• spotbugs-exclude.xml and pom.xml: the build configuration suppresses non-deterministic RCN_REDUNDANT_NULLCHECK_OF_NONNULL_VALUE and NP_NONNULL_RETURN_VIOLATION false positives on the @Nonnull getters/record accessors of STNU and its inner classes, and the same RCN/NP false positives on DenseTCGraph (whose reported set shifts with the bytecode layout). The javadoc configuration in pom.xml no longer declares implSpec and implNote as custom tags, since both have been standard javadoc tags since JDK 8 and no comment in the project used them.

Tests:

• CliPrototypeNPERegressionTest: one case per command-line main and per “String graphML” constructor, each loading an instance through the very code path its main uses, so the NullPointerException that killed those tools on start cannot come back unnoticed.
• CSTNFamilyCheckOutcomeTest: each class of the CSTN family records the kind of check it performs, with the algorithm that ran, for a positive and for a negative verdict; the verdict is written on the cleaned copy as well; initAndCheck clears an outcome set beforehand.
• DenseTCGraphTest and SparseTCGraphTest: backend-preserving construction, GraphML I/O and safe rename semantics (including A-label rewriting and cache invalidation); with the GraphAlgs and algorithm tests, equivalent algorithmic results on both backends and predecessor-graph reuse.
• DispatchabilityBenchmarkRunnerTest: smoke test that runs the runner on a small DC instance with all algorithms enabled and checks the structure of the produced CSV (header, per-instance data row field count, global-statistics section) and the option validation.
• EditorOutcomePropagationTest: drives the controller without a display and checks the editor's side — the verdict of a completed check reaches the input network and the document becomes worth saving, without the result being declared stale; the dispatchable form stays on the result alone; a structural edit clears the verdict and a layout edit does not; a command that installs a different network, such as the conversion of a CSTNU into a CSTN, leaves the input network without a verdict; and both files, the input one and the result one, keep what they were given when they are written and read again.
• FDPlusMinusEquivalenceSlowIT: holds the two 501-node instances that FDPlusMinusEquivalenceTest used to run. Each of the three bugs that test guards was reintroduced in turn to find out which instance actually catches it: the two small ones catch all three, the two large ones catch nothing more at a hundred times the cost. The default build no longer runs them, and the test class documents how to.
• FDPlusMinusEquivalenceTest: regression test guarding the collapseRigidComponents fixes. It runs applyFD_STNUPlusMinimization (FD phase-5 minimization followed by applyBetterMinDispESTNU) and applyFD_STNUPlusMinimizationMinus (the same minimization without the redundant phase-5 pass) on instances whose rigid components involve contingent time-points, and asserts that the two produce identical networks (edge set, ordinary/labeled values, and constraint type). Before the fixes the two diverged, because the extra phase-5 pass masked the rigid-component bugs.
• GraphMLOutcomeTest: the stored outcomes round-trip through GraphML, and are dropped when the fingerprint is missing, of a version this tool cannot compare, or no longer matching; a file written before the outcome keys existed loads normally.
• MDEBenchmarkRunnerTest: the same smoke test as DispatchabilityBenchmarkRunnerTest, for MDEBenchmarkRunner.
• MDEPhasesTest: characterization tests for the individual phases of the applyMDE() algorithm (M1, M2, M3, M4, M5) on the reference network time26-fig26a.stnu. For each phase the test renders the resulting graph in Luke's plain format (the graph g for M1/M2/M3/M5, the collapsed graph gPrime for M4) and checks it against the expected output stored in src/test/resources/time26-fig26a_M<phase>.expected.
• MDEStatsRunnerTest: runs applyMDE() phase by phase on 500_000.stnu (removing the Z node after initAndCheck, as the reference simulator has no horizon) and asserts the per-step ordinary/wait edge counts, guarding the dominated-wait fix (input 1447 ordinary/0 wait; final 2397 ordinary/7 wait). It lives in the it.univr.di.cstnu.algorithms test package to reach the package-private mde* phase methods without widening any visibility.
• NetworkFingerprintTest: the fingerprint is the same for a network held in the sparse and in the dense backend, although the two do not iterate in the same order, and the same whatever the registration order of the A-labels; moving a node, changing a route or an annotation leaves it alone, while changing a weight, a case label or a constraint type changes it; it survives a save and a read.
• OrderInsensitive: test helper that canonicalizes the toString() of collections whose element order is not semantically meaningful (predecessor edges, undominated edges, strongly connected components, observation nodes), so that order-fragile assertions compare content rather than the incidental iteration order.
• OSTNUTest (extended): two networks from the literature became tests. Figure 4 of “Agile Controllability in Simple Temporal Networks with Uncertainty and Oracles” is asserted both in its outcome and in the whole map of propositions assigned to the pairs, so a change altering which proposition goes with which pair cannot pass while the boolean outcome stays right. Figure 2 of the TIME 2024 paper on the same subject is asserted not agilely controllable: the paper declares it controllable, the implementation is right, and the arithmetic is recorded with the test so that nobody “fixes” the checker to agree with the paper.
• OutcomeSemanticsTest: the outcomes follow the copy rules — no outcome in a copy, on either backend, both outcomes in a content move through takeFrom and replaceContentsFrom — clearOutcomes clears both, and the two record-building entry points produce the expected records.
• STNCheckOutcomeTest: STN records the kind of check it performs, with the algorithm that ran, for a positive and for a negative verdict; initAndCheck clears an outcome set beforehand; makeMinimalDispatchable records the minimal form.
• STNTest.testVelocity: removed. A flaky performance micro-benchmark (it asserted a for-loop is faster than a stream, recursed on itself, and built 10001-node graphs, causing intermittent OutOfMemoryError); it verified no behavior of the project's code.
• STNUAddSemiRigidCyclesTest: drives the tool on instances generated for both diamond flavours – the depth is discovered as 4 and as 6, the expected number of edges is added with the values the previous version hardcoded, every path is still tight after the repair, and the result is dynamically controllable – and checks that an instance whose W was left unconnected, and a 3-nested instance, which has no U node at all, are both refused.
• STNUCheckOutcomeTest: MDE yields the minimal form and FD_STNU_IMPROVED the dispatchable one; applyBetterMinDispESTNU turns a dispatchable network into a minimal one without disturbing the verdict of the check that preceded it; initAndCheck clears an outcome set beforehand; MDE runs when a stored outcome or a previous check on the same object declares the network controllable, and refuses it otherwise.
• STNURandomGeneratorTest: every W of a generated diamond has an edge leaving it, for the single and for the 3-nested structure, and --withDiamonds produces instances again.
• TemporalConstraintGraphContractTest: the shared graph contract, backend-preserving construction and GraphML I/O. The observer index is verified on the mutation path as well — a proposition assigned after the node is inserted, changed, cleared, and a duplicate attempted by mutation — with every case run against both backends, so the two cannot drift apart again.

v6.6

Date: 2026-05-30

Added the following classes:

• CompactLogFormatter: compact formatter for java.util.logging records. It supports the usual SimpleFormatter arguments and adds arguments for printing source method and source class names without their packages.

Updated the following classes:

• Debug: the development default of Debug.ON is now true. Release package builds still compile with debug code disabled through the Maven build configuration and then restore the source value.
• GraphML2Luke: fixed the conversion of contingent links to Luke's plain STNU format. The converter now reconstructs activation node, contingent node, lower bound, and upper bound from both raw and initialized STNU encodings, writes only one line per contingent link, and exposes convert(File) and convert(File, File) utility methods.
• STNU: extended the CHECK_ACTIVATION_UNIQUENESS methods to reject networks containing contingent links in sequence: a contingent node cannot be the activation node of another contingent link. The same check also enforces that distinct contingent links cannot share the same activation node. The initAndCheck method now uses the inverse contingent-node map for these checks when available. A check was also added to reject lower-case edges having the zero node as contingent. SRNCycleFinderBackPropagation logging/status handling was cleaned, and the MDE stand-in edge generation now avoids producing a self stand-in edge. The class Javadoc was updated to document that forbidden contingent-link configurations must be separated by inserting one or more support nodes connected by zero-distance constraints.
• CSTNU, CSTNPSU, OSTNU, PSTN: updated the class Javadocs to document that well-defined networks must not contain contingent links in sequence and that distinct contingent links cannot share the same activation node.

v6.5

Date: 2026-01-26

• STNU: fixed a bug in the MinDispESTNU (MDE) algorithm: it now manages rigid components containing activation timepoints correctly. Method applyMinDispatchableESTNU was renamed to applyBetterMinDispESTNU.
• STNUEdge: added setWait() method and fixed updateWait().

v6.4

Date: 2025-12-29

• STNU: added MinDispESTNU (MDE) algorithm.

v6.3

Date: 2025-09-05

• STNU: renamed applyFastDispatchable_STNU to applyFD_STNU. Improved the method that collapses rigid components: it can now correctly collapse rigid components that also contain contingent links.
• OSTNU: fixed a bug in the determination of execution time. It was limited to cases where the network was not agile.

v6.2

Date: 2025-05-30

Updated the following classes:

• STNU: added the method minDEbetterGetStandInEdgesAssumingManyDiamonds, which can determine stand-in edges in instances containing nested diamond structures better than minDEgetStandInEdges. To use this optimization when finding the minimal dispatchable version of a network, call applyMinDispatchableESTNU(true).
• STNUEdge: added the GET_MIN_VALUE_BETWEEN_ORDINARY_AND_WAIT method.
• STNURandomGenerator: added an option to generate instances containing a 6-deep nested diamond.
• Constants: sumWithOverflowCheck no longer throws an exception if the sum is +/-∞; it returns the result as +/-∞.
• DispatchabilityBenchmarkRunner: improved the handling of non-well-formed instances. They are now ignored without stopping the process.

v6.1

Date: 2025-04-09

Updated the following classes:

• STN: cleaned up several methods. In particular, GET_SSSP_BellmanFord and GET_SSSP_Dijkstra now contain all variants of the corresponding algorithms. Renamed all static methods by capitalizing their names.
• STNU: added the static method GET_APSP_JohnsonO to determine the APSP graph, considering only the ordinary values of the network. Extended the method applyMinDispatchableESTNU: it is possible to request the fastMinDispatch algorithm published in L. Hunsberger and R. Posenato, “Faster Algorithm for Converting an STNU into Minimal Dispatchable Form,” in 31st International Symposium on Temporal Representation and Reasoning (TIME 2024), in LIPIcs, vol. 318. 2024, p. 11:1-11:14. DOI: 10.4230/LIPICS.TIME.2024.11. (Algorithm 2, newGenStandIns). This variant is faster only when the network contains at least 4-nested diamond structures.
• OSTNU: fixed a bug that did not handle some cases derived from the scenario where two contingent timepoints require both their oracles to be scheduled. The class cannot handle such a case. Now, the dynamic check returns false in such cases.
• ExtendedPriorityQueue.java: added a new constructor that allows the user to specify the initial size.
• STNEdge.java: added the functional interface EdgeValue.

New classes/interfaces:

• GraphAlgs.java: moved a lot of graph algorithms from STN.java to this file to rationalize the possible variants.
• GraphDistance.java: new representation of a graph distance based on a double hash map to speed up the retrieval of distances by specifying the node endpoints of a distance.

v6.0

Date: 2024-10-20

The update of the library fastutil to version 8.5.14 revealed a subtle weakness of all classes in the subpackage it.univr.di.labeledvalue and, as a consequence, in the subpackage it.univr.di.cstnu.graph. Therefore, it was necessary to adjust some methods in the classes of it.univr.di.labeledvalue and to reconsider the opportunity of some methods in the interface it.univr.di.graph.CSTNEdge and all its derived interfaces.

While the modifications in it.univr.di.labeledvalue are conservative, the ones made in it.univr.di.cstnu.graph are not. In particular, from this version, it.univr.di.graph.CSTNEdge and its derived interfaces do not allow direct access to maps containing the labeled values of an edge and offer only one method, getLabeledValues(), to have a directed view of all map entries. This method must be used only to scan all the entries in a fast, read-only mode. This is because the validity of the returned set is guaranteed if and only if the corresponding map is not modified during the scan. Moreover, if any of the entries of the returned set are modified directly, the validity of the set of labeled values is not guaranteed.

All possible maps (labeled values, upper-case labeled values, lower-case labeled values, etc.) must be modified using the methods for adding/merging/removing labeled values present in the it.univr.di.graph.CSTNEdge and its derived interfaces.

If one needs to scan all labeled values of an edge to remove/modify some of them quickly, a safe way is:

1. Retrieve the set of all the labels of the labeled values using the method getLabelsOfLabeledValues(),
2. Scan such a set of labels
   1. Retrieve each labeled value using the method getValue(Label label)
   2. Modify/remove the labeled value using one of the methods mergeLabeledValue(Label l, int i), putLabeledValue(Label l, int i), or removeLabeledValue(Label l)

The same approach is valid for upper-case/lower-case labeled values using the corresponding methods.

v5.0

Date: 2024-10-07

The dependency on the MATLAB library present in version 4.13 was too strong. So, I decided to split the project into two projects. This division affects only the use of the class PSTN.

• CSTNU Tool (this project). It is the core project and, limited to the class PSTN, it contains its definition and relative algorithms that cannot be used directly because the object instantiation requires an external actor class that implements the it.univr.di.cstnu.util.OptimizationEngine functional interface to be executed. The CSTNU Tool project does not contain any implementation of the OptimizationEngine because I haven't found a full-fledged open-source implementation of a nonlinear optimization problem solver.
• MatLabPlugin4CSTNUTool. It offers an implementation of the it.univr.di.cstnu.util.OptimizationEngine functional interface using the MATLAB software. This plugin, together with CSTNU Tool, allows users to create and use PSTN objects. Refer to the MatLabPlugin4CSTNUTool website to discover how to compile and use this plugin within this project.

Added the following classes:

• OptimizationEngine: a functional interface that represents a method for solving a nonlinear optimization problem. Class PSTN depends on this interface. A possible implementation of this interface is offered in the project MatLabPlugin4CSTNUTool.
• LogNormalDistribution: represents log-normal distribution parameters. It was a subclass of PSTN.

Added three test files: notDC002.stnu, notDC020.stnu, and notDC033.stnu.

Removed the following classes:

• MatLabEngine: moved to MatLabPlugin4CSTNUTool
• PSTNTest: moved to MatLabPlugin4CSTNUTool
• PSTNBenchmarkRunner: moved to MatLabPlugin4CSTNUTool

Updated the following classes:

• STNUEdge, STNUEdgeInt: Method updateValue(int) cannot stay in interface STNUEdge, otherwise in class STNUEdgeInt the method is overridden by the method updateValue(int) of the superclass STNEdgeInt. Therefore, updateValue(int) was moved into STNUEdgeInt.
• STNURTE: parameters --env and --rted now accept values of StrategyEnum.
• LabeledNode, TNGraphMLReader, PSTN: the dependency on the class PSTN.LogNormalDistribution is now updated to class LogNormalDistribution.
• PSTN: the class's constructors require an object of type OptimizationEngine.

v4.13

Date: 2024-07-09

Added the following classes:

• PSTN: Probabilistic Simple Temporal Network. A specialized version of STNU where each contingent link duration can be described by a log-normal probability distribution Since the networks are represented as distance graphs, the edges associated with a contingent link of a PSTN are still represented as upper-case and lower-case edges. This representation is also useful because the DC checking/execution of a PSTN is done considering its correlated STNU. Hence, the log-normal distribution parameters are stored in the contingent node as a field PSTN.LogNormalDistributionParameter logNormalDistributionParameter. Determining an approximating (correlated) STNU of a PSTN requires solving a nonlinear optimization problem. In this release, such a problem is solved using MATLAB's fmincon function. Therefore, if it is required to use the PSTN class, executing the library offering access to a MATLAB-licensed engine is necessary. The core MATLAB engine must be extended with the modules “Optimization Toolbox” and “Statistics and Machine Learning Toolbox” (thanks to Kim van den Houten and Léon Planken for clarification). For macOS systems, where MATLAB is usually installed in /Applications/MATLAB_R2024a.app/, it is enough to add -Djava.library.path=/Applications/MATLAB_R2024a.app/bin/maca64 to the java command.

Updated the following classes:

• LabeledNode: added a field to represent log-normal parameters for contingent duration in contingent links of a PSTN. This field is significant and considered only on the contingent nodes of a PSTN. See the description of PSTN.
• ALabel: added method getALetter()
• ExtendedPriorityQueue: added method getFirstPriority()
• STN: made serializable.
• STNU: added the method applySRNCycleFinder() that can be called with CheckAlgorithm.SRNCycleFinder during the DC checking phase. This method returns detailed information about the possible semi-negative cycle found during a check. This information is inside the object STNUCheckStatus returned by dynamicControllabilityCheck(CheckAlgorithm, SRNCycleFinder).
• STNURTE: added the possibility to specify an execution strategy as a parameter. Some standard execution strategies are given in the enum STNURTE.StrategyEnum. Thanks to Kim van den Houten and Léon Planken for the first implementation of this idea.
• TNGraph, TNGraphReader, and TNGraphWriter expanded to manage PSTN.

v4.12

Date: 2024-03-08

Added the following classes:

• OSTNU: class representing Simple Temporal Networks with Uncertainty and Oracles.

Updated the following classes:

• STNURTE: fixed minor bugs when executing networks that had useless wait constraints involving contingent timepoints.
• STNU: simplified some checks in applyMinDispatchableESTNU() methods. Added the original FD_STNU algorithm implementation. Therefore, there are now two implementations of FD_STNU: FD_STNU (the original) and FD_STNU_IMPROVED (as the original, but it does not add waits that are more negative than the duration of the relative contingent link).

v4.11

Date: 2024-02-14

Added the following classes:

• STNURTE: class for implementing a Real-Time Execution algorithm for STNUs.
• TimeInterval: utility class represents a time interval where the lower bound is guaranteed to be ≤ upper bound.
• ActiveWaits: utility class to represent an active wait.

Updated the following classes:

• Class STNU: implemented the MinDispatchableESTNU algorithm. Changed the name of some methods. Fixed minor bugs.
• Class STN: fixed a bug in GET_STRONG_CONNECTED_COMPONENTS and GET_STRONG_CONNECTED_COMPONENTS_HELPER methods. Changed the name of some methods.
• Class TNGraphMLReader.java: reads the name of the graph from the attributed Name in the document.
• Class TNGraph: addEdge throws an exception if the edge already exists. Returning a false value was not sufficient to avoid some errors. Added the methods makeNewEdge and getUniqueEdgeName.
• Class ExtendedPriorityQueue.java: renamed from MinPriorityQueue. Renamed some of its methods to represent a generic priority queue (min or max). Now, it depends on a better heap library.

v4.10

Date: 2023-11-02

Switched to Java 21. To Apple macOS users: it seems that OpenJDK 17 has some problems running the TNEditor because of missing system libraries. I recommend using Temurin 21 (https://adoptium.net/): I tested it, and it works without problems.

• Class STN: method makeFastDispatchMinimization adds constraints from the source node to guarantee that the source node can reach any node.
• Class TNEditor: for STN instances, the dispatchable version is determined using the makeFastDispatchMinimization method.

v4.9

Date: 2023-07-20

• Class AbstractCSTN: the reset() method does not remove the internal graph.
• Class PriorityQueue: added methods delete() and getElements().
• Class TNEditor: added Capture function for saving networks shown in the application as PNG images.
• Class FTNU: added a constructor that accepts an XML string describing the network.
• Class CSTNPSU: method getEMaxDistanceInContingencyGraph(contingencyGraph) replaced by getMaxPathContingencySpanInContingencyGraph(nodeName, contingencyGraph). Added the method configureSubNetworks(subNetworks, n).
• Fixed several minor bugs.
• Code cleaned in most of the classes.

v4.8

Date: 2022-12-28

• Class CSTNPSU: added method getPrototypalLink() for determining Prototypal Link with contingency (PLC).
• Class FTNU (Flexible Temporal Network with Uncertainty): it is an alternative name for the class CSTNPSU.
• Cleaned the code of many classes.

v4.7

Date: 2022-11-01

Added the new class PCSTNU (Parameterized CSTNU) to represent CSTNU with parameter timepoints.

• Interface Node: added methods for checking if a node is a parameter one.
• Class AbstractNode: default methods were removed because they were moved into the Node interface.
• Class LabeledNode: added a new field to identify parameter timepoints.
• Class TNGraph: added code for managing PCSTNU instances and improved some logging code.

Fixed some minor issues:

• Class AbstractCSTN: improved the determination of the max-edge value.
• Class CSTNPSU: improved the determination of all constraints when the parameter propagationOnlyToZ is false.
• Class STN: A useless annotation was removed.

v4.6

Date: 2022-06-03

The project has been updated to run with Java 17. Moreover, from this release, the source code is tested by spotbugs configured with maximum effort and minimal threshold parameters.

• Class STNUDensifier: improved, allowing the requirement of an exact number of edges (which can require removing edges).
• Class STNU: Changed the name of the fast dispatch algorithm.
• Class Checker: Made the long parameter specifications prefixed by --.
• Class STNURandomGenerator: improved the documentation of the README.txt generated to describe a benchmark.

v4.5

Date: 2022-03-30

• Class Checker: Two statistical indices are added when STNU is checked.
• Class PriorityQueue: An open hash now realizes the map of entries for better performance. Removed throws of exceptions when it is not necessary.
• Class STN: Generalized all methods to accept edges that extend STNEdge. In this way, the STNU class can also use some static methods. Fixed a bug in the getStrongComponents method.
• Class STNU: added fastSTNUdispatchability method. Changed the name of the method RUL2020 to RUL2021. Fixed some bugs with other methods and improved the efficiency of some methods.
• Classes Component and AbstractComponent: removed the color attribute because it is necessary to have lightweight components. All complementary attributes will be removed.
• Interface STNUEdge: improved the representation of contingent/wait edges, representing such data as an object of the internal class ContingentCasePair.
• Class STNEdgeInt: improved default constructor.
• Class STNUEdgeInt: improved default constructor.
• Improved the representation of contingent/wait edges, representing such data as an object of the internal class ContingentCasePair.
• Class TNGraph: changed internal maps representation and added two caches to speed up the getInEdgesAndNodes and getOutEdgesAndNodes methods. The removing observer instruction in the removeEdge method is removed for performance reasons. Now, when an edge is removed from a graph, all its observing graphs are removed. This is not the correct behavior, but removing only the correct graph requires too much time for the library method. This issue will be fixed in a future release. The copy constructor of a graph clones the internal labelAlphabet so that labelAlphabet is not shared by different graphs.
• Class CSTNPSU: fixed a bug in the initAndCheck method that did not allow the specification of a guarded link with a label in the external bounds.
• Class TNEditor: added visualization of cursor position coordinates.
• Class CSTNULabelEditingGraphMousePlugin: fixed the bug that made a contingent edge ordinary after an edit of its value.
• Class CSTNU: added a check to guarantee that an activation node is associated with only one contingent node.
• New class TNPredecessorGraph: class for representing predecessor TNGraph very compactly.

v4.4

Date: 2022-01-03

• Improved the parser of labeled value map/set.
• Class AbstractCSTN: improved checkAndInit: all negative edges going to an observation timepoint are checked and cleaned.
• Class STN: improved all SSSP algorithms, making each node reachable by Z in the case of forward search. Fixed a bug in the makeDispatchable() method: it did not remove all dominated edges if their opposites were absent. Added methods getAccumumulateUndominateEdges and getFastDispatchMinimization, a faster method for determining the dispatchable version of a network.
• Class PriorityQueue: removed the ambiguous method value.
• Class TNGraph: introduced the unmodifiable(TNGraph) static method.
• Class ALabelAlphabet: added a new constructor.
• Class LabeledNode: started its refactoring. The next releases will specialize this class to optimize its memory footprint.

v4.3

Date: 2021-10-20

• Class LabeledNode: extended for the Tarjan algorithm.
• Class STN: added BFCT (a.k.a. Tarjan algorithm) algorithm in STN class. This algorithm can return a negative cycle if the network is inconsistent.
• Class NodePriorityHeap: renamed as PriorityQueue and made generic.
• Class LabeledNode: removed rendering code.
• Class NodeRendering: new class to customize the rendering of LabeledNode in TNEditor.
• Class TNEditor: cleaned the GUI a little bit.
• Removed the dependency on the FreeHep library because FreeHep does not work with JRE > 8.
• Removed ‘normal’ and ‘constraint’ types for Edge in favor of requirement because in Temporal Networks, requirement is more appropriate.
• Improved all documentation (now, there is only one README.md). Added the BUILDING.md document, which explains how to build a package and
• The preliminary steps to take before a commit (only for developers).

v4.2

Date: 2021-10-07

• Fixed the main method of the STN class: now it checks a given network.
• Fixed an initialization error of the graphic driver in TNEditor and improved the Save dialog.

v4.1

Date: 2021-08-17

• Program CSTNEditor is renamed as TNEditor.
• Removed all unnecessary exceptions.

v4.0

Date: 2021-08-01

• Relevant change: the library is now a JVM 11 library but is still compatible with JVM 8.
• Improved Javadoc for almost all classes/methods.
• Fixed all spotbugs bugs/errors at medium level and max effort.

v3.6

Date: 2021-06-20

• Fixed a bug in the CSTNPotential class: the dynamicCheck() method worked correctly, but, in the end, the edges in the checked graph were wrongly saved in reverse.
• Refactored classes GraphMLReader and GraphMLWriter to make them more general. Now, GraphMLReader can build a TNGraph from a string representing it in GraphML format, and GraphMLWriter can serialize a TNGraph in GraphML format.
• Class CSTNU: added the constructor CSTNU(String) for building an instance from a GraphML string.
• Class AbstractCSTN: added the method String getGCheckedAsGraphML().

v3.5

Date: 2021-06-14

• Fixed a small bug in the Dijkstra method in the STN class.
• Class NodePriorityHeap refactored.

v3.4

Date: 2021-06-03

• CSTNU Check also propagates the bounds of a contingent link as normal constraints to avoid a contingent link having an upper-case value different from the negated upper bound.
• Fixed a graphical interface initialization error.

v3.3

Date: 2021-05-23

• CSTN(U)CheckStatus also stores the node that has a negative loop when the network is NOT DC.
• All DC checking methods save the resulting graph into a file before returning the check status.
• Improved some Javadoc comments.

v3.2

Date: 2021-01-14

• Fixed a coding error when saving a network to a file. From this release, the file encoding is UTF-8, independent of the execution platform.
• Fixed an initialization error in the CSTNU class.
• Fixed almost all Javadoc errors.

v3.1

Date: 2020-12-28

• Some cleanup actions.
• Added copyright and licenses for publication on archive.softwareheritage.org.

v3.0

Date: 2020-11-15

• STNU class added with different DC checking algorithms: Morris2016, RUL2018, and RUL2020 faster one.
• CSTNPSU class offers a DC check sound-and-complete that can also adjust guarded links to the right ranges for an execution.
• Fixed some minor bugs.

v2.11

Date: 2020-02-02

• Graphical interface simplified.
• Now, it is more intuitive to add/remove nodes/edges.
• CSTNPSU class offers a sound-and-complete DC check.

v2.10

Date: 2020-02-02

• CSTN class restored to previous algorithms.
• Removed the possibility of checking without using unknown literals.
• This version considers the new rule and algorithm names published in a work presented at ICAPS 2020.
• CSTN class implements two DC checking algorithms. With option --limitedToZ, the algorithm is the one presented at IJCAI18 (algorithm HR_18). Without --limitedToZ, the algorithm is the one presented at ICAPS19 (algorithm HR_19). This last version is not as efficient as IJCAI18.
• For a very efficient version, consider the CSTNPotential class (reintroduced but in a new form) that makes DC checking assuming IR semantics and nodes without labels (algorithm HR_20).
• CSTNPotential class implements the new DC checking algorithm based on single-sink shortest paths and potential R0 and potential R3 rules.
• For all objects containing a labeled values field, the default implementation class is LabeledIntTreeMap. To change to this default class, I modified the field DEFAULT_LABELEDINTMAP_CLASS of LabeledIntMapSupplier and recompiled the sources.
• CSTNPSU class allows the representation and the verification of temporal constraints containing guarded links. The DC checking algorithm is sound but not complete. Moreover, the guarded link bounds are not guaranteed to be shrunk correctly.

v2.00

Date: 2019-11-07

• CSTN class implements a 3-rule DC algorithm. This algorithm consists of three rules (LP, R0, and R3*) for generating the -∞ value and six rules for managing -∞ values stored as potential values in nodes.
• Added CSTNSPFA class that implements the DC checking algorithm as a single-sink Bellman-Ford one. Therefore, only node potential values are generated. This class uses only three rules.

v1.26.vassar

Date: 2019-10-21

• Rewrote many classes to represent edges and graphs for STN networks efficiently.
• Removed class CSTNPotential (last svn-version 296).
• Added class STN & companions for some STN-specific algorithms.

v1.26.0

Date: 2019-03-23

• CSTNU class has a new field, contingentAlsoAsOrdinary, default false. When true, the DC checking method also propagates contingent links as ordinary constraints. This allows users to see some ordinary values more accurately.

v1.25.0

Date: 2018-11-22

• Minor code optimization and minor bug fixes.
• From this release, the software must be run using JRE 1.8.

v1.24.0

Date: 2018-07-18

• CSTN class allows the DC checking without using the unknown literals (necessary for completeness): it is just a tool for studying the necessity of unknown literals.
• Literal and Label classes are now immutable.
• Minor code optimization.

v1.23.2

Date: 2018-02-21

• Class CSTNU cleaned and optimized. From this release, the DC checking algorithm is sound and complete.
• A contingent link can have a label even if it is not required for sound and completeness.
• Class CSTNPSU.java added.
• Subpackage ‘attic’ removed. (last svn revision 243).
• SVN version: 245.

v1.22.4

Date: 2018-01-10

• Code cleaning

v1.22.3

Date: 2017-12-14

• Class CSTNU optimized.
• Class CSTNURunningTime removed.
• Class CSTNRunningTime was renamed Checker.

v1.22.2

Date: 2017-11-24

• Code optimization

v1.22.1

Date: 2017-11-22

• The following classes have been renamed, reordering inside terms:

1. CSTNEpsilon.java
2. CSTNEpsilon3R.java
3. CSTNEpsilon3RwoNodeLabels.java
4. CSTNEpsilonwoNodeLabels.java
5. CSTNIR.java
6. CSTNIR3R.java
7. CSTNIR3RwoNodeLabels.java
8. CSTNIRwoNodeLabels.java

v1.22.0

Date: 2017-11-21

• Introduced new classes and renamed old ones. There are 13 classes for checking CSTN/CSTNU:

1. it.univr.di.algorithms.CSTN.java
2. it.univr.di.algorithms.CSTN2CSTN0.java
3. it.univr.di.algorithms.CSTN3RIR.java: as IR CSTN, but DC checking uses only three rules.
4. it.univr.di.algorithms.CSTN3RwoNodeLabelEpsilon.java
5. it.univr.di.algorithms.CSTN3RwoNodeLabelIR.java
6. it.univr.di.algorithms.CSTNEpsilon.java
7. it.univr.di.algorithms.CSTNIR.java
8. it.univr.di.algorithms.CSTNU.java
9. it.univr.di.algorithms.CSTNU2CSTN.java
10. it.univr.di.algorithms.CSTNU2UppaalTiga.java
11. it.univr.di.algorithms.CSTNwoNodeLabel.java
12. it.univr.di.algorithms.CSTNwoNodeLabelEpsilon.java
13. it.univr.di.algorithms.CSTNwoNodeLabelIR.java

• Replaced Ω node with equivalent constraints in all CSTN classes.
• Removed Ω node from LabeledIntGraph and the relative reader/writer.
• Improved CSTN Layout for laying out nodes without explicit temporal relation with Z.
• Started classes re-factoring and exploiting Java 8's new features.
• CSTNRunningTime and CSTNURunningTime are made multithreaded.

v1.21.0

Date: 2017-11-09

• Class CSTNUGraphMLReader can read CSTN files that do not contain meta-information about UC and LC values.
• CSTNirRestricted renamed CSTNir3R.
• CSTNwoNodeLabel cleaned.
• Added classes CSTNirwoNodeLabel and CSTNir3RwoNodeLabel.
• Simplified CSTNRunningTime.

v1.20.0

Date: 2017-11-03

• The Jung library has been upgraded to version 2.1.1.
• This update required an adaptation of all GUI classes.
• CSTNU DC checking algorithm is now sound and complete.
• CSTNEditor now allows you to view a graph in a bigger window and save it as a PDF or other graphical format. The export menu is accessible by clicking the mouse inside the window containing the graph to export.
• There are now six classes for checking CSTN/CSTNU:

1. it.univr.di.algorithms.CSTN: it checks a CSTN instance assuming the standard semantics.
2. it.univr.di.algorithms.CSTNepsilon: it checks a CSTN instance assuming a not-zero reaction time (epsilon).
3. it.univr.di.algorithms.CSTNir: it checks a CSTN instance assuming instantaneous reactions.
4. it.univr.di.algorithms.CSTNirRestricted: as it.univr.di.algorithms.CSTNir, but the used rules are three instead of 6. This checking can be faster than it.univr.di.algorithms.CSTNir.
5. it.univr.di.algorithms.CSTNU: it checks a CSTNU instance assuming instantaneous reactions.
6. it.univr.di.algorithms.CSTNwoNodeLabel: it checks a CSTN instance assuming the standard semantics. The instance is translated into an equivalent CSTN instance without node labels and then checked.

• GraphMLReader has been rewritten because it is based on Jung GraphMLReader2, which cannot manage big attribute data.
• GraphMLReader has been renamed CSTNUGraphMLReader.
• GraphMLWriter has been renamed CSTNUGraphMLWriter.

v1.10.0

Date: 2017-06-22

• Package reorganization.
• CSTNEditor cleaned and optimized.

v1.9.0

Date: 2016-03-31

• Labels are represented more compactly.
• Labeled value sets require less memory. Choosing which representation to use for labeled value sets is still possible.

v1.8.0

Date: 2016-02-24

• A new optimized class represents graphs.

v1.7.9

Date: 2015-11-26

• Added the new feature to CSTN DC-checking. Now, the DC-checking algorithm considers a user-specified ‘reaction time’ ε (ε > 0) of the system during the checking of a network. A reaction time ε means that an engine that executes a CSTN reacts in at least ε time units to a setting of a true value to a proposition.

v1.7.8

Date: 2015-10-28

• A new sanity check about the correctness of an input CSTNU was added. Each contingent time point has to have one incoming edge of the type ‘contingent’ and one outgoing edge of the type ‘contingent’ from/to the same node, representing the activation time point.

v1.7.7

Date: 2015-10-22

• Fixed another issue with instantaneous reaction in CSTNU. Thanks to Dian Liu for his help in discovering this error.
• I repeat that, even in this release, it is better to set any timepoint—that depends on an observation timepoint or follows a contingent timepoint—to a non-zero distance from the considered observation timepoint or the contingent one.

v1.7.6

Date: 2015-09-30

• Fixed a subtle bug in the generation of new edges. Thanks to Dian Liu for his help in discovering this error.

v1.7.5

Date: 2015-09-23

• Cleaned some log messages.
• We have discovered that the instantaneous reaction feature requires a sharp adjustment in the network semantics.
• We are currently working on introducing an ε-reaction (with ε ≥ 0) feature.
• In the meantime, for CSTN, it is possible to DC check assuming instantaneous reaction (ε = 0), while for CSTNU, it is only possible to check DC assuming non-instantaneous reaction (ε > 0).
• For now, it is better to set any timepoint—that depends on an observation timepoint or follows a contingent timepoint—to a non-zero distance from the considered observation timepoint or contingent one.

v1.7.4

Date: 2015-09-13

• In this release, a stricter check of contingent links has been introduced. Bounds of a contingent link A==[x, y]⇒B must observe the property 0<x<y<∞. Moreover, since for CSTNU instances, the concept of ‘instantaneous reactions’ has not yet been defined, it is not possible to define a CSTNU instance in which there exists a constraint like C–[0,0]→B, where B is contingent. This constraint requires that C be executed simultaneously with the contingent time point B. However, this is impossible because the environment decides B, and the runtime engine must observe it before executing a standard node like C.

v1.7.3

Date: 2015-09-10

• This release contains some minor bug fixes and a revision of the public methods of class it.univr.di.cstnu.algorithms.CSTNU.
• Now, it is possible to check the controllability of a CSTN instance by instantiating a CSTNU object and calling its dynamicControllabilityCheck(LabeledIntGraph) method.
• To check the controllability of a CSTNU instance, create a LabeledIntGraph object representing the instance (the LabeledIntGraph class also has a method for loading an instance from a file written in GraphML format), instantiate a CSTNU object, and call its method dynamicControllabilityCheck(LabeledIntGraph), passing the created graph. Moreover, added the class it.univr.di.cstnu.algorithms.CSTNURunningTime and the script CSTNURunningTime for checking a bundle of CSTNU instances and getting some execution time statistics.

v1.7.2

Date: 2015-06-24

• This release contains minor bug fixes and a README file explaining the proposed examples of CSTNU/CSTN instances.
• Thanks to Huan Wang for his comments.

v1.7.1

Date: 2015-05-28

• This release contains a faster Dynamic Consistency check for CSTNs.
• The Java class CSTN.java has been completely rewritten and almost optimized for a faster check.

v1.7.0

Date: 2015-03-23

• This release is the first public release.