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:

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

const factory = new DataFactory();

Check if two graphs are isomorphic

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

Check if two graphs are not isomorphic

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

Check if two graphs with nested quads are isomorphic

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.