topologyR: Topological Connectivity Analysis for Numeric Data

Abstract

The package is now licensed under GPL (>= 3) DESCRIPTION declares License: GPL (>= 3), and LICENSE.md carries the full text of version 3 of the GNU General Public License, excluded from the built package. Every commit in the history of the repository is by the author, so the change of licence needs no other consent. The two-line file required by the previous MIT declaration is gone. Unequally spaced instants horizontal_visibility_graph(), natural_visibility_graph() and generate_bitopology() gain an argument times: NULL (the instants 1, ..., n, as before) or a numeric, Date or date-time vector of finite, strictly increasing instants. The natural criterion uses them as abscissae; the horizontal criterion depends only on their order, so for it they are validated and recorded but change nothing. The graph objects gain a field times with the instants used. The new function time_reverse() returns a series read backwards together with its instants reflected (-rev(times)), the operation under which the forward and backward topologies are exchanged (theorem T1). Reversing the values alone over the same instants is a different operation when the gaps between consecutive instants are not palindromic, and for the natural criterion it can change the graph: with the instants 0, 1, 4 and the values 0, 2, 4 it creates an edge that the original series does not have. The natural visibility criterion is decided exactly Each visibility decision of natural_visibility_graph() is the sign of y_a (t_b - t_k) + y_b (t_k - t_a) - y_k (t_b - t_a), and it is now computed exactly on the doubles received, under the hypotheses on the floating-point arithmetic stated in the new help page ?natural_visibility_exactness: the sign of a floating-point evaluation is accepted only when the result exceeds a threshold above which that sign is proved correct, and otherwise the quantity is evaluated in integer arithmetic on the mantissas and exponents of its six products (Shewchuk, 1997, for the adaptive scheme). Up to 0.3.0 the engine compared rounded slopes. On 2,800 test series the two engines return identical edge lists in 2,558 cases. The other 242, all among the 500 series of rounded decimals lying almost on a straight line, differ from the definition applied to the stored numbers: across them 0.3.0 misses 596 edges that the definition gives and adds 67 that it does not, and 194 of them only miss edges. The comparison is reproducible with the scripts in dev/compare_with_0.3.0, which also find no discrepancy with 0.4.0. For decimal data the documentation of natural_visibility_graph() explains when and how to obtain the graph of the recorded decimals instead. Consequences: theorem T1 holds exactly in the computation for every input, and the graph does not change under exact positive affine changes of the values or of the time scale, when the new values are finite doubles equal to the exact images. The exact evaluation runs when the threshold does not certify the sign, which happens near a tie (for instance on data with many collinear points), when an input exceeds 2^510 in magnitude, or when the computed sum of the magnitudes of the two products does not exceed 2^-930, about 1.1e-280. It costs more than the floating-point evaluation, so data that trigger it often take longer. The threshold is valid in every IEEE 754 rounding mode, with evaluation in binary64, in a format with at least 64 significand bits or in the x87 format at 53 bits. The floating-point stage is used only when the six inputs of a decision are at most 2^510 in magnitude, so that no intermediate value overflows (a directed rounding mode can turn an overflow into the largest finite double instead of an infinity, with a relative error no longer bounded by 2u), and each of its intermediate values is stored, so that every operation is rounded to double before the next one uses it and the compiler cannot fuse a product into the subtraction or reorder the operations. The build stops with an error when doubles are not binary64, when operations on doubles are evaluated in another format than binary64 or one with at least 64 significand bits (FLT_EVAL_METHOD), with -ffast-math or -ffinite-math-only, and, under GCC, with any option that makes the compiler set __GCC_IEC_559 to 0 (among them -funsafe-math-optimizations, -fassociative-math, -freciprocal-math and -fno-signed-zeros); Clang does not reveal its reassociation options, which the stored intermediates make harmless. horizontal_visibility_graph() and natural_visibility_graph() compute in the non-stop mode of IEEE 754, with every floating-point trap disabled and the caller's environment restored at exit, and stop with an error when the floating-point environment does not provide IEEE 754 double arithmetic: subnormal numbers flushed to zero or read as zero, or operations with fewer than 53 significant bits (as with the x87 precision control set to 24 bits), conditions that some libraries create. The proofs of both stages, their hypotheses on the arithmetic and what is checked of them are written in the new help page ?natural_visibility_exactness. Incomplete computations are flagged, and only what is exact is reported The flag complete of generate_topology(), generate_alexandrov_topology() and complete_topology() is renamed topology_complete, the name the accompanying article uses. It is NA when no enumeration was requested (it used to be FALSE, which also meant "truncated"), FALSE when the enumeration was truncated or the base was truncated, and TRUE only when the enumerated family is the whole topology. Up to 0.3.0 a truncated base could be enumerated to completion and flagged complete although the union closure of a truncated base is not the topology. verify_axioms now runs only when topology_complete is TRUE. The connected components are exact even when max_base_sets truncates the base, because the engine always keeps the whole subbase; the documentation said they could be approximate, and now gives the proof. bitopology_invariants() reports the two base sizes, and the gains with respect to the Alexandrov topology, as NA when the corresponding base was truncated, and adds the fields forward_base_complete and backward_base_complete. It stops with an error when a topology was computed with check_connected = FALSE (it used to count zero components) or when n_elements does not match the points of the components. bitopology_invariants() decides pairwise connectedness exactly, from the two subbases and without enumerating either topology: the space is pairwise connected if and only if the digraph with an arc x -> y when y lies in the smallest forward-open set of x or x in the smallest backward-open set of y is strongly connected, and a strongly connected component that no arc leaves is a witness. The answer is never NA. Up to 0.3.0 the check needed both topologies enumerated, answered NA otherwise, and ran only when both reported complete, a flag that a truncated base did not clear. Count arguments (n_elements, max_open_sets, max_base_sets) are validated before they are converted to integers: a fraction, a string, a logical value, a missing value or a vector is rejected with an error, instead of being truncated or coerced (max_open_sets = 2.7 used to mean 2). generate_topology() rejects a negative max_open_sets or a non-positive max_base_sets, and so does generate_alexandrov_topology() with a negative max_open_sets. With check_connected = FALSE, connected is a logical NA, as documented; it used to be an integer NA. verify_axioms = TRUE checks every axiom of a topology on a finite set: the empty set and the whole set are members and the family is closed under the union and the intersection of any two members. It used to check pairwise intersections only, although its result is called axioms_ok. Documentation corrected The pair of topologies does not "quantify temporal irreversibility", and a reversible process does not make them homeomorphic: theorem T1 has no converse. The manual pages now state T1 with its proof and say what it does and does not imply; irreversibility_components is no longer described as a necessary condition for reversibility, and asymmetry_direction is no longer tied to "gradual expansions and abrupt contractions". The paragraph attributing an irreversibility prediction to Lacasa and Toral (2010), whose article does not discuss irreversibility, is removed; Lacasa et al. (2012) is cited for the visibility-graph approach to irreversibility. The base of generate_alexandrov_topology() is the minimal base of the topology, which is not closed under intersection in general; the page said it was. The construction is a closed-neighbourhood variant of that of Nada, El Atik and Atef (2018), who use the open post classes of the adjacency relation; the documentation no longer attributes the closed neighbourhoods to them. Kelly (1963) is cited for bitopological spaces only, with its correct volume, and no longer next to "temporal irreversibility" in the package description or as the source of pairwise connectedness. The bitopological space of a directed visibility graph is pairwise disconnected for every series with at least two observations: every final segment of indices is open in the forward topology and every initial segment in the backward one. The documentation says so, and that the pairwise check therefore carries no information about a series. The base-size gains are counts of the construction, not measures of how much finer the Nada topology is; the two gains are always equal when defined, by the theorem that makes the two base sizes equal. The example of is_topology_connected_exact() labelled "A connected topology" was not a topology; both examples now are. Every exported function documents its parameters, return value, design decisions, methodological notes and dependencies, and every reference is checked against the list in dev/REFERENCIAS_APA7.md. The user manual is rewritten to match the p