RDF Isomorphism


Determines if two RDF graphs are isomorphic,
i.e., if two RDF graphs are equal while ignoring quad order
and ignoring non-equal blank node labels between the graphs.

This package is can be useful within unit/spec tests.

This library accepts RDFJS-compliant quads.

Usage

The following examples assume the following imports:

``javascript
import { DataFactory } from "rdf-data-factory"; // External library
import { isomorphic } from "rdf-isomorphic";

const factory = new DataFactory();
`

$3

`javascript
const graphA = [
factory.quad(
factory.blankNode('s1'),
factory.namedNode('p'),
factory.blankNode('o1'),
),
];
const graphB = [
factory.quad(
factory.blankNode('s2'),
factory.namedNode('p'),
factory.blankNode('o2'),
),
];
isomorphic(graphA, graphB); // Outputs true
`

$3

`javascript
const graphA = [
factory.quad(
factory.blankNode('s1'),
factory.namedNode('p1'),
factory.blankNode('o1'),
),
];
const graphB = [
factory.quad(
factory.blankNode('s2'),
factory.namedNode('p2'),
factory.blankNode('o2'),
),
];
isomorphic(graphA, graphB); // Outputs false
`

$3

`javascript
const graphA = [
factory.quad(
factory.quad(
factory.blankNode('sInner'),
factory.namedNode('pInner'),
factory.blankNode('o1'),
),
factory.namedNode('pOuter'),
factory.namedNode('oOuter'),
)
];
const graphB = [
factory.quad(
factory.quad(
factory.blankNode('sInner'),
factory.namedNode('pInner'),
factory.blankNode('o2'),
),
factory.namedNode('pOuter'),
factory.namedNode('oOuter'),
)
];
isomorphic(graphA, graphB); // Outputs true
``

Algorithm

This algorithm is based on the RDF isomorphism checker in RDF.rb,
which in its turn is based on the algorithm described by Jeremy Carrol.

In summary, the algorithm generates a hash for each blank node based on the connected resources.
These hashes are then compared between the two given graphs, and a bijection is attempted to be created.
If no such bijection can be found, then the graphs are considered non-isomorphic.

The implementation of this package is inspired by the Ruby RDF::Isomorphic gem.

The algorithm has been adapted to work this nested quads by Ruben Taelman.

License

This software is written by Ruben Taelman.

This code is released under the MIT license.