Source code

Download source archive ↓

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)