src/rdflib/compare.py
1"""
2A collection of utilities for canonicalizing and inspecting graphs.
3
4Among other things, they solve of the problem of deterministic bnode
5comparisons.
6
7Warning: the time to canonicalize bnodes may increase exponentially on
8degenerate larger graphs. Use with care!
9
10Example of comparing two graphs:
11
12```python
13>>> g1 = Graph().parse(format='n3', data='''
14... @prefix : <http://example.org/ns#> .
15... <http://example.org> :rel
16... <http://example.org/same>,
17... [ :label "Same" ],
18... <http://example.org/a>,
19... [ :label "A" ] .
20... ''')
21>>> g2 = Graph().parse(format='n3', data='''
22... @prefix : <http://example.org/ns#> .
23... <http://example.org> :rel
24... <http://example.org/same>,
25... [ :label "Same" ],
26... <http://example.org/b>,
27... [ :label "B" ] .
28... ''')
29>>>
30>>> iso1 = to_isomorphic(g1)
31>>> iso2 = to_isomorphic(g2)
32
33```
34
35These are not isomorphic
36
37```python
38>>> iso1 == iso2
39False
40
41```
42
43Diff the two graphs:
44
45```python
46>>> in_both, in_first, in_second = graph_diff(iso1, iso2)
47
48```
49
50Present in both:
51
52```python
53>>> def dump_nt_sorted(g):
54... for l in sorted(g.serialize(format='nt').splitlines()):
55... if l: print(l.decode('ascii'))
56>>> dump_nt_sorted(in_both) #doctest: +SKIP
57<http://example.org>
58 <http://example.org/ns#rel> <http://example.org/same> .
59<http://example.org>
60 <http://example.org/ns#rel> _:cbcaabaaba17fecbc304a64f8edee4335e .
61_:cbcaabaaba17fecbc304a64f8edee4335e
62 <http://example.org/ns#label> "Same" .
63```
64
65Only in first:
66
67```python
68>>> dump_nt_sorted(in_first) #doctest: +SKIP
69<http://example.org>
70 <http://example.org/ns#rel> <http://example.org/a> .
71<http://example.org>
72 <http://example.org/ns#rel> _:cb124e4c6da0579f810c0ffe4eff485bd9 .
73_:cb124e4c6da0579f810c0ffe4eff485bd9
74 <http://example.org/ns#label> "A" .
75```
76
77Only in second:
78
79```python
80>>> dump_nt_sorted(in_second) #doctest: +SKIP
81<http://example.org>
82 <http://example.org/ns#rel> <http://example.org/b> .
83<http://example.org>
84 <http://example.org/ns#rel> _:cb558f30e21ddfc05ca53108348338ade8 .
85_:cb558f30e21ddfc05ca53108348338ade8
86 <http://example.org/ns#label> "B" .
87```
88"""
89
90from __future__ import annotations
91
92# TODO:
93# - Doesn't handle quads.
94# - Add warning and/or safety mechanism before working on large graphs?
95# - use this in existing Graph.isomorphic?
96
97__all__ = [
98 "IsomorphicGraph",
99 "to_isomorphic",
100 "isomorphic",
101 "to_canonical_graph",
102 "graph_diff",
103 "similar",
104]
105
106from collections import defaultdict
107from datetime import datetime
108from hashlib import sha256
109from typing import (
110 TYPE_CHECKING,
111 Callable,
112 Dict,
113 Iterator,
114 List,
115 Optional,
116 Set,
117 Tuple,
118 Union,
119)
120
121from rdflib.graph import ConjunctiveGraph, Graph, ReadOnlyGraphAggregate, _TripleType
122from rdflib.term import BNode, IdentifiedNode, Node, URIRef
123
124if TYPE_CHECKING:
125 from _hashlib import HASH
126
127
128def _total_seconds(td):
129 result = td.days * 24 * 60 * 60
130 result += td.seconds
131 result += td.microseconds / 1000000.0
132 return result
133
134
135class _runtime: # noqa: N801
136 def __init__(self, label):
137 self.label = label
138
139 def __call__(self, f):
140 if self.label is None:
141 self.label = f.__name__ + "_runtime"
142
143 def wrapped_f(*args, **kwargs):
144 start = datetime.now()
145 result = f(*args, **kwargs)
146 if "stats" in kwargs and kwargs["stats"] is not None:
147 stats = kwargs["stats"]
148 stats[self.label] = _total_seconds(datetime.now() - start)
149 return result
150
151 return wrapped_f
152
153
154class _call_count: # noqa: N801
155 def __init__(self, label):
156 self.label = label
157
158 def __call__(self, f):
159 if self.label is None:
160 self.label = f.__name__ + "_runtime"
161
162 def wrapped_f(*args, **kwargs):
163 if "stats" in kwargs and kwargs["stats"] is not None:
164 stats = kwargs["stats"]
165 if self.label not in stats:
166 stats[self.label] = 0
167 stats[self.label] += 1
168 return f(*args, **kwargs)
169
170 return wrapped_f
171
172
173class IsomorphicGraph(ConjunctiveGraph):
174 """An implementation of the RGDA1 graph digest algorithm.
175
176 An implementation of RGDA1 (publication below),
177 a combination of Sayers & Karp's graph digest algorithm using
178 sum and SHA-256 <http://www.hpl.hp.com/techreports/2003/HPL-2003-235R1.pdf>
179 and traces <http://pallini.di.uniroma1.it>, an average case
180 polynomial time algorithm for graph canonicalization.
181
182 McCusker, J. P. (2015). WebSig: A Digital Signature Framework for the Web.
183 Rensselaer Polytechnic Institute, Troy, NY.
184 http://gradworks.umi.com/3727015.pdf
185 """
186
187 def __init__(self, **kwargs):
188 super(IsomorphicGraph, self).__init__(**kwargs)
189
190 def __eq__(self, other):
191 """Graph isomorphism testing."""
192 if not isinstance(other, IsomorphicGraph):
193 return False
194 elif len(self) != len(other):
195 return False
196 return self.internal_hash() == other.internal_hash()
197
198 def __ne__(self, other):
199 """Negative graph isomorphism testing."""
200 return not self.__eq__(other)
201
202 def __hash__(self):
203 return super(IsomorphicGraph, self).__hash__()
204
205 def graph_digest(self, stats=None):
206 """Synonym for IsomorphicGraph.internal_hash."""
207 return self.internal_hash(stats=stats)
208
209 def internal_hash(self, stats=None):
210 """
211 This is defined instead of `__hash__` to avoid a circular recursion
212 scenario with the Memory store for rdflib which requires a hash lookup
213 in order to return a generator of triples.
214 """
215 return _TripleCanonicalizer(self).to_hash(stats=stats)
216
217
218HashFunc = Callable[[str], int]
219ColorItem = Tuple[Union[int, str], URIRef, Union[int, str]]
220ColorItemTuple = Tuple[ColorItem, ...]
221HashCache = Optional[Dict[ColorItemTuple, str]]
222Stats = Dict[str, Union[int, str]]
223
224
225class Color:
226 def __init__(
227 self,
228 nodes: List[IdentifiedNode],
229 hashfunc: HashFunc,
230 color: ColorItemTuple = (),
231 hash_cache: HashCache = None,
232 ):
233 if hash_cache is None:
234 hash_cache = {}
235 self._hash_cache = hash_cache
236 self.color = color
237 self.nodes = nodes
238 self.hashfunc = hashfunc
239 self._hash_color = None
240
241 def __str__(self):
242 nodes, color = self.key()
243 return "Color %s (%s nodes)" % (color, nodes)
244
245 def key(self):
246 return (len(self.nodes), self.hash_color())
247
248 def hash_color(self, color: Optional[Tuple[ColorItem, ...]] = None) -> str:
249 if color is None:
250 color = self.color
251 if color in self._hash_cache:
252 return self._hash_cache[color]
253
254 def stringify(x):
255 if isinstance(x, Node):
256 return x.n3()
257 else:
258 return str(x)
259
260 if isinstance(color, Node):
261 return stringify(color)
262 value = 0
263 for triple in color:
264 value += self.hashfunc(" ".join([stringify(x) for x in triple]))
265 val: str = "%x" % value
266 self._hash_cache[color] = val
267 return val
268
269 def distinguish(self, W: Color, graph: Graph): # noqa: N803
270 colors: Dict[str, Color] = {}
271 for n in self.nodes:
272 new_color: Tuple[ColorItem, ...] = list(self.color) # type: ignore[assignment]
273 for node in W.nodes:
274 new_color += [ # type: ignore[operator]
275 (1, p, W.hash_color()) for s, p, o in graph.triples((n, None, node))
276 ]
277 new_color += [ # type: ignore[operator]
278 (W.hash_color(), p, 3) for s, p, o in graph.triples((node, None, n))
279 ]
280 new_color = tuple(new_color)
281 new_hash_color = self.hash_color(new_color)
282
283 if new_hash_color not in colors:
284 c = Color([], self.hashfunc, new_color, hash_cache=self._hash_cache)
285 colors[new_hash_color] = c
286 colors[new_hash_color].nodes.append(n)
287 return colors.values()
288
289 def discrete(self):
290 return len(self.nodes) == 1
291
292 def copy(self):
293 return Color(
294 self.nodes[:], self.hashfunc, self.color, hash_cache=self._hash_cache
295 )
296
297
298_HashT = Callable[[], "HASH"]
299
300
301class _TripleCanonicalizer:
302 def __init__(self, graph: Graph, hashfunc: _HashT = sha256):
303 self.graph = graph
304
305 def _hashfunc(s: str):
306 h = hashfunc()
307 h.update(str(s).encode("utf8"))
308 return int(h.hexdigest(), 16)
309
310 self._hash_cache: HashCache = {}
311 self.hashfunc = _hashfunc
312
313 def _discrete(self, coloring: List[Color]) -> bool:
314 return len([c for c in coloring if not c.discrete()]) == 0
315
316 def _initial_color(self) -> List[Color]:
317 """Finds an initial color for the graph.
318
319 Finds an initial color of the graph by finding all blank nodes and
320 non-blank nodes that are adjacent. Nodes that are not adjacent to blank
321 nodes are not included, as they are a) already colored (by URI or literal)
322 and b) do not factor into the color of any blank node.
323 """
324 bnodes: Set[BNode] = set()
325 others = set()
326 self._neighbors = defaultdict(set)
327 for s, p, o in self.graph:
328 nodes = set([s, p, o])
329 b = set([x for x in nodes if isinstance(x, BNode)])
330 if len(b) > 0:
331 others |= nodes - b
332 bnodes |= b
333 if isinstance(s, BNode):
334 self._neighbors[s].add(o)
335 if isinstance(o, BNode):
336 self._neighbors[o].add(s)
337 if isinstance(p, BNode):
338 self._neighbors[p].add(s)
339 self._neighbors[p].add(p)
340 if len(bnodes) > 0:
341 return [Color(list(bnodes), self.hashfunc, hash_cache=self._hash_cache)] + [
342 # type error: List item 0 has incompatible type "Union[IdentifiedNode, Literal]"; expected "IdentifiedNode"
343 # type error: Argument 3 to "Color" has incompatible type "Union[IdentifiedNode, Literal]"; expected "Tuple[Tuple[Union[int, str], URIRef, Union[int, str]], ...]"
344 Color([x], self.hashfunc, x, hash_cache=self._hash_cache) # type: ignore[list-item, arg-type]
345 for x in others
346 ]
347 else:
348 return []
349
350 def _individuate(self, color, individual):
351 new_color = list(color.color)
352 new_color.append((len(color.nodes),))
353
354 color.nodes.remove(individual)
355 c = Color(
356 [individual], self.hashfunc, tuple(new_color), hash_cache=self._hash_cache
357 )
358 return c
359
360 def _get_candidates(self, coloring: List[Color]) -> Iterator[Tuple[Node, Color]]:
361 for c in [c for c in coloring if not c.discrete()]:
362 for node in c.nodes:
363 yield node, c
364
365 def _refine(self, coloring: List[Color], sequence: List[Color]) -> List[Color]:
366 sequence = sorted(sequence, key=lambda x: x.key(), reverse=True)
367 coloring = coloring[:]
368 while len(sequence) > 0 and not self._discrete(coloring):
369 W = sequence.pop() # noqa: N806
370 for c in coloring[:]:
371 if len(c.nodes) > 1 or isinstance(c.nodes[0], BNode):
372 colors = sorted(
373 c.distinguish(W, self.graph),
374 key=lambda x: x.key(),
375 reverse=True,
376 )
377 coloring.remove(c)
378 coloring.extend(colors)
379 try:
380 si = sequence.index(c)
381 sequence = sequence[:si] + colors + sequence[si + 1 :]
382 except ValueError:
383 sequence = colors[1:] + sequence
384 combined_colors: List[Color] = []
385 combined_color_map: Dict[str, Color] = dict()
386 for color in coloring:
387 color_hash = color.hash_color()
388 # This is a hash collision, and be combined into a single color for individuation.
389 if color_hash in combined_color_map:
390 combined_color_map[color_hash].nodes.extend(color.nodes)
391 else:
392 combined_colors.append(color)
393 combined_color_map[color_hash] = color
394 return combined_colors
395
396 @_runtime("to_hash_runtime")
397 def to_hash(self, stats: Optional[Stats] = None):
398 result = 0
399 for triple in self.canonical_triples(stats=stats):
400 result += self.hashfunc(" ".join([x.n3() for x in triple]))
401 if stats is not None:
402 stats["graph_digest"] = "%x" % result
403 return result
404
405 def _experimental_path(self, coloring: List[Color]) -> List[Color]:
406 coloring = [c.copy() for c in coloring]
407 while not self._discrete(coloring):
408 color = [x for x in coloring if not x.discrete()][0]
409 node = color.nodes[0]
410 new_color = self._individuate(color, node)
411 coloring.append(new_color)
412 coloring = self._refine(coloring, [new_color])
413 return coloring
414
415 def _create_generator(
416 self,
417 colorings: List[List[Color]],
418 groupings: Optional[Dict[Node, Set[Node]]] = None,
419 ) -> Dict[Node, Set[Node]]:
420 if not groupings:
421 groupings = defaultdict(set)
422 for group in zip(*colorings):
423 g = set([c.nodes[0] for c in group])
424 for n in group:
425 g |= groupings[n]
426 for n in g:
427 groupings[n] = g
428 return groupings
429
430 @_call_count("individuations")
431 def _traces(
432 self,
433 coloring: List[Color],
434 stats: Optional[Stats] = None,
435 depth: List[int] = [0],
436 ) -> List[Color]:
437 if stats is not None and "prunings" not in stats:
438 stats["prunings"] = 0
439 depth[0] += 1
440 candidates = self._get_candidates(coloring)
441 best: List[List[Color]] = []
442 best_score = None
443 best_experimental_score = None
444 last_coloring = None
445 generator: Dict[Node, Set[Node]] = defaultdict(set)
446 visited: Set[Node] = set()
447 for candidate, color in candidates:
448 if candidate in generator:
449 v = generator[candidate] & visited
450 if len(v) > 0:
451 visited.add(candidate)
452 continue
453 visited.add(candidate)
454 coloring_copy: List[Color] = []
455 color_copy = None
456 for c in coloring:
457 c_copy = c.copy()
458 coloring_copy.append(c_copy)
459 if c == color:
460 color_copy = c_copy
461 new_color = self._individuate(color_copy, candidate)
462 coloring_copy.append(new_color)
463 refined_coloring = self._refine(coloring_copy, [new_color])
464 color_score = tuple([c.key() for c in refined_coloring])
465 experimental = self._experimental_path(coloring_copy)
466 experimental_score = set([c.key() for c in experimental])
467 if last_coloring:
468 # type error: Statement is unreachable
469 generator = self._create_generator( # type: ignore[unreachable]
470 [last_coloring, experimental], generator
471 )
472 last_coloring = experimental
473 if best_score is None or best_score < color_score: # type: ignore[unreachable]
474 best = [refined_coloring]
475 best_score = color_score
476 best_experimental_score = experimental_score
477 elif best_score > color_score: # type: ignore[unreachable]
478 # prune this branch.
479 if stats is not None and isinstance(stats["prunings"], int):
480 stats["prunings"] += 1
481 elif experimental_score != best_experimental_score:
482 best.append(refined_coloring)
483 else:
484 # prune this branch.
485 if stats is not None and isinstance(stats["prunings"], int):
486 stats["prunings"] += 1
487 discrete: List[List[Color]] = [x for x in best if self._discrete(x)]
488 if len(discrete) == 0:
489 best_score = None
490 best_depth = None
491 for coloring in best:
492 d = [depth[0]]
493 new_color = self._traces(coloring, stats=stats, depth=d)
494 color_score = tuple([c.key() for c in refined_coloring])
495 if best_score is None or color_score > best_score: # type: ignore[unreachable]
496 discrete = [new_color]
497 best_score = color_score
498 best_depth = d[0]
499 depth[0] = best_depth # type: ignore[assignment]
500 return discrete[0]
501
502 def canonical_triples(self, stats: Optional[Stats] = None):
503 if stats is not None:
504 start_coloring = datetime.now()
505 coloring = self._initial_color()
506 if stats is not None:
507 stats["triple_count"] = len(self.graph)
508 stats["adjacent_nodes"] = max(0, len(coloring) - 1)
509 coloring = self._refine(coloring, coloring[:])
510 if stats is not None:
511 stats["initial_coloring_runtime"] = _total_seconds(
512 datetime.now() - start_coloring
513 )
514 stats["initial_color_count"] = len(coloring)
515
516 if not self._discrete(coloring):
517 depth = [0]
518 coloring = self._traces(coloring, stats=stats, depth=depth)
519 if stats is not None:
520 stats["tree_depth"] = depth[0]
521 elif stats is not None:
522 stats["individuations"] = 0
523 stats["tree_depth"] = 0
524 if stats is not None:
525 stats["color_count"] = len(coloring)
526
527 bnode_labels: Dict[Node, str] = dict(
528 [(c.nodes[0], c.hash_color()) for c in coloring]
529 )
530 if stats is not None:
531 stats["canonicalize_triples_runtime"] = _total_seconds(
532 datetime.now() - start_coloring
533 )
534 for triple in self.graph:
535 result = tuple(self._canonicalize_bnodes(triple, bnode_labels))
536 yield result
537
538 def _canonicalize_bnodes(
539 self,
540 triple: _TripleType,
541 labels: Dict[Node, str],
542 ):
543 for term in triple:
544 if isinstance(term, BNode):
545 yield BNode(value="cb%s" % labels[term])
546 else:
547 yield term
548
549
550def to_isomorphic(graph: Graph) -> IsomorphicGraph:
551 if isinstance(graph, IsomorphicGraph):
552 return graph
553 result = IsomorphicGraph()
554 if hasattr(graph, "identifier"):
555 result = IsomorphicGraph(identifier=graph.identifier)
556 result += graph
557 return result
558
559
560def isomorphic(graph1: Graph, graph2: Graph) -> bool:
561 """Compare graph for equality.
562
563 Uses an algorithm to compute unique hashes which takes bnodes into account.
564
565 Example:
566 ```python
567 >>> g1 = Graph().parse(format='n3', data='''
568 ... @prefix : <http://example.org/ns#> .
569 ... <http://example.org> :rel <http://example.org/a> .
570 ... <http://example.org> :rel <http://example.org/b> .
571 ... <http://example.org> :rel [ :label "A bnode." ] .
572 ... ''')
573 >>> g2 = Graph().parse(format='n3', data='''
574 ... @prefix ns: <http://example.org/ns#> .
575 ... <http://example.org> ns:rel [ ns:label "A bnode." ] .
576 ... <http://example.org> ns:rel <http://example.org/b>,
577 ... <http://example.org/a> .
578 ... ''')
579 >>> isomorphic(g1, g2)
580 True
581 >>> g3 = Graph().parse(format='n3', data='''
582 ... @prefix : <http://example.org/ns#> .
583 ... <http://example.org> :rel <http://example.org/a> .
584 ... <http://example.org> :rel <http://example.org/b> .
585 ... <http://example.org> :rel <http://example.org/c> .
586 ... ''')
587 >>> isomorphic(g1, g3)
588 False
589
590 ```
591 """
592 gd1 = _TripleCanonicalizer(graph1).to_hash()
593 gd2 = _TripleCanonicalizer(graph2).to_hash()
594 return gd1 == gd2
595
596
597def to_canonical_graph(
598 g1: Graph, stats: Optional[Stats] = None
599) -> ReadOnlyGraphAggregate:
600 """Creates a canonical, read-only graph.
601
602 Creates a canonical, read-only graph where all bnode id:s are based on
603 deterministical SHA-256 checksums, correlated with the graph contents.
604 """
605 graph = Graph()
606 graph += _TripleCanonicalizer(g1).canonical_triples(stats=stats)
607 return ReadOnlyGraphAggregate([graph])
608
609
610def graph_diff(g1: Graph, g2: Graph) -> Tuple[Graph, Graph, Graph]:
611 """Returns three sets of triples: "in both", "in first" and "in second"."""
612 # bnodes have deterministic values in canonical graphs:
613 cg1 = to_canonical_graph(g1)
614 cg2 = to_canonical_graph(g2)
615 in_both = cg1 * cg2
616 in_first = cg1 - cg2
617 in_second = cg2 - cg1
618 return (in_both, in_first, in_second)
619
620
621_MOCK_BNODE = BNode()
622
623
624def similar(g1: Graph, g2: Graph):
625 """Checks if the two graphs are "similar".
626
627 Checks if the two graphs are "similar", by comparing sorted triples where
628 all bnodes have been replaced by a singular mock bnode (the
629 `_MOCK_BNODE`).
630
631 This is a much cheaper, but less reliable, alternative to the comparison
632 algorithm in `isomorphic`.
633 """
634 return all(t1 == t2 for (t1, t2) in _squashed_graphs_triples(g1, g2))
635
636
637def _squashed_graphs_triples(g1: Graph, g2: Graph):
638 for t1, t2 in zip(sorted(_squash_graph(g1)), sorted(_squash_graph(g2))):
639 yield t1, t2
640
641
642def _squash_graph(graph: Graph):
643 return (_squash_bnodes(triple) for triple in graph)
644
645
646def _squash_bnodes(triple):
647 return tuple((isinstance(t, BNode) and _MOCK_BNODE) or t for t in triple)