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()