Re: URDNA2015 Implementation Question

On 7/7/22 6:10 PM, Daniel Petranek wrote:
> Hello, I'm working on implementing the RDF Dataset Canonicalization
> algorithm[0], using the
> <> implementation as a
> reference.

Hi Daniel!

> I've got an implementation with all the tests passing except evil(1),
> evil(2), and evil(3), and I was wondering if you could clarify a point
> for me - step 5.4 of the Hash N-Degree Quads algorithm which states:
> "For each permutation of blank node list:".
> I've instrumented the rdf-canonicalize library so I can inspect the
> order of execution, and it appears that what differs between my
> implementation and the Javascript one is the order of the permutations.
> The spec doesn't say how the permutations should be ordered, and my
> intuition is that the order does indeed matter - though I'm happy to be
> corrected if I'm wrong.
> So, here is my question(s):
> - Does the order of the permutations matter?
> - If so, what order should they be in?

Nope, the permutation order should not matter. So I would expect there
to be some other deviation in your implementation from the algorithm.

> The ref-canonicalize library implements the Steinhaus-Johnson-Trotter
> algorithm, which I'm happy to do as well if necessary. But if the
> specific order matters I think it should be a part of the spec.

Nope, as long as you cover all the permutations, they can be in any
order. You may find it easier to debug if you use the same permutation
algorithm, but it's not necessary for correctness.

Good luck!

Dave Longley
Digital Bazaar, Inc.

Received on Friday, 8 July 2022 05:01:53 UTC