rdf-isomorphic

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 * as DataFactory from "@rdfjs/data-model"; // External library
import {isomorphic} from "rdf-isomorphic";

Check if two graphs are isomorphic

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

Check if two graphs are not isomorphic

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

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.

License

This software is written by Ruben Taelman.

This code is released under the MIT license.