Node equivalence compares graph nodes by structure rather than object identity. Equivalent nodes share terminal status, outgoing-edge count, edge labels, and reference-identical successor nodes. section 5.4.2
A pair of nodes is equivalent when:
- Both nodes are, or are not, end-of-word nodes. section 5.4.2
- They have the same number of outgoing edges and the same edge labels. section 5.4.2
- Each matching label leads to reference-identical successor nodes. section 5.4.2
- Leaf nodes are equivalent because they have no outgoing edges and always mark the end of a word. section 5.4.2
Listing 5.6 Computing Node equivalence with an equality comparer
sealed class DawgBuilder
{
private class NodeEquality : IEqualityComparer<Node>
{
public bool Equals(Node? x, Node? y)
{
if (ReferenceEquals(x, y))
return true;
if (ReferenceEquals(x, null) || ReferenceEquals(y, null))
return false;
if (x.IsEnd != y.IsEnd || x.Count != y.Count)
return false;
return x.EdgeLabels.All(e =>
y.HasEdge(e) &&
ReferenceEquals(x.FollowEdge(e), y.FollowEdge(e)));
}
Inspect the C# equality comparer that applies quick identity, null, terminal-status, edge-count, label, and successor checks. section 5.4.2
Listing 5.7 Finishing the Node equality comparer
public int GetHashCode(Node n)
{
var h = new HashCode();
h.Add(n.IsEnd);
foreach(var e in n.EdgeLabels.OrderBy(c=>c))
{
h.Add(e);
h.Add(n.FollowEdge(e)); #1
}
return h.ToHashCode();
}
}
Inspect hash-code construction from terminal status, ordered edge labels, and successor nodes; mutable nodes must not change their hash while stored in hashed collections. section 5.4.2
