# RELEASE NOTES ### v7.3 Date: not released yet; in development. SVN revisions: `r1193–TBD` (r1193 is the first revision of this cycle, the one that opened it by moving the version in `pom.xml` to 7.3; the final revision will be the release commit). The version in `pom.xml` moved to 7.3 as the first act of the cycle so that the artefacts of the work that follows — `CSTNU-Tool-7.3.jar` and `CstnuTool-7.3.tgz`, both named after `${project.version}` — cannot overwrite the 7.2 ones, which stay the published reference until the next release. `codemeta.json` still describes 7.2, the released version, and moves at release time. ### v7.2 Date: 2026-09-10 SVN revisions: `r1181–r1191` (r1181 opened the cycle by moving the version in `pom.xml` to 7.2, r1191 is 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:`. 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.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](https://profs.scienze.univr.it/~posenato/software/cstnu/) (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](https://profs.scienze.univr.it/~posenato/software/cstnu/matlabplugin). 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](https://profs.scienze.univr.it/~posenato/software/cstnu/matlabplugin) 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](https://profs.scienze.univr.it/~posenato/software/cstnu/matlabplugin). * `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](https://profs.scienze.univr.it/~posenato/software/cstnu/matlabplugin) * `PSTNTest`: moved to [MatLabPlugin4CSTNUTool](https://profs.scienze.univr.it/~posenato/software/cstnu/matlabplugin) * `PSTNBenchmarkRunner`: moved to [MatLabPlugin4CSTNUTool](https://profs.scienze.univr.it/~posenato/software/cstnu/matlabplugin) 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](https://en.wikipedia.org/wiki/Log-normal_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: ```bash 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