Source code

Download source archive ↓

src/rdflib/tools/graphisomorphism.py

1"""
2A commandline tool for testing if RDF graphs are isomorpic, i.e. equal
3if BNode labels are ignored.
4"""
5
6from itertools import combinations
7
8from rdflib import BNode, Graph
9
10
11class IsomorphicTestableGraph(Graph):
12    """
13    Ported from:
14    http://www.w3.org/2001/sw/DataAccess/proto-tests/tools/rdfdiff.py
15    (Sean B Palmer's RDF Graph Isomorphism Tester)
16    """
17
18    def __init__(self, **kargs):
19        super(IsomorphicTestableGraph, self).__init__(**kargs)
20        self.hash = None
21
22    def internal_hash(self):
23        """
24        This is defined instead of __hash__ to avoid a circular recursion
25        scenario with the Memory store for rdflib which requires a hash
26        lookup in order to return a generator of triples
27        """
28        return hash(tuple(sorted(self.hashtriples())))
29
30    def hashtriples(self):
31        for triple in self:
32            g = ((isinstance(t, BNode) and self.vhash(t)) or t for t in triple)
33            yield hash(tuple(g))
34
35    def vhash(self, term, done=False):
36        return tuple(sorted(self.vhashtriples(term, done)))
37
38    def vhashtriples(self, term, done):
39        for t in self:
40            if term in t:
41                yield tuple(self.vhashtriple(t, term, done))
42
43    def vhashtriple(self, triple, term, done):
44        for p in range(3):
45            if not isinstance(triple[p], BNode):
46                yield triple[p]
47            elif done or (triple[p] == term):
48                yield p
49            else:
50                yield self.vhash(triple[p], done=True)
51
52    def __eq__(self, G):  # noqa: N803
53        """Graph isomorphism testing."""
54        if not isinstance(G, IsomorphicTestableGraph):
55            return False
56        elif len(self) != len(G):
57            return False
58        elif list.__eq__(list(self), list(G)):
59            return True  # @@
60        return self.internal_hash() == G.internal_hash()
61
62    def __ne__(self, G):  # noqa: N803
63        """Negative graph isomorphism testing."""
64        return not self.__eq__(G)
65
66
67def main():
68    import sys
69    from optparse import OptionParser
70
71    usage = """usage: %prog [options] file1 file2 ... fileN"""
72    op = OptionParser(usage=usage)
73    op.add_option(
74        "-s",
75        "--stdin",
76        action="store_true",
77        default=False,
78        help="Load from STDIN as well",
79    )
80    op.add_option(
81        "--format",
82        default="xml",
83        dest="inputFormat",
84        metavar="RDF_FORMAT",
85        choices=["xml", "trix", "n3", "nt", "rdfa"],
86        help="The format of the RDF document(s) to compare"
87        + "One of 'xml','n3','trix', 'nt', "
88        + "or 'rdfa'.  The default is %default",
89    )
90
91    (options, args) = op.parse_args()
92
93    graphs = []
94    graph2FName = {}  # noqa: N806
95    if options.stdin:
96        graph = IsomorphicTestableGraph().parse(sys.stdin, format=options.inputFormat)
97        graphs.append(graph)
98        graph2FName[graph] = "(STDIN)"
99    for fn in args:
100        graph = IsomorphicTestableGraph().parse(fn, format=options.inputFormat)
101        graphs.append(graph)
102        graph2FName[graph] = fn
103    checked = set()
104    for graph1, graph2 in combinations(graphs, 2):
105        if (graph1, graph2) not in checked and (graph2, graph1) not in checked:
106            assert graph1 == graph2, "%s != %s" % (
107                graph2FName[graph1],
108                graph2FName[graph2],
109            )
110
111
112if __name__ == "__main__":
113    main()