--- a/spec/latest/index.html Sun Aug 14 19:27:20 2011 -0400
+++ b/spec/latest/index.html Tue Aug 16 02:17:08 2011 -0400
@@ -2271,38 +2271,101 @@
<p>When performing the steps required by the normalization algorithm,
it is helpful to track the many pieces of information in a
-data structure called the <tdef>normalization state</tdef>. The information
+data structure called the <tdef>normalization state</tdef>. Many of these
+pieces simply provide indexes into the graph. The information
contained in the <tref>normalization state</tref> is described below.</p>
<dl>
+ <dt><tdef>node state</tdef></dt>
+ <dd>
+ Each node in the graph will be assigned a <tref>node state</tref>. This
+ state contains the information necessary to deterministically
+ <tref>label</tref> all nodes in the graph. A <tref>node state</tref>
+ includes:
+ <dl>
+ <dt><tdef>node reference</tdef></dt>
+ <dd>
+ A <tref>node reference</tref> is a reference to a node in the graph.
+ For a given <tref>node state</tref>, its <tref>node reference</tref>
+ refers to the node that the state is for. When a
+ <tref>node state</tref> is created, its <tref>node reference</tref>
+ should be to the node it is created for.
+ </dd>
+ <dt><tdef>outgoing list</tdef></dt>
+ <dd>
+ Lists the <tref>label</tref>s for all nodes that are properties of
+ the <tref>node reference</tref>. This list should be initialized
+ by iterating over every object associated with a property in the
+ <tref>node reference</tref> adding its label if it is another node.
+ </dd>
+ <dt><tdef>incoming list</tdef></dt>
+ <dd>
+ Lists the <tref>label</tref>s for all nodes in the graph for which
+ the <tref>node reference</tref> is a property. This list is
+ initialized to an empty list.
+ </dd>
+ <dt><tdef>outgoing serialization map</tdef></dt>
+ <dd>
+ Maps node <tref>label</tref>s to <tref>serialization label</tref>s.
+ This map is initialized to an empty map. When this map is populated,
+ it will be filled with keys that are the <tref>label</tref>s of every node in the
+ graph with a label that begins with <code>_:</code> and that has a
+ path, via properties, that starts with the
+ <tref>node reference</tref>.
+ </dd>
+ <dt><tdef>outgoing serialization</tdef></dt>
+ <dd>
+ A string that can be lexicographically compared to the
+ <tref>outgoing serialization</tref>s of other
+ <tref>node state</tref>s. It is a representation of the
+ <tref>outgoing serialization map</tref> and other related
+ information. This string is initialized to an empty string.
+ </dd>
+ <dt><tdef>incoming serialization map</tdef></dt>
+ <dd>
+ Maps node <tref>label</tref>s to <tref>serialization label</tref>s.
+ This map is initialized to an empty map. When this map is populated,
+ it will be filled with keys that are the <tref>label</tref>s of every
+ node in the graph with a <tref>label</tref> that begins with
+ <code>_:</code> and that has a path, via properties, that ends with
+ the <tref>node reference</tref>.
+ </dd>
+ <dt><tdef>incoming serialization</tdef></dt>
+ <dd>
+ A string that can be lexicographically compared to the
+ <tref>outgoing serialization</tref>s of other
+ <tref>node state</tref>s. It is a representation of the
+ <tref>incoming serialization map</tref> and other related
+ information. This string is initialized to an empty string.
+ </dd>
+ </dl>
+ </dd>
+ <dt><tdef>node state map</tdef></dt>
+ <dd>
+ A mapping from a node's <tref>label</tref> to a <tref>node state</tref>.
+ It is initialized to an empty map.
+ </dd>
<dt><tdef>labeling prefix</tdef></dt>
<dd>
- A random base string that starts with the characters <code>_:</code>, is
- not used by any other node's <tref>label</tref> 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. To prevent further collisions, an incrementing
- <tref>labeling counter</tref> is appended to the base string. For
- example, <code>_:j8r3k</code> is a proper <tref>labeling prefix</tref>.
- </dd>
- <dt><tdef>deterministic labeling prefix</tdef></dt>
- <dd>
- A base string with the value <code>_:c14n</code>. The prefix is used to
- deterministically name nodes during the normalization algorithm. The
- <tref>deterministic labeling counter</tref> is appended to the base string
- to ensure that there are no collisions.
+ The labeling prefix is a string that is used as the beginning of a node
+ <tref>label</tref>. It should be initialized to a random base string that
+ starts with the characters <code>_:</code>, is not used by any other
+ node's <tref>label</tref> in the <tref>JSON-LD input</tref>, and does not
+ start with the characters <code>_:c14n</code>. The prefix has two uses.
+ First it 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. Second, it will eventually be set to <code>_:c14n</code> to
+ generate the final, deterministic labels for nodes in the graph. This
+ prefix will be concatenated with the <tref>labeling counter</tref> to
+ produce a node <tref>label</tref>. For example, <code>_:j8r3k</code> is
+ a proper initial value for the <tref>labeling prefix</tref>.
</dd>
<dt><tdef>labeling counter</tdef></dt>
<dd>
- A counter that is used to re-label nodes that are not labeled, or that
- conflict with the canonicalization naming scheme.
- </dd>
- <dt><tdef>deterministic labeling counter</tdef></dt>
- <dd>
- A counter this is used to re-label nodes in a deterministic manner for
- the normalization output.
+ A counter that is used to label nodes. It is appended to the
+ <tref>labeling prefix</tref> to create a node <tref>label</tref>. It is
+ initialized to <code>1</code>.
</dd>
<dt><tdef>map of flattened nodes</tdef></dt>
<dd>
@@ -2312,22 +2375,6 @@
and has had all properties for the same node merged into a single
<tref>JSON object</tref>.
</dd>
- <dt><tdef>incoming map</tdef></dt>
- <dd>
- Relates graph node IRIs 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>incoming map</tref> is the <tref>label</tref> for <tref>beta</tref> and
- the value is an array containing at least node <tref>alpha</tref>.
- </dd>
- <dt><tdef>outgoing map</tdef></dt>
- <dd>
- Relates graph node IRIs to the target 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>outgoing map</tref> is the subject
- IRI of <tref>alpha</tref> and the value is an array containing at least
- <tref>beta</tref>.
- </dd>
</dl>
</section>
@@ -2344,15 +2391,10 @@
</p>
<ol class="algorithm">
-<li>Create a <tref>normalization state</tref> and initialize all array
- values to an empty array, all map values to an empty map, all
- string values to an empty string and all number values to <code>0</code>.</li>
<li>Expand the <tref>JSON-LD input</tref> according to the steps in
the <a href="#expansion-algorithm">Expansion Algorithm</a> and store the
result as the <strong>expanded input</strong>.</li>
-<li>Initialize the <tref>labeling prefix</tref> to a value that doesn't
-collide with any other <tref>label</tref> prefix in the graph. Initialize the
-<tref>labeling counter</tref> to 1.
+<li>Create a <tref>normalization state</tref>.</li>
<li>Initialize the <tref>map of flattened nodes</tref> by recursively
processing every <tdef>expanded node</tdef> in the
<strong>expanded input</strong> in depth-first order:
@@ -2384,22 +2426,18 @@
key-value pair where the key is <code>@iri</code> and the value is
the value of the <code>@subject</code> key in the node.</li>
</ol></li>
-<li>Initialize the <tref>outgoing map</tref> by iterating over every object
- associated with a property in the node, and if it is another node,
- adding the association to the list of nodes associated with the current
- node.</li>
-<li>Initialize the <tref>incoming map</tref> by iterating over every
- node in the graph and mapping its <tref>label</tref> to the list of all
- other nodes that refer to it.</li>
-<li>For every entry in the <tref>map of flattened nodes</tref> that has a
-<tref>label</tref> that begins with <code>_:c14n</code>, relabel the <tref>label</tref>
-using the steps in the
-<a href="#node-relabeling-algorithm">Node Relabeling Algorithm</a> with the
-following parameters; the <tref>normalization state</tref>,
-the <tref>old label</tref> should be the value of <tref>label</tref>,
-the <tref>naming base string</tref> should be the value
-of <tref>labeling prefix</tref> and the <tref>renaming counter</tref> should be
-the value of <tref>labeling counter</tref>.
+<li>For every entry in the <tref>map of flattened nodes</tref>, insert a
+ key-value pair into the <tref>node state map</tref> where the key is the
+ key from the <tref>map of flattened nodes</tref> and the value is a
+ <tref>node state</tref> where its <tref>node reference</tref> refers to
+ the value from the <tref>map of flattened nodes</tref>.
+<li>Populate the <tref>incoming list</tref> for each <tref>node state</tref>
+ by iterating over every node in the graph and adding its <tref>label</tref>
+ to the <tref>incoming list</tref> associated with each node found in its
+ properties.</li>
+<li>For every entry in the <tref>node state map</tref> that has a
+<tref>label</tref> that begins with <code>_:c14n</code>, relabel the node
+using the <a href="#node-relabeling-algorithm">Node Relabeling Algorithm</a>.
<li>Label all of the nodes that contain a <code>@subject</code> key associated
with a value starting with <code>_:</code> according to the steps in the
<a href="#deterministic-labeling-algorithm">Deterministic Labeling Algorithm</a>.
@@ -2412,38 +2450,32 @@
<p>This algorithm renames a node by generating a unique
<tdef>new label</tdef> and updating all references to that <tref>label</tref>
-in the <tref>incoming map</tref> and the <tref>outgoing map</tref>. The
-following parameters must be given as input to the algorithm.
-
-<dl class="algorithm">
- <dt><tref>normalization state</tdef></dt>
- <dd>A reference to the current normalization state.</dd>
- <dt><tdef>old label</tdef></dt>
- <dd>The string value to use when performing look-ups on the
- <tref>incoming map</tref> and the <tref>outgoing map</tref>.</dd>
- <dt><tdef>naming base string</tdef></dt>
- <dd>The base string to utilize when generating the <tref>new label</tref>.
- </dd>
- <dt><tdef>renaming counter</tdef></dt>
- <dd>The counter that ensures uniqueness for all <tref>new label</tref>s that
- are generated. This value must be passed in by reference as changes
- to it must be reflected elsewhere in the normalization algorithm.</dd>
-</dl>
+in the <tref>node state map</tref>. The <tdef>old label</tdef> and the
+<tref>normalization state</tref> must be given as an input to the
+algorithm. The <tref>old label</tref> is the current <tref>label</tref> of
+the node that is to be relabeled.
<p>The node relabeling algorithm is as follows:</p>
<ol class="algorithm">
+ <li>If the <tref>labeling prefix</tref> is <code>_:c14n</code> and the
+ <tref>old label</tref> begins with <code>_:c14n</code> then return as
+ the node has already been renamed.
+ </li>
<li>Generate the <tdef>new label</tdef> by concatenating the
- <tref>naming base string</tref> with the string value of the
- <tref>renaming counter</tref>. Increment the <tref>renaming counter</tref>
- by one.
- </li>
- <li>For each node that is associated with the <tref>old label</tref> in the
- <tref>incoming map</tref>, update all properties that reference the
- <tref>old label</tref> with the <tref>new label</tref>.</li>
- <li>Change the <tref>old label</tref> keys in the <tref>incoming map</tref>
- and the <tref>outgoing map</tref> to the <tref>new label</tref>.</li>
- <li>Return the <tref>new label</tref> as the result.</li>
+ <tref>labeling prefix</tref> with the string value of the
+ <tref>labeling counter</tref>. Increment the <tref>labeling counter</tref>.
+ </li>
+ <li>For the <tref>node state</tref> associated with the
+ <tref>old label</tref>, update every node in the <tref>incoming list</tref>
+ by changing all the properties that reference the <tref>old label</tref> to
+ the <tref>new label</tref>.
+ </li>
+ <li>Change the <tref>old label</tref> key in the <tref>node state map</tref>
+ to the <tref>new label</tref> and set the associated
+ <tref>node reference</tref>'s <tref>label</tref> to the
+ <tref>new label</tref>.
+ </li>
</ol>
</section>
@@ -2451,119 +2483,72 @@
<h4>Deterministic Labeling Algorithm</h4>
<p>The deterministic labeling algorithm takes the
-<tref>map of flattened nodes</tref>
-and produces a sorted list of deterministically named and expanded nodes from
-the graph.
+<tref>normalization state</tref>
+and produces a <tdef>list of finished nodes</tdef> that is sorted and
+contains deterministically named and expanded nodes from the graph.
<ol class="algorithm">
- <li>Initialize the <tref>deterministic labeling counter</tref> to
- <code>1</code> and
- the <tdef>sorted list of expanded nodes</tdef> to an empty array.</li>
- <li>Place a reference to each of the nodes in the
- <tref>map of flattened nodes</tref> into a
- <tref>list of expanded nodes</tref>.
- <li>Move every node with an IRI that does not start with <code>_:</code>
- from the <tref>list of expanded nodes</tref> into the
- <tref>sorted list of expanded nodes</tref>.</li>
- <li>Create a <tdef>map of outgoing serialization maps</tdef> where the
- key is an unlabeled node identifier and the value is a map. The value
- map contains a <tref>serialization map</tref> with keys that are
- unlabeled node identifiers that map to values that are
- <tref>serialization label</tref>s.</li>
- <li>Create a <tdef>map of outgoing serializations</tdef> where the key is
- an unlabeled node identifier and the value is a serialization string.
- </li>
- <li>Create a <tdef>map of incoming serialization maps</tdef> where the key
- is an unlabeled node identifier and the value is a map. The value
- map contains a <tref>serialization map</tref> with keys that are
- unlabeled node identifiers that map to values that are
- <tref>serialization label</tref>s.</li>
- <li>Create a <tdef>map of incoming serializations</tdef> where the key is
- an unlabeled node identifier and the value is a serialization string.
- </li>
- <li>Append to the <tref>sorted list of expanded nodes</tref> by processing
- the remainder of the <tref>list of expanded nodes</tref> until it is empty:
+ <li>Set the <tref>labeling prefix</tref> to <code>_:c14n</code>, the
+ <tref>labeling counter</tref> to <code>1</code>,
+ the <tdef>list of finished nodes</tdef> to an empty array, and create
+ an empty array, the <tdef>list of unfinished nodes</tdef>.</li>
+ <li>For each <tref>node reference</tref> in the <tref>node state map</tref>:
<ol class="algorithm">
- <li>Sort the <tref>list of expanded nodes</tref> in descending order
- using the
+ <li>If the node's <tref>label</tref> does not start with <code>_:</code>
+ then put the <tref>node reference</tref> in the
+ <tref>list of finished nodes</tref>.
+ </li>
+ <li>If the node's <tref>label</tref> does start with <code>_:</code>
+ then put the <tref>node reference</tref> in the
+ <tref>list of unfinished nodes</tref>.
+ </li>
+ </ol>
+ </li>
+ <li>Append to the <tref>list of finished nodes</tref> by processing
+ the remainder of the <tref>list of unfinished nodes</tref> until it is
+ empty:
+ <ol class="algorithm">
+ <li>Sort the <tref>list of unfinished nodes</tref> in descending order
+ according to the
<a href="#deep-comparison-algorithm">Deep Comparison Algorithm</a> to
determine the sort order.</li>
- <li>Create a <tdef>list of all old labels</tdef> and initialize it to an
+ <li>Create a <tdef>list of labels</tdef> and initialize it to an
empty array.</li>
- <li>Relabel the first node in the
- resorted <tref>list of expanded nodes</tref> according to the
- <a href="#node-relabeling-algorithm">Node Relabeling Algorithm</a>
- with the following parameters;
- <tref>naming base string</tref> is the value of the
- <tref>deterministic labeling prefix</tref> and the
- <tref>renaming counter</tref> is the
- <tref>deterministic labeling counter</tref>.
- Place the <tref>old label</tref>
- in the <tref>list of all old labels</tref>.
- </li>
- <li>Relabel all of the nodes in the
- <tref>outgoing serialization map</tref> for the <tref>old label</tref>:
- <ol class="algorithm">
- <li>Create a <tdef>list of old labels</tdef> and
- add all of the keys from the <tref>outgoing serialization map</tref>
- to the list.</li>
- <li>Sort the <tref>list of old labels</tref> lexicographically using
- each associated value from the
- <tref>outgoing serialization map</tref>.</li>
- <li>For each <tref>old label</tref> in the
- <tref>list of old labels</tref> get the node from the
- <tref>map of flattened nodes</tref> and relabel it according to the
- <a href="#node-relabeling-algorithm">Node Relabeling Algorithm</a>
- with the following parameters;
- <tref>naming base string</tref> is the value of the
- <tref>deterministic labeling prefix</tref> and the
- <tref>renaming counter</tref> is the
- <tref>deterministic labeling counter</tref>.
- Place the <tref>old label</tref>
- in the <tref>list of all old labels</tref>.
- </li></ol></li>
- <li>Relabel all of the nodes in the
- <tref>incoming serialization map</tref> for the <tref>old label</tref>:
- <ol class="algorithm">
- <li>Create a <tdef>list of old labels</tdef> and
- add all of the keys from the <tref>incoming serialization map</tref>
- to the list.</li>
- <li>Sort the <tref>list of old labels</tref> lexicographically using
- each associated value from the
- <tref>incoming serialization map</tref>.</li>
- <li>For each <tref>old label</tref> in the
- <tref>list of old labels</tref> get the node from the
- <tref>map of flattened nodes</tref> and relabel it according to the
- <a href="#node-relabeling-algorithm">Node Relabeling Algorithm</a>
- with the following parameters;
- <tref>naming base string</tref> is the value of the
- <tref>deterministic labeling prefix</tref> and the
- <tref>renaming counter</tref> is the
- <tref>deterministic labeling counter</tref>.
- Place the <tref>old label</tref>
- in the <tref>list of all old labels</tref>.
- </li></ol></li>
- <li>For each <tref>old label</tref> in the
- <tref>list of old labels</tref>, if any
- <tref>outgoing serialization map</tref> contains a key that
- matches the <tref>old label</tref>, then remove the entry in the
- <tref>map of outgoing serializations</tref> and remove the
- entry in the <tref>map of outgoing serialization maps</tref>.
- </li>
- <li>For each <tref>old label</tref> in the
- <tref>list of old labels</tref>, if any
- <tref>incoming serialization map</tref> contains a key that
- matches the <tref>old label</tref>, then remove the entry in the
- <tref>map of incoming serializations</tref> and remove the
- entry in the <tref>map of incoming serialization maps</tref>.
- </li>
- <li>
- Remove each node with a <tref>label</tref> that starts with
- <code>_:c14n</code> from the <tref>list of expanded nodes</tref> and
- add it to the <tref>sorted list of expanded nodes</tref>.
- </ol></li>
- <li>Sort the <tref>sorted list of expanded nodes</tref> in descending order
- using the
+ <li>For the first node from the <tref>list of unfinished nodes</tref>:
+ <ol class="algorithm">
+ <li>Add its <tref>label</tref> to the <tref>list of labels</tref>.
+ </li>
+ <li>For each key-value pair from its associated
+ <tref>outgoing serialization map</tref>, add the key to a list and
+ then sort the list according to the lexicographical order of the
+ keys' associated values. Append the list to the
+ <tref>list of nodes to label</tref>.
+ </li>
+ <li>For each key-value pair from its associated
+ <tref>incoming serialization map</tref>, add the key to a list and
+ then sort the list according to the lexicographical order of the
+ keys' associated values. Append the list to the
+ <tref>list of nodes to label</tref>.
+ </li></ol></li>
+ <li>For each <tref>label</tref> in the <tref>list of labels</tref>,
+ relabel the associated node according to the
+ <a href="#node-relabeling-algorithm">Node Relabeling Algorithm</a>. If
+ any <tref>outgoing serialization map</tref> contains a key that
+ matches the <tref>label</tref>, clear the map and set the associated
+ <tref>outgoing serialization</tref> to an empty string. If any
+ <tref>incoming serialization map</tref> contains a key that
+ matches the <tref>label</tref>, clear the map and set the associated
+ <tref>incoming serialization</tref> to an empty string.
+ </li>
+ <li>
+ Remove each node with a <tref>label</tref> that starts with
+ <code>_:c14n</code> from the <tref>list of unfinished nodes</tref> and
+ add it to the <tref>list of finished nodes</tref>.
+ </li>
+ </ol>
+ </li>
+ <li>Sort the <tref>list of finished nodes</tref> in descending order
+ according to the
<a href="#deep-comparison-algorithm">Deep Comparison Algorithm</a> to
determine the sort order.</li>
</ol>
@@ -2602,29 +2587,29 @@
<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
+ <li>Sort <tref>alpha list</tref> and <tref>beta list</tref> according to
+ 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
+ <tref>beta list</tref> according to 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>incoming map</tref> to determine order:
+ <li>Process the <tref>incoming list</tref>s associated with each node to
+ determine order:
<ol class="algorithm">
- <li>The node with fewer entries in the <tref>incoming map</tref>
- is first.</li>
- <li>Sort the <tref>incoming map</tref> entry for <tref>alpha</tref>
- into a <tdef>list of sorted alpha mappings</tdef>. Sort the
- <tref>incoming map</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>
+ <li>The node with the shortest <tref>incoming list</tref> is first.</li>
+ <li>Sort the <tref>incoming list</tref>s according to incoming property
+ and then incoming <tref>label</tref>.
+ <li>The node associated with the least number of incoming unlabeled
+ nodes is first.</li>
+ <li>For each offset into the <tref>incoming list</tref>s,
+ compare the associated properties and <tref>label</tref>s.
+ The node associated with the lexicographically lesser associated
+ property is first. The node associated with the lexicographically
+ lesser <tref>label</tref> is first.</li>
</ol></li>
<li>Otherwise, the nodes are equivalent.</li>
</section>
@@ -2675,69 +2660,110 @@
not truly equivalent.
</p>
+<p>When performing the steps required by the deep comparison algorithm, it
+is helpful to track state information about mappings. The information
+contained in a <tref>mapping state</tref> is described below.</p>
+
+<dl class="algorithm">
+ <dt><tdef>mapping state</tdef></dt>
+ <dd>
+ <dl>
+ <dt><tdef>mapping counter</tdef></dt>
+ <dd>
+ Keeps track of the number of nodes that have been mapped to
+ <tref>serialization labels</tref>. It is initialized to
+ <code>1</code>.
+ </dd>
+ <dt><tdef>processed labels map</tdef></dt>
+ <dd>
+ Keeps track of the <tref>label</tref>s of nodes that have already
+ been assigned <tref>serialization label</tref>s. It is initialized
+ to an empty map.
+ </dd>
+ <dt><tdef>serialized labels map</tdef></dt>
+ <dd>
+ Maps a node <tref>label</tref> to its associated
+ <tref>serialization label</tref>. It is initialized to an empty map.
+ </dd>
+ <dt><tdef>adjacent info map</tdef></dt>
+ <dd>
+ Maps a <tref>serialization label</tref> to the node
+ <tref>label</tref> associated with it, the list of sorted
+ <tref>serialization label</tref>s for adjacent nodes, and the map of
+ adjacent node <tref>serialiation label</tref>s to their associated
+ node <tref>label</tref>s. It is initialized to an empty map.
+ </dd>
+ <dt><tdef>key stack</tdef></dt>
+ <dd>
+ A stack where each element contains an array of adjacent
+ <tref>serialization label</tref>s and an index into that array. It
+ is initialized to a stack containing a single element where its
+ array contains a single string element <code>s1</code> and its
+ index is set to <code>0</code>.
+ </dd>
+ <dt><tdef>serialized keys</tdef></dt>
+ <dd>
+ Keeps track of which <tref>serialization label</tref>s have already
+ been written at least once to the <tref>serialization string</tref>.
+ It is initialized to an empty map.
+ </dd>
+ <dt><tdef>serialization string</tdef></dt>
+ <dd>
+ A string that is incrementally updated as a serialization is built.
+ It is initialized to an empty string.
+ </dd>
+ </dl>
+ </dd>
+</dl>
+
+<p>The deep comparison algorithm is as follows:</p>
+
<ol class="algorithm">
<li>Perform a comparison between <tref>alpha</tref> and <tref>beta</tref>
- using the steps in the
+ according to the
<a href="#shallow-comparison-algorithm">Shallow Comparison Algorithm</a>.
If the result does not show that the two nodes are equivalent, return
the result.
</li>
- <li>Initialize the <tdef>mapping counter</tdef> to <code>1</code>.
- Initialize the <tdef>list of unserialized labels</tdef> to an
- empty array. Initialize the
- <tdef>processed labels map</tdef>,
- the <tdef>incoming serialization map</tdef>,
- the <tdef>outgoing serialization map</tdef>, and
- the <tdef>serialized labels map</tdef> to empty maps.
- <li>Compare incoming and outgoing edges for each node, updating the
- serialization maps as each node is processed:
+ <li>Compare incoming and outgoing edges for each node, updating their
+ associated <tref>node state</tref> as each node is processed:
<ol class="algorithm">
- <li>If the <tref>label</tref> for <tref>alpha</tref> does not exist in the
- <tref>outgoing serialization map</tref>, generate the serialization by
- following the steps in the
- <a href="#node-serialization-algorithm">Node Serialization Algorithm</a>.
- Provide <tref>alpha</tref>,
- the <tref>processed labels map</tref>,
- the <tref>outgoing serialization map</tref>,
- the <tref>serialized labels map</tref> and the
- <tref>list of unserialized labels</tref> to the algorithm as inputs.
- <li>If the <tref>label</tref> for <tref>beta</tref> does not exist in the
- <tref>outgoing serialization map</tref>, generate the serialization by
- following the steps in the
+ <li>If the <tref>outgoing serialization map</tref> for <tref>alpha</tref>
+ is empty, generate the serialization according to the
<a href="#node-serialization-algorithm">Node Serialization Algorithm</a>.
- Provide <tref>beta</tref>,
- the <tref>processed labels map</tref>,
- the <tref>outgoing serialization map</tref>,
- the <tref>serialized labels map</tref> and the
- <tref>list of unserialized labels</tref> to the algorithm as inputs.
- <li>If the lexicographical value of the entry for <tref>alpha</tref> in
- the <tref>outgoing serialization map</tref> is greater than the entry
- for <tref>beta</tref> in the <tref>outgoing serialization map</tref>,
- then <tref>alpha</tref> is first. If the lexicographical value is less,
- then <tref>beta</tref> is first.</li>
- <li>If the <tref>label</tref> for <tref>alpha</tref> does not exist in the
- <tref>incoming serialization map</tref>, generate the serialization by
- following the steps in the
+ Provide <tref>alpha</tref>'s <tref>node state</tref>, a new
+ <tref>mapping state</tref>,
+ <code>outgoing direction</code> to the algorithm as inputs.
+ <li>If the <tref>outgoing serialization map</tref> for <tref>beta</tref>
+ is empty, generate the serialization according to the
<a href="#node-serialization-algorithm">Node Serialization Algorithm</a>.
- Provide <tref>alpha</tref>,
- the <tref>processed labels map</tref>,
- the <tref>incoming serialization map</tref>,
- the <tref>serialized labels map</tref> and the
- <tref>list of unserialized labels</tref> to the algorithm as inputs.
- <li>If the <tref>label</tref> for <tref>beta</tref> does not exist in the
- <tref>incoming serialization map</tref>, generate the serialization by
- following the steps in the
+ Provide <tref>beta</tref>'s <tref>node state</tref>, a new
+ <tref>mapping state</tref>, and
+ <code>outgoing direction</code> to the algorithm as inputs.
+ <li>If <tref>alpha</tref>'s <tref>outgoing serialization</tref> is
+ lexicographically less than <tref>beta</tref>'s, then
+ <tref>alpha</tref> is first. If it is greater, then <tref>beta</tref>
+ is first.</li>
+ <li>If the <tref>incoming serialization map</tref> for <tref>alpha</tref>
+ is empty, generate the serialization according to the
<a href="#node-serialization-algorithm">Node Serialization Algorithm</a>.
- Provide <tref>beta</tref>,
- the <tref>processed labels map</tref>,
- the <tref>incoming serialization map</tref>,
- the <tref>serialized labels map</tref> and the
- <tref>list of unserialized labels</tref> to the algorithm as inputs.
- <li>If the lexicographical value of the entry for <tref>alpha</tref> in
- the <tref>incoming serialization map</tref> is greater than the entry
- for <tref>beta</tref> in the <tref>incoming serialization map</tref>,
- then <tref>alpha</tref> is first. If the lexicographical value is less,
- then <tref>beta</tref> is first.</li>
+ Provide <tref>alpha</tref>'s <tref>node state</tref>, a new
+ <tref>mapping state</tref> with its <tref>serialized labels map</tref>
+ set to a copy of <tref>alpha</tref>'s
+ <tref>outgoing serialization map</tref>, and
+ <code>incoming direction</code> to the algorithm as inputs.
+ <li>If the <tref>incoming serialization map</tref> for <tref>beta</tref>
+ is empty, generate the serialization according to the
+ <a href="#node-serialization-algorithm">Node Serialization Algorithm</a>.
+ Provide <tref>beta</tref>'s <tref>node state</tref>, a new
+ <tref>mapping state</tref> with its <tref>serialized labels map</tref>
+ set to a copy of <tref>beta</tref>'s
+ <tref>outgoing serialization map</tref>, and
+ <code>incoming direction</code> to the algorithm as inputs.
+ <li>If <tref>alpha</tref>'s <tref>incoming serialization</tref> is
+ lexicographically less than <tref>beta</tref>'s, then
+ <tref>alpha</tref> is first. If it is greater, then <tref>beta</tref>
+ is first.</li>
</ol></li>
</ol>
</section>
@@ -2746,27 +2772,31 @@
<h4>Node Serialization Algorithm</h4>
<p>
-The node serialization algorithm takes a node,
-a <tref>processed labels map</tref>, a
-<tdef>serialization map</tdef>, a <tref>serialized labels map</tref>,
-and a <tref>list of unserialized labels</tref> as inputs and generates
-deterministic serializations for all unlabeled nodes in the graph.
+The node serialization algorithm takes a <tref>node state</tref>, a
+<tref>mapping state</tref>, and a <tdef>direction</tdef> (either
+<code>outgoing direction</code> or <code>incoming direction</code>) as
+inputs and generates a deterministic serialization for the
+<tref>node reference</tref>.
</p>
<ol class="algorithm">
<li>If the <tref>label</tref> exists in the
<tref>processed labels map</tref>, terminate the algorithm as the
- <tref>serialization label</tref> has already been created</li>
+ <tref>serialization label</tref> has already been created.
+</li>
<li>Set the value associated with the <tref>label</tref> in the
<tref>processed labels map</tref> to <code>true</code>.
+</li>
<li>Generate the next <tdef>serialization label</tdef> for the
- <tref>label</tref> following the
- <a href="#serialization-label-generation-algorithm">Serialization Label Generation Algorithm</a>
- passing the <tref>label</tref> and the <tref>mapping count</tref> as
- parameters to the algorithm.</li>
-<li>For every property in the node that references a target node with a
-<tref>label</tref> that starts with <code>_:</code>
-(the <tdef>target node label</tdef>):
+ <tref>label</tref> according to the
+ <a href="#serialization-label-generation-algorithm">Serialization Label Generation Algorithm</a>.
+</li>
+<li>Create an empty array called the <tref>list of unserialized labels</tref>.
+</li>
+<li>For every <tref>label</tref> in a list, where the list the <tref>outgoing list</tref> if
+the <tref>direction</tref> is <code>outgoing direction</code> and the
+<tref>incoming list</tref> otherwise, if the <tref>label</tref> starts with
+<code>_:</code>, it is the <tdef>target node label</tdef>:
<ol class="algorithm">
<li>Look up the <tref>target node label</tref> in the
<tref>processed labels map</tref> and if a mapping exists,