Class NetworkFingerprint

java.lang.Object
it.univr.di.cstnu.graph.NetworkFingerprint
public final class NetworkFingerprint extends Object
Computes a compact, deterministic fingerprint of the semantic content of a TemporalConstraintGraph.

The fingerprint is sha256:v1: followed by the lowercase hexadecimal encoding of the SHA-256 digest of the canonical semantic form of the graph, defined in this class. The canonical form is a line-oriented UTF-8 text that depends only on the semantic content of the network, never on the GraphML file that produced it, on the order in which nodes and edges were inserted, nor on the concrete backend (SparseTCGraph or DenseTCGraph).

Canonical form. Records are separated by '\n', fields within a record by '\t': 

  type=<TemporalConstraintNetworkType>
  node<\t><name>[<\t><observed>][<\t><parameter>][<\t><label>][<\t><potential>][<\t><lognormal>]
  edge<\t><source><\t><destination><\t><name><\t><constraintType>[<\t><labeledValues>][<\t><value>][<\t><case>][<\t><upper>][<\t><lower>]
Node records appear in name order; edge records appear ordered by (source name, destination name). The name of an edge is not part of the form: the pair of endpoints identifies it, since the model admits no parallel edges, and renaming an edge does not change the network.

The optional fields are present only for the network kinds that TCGraphMLWriter writes and TCGraphMLReader reads back (writer/reader parity), and mirror exactly the accessors those classes use:

Fields per network kind
fieldkinds that persist it
observedOSTNU, CSTN, CSTNU, CSTNPSU, PCSTNU
parameterPCSTNU always; CSTNU, CSTNPSU when at least one node is a parameter node
labelCSTN, CSTNU, CSTNPSU, PCSTNU
potentialOSTNU, CSTN, CSTNU, CSTNPSU, PCSTNU (the empty-A-Label view)
lognormalPSTN (empty when the node has no distribution)
labeledValuesOSTNU, CSTN, CSTNU, CSTNPSU, PCSTNU
valueSTN, STNU, PSTN
caseSTNU, PSTN (empty when the edge has no case label)
upper, lowerOSTNU, CSTNU, CSTNPSU, PCSTNU
Field encodings:
  • observed is the observed-proposition character (Constants.UNKNOWN when the node observes nothing);
  • parameter is 1 or 0;
  • label is Label.toString();
  • potential is the (label:value) pairs, ';'-joined, ordered by (label, value);
  • lognormal is location;scale;shift (locale-independent);
  • value is the ordinary edge weight as an integer;
  • case is UC(name):value or LC(name):value;
  • upper and lower are the (aLabel:label:value) triples, ';'-joined, ordered by (aLabel, label, value);
  • aLabel is the canonical form of an A-Label: the names of its A-Letters, sorted lexicographically and ','-joined (the empty string for the empty A-Label). Names, not ALabel.toString(), are used because the latter is ordered by alphabet-registration position and would make the fingerprint depend on insertion order;
  • names and labels are escaped by replacing '\' with "\\", '\t' with "\t" and '\n' with "\n".

The canonical form deliberately omits presentation and derived data: coordinates, graph name, annotations (including stored check outcomes), edge routes, node isContingent flags (derived from edge weights), the Z designation (derived from the node name) and the A-Label-keyed node potentials (never persisted). As a consequence the fingerprint of a network is stable across a save/read round trip — with one documented exception: a graph that declares itself CSTNU but contains parameter nodes is written and reloaded as PCSTNU (see TCGraphMLReader), so its type field, hence its fingerprint, changes on reload.

Author:
posenato

  • Field Details

    • VERSION

      public static final String VERSION
      Version tag of the fingerprint format. When the canonical form or the hashing scheme changes, this tag must change too, so that fingerprints computed by an older release are no longer mistaken for current ones.
      See Also:

    • PREFIX

      public static final String PREFIX
      Every fingerprint starts with this prefix. isVersionComparable(String) recognizes it.
      See Also:

  • Method Details

    • of

      @Nonnull public static String of(@Nonnull TemporalConstraintGraph<? extends Edge> graph)
      Returns the fingerprint of the semantic content of graph.
      Parameters:
      graph - a temporal constraint graph
      Returns:
      PREFIX + lowercase hex SHA-256 of the canonical semantic form of graph

    • canonicalForm

      static String canonicalForm(@Nonnull TemporalConstraintGraph<? extends Edge> graph)
      Returns the canonical semantic form of graph, as defined in the class documentation.
      Parameters:
      graph - a temporal constraint graph
      Returns:
      the canonical form of graph

    • isVersionComparable

      public static boolean isVersionComparable(@Nullable String storedFingerprint)
      Tells whether storedFingerprint carries the current version prefix, i.e. whether it was produced by a release with the same canonical form and hashing scheme as this one. A fingerprint whose version differs is not a mismatch of the network content: it cannot be compared at all.
      Parameters:
      storedFingerprint - the fingerprint stored alongside a check outcome, possibly null
      Returns:
      true iff storedFingerprint starts with PREFIX

    • matches

      public static boolean matches(@Nullable String storedFingerprint, @Nonnull TemporalConstraintGraph<? extends Edge> graph)
      Returns true iff storedFingerprint is version-comparable and equals the fingerprint of the semantic content of graph. A stored fingerprint with a different version is reported as false here; use isVersionComparable(String) to tell "not comparable" apart from a genuine content mismatch.
      Parameters:
      storedFingerprint - the fingerprint stored alongside a check outcome, possibly null
      graph - the graph to compare against
      Returns:
      true iff storedFingerprint is comparable and equals of(TemporalConstraintGraph)