# RDF Isomorphism

This is an RDF.rb extension for RDF Isomorphism functionality for RDF::Enumerables. That includes RDF::Repository, RDF::Graph, query results, and more.

## Synopsis:

``````require 'rdf/isomorphic'
require 'rdf/ntriples'

a.first
# < RDF::Statement:0xd344c4(<http://example.org/a> <http://example.org/prop> <_:abc> .) >

b.first
# < RDF::Statement:0xd3801a(<http://example.org/a> <http://example.org/prop> <_:testing> .) >

a.isomorphic_with? b
# true

a.bijection_to b
# { #<RDF::Node:0xd345a0(_:abc)>=>#<RDF::Node:0xd38574(_:testing)> }
``````

## Algorithm

The algorithm used here is very similar to the one described by Jeremy Carroll in http://www.hpl.hp.com/techreports/2001/HPL-2001-293.pdf. See http://blog.datagraph.org/2010/03/rdf-isomorphism.

Generally speaking, the Carroll algorithm is a very good fit for RDF graphs. It is a specialization of the naive factorial-time test for graph isomorphism, wherein non-anonymous RDF data lets us eliminate vast quantities of options well before we try them. Pathological cases, such as graphs which only contain anonymous resources, may experience poor performance.

### Equality

Although it was considered to provide `==` to mean isomorphic, RDF isomorphism can sometimes be a factorial-complexity problem and it seemed better to perhaps not overwrite such a commonly used method for that. But it's really useful for specs in RDF libraries. Try this in your tests:

``````require 'rdf/isomorphic'
module RDF
module Isomorphic
alias_method :==, :isomorphic_with?
end
end

describe 'something' do
context 'does' do
it 'should be equal' do
repository_a.should == repository_b
end
end
end
``````

## Contributing

This repository uses Git Flow to mange development and release activity. All submissions must be on a feature branch based on the develop branch to ease staging and integration.

• Do your best to adhere to the existing coding conventions and idioms.
• Don't use hard tabs, and don't leave trailing whitespace on any line. Before committing, run `git diff --check` to make sure of this.
• Do document every method you add using YARD annotations. Read the tutorial or just look at the existing code for examples.
• Don't touch the `.gemspec` or `VERSION` files. If you need to change them, do so on your private branch only.
• Do feel free to add yourself to the `CREDITS` file and the corresponding list in the the `README`. Alphabetical order applies.
• Don't touch the `AUTHORS` file. If your contributions are significant enough, be assured we will eventually add you in there.
• Do note that in order for us to merge any non-trivial changes (as a rule of thumb, additions larger than about 15 lines of code), we need an explicit public domain dedication on record from you.