Function sophia_api::graph::isomorphic_graphs

source · [−]

pub fn isomorphic_graphs<G1, G2>(
    g1: &G1, 
    g2: &G2
) -> StreamResult<bool, G1::Error, G2::Error> where
    G1: Graph,
    G2: Graph,
    GTerm<G1>: Clone + Eq + Hash,
    GTerm<G2>: Clone + Eq + Hash,

Expand description

Checks if both graphs are isomorphic blank node equal.

According to the RDF specs this means that a mapping for blank nodes in g1 exists so that g1 == g2.

The algorithm is inspired from a similar one in Oxigraph and is extended for the generalized RDF model of sophia.

Errors

Both graphs may fail traversing (and this is done several times). Accordingly, a StreamError returned, where SourceErrors originate from g1 and SinkErrors originate from g2

As this algorithm has to enumerates the triples of each graph several times, the algorithm gets more expensive with bigger numbers of triples. In the same way the number of blank nodes contributes to the cost.

Note however that the algorithm uses some heuristics, to avoid the combinatorial explosion of trying every possible bnode-pairing. As a result, it is not 100% accurate (see below).

Accuracy

If g1 and g2 are isomorphic, the function will always return true.

If they are not isomorphic, the function will generally return false, but a few pathological cases may be falses positives (i.e. recognized as isomorphic while they are not).

For example, the graph:

    _:a :rel _:b.
    _:b :rel _:a.
    _:c :rel _:c.

and the graph:

    _:a :rel _:b.
    _:b :rel _:c.
    _:c :rel _:a.

are considered isomorphic by this algorithm, because they have the same number of blank nodes and arcs, and all of their blank nodes are locally indistinguisable (same number of incoming and outgoinc arcs, linking them to undistinguishable blank nodes).

Correctly answering in this kind of pathological case requires a combinatorial exploration of all possible bnode-pairings, which would make the algorithm very slow in the worst case.

The choice has been made to accept this flaw, as such undistinguishable blank nodes are very rare in real data, and not particularly useful.

Function sophia_api::graph::isomorphic_graphs

Errors

Performance

Accuracy