author Manu Sporny Mon, 08 Aug 2011 15:43:47 -0400 changeset 140 4298ae98c45e parent 139 e8d66eb3a298 child 141 18819e8ce8f5
Rewrote Shallow Comparison and Object Comparison algorithms.
 spec/latest/index.html
```--- a/spec/latest/index.html	Sun Aug 07 23:38:45 2011 -0700
+++ b/spec/latest/index.html	Mon Aug 08 15:43:47 2011 -0400
@@ -2159,6 +2159,21 @@
names that already exist as well as the names that will be generated by the
normalization algorithm.
</dd>
+   <dt><tdef>alpha</tdef> and <tdef>beta</tdef> values</dt>
+   <dd>
+     The words <tref>alpha</tref> and <tref>beta</tref> refer to the first and
+     second nodes or values being examined in an algorithm. The names are
+     merely used to refer to each input value to a comparison algorithm.
+   </dd>
+   <dt><tdef>naming base string</tdef></dt>
+   <dd>
+     An unlabeled node naming prefix that is not used by any other node
+     in the <tref>JSON-LD input</tref> and does not start with the characters
+     <code>c14n</code>. The prefix is used to temporarily name nodes during
+     the normalization algorithm in a way that doesn't collide with the
+     names that already exist as well as the names that will be generated by the
+     normalization algorithm.
+   </dd>
</dl>
</section>

@@ -2205,18 +2220,30 @@
<section>
<h4>Node Labeling Algorithm</h4>

-<p>The node labeling algorithm sorts all of the unlabeled nodes in the graph
-and deterministically names them in descending order.</p>
+<p>The node labeling algorithm takes the <tref>list of expanded nodes</tref>
+and sorts the list, deterministically naming all of the unlabeled nodes
+in the graph.</p>

<ol class="algorithm">
-  <li>???Create a <tdef>property to unlabeled node mapping</tdef> that relates
-    property IRIs to unlabeled node identifiers. Create a key for every
-    property that is associated with a value that has an unlabeled node
-    identifier.</li>
-  <li>???Create a <tdef>unlabeled node references mapping</tdef> that relates
-    unlabeled nodes to the subjects that refer to them. Create a key for every
-    unlabeled node with mappings to each node that references the unlabeled
-    node.???</li>
+  <li>Create a <tdef>forward mapping</tdef> that relates graph
+    nodes to the IRIs of the targets nodes that
+    they reference. For example, if a node <tref>alpha</tref> refers to a
+    node <tref>beta</tref> via a property, the key in the
+    <tref>forward mapping</tref> is the subject IRI of <tref>alpha</tref> and
+    the value is an array containing at least the subject IRI of
+    <tref>beta</tref>.
+    <ol class="algorithm">
+      <li>Add all forward mappings for every node in the graph.</li>
+    </ol></li>
+  <li>Create a <tdef>reverse mapping</tdef> that relates graph nodes
+    to every other node that refers to them in the graph.
+    For example, if a node <tref>alpha</tref> refers to a
+    node <tref>beta</tref> via a property, the key in the
+    <tref>reverse mapping</tref> is the subject IRI for <tref>beta</tref> and
+    the value is an array containing at least the IRI for <tref>alpha</tref>.
+    <ol class="algorithm">
+      <li>Add all reverse mappings for every node in the graph.</li>
+    </ol></li>
<li>Label every unlabeled node according to the
<a href="#label-generation-algorithm">Label Generation Algorithm</a>
in descending order using the
@@ -2230,24 +2257,92 @@

<p>
The shallow comparison algorithm takes two unlabeled nodes,
-<strong>alpha</strong> and <strong>beta</strong>, as input and
+<tref>alpha</tref> and <tref>beta</tref>, as input and
determines which one should come first in a sorted list. The following
algorithm determines the steps that are executed in order to determine the
node that should come first in a list:
</p>

<ol class="algorithm">
-  <li>The node with fewer properties is first.</li>
-  <li>The node with the lexicographically lesser property is first.</li>
-  <li>???Do CompareObjects for each equivalent property.???</li>
-  <li>The node with fewer entries in the
-    <tref>unlabeled node references mapping</tref> is first.</li>
-  <li>???The node with the reference IRI (vs. bnode) is first.???</li>
-  <li>???The node with the lexicographically lesser reference IRI
-    is first.???</li>
-  <li>???The node with the lexicographically lesser reference property
-    is first.???</li>
+  <li>Compare the total number of node properties. The node with fewer
+    properties is first.</li>
+  <li>Lexicographically sort the property IRIs for each node and compare
+    the sorted lists. If an IRI is found to be lexicographically smaller, the
+    node containing that IRI is first.</li>
+  <li>Compare the property values against one another:
+    <ol class="algorithm">
+      <li>Create an <tdef>alpha list</tdef> by adding all values associated
+        with the <tref>alpha</tref> property that is not an unlabeled node.
+        Track the number of unlabeled nodes not added to the list using an
+        <tdef>alpha unlabeled counter</tdef>.</li>
+      <li>Create a <tdef>beta list</tdef> by adding all values associated
+        with the <tref>beta</tref> property that is not an unlabeled node.
+        Track the number of unlabeled nodes not added to the list using an
+        <tdef>beta unlabeled counter</tdef>.
+      <li>Compare the length of <tref>alpha list</tref> and
+        <tref>beta list</tref>. The node associated with the list containing the
+        lesser number of items is first.</li>
+      <li>Compare the <tref>alpha unlabeled counter</tref> to the
+        <tref>beta unlabeled counter</tref>, the node associated with the lesser
+        value is first.</li>
+      <li>Sort <tref>alpha list</tref> and <tref>beta list</tref> using the
+        <a href="#object-comparison-algorithm">Object Comparison Algorithm</a>
+        as the sorting comparator.
+        For each offset into the <tref>alpha list</tref>, compare the item
+        at the offset against the item at the same offset in the
+        <tref>beta list</tref> using the
+        <a href="#object-comparison-algorithm">Object Comparison Algorithm</a>.
+        The node associated with the lesser item is first.
+    </ol></li>
+  <li>Process the <tref>reverse mapping</tref> to determine order:
+    <ol class="algorithm">
+      <li>The node with fewer entries in the <tref>reverse mapping</tref>
+      is first.</li>
+      <li>Sort the <tref>reverse mapping</tref> entry for <tref>alpha</tref>
+        into a <tdef>list of sorted alpha mappings</tdef>. Sort the
+        <tref>reverse mapping</tref> entry for <tref>beta</tref>
+        into a <tdef>list of sorted beta mappings</tdef>.
+      <li>The node associated with the list of sorted mappings
+        with the least number of unlabeled nodes is first.</li>
+      <li>For each offset into the <tref>list of sorted alpha mappings</tref>,
+        compare the IRI at the offset against the IRI at the same offset in the
+        <tref>list of sorted beta mappings</tref>.
+        The node associated with the lexicographically lesser IRI is first.</li>
+    </ol></li>
+  <li>Otherwise, the nodes are equal.</li>
+</section>
+
+<section>
+<h4>Object Comparison Algorithm</h4>
+
+<p>
+The object comparison algorithm is designed to compare two graph node
+property values, <tref>alpha</tref> and <tref>beta</tref>, against the other.
+The algorithm is useful when sorting two lists of graph node properties.
+</p>
+
+<ol class="algorithm">
+  <li>If one of the values is a string and the other is not, the value that is
+    a string is first.</li>
+  <li>If both values are strings, the lexicographically lesser string is
+    first.</li>
+  <li>If one of the values is a literal and the other is not, the value that is
+    a literal is first.</li>
+  <li>If both values are literals
+    <ol class="algorithm">
+      <li>The lexicographically lesser string associated with
+        <code>@literal</code> is first.</li>
+      <li>The lexicographically lesser string associated with
+        <code>@datatype</code> is first.</li>
+      <li>The lexicographically lesser string associated with
+        <code>@language</code> is first.</li>
+    </ol></li>
+  <li>If both values are expanded IRIs, the
+    lexicographically lesser string associated with <code>@iri</code>
+    is first.</li>
+  <li>Otherwise, the two values are equivalent.</li>
</ol>
+
</section>

<section>```