--- a/env/lib/python3.7/site-packages/rdflib/compare.py	Thu May 14 16:47:39 2020 -0400
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,562 +0,0 @@
-# -*- coding: utf-8 -*-
-"""
-A collection of utilities for canonicalizing and inspecting graphs.
-
-Among other things, they solve of the problem of deterministic bnode
-comparisons.
-
-Warning: the time to canonicalize bnodes may increase exponentially on
-degenerate larger graphs. Use with care!
-
-Example of comparing two graphs::
-
-    >>> g1 = Graph().parse(format='n3', data='''
-    ...     @prefix : <http://example.org/ns#> .
-    ...     <http://example.org> :rel
-    ...         <http://example.org/same>,
-    ...         [ :label "Same" ],
-    ...         <http://example.org/a>,
-    ...         [ :label "A" ] .
-    ... ''')
-    >>> g2 = Graph().parse(format='n3', data='''
-    ...     @prefix : <http://example.org/ns#> .
-    ...     <http://example.org> :rel
-    ...         <http://example.org/same>,
-    ...         [ :label "Same" ],
-    ...         <http://example.org/b>,
-    ...         [ :label "B" ] .
-    ... ''')
-    >>>
-    >>> iso1 = to_isomorphic(g1)
-    >>> iso2 = to_isomorphic(g2)
-
-These are not isomorphic::
-
-    >>> iso1 == iso2
-    False
-
-Diff the two graphs::
-
-    >>> in_both, in_first, in_second = graph_diff(iso1, iso2)
-
-Present in both::
-
-    >>> def dump_nt_sorted(g):
-    ...     for l in sorted(g.serialize(format='nt').splitlines()):
-    ...         if l: print(l.decode('ascii'))
-
-    >>> dump_nt_sorted(in_both) #doctest: +SKIP
-    <http://example.org>
-        <http://example.org/ns#rel> <http://example.org/same> .
-    <http://example.org>
-        <http://example.org/ns#rel> _:cbcaabaaba17fecbc304a64f8edee4335e .
-    _:cbcaabaaba17fecbc304a64f8edee4335e
-        <http://example.org/ns#label> "Same" .
-
-Only in first::
-
-    >>> dump_nt_sorted(in_first) #doctest: +SKIP
-    <http://example.org>
-        <http://example.org/ns#rel> <http://example.org/a> .
-    <http://example.org>
-        <http://example.org/ns#rel> _:cb124e4c6da0579f810c0ffe4eff485bd9 .
-    _:cb124e4c6da0579f810c0ffe4eff485bd9
-        <http://example.org/ns#label> "A" .
-
-Only in second::
-
-    >>> dump_nt_sorted(in_second) #doctest: +SKIP
-    <http://example.org>
-        <http://example.org/ns#rel> <http://example.org/b> .
-    <http://example.org>
-        <http://example.org/ns#rel> _:cb558f30e21ddfc05ca53108348338ade8 .
-    _:cb558f30e21ddfc05ca53108348338ade8
-        <http://example.org/ns#label> "B" .
-"""
-
-
-# TODO:
-# - Doesn't handle quads.
-# - Add warning and/or safety mechanism before working on large graphs?
-# - use this in existing Graph.isomorphic?
-
-__all__ = ['IsomorphicGraph', 'to_isomorphic', 'isomorphic',
-           'to_canonical_graph', 'graph_diff', 'similar']
-
-from rdflib.graph import Graph, ConjunctiveGraph, ReadOnlyGraphAggregate
-from rdflib.term import BNode, Node
-try:
-    import hashlib
-    sha256 = hashlib.sha256
-except ImportError:
-    # for Python << 2.5
-    import sha256
-    sha256 = sha256.new
-
-from datetime import datetime
-from collections import defaultdict
-
-
-def _total_seconds(td):
-    result = td.days * 24 * 60 * 60
-    result += td.seconds
-    result += td.microseconds / 1000000.0
-    return result
-
-
-class _runtime(object):
-    def __init__(self, label):
-        self.label = label
-
-    def __call__(self, f):
-        if self.label is None:
-            self.label = f.__name__ + "_runtime"
-
-        def wrapped_f(*args, **kwargs):
-            start = datetime.now()
-            result = f(*args, **kwargs)
-            if 'stats' in kwargs and kwargs['stats'] is not None:
-                stats = kwargs['stats']
-                stats[self.label] = _total_seconds(datetime.now() - start)
-            return result
-        return wrapped_f
-
-
-class _call_count(object):
-    def __init__(self, label):
-        self.label = label
-
-    def __call__(self, f):
-        if self.label is None:
-            self.label = f.__name__ + "_runtime"
-
-        def wrapped_f(*args, **kwargs):
-            if 'stats' in kwargs and kwargs['stats'] is not None:
-                stats = kwargs['stats']
-                if self.label not in stats:
-                    stats[self.label] = 0
-                stats[self.label] += 1
-            return f(*args, **kwargs)
-        return wrapped_f
-
-
-class IsomorphicGraph(ConjunctiveGraph):
-    """An implementation of the RGDA1 graph digest algorithm.
-
-    An implementation of RGDA1 (publication below),
-    a combination of Sayers & Karp's graph digest algorithm using
-    sum and SHA-256 <http://www.hpl.hp.com/techreports/2003/HPL-2003-235R1.pdf>
-    and traces <http://pallini.di.uniroma1.it>, an average case
-    polynomial time algorithm for graph canonicalization.
-    
-    McCusker, J. P. (2015). WebSig: A Digital Signature Framework for the Web.
-    Rensselaer Polytechnic Institute, Troy, NY.
-    http://gradworks.umi.com/3727015.pdf
-    """
-
-    def __init__(self, **kwargs):
-        super(IsomorphicGraph, self).__init__(**kwargs)
-
-    def __eq__(self, other):
-        """Graph isomorphism testing."""
-        if not isinstance(other, IsomorphicGraph):
-            return False
-        elif len(self) != len(other):
-            return False
-        return self.internal_hash() == other.internal_hash()
-
-    def __ne__(self, other):
-        """Negative graph isomorphism testing."""
-        return not self.__eq__(other)
-
-    def graph_digest(self, stats=None):
-        """Synonym for IsomorphicGraph.internal_hash."""
-        return self.internal_hash(stats=stats)
-
-    def internal_hash(self, stats=None):
-        """
-        This is defined instead of __hash__ to avoid a circular recursion
-        scenario with the Memory store for rdflib which requires a hash lookup
-        in order to return a generator of triples.
-        """
-        return _TripleCanonicalizer(self).to_hash(stats=stats)
-
-
-class Color:
-    def __init__(self, nodes, hashfunc, color=(), hash_cache=None):
-        if hash_cache is None:
-            hash_cache = {}
-        self._hash_cache = hash_cache
-        self.color = color
-        self.nodes = nodes
-        self.hashfunc = hashfunc
-        self._hash_color = None
-
-    def key(self):
-        return (len(self.nodes), self.hash_color())
-
-    def hash_color(self, color=None):
-        if color is None:
-            color = self.color
-        if color in self._hash_cache:
-            return self._hash_cache[color]
-
-        def stringify(x):
-            if isinstance(x, Node):
-                return x.n3()
-            else:
-                return str(x)
-        if isinstance(color, Node):
-            return stringify(color)
-        value = 0
-        for triple in color:
-            value += self.hashfunc(' '.join([stringify(x) for x in triple]))
-        val = "%x" % value
-        self._hash_cache[color] = val
-        return val
-
-    def distinguish(self, W, graph):
-        colors = {}
-        for n in self.nodes:
-            new_color = list(self.color)
-            for node in W.nodes:
-                new_color += [
-                    (1, p, W.hash_color())
-                    for s, p, o in graph.triples((n, None, node))]
-                new_color += [
-                    (W.hash_color(), p, 3)
-                    for s, p, o in graph.triples((node, None, n))]
-            new_color = tuple(new_color)
-            new_hash_color = self.hash_color(new_color)
-
-            if new_hash_color not in colors:
-                c = Color(
-                    [], self.hashfunc, new_color,
-                    hash_cache=self._hash_cache)
-                colors[new_hash_color] = c
-            colors[new_hash_color].nodes.append(n)
-        return list(colors.values())
-
-    def discrete(self):
-        return len(self.nodes) == 1
-
-    def copy(self):
-        return Color(
-            self.nodes[:], self.hashfunc, self.color,
-            hash_cache=self._hash_cache)
-
-
-class _TripleCanonicalizer(object):
-
-    def __init__(self, graph, hashfunc=sha256):
-        self.graph = graph
-
-        def _hashfunc(s):
-            h = hashfunc()
-            h.update(str(s).encode("utf8"))
-            return int(h.hexdigest(), 16)
-        self._hash_cache = {}
-        self.hashfunc = _hashfunc
-
-
-    def _discrete(self, coloring):
-        return len([c for c in coloring if not c.discrete()]) == 0
-
-
-    def _initial_color(self):
-        """Finds an initial color for the graph.
-
-        Finds an initial color fo the graph by finding all blank nodes and
-        non-blank nodes that are adjacent. Nodes that are not adjacent to blank
-        nodes are not included, as they are a) already colored (by URI or literal)
-        and b) do not factor into the color of any blank node.
-        """
-        bnodes = set()
-        others = set()
-        self._neighbors = defaultdict(set)
-        for s, p, o in self.graph:
-            nodes = set([s, o])
-            b = set([x for x in nodes if isinstance(x, BNode)])
-            if len(b) > 0:
-                others |= nodes - b
-                bnodes |= b
-                if isinstance(s, BNode):
-                    self._neighbors[s].add(o)
-                if isinstance(o, BNode):
-                    self._neighbors[o].add(s)
-        if len(bnodes) > 0:
-            return [
-                    Color(list(bnodes), self.hashfunc, hash_cache=self._hash_cache)
-                ] + [
-                    Color([x], self.hashfunc, x, hash_cache=self._hash_cache)
-                    for x in others
-                ]
-        else:
-            return []
-
-    def _individuate(self, color, individual):
-        new_color = list(color.color)
-        new_color.append((len(color.nodes),))
-
-        color.nodes.remove(individual)
-        c = Color([individual], self.hashfunc, tuple(new_color),
-                  hash_cache=self._hash_cache)
-        return c
-
-    def _get_candidates(self, coloring):
-        candidates = [c for c in coloring if not c.discrete()]
-        for c in [c for c in coloring if not c.discrete()]:
-            for node in c.nodes:
-                yield node, c
-
-    def _refine(self, coloring, sequence):
-        sequence = sorted(sequence, key=lambda x: x.key(), reverse=True)
-        coloring = coloring[:]
-        while len(sequence) > 0 and not self._discrete(coloring):
-            W = sequence.pop()
-            for c in coloring[:]:
-                if len(c.nodes) > 1:
-                    colors = sorted(c.distinguish(W, self.graph),
-                                    key=lambda x: x.key(),
-                                    reverse=True)
-                    coloring.remove(c)
-                    coloring.extend(colors)
-                    try:
-                        si = sequence.index(c)
-                        sequence = sequence[:si] + colors + sequence[si+1:]
-                    except ValueError:
-                        sequence = colors[1:] + sequence
-
-        return coloring
-
-    @_runtime("to_hash_runtime")
-    def to_hash(self, stats=None):
-        result = 0
-        for triple in self.canonical_triples(stats=stats):
-            result += self.hashfunc(' '.join([x.n3() for x in triple]))
-        if stats is not None:
-            stats['graph_digest'] = "%x" % result
-        return result
-
-    def _experimental_path(self, coloring):
-        coloring = [c.copy() for c in coloring]
-        while not self._discrete(coloring):
-            color = [x for x in coloring if not x.discrete()][0]
-            node = color.nodes[0]
-            new_color = self._individuate(color, node)
-            coloring.append(new_color)
-            coloring = self._refine(coloring, [new_color])
-        return coloring
-
-    def _create_generator(self, colorings, groupings=None):
-        if not groupings:
-            groupings = defaultdict(set)
-        for group in zip(*colorings):
-            g = set([c.nodes[0] for c in group])
-            for n in group:
-                g |= groupings[n]
-            for n in g:
-                groupings[n] = g
-        return groupings
-
-    @_call_count("individuations")
-    def _traces(self, coloring, stats=None, depth=[0]):
-        if stats is not None and 'prunings' not in stats:
-            stats['prunings'] = 0
-        depth[0] += 1
-        candidates = self._get_candidates(coloring)
-        best = []
-        best_score = None
-        best_experimental = None
-        best_experimental_score = None
-        last_coloring = None
-        generator = defaultdict(set)
-        visited = set()
-        for candidate, color in candidates:
-            if candidate in generator:
-                v = generator[candidate] & visited
-                if len(v) > 0:
-                    visited.add(candidate)
-                    continue
-            visited.add(candidate)
-            coloring_copy = []
-            color_copy = None
-            for c in coloring:
-                c_copy = c.copy()
-                coloring_copy.append(c_copy)
-                if c == color:
-                    color_copy = c_copy
-            new_color = self._individuate(color_copy, candidate)
-            coloring_copy.append(new_color)
-            refined_coloring = self._refine(coloring_copy, [new_color])
-            color_score = tuple([c.key() for c in refined_coloring])
-            experimental = self._experimental_path(coloring_copy)
-            experimental_score = set([c.key() for c in experimental])
-            if last_coloring:
-                generator = self._create_generator(
-                    [last_coloring, experimental],
-                    generator)
-            last_coloring = experimental
-            if best_score is None or best_score < color_score:
-                best = [refined_coloring]
-                best_score = color_score
-                best_experimental = experimental
-                best_experimental_score = experimental_score
-            elif best_score > color_score:
-                # prune this branch.
-                if stats is not None:
-                    stats['prunings'] += 1
-            elif experimental_score != best_experimental_score:
-                best.append(refined_coloring)
-            else:
-                # prune this branch.
-                if stats is not None:
-                    stats['prunings'] += 1
-        discrete = [x for x in best if self._discrete(x)]
-        if len(discrete) == 0:
-            best_score = None
-            best_depth = None
-            for coloring in best:
-                d = [depth[0]]
-                new_color = self._traces(coloring, stats=stats, depth=d)
-                color_score = tuple([c.key() for c in refined_coloring])
-                if best_score is None or color_score > best_score:
-                    discrete = [new_color]
-                    best_score = color_score
-                    best_depth = d[0]
-            depth[0] = best_depth
-        return discrete[0]
-
-    def canonical_triples(self, stats=None):
-        if stats is not None:
-            start_canonicalization = datetime.now()
-        if stats is not None:
-            start_coloring = datetime.now()
-        coloring = self._initial_color()
-        if stats is not None:
-            stats['triple_count'] = len(self.graph)
-            stats['adjacent_nodes'] = max(0, len(coloring) - 1)
-        coloring = self._refine(coloring, coloring[:])
-        if stats is not None:
-            stats['initial_coloring_runtime'] = _total_seconds(datetime.now() - start_coloring)
-            stats['initial_color_count'] = len(coloring)
-
-        if not self._discrete(coloring):
-            depth = [0]
-            coloring = self._traces(coloring, stats=stats, depth=depth)
-            if stats is not None:
-                stats['tree_depth'] = depth[0]
-        elif stats is not None:
-            stats['individuations'] = 0
-            stats['tree_depth'] = 0
-        if stats is not None:
-            stats['color_count'] = len(coloring)
-
-        bnode_labels = dict([(c.nodes[0], c.hash_color()) for c in coloring])
-        if stats is not None:
-            stats["canonicalize_triples_runtime"] = _total_seconds(datetime.now() - start_coloring)
-        for triple in self.graph:
-            result = tuple(self._canonicalize_bnodes(triple, bnode_labels))
-            yield result
-
-    def _canonicalize_bnodes(self, triple, labels):
-        for term in triple:
-            if isinstance(term, BNode):
-                yield BNode(value="cb%s" % labels[term])
-            else:
-                yield term
-
-
-def to_isomorphic(graph):
-    if isinstance(graph, IsomorphicGraph):
-        return graph
-    return IsomorphicGraph(store=graph.store)
-
-
-def isomorphic(graph1, graph2):
-    """Compare graph for equality.
-
-    Uses an algorithm to compute unique hashes which takes bnodes into account.
-
-    Examples::
-
-        >>> g1 = Graph().parse(format='n3', data='''
-        ...     @prefix : <http://example.org/ns#> .
-        ...     <http://example.org> :rel <http://example.org/a> .
-        ...     <http://example.org> :rel <http://example.org/b> .
-        ...     <http://example.org> :rel [ :label "A bnode." ] .
-        ... ''')
-        >>> g2 = Graph().parse(format='n3', data='''
-        ...     @prefix ns: <http://example.org/ns#> .
-        ...     <http://example.org> ns:rel [ ns:label "A bnode." ] .
-        ...     <http://example.org> ns:rel <http://example.org/b>,
-        ...             <http://example.org/a> .
-        ... ''')
-        >>> isomorphic(g1, g2)
-        True
-
-        >>> g3 = Graph().parse(format='n3', data='''
-        ...     @prefix : <http://example.org/ns#> .
-        ...     <http://example.org> :rel <http://example.org/a> .
-        ...     <http://example.org> :rel <http://example.org/b> .
-        ...     <http://example.org> :rel <http://example.org/c> .
-        ... ''')
-        >>> isomorphic(g1, g3)
-        False
-    """
-    gd1 = _TripleCanonicalizer(graph1).to_hash()
-    gd2 = _TripleCanonicalizer(graph2).to_hash()
-    return gd1 == gd2
-
-
-
-def to_canonical_graph(g1):
-    """Creates a canonical, read-only graph.
-
-    Creates a canonical, read-only graph where all bnode id:s are based on
-    deterministical SHA-256 checksums, correlated with the graph contents.
-    """
-    graph = Graph()
-    graph += _TripleCanonicalizer(g1).canonical_triples()
-    return ReadOnlyGraphAggregate([graph])
-
-
-def graph_diff(g1, g2):
-    """Returns three sets of triples: "in both", "in first" and "in second"."""
-    # bnodes have deterministic values in canonical graphs:
-    cg1 = to_canonical_graph(g1)
-    cg2 = to_canonical_graph(g2)
-    in_both = cg1 * cg2
-    in_first = cg1 - cg2
-    in_second = cg2 - cg1
-    return (in_both, in_first, in_second)
-
-
-
-_MOCK_BNODE = BNode()
-
-
-def similar(g1, g2):
-    """Checks if the two graphs are "similar".
-
-    Checks if the two graphs are "similar", by comparing sorted triples where
-    all bnodes have been replaced by a singular mock bnode (the
-    ``_MOCK_BNODE``).
-
-    This is a much cheaper, but less reliable, alternative to the comparison
-    algorithm in ``isomorphic``.
-    """
-    return all(t1 == t2 for (t1, t2) in _squashed_graphs_triples(g1, g2))
-
-
-def _squashed_graphs_triples(g1, g2):
-    for (t1, t2) in zip(sorted(_squash_graph(g1)), sorted(_squash_graph(g2))):
-        yield t1, t2
-
-
-def _squash_graph(graph):
-    return (_squash_bnodes(triple) for triple in graph)
-
-
-def _squash_bnodes(triple):
-    return tuple((isinstance(t, BNode) and _MOCK_BNODE) or t for t in triple)