class Rule(object):
    """Class representing rewriting rules.

    A rewriting rule consists of the three graphs:
    `p` -- preserved part (or interface), `lhs` -- left hand side,
    `rhs` -- right hand side, and two mappings:
    from `p` to `lhs` and from `p` to `rhs`.
    Informally, `lhs` represents a pattern to match
    in a graph, subject to rewriting. `p` together with
    `p` -> `lhs` mapping specifies a part of
    the pattern which stays preseved during rewriting,
    i.e. all the nodes/edges/attributes present
    in `lhs` but not `p` will be removed.
    `rhs` and `p` -> `rhs` specify nodes/edges/attributes
    to add to the `p`. In addition, rules defined
    is such a way allow to clone and merge nodes.
    If two nodes from `p` map to the same node in `lhs`,
    the node corresponding to this node of the
    pattern will be cloned. Symmetrically, if two nodes
    from `p` map to the same node in `rhs`,
    the corresponding two nodes will be merged.

    Attributes
    ----------
    p : regaph.graphs.Graph
        Preserved part of the rule
    lhs : regaph.graphs.Graph
        Left-hand side (pattern) of the rule
    rhs : regaph.graphs.Graph
        Right-hand side of the rule
    p_lhs : dict
        Homomorphism between `p` and `lhs` given by
        a dictionary with keys -- nodes of `p`,
        values -- nodes of `lhs`.
    p_rhs : dict
        Homomorphism between `p` and `rhs` given by
        a dictionary with keys -- nodes of `p`,
        values -- nodes of `rhs`.
    """

    def __init__(self, p=None, lhs=None, rhs=None,
                 p_lhs=None, p_rhs=None):
        """Rule initialization.

        A rule is initialized with p, lhs, rhs graphs, and
        p -> lhs & p -> rhs homomorphisms, these homomorphisms
        are checked to be valid ones (edge and attribute preserving).
        By default the homomorphisms p -> lhs & p -> rhs are None,
        in this case they are initialized as the identity homomorphism
        (id(p)).

        Parameters
        ----------
        p : regaph.graphs.Graph
            Preserved part of the rule
        lhs : regaph.graphs.Graph
            Left-hand side (pattern) of the rule
        rhs : regaph.graphs.Graph
            Right-hand side of the rule
        p_lhs : dict
            Homomorphism between `p` and `lhs` given by
            a dictionary with keys -- nodes of `p`,
            values -- nodes of `lhs`
        p_rhs : dict
            Homomorphism between `p` and `rhs` given by
            a dictionary with keys -- nodes of `p`,
            values -- nodes of `rhs`
        """
        if p is None:
            p = NXGraph()
        if lhs is None:
            lhs = p
        if rhs is None:
            rhs = p

        self.p = NXGraph.copy(p)
        self.lhs = NXGraph.copy(lhs)
        self.rhs = NXGraph.copy(rhs)

        if not p_lhs:
            self.p_lhs = identity(p, lhs)
        else:
            check_homomorphism(p, lhs, p_lhs)
            self.p_lhs = copy.deepcopy(p_lhs)

        if not p_rhs:
            self.p_rhs = identity(p, rhs)
        else:
            check_homomorphism(p, rhs, p_rhs)
            self.p_rhs = copy.deepcopy(p_rhs)

        return

    @classmethod
    def from_transform(cls, pattern, commands=None):
        """Initialize a rule from the transformation.

        On input takes a pattern which is used as `lhs` of the rule,
        as an optional argument transformation commands can be provided,
        by default the list of commands is empty and all `p`, `lhs` and `rhs`
        are initialized to be the same graph (pattern), later on
        when transformations are applied `p` and `rhs` are being updated.
        If list of commands is specified, these commands are simplified,
        transformed to the canonical order, and applied to `p`, `lhs` and `rhs`.

        Parameters
        ----------
        pattern : networkx.(Di)Graph
            Pattern graph to initialize and the lhs of the rule.
        commands : str, optional
            Script containing transformation commands, which
            can be parsed by `regraph.parser.parse`.

        """
        if not isinstance(pattern, NXGraph):
            RuleError(
                "The initial pattern should be an instance of NXGraph")

        lhs = pattern

        p = NXGraph.copy(lhs)
        rhs = NXGraph.copy(lhs)

        p_lhs = dict([(n, n) for n in pattern.nodes()])
        p_rhs = dict([(n, n) for n in pattern.nodes()])

        rule = cls(p, lhs, rhs, p_lhs, p_rhs)

        # if the commands are provided, perform respecitive transformations
        if commands:
            # 1. make the commands canonical
            # commands = make_canonical_commands(p, commands, True)
            # 2. apply the commands

            command_strings = [
                c for b in commands if len(b) > 0 for c in b.splitlines()
            ]

            actions = []
            for command in command_strings:
                try:
                    parsed = parser.parseString(command).asDict()
                    actions.append(parsed)
                except:
                    raise ParsingError("Cannot parse command '%s'" % command)

            for action in actions:
                if action["keyword"] == "clone":
                    node_name = None
                    if "node_name" in action.keys():
                        node_name = action["node_name"]
                    rule.inject_clone_node(action["node"], node_name)
                elif action["keyword"] == "merge":
                    node_name = None
                    if "node_name" in action.keys():
                        node_name = action["node_name"]
                    rule.inject_merge_nodes(
                        action["nodes"],
                        node_name)
                elif action["keyword"] == "add_node":
                    name = None
                    attrs = {}
                    if "node" in action.keys():
                        name = action["node"]
                    if "attributes" in action.keys():
                        attrs = action["attributes"]
                    rule.inject_add_node(name, attrs)
                elif action["keyword"] == "delete_node":
                    rule.inject_remove_node(action["node"])
                elif action["keyword"] == "add_edge":
                    attrs = {}
                    if "attributes" in action.keys():
                        attrs = action["attributes"]
                    rule.inject_add_edge(
                        action["node_1"],
                        action["node_2"],
                        attrs)
                elif action["keyword"] == "delete_edge":
                    rule.inject_remove_edge(
                        action["node_1"],
                        action["node_2"])
                elif action["keyword"] == "add_node_attrs":
                    rule.inject_add_node_attrs(
                        action["node"],
                        action["attributes"])
                elif action["keyword"] == "add_edge_attrs":
                    rule.inject_add_edge_attrs(
                        action["node_1"],
                        action["node_2"],
                        action["attributes"])
                elif action["keyword"] == "delete_node_attrs":
                    rule.inject_remove_node_attrs(
                        action["node"],
                        action["attributes"])
                elif action["keyword"] == "delete_edge_attrs":
                    rule.inject_remove_edge_attrs(
                        action["node_1"],
                        action["node_2"],
                        action["attributes"])
                else:
                    raise ParsingError("Unknown command %s" %
                                       action["keyword"])
        return rule

    def __eq__(self, rule):
        """Rule equality operator."""
        return (
            self.p == rule.p and
            self.lhs == rule.lhs and
            self.rhs == rule.rhs and
            self.p_lhs == rule.p_lhs and
            self.p_rhs == rule.p_rhs
        )

    def __str__(self):
        """String representation of a rule."""
        return (
            "Left hand side\n{}\n{}\n".format(
                self.lhs.nodes(data=True), self.lhs.edges(data=True)) +
            "Preserved part\n{}\n{}\n".format(
                self.p.nodes(data=True), self.p.edges(data=True)) +
            "Right hand side\n{}\n{}\n".format(
                self.rhs.nodes(data=True), self.rhs.edges(data=True)) +
            "P->L Homomorphism : {}\n".format(self.p_lhs) +
            "P->R Homomorphism : {}\n".format(self.p_rhs)
        )

    def inject_clone_node(self, n, new_node_id=None):
        """Inject cloning of a node by the rule.

        This procedure clones `n` in the preserved part
        and the right-hand side.

        Parameters
        ----------
        n : hashable
            Node from `lhs` to clone
        new_node_id : hashable
            Id for the clone

        Returns
        -------
        p_new_node_id : hashable
            Id of the new clone node in the preserved part
        rhs_new_node_id : hashable
            Id of the new clone node in the right-hand side


        Raises
        ------
        RuleError
            If the node to clone is already being removed by the rule
            or if node with the specified clone id already exists in p.
        """
        p_nodes = keys_by_value(self.p_lhs, n)
        if len(p_nodes) == 0:
            raise RuleError(
                "Cannot inject cloning: node '%s' is already "
                "being removed by the rule, revert its removal "
                "first" % n)
        else:
            if new_node_id is not None and new_node_id in self.p.nodes():
                raise RuleError(
                    "Node with id '%s' already exists in the "
                    "preserved part!")
            some_p_node = p_nodes[0]
            p_new_node_id = self.p.clone_node(some_p_node, new_node_id)
            self.p_lhs[p_new_node_id] = n

            # add it to the rhs
            # generate a new id for rhs
            rhs_new_node_id = self.rhs.clone_node(self.p_rhs[some_p_node])
            self.p_rhs[p_new_node_id] = rhs_new_node_id

        return (p_new_node_id, rhs_new_node_id)

    def inject_remove_node(self, p_node_id):
        """Inject a new node removal to the rule.

        This method removes the indicated node from `p`

        Parameters
        ----------
        p_node_id
            Id of the node in `p` that should be removed
            by the rule.
        """
        # remove corresponding nodes from p and rhs
        if p_node_id in self.p.nodes():
            self.p.remove_node(p_node_id)
        else:
            raise RuleError(
                "Node '{}' does not exist in the preserved part".format(
                    p_node_id))
        if self.p_rhs[p_node_id] in self.rhs.nodes():
            self.rhs.remove_node(self.p_rhs[p_node_id])
            affected_nodes = keys_by_value(self.p_rhs, self.p_rhs[p_node_id])
            for node in affected_nodes:
                del self.p_rhs[node]
            del self.p_lhs[p_node_id]
        return

    def inject_remove_edge(self, n1, n2):
        """Inject removal of an edge by the rule.

        Parameters
        ----------
        n1 : hashable
            Id of an edge's source node in `p`.
        n2 : hashable
            Id of an edge's target node in `p`.

        Raises
        ------
        RuleError
            If some of the nodes are not found in `p`,
            or if a corresponding edge in `p` does not exist.
        """

        if (n1, n2) in self.p.edges():
            self.p.remove_edge(n1, n2)
            self.rhs.remove_edge(self.p_rhs[n1], self.p_rhs[n2])
        else:
            raise RuleError(
                "Edge '{}->{}' does not exist in the preserved part".format(
                    n1, n2))

        return

    def inject_remove_node_attrs(self, n, attrs):
        """Inject a removal of node attrs by the rule.

        Parameters
        ----------
        n : hashable
            Id of a node whose attrs to remove (node from the
            preserved part).
        attrs : dict
            Dictionary with attributes to remove.

        Raises
        ------
        RuleError
            If `n` does not exist in the preserved part of the rule,
            or when the node whose attrs should be removed
            is itself is being removed by the rule.

        """
        if n not in self.p.nodes():
            raise RuleError(
                "Node '{}' does not exist in the preserved part".format(
                    n))

        self.p.remove_node_attrs(n, attrs)
        self.rhs.remove_node_attrs(self.p_rhs[n], attrs)
        return

    def inject_remove_edge_attrs(self, n1, n2, attrs):
        """Inject a removal of edge attrs by the rule.

        Parameters
        ----------
        n1 : hashable
            Id of an edge's source node in  `p`.
        n2 : hashable
            Id of an edge's target node in `p`.
        attrs : dict
            Dictionary with attributes to remove.

        Raises
        ------
        RuleError
            If edge `n1-> n2` does not exist in the preserved part of the rule,
            or when the node whose attrs should be removed
            is itself is being removed by the rule.

        """
        if n1 not in self.p.nodes():
            raise RuleError(
                "Node '{}' does not exist in the preserved "
                "part of the rule".format(n1)
            )
        if n2 not in self.p.nodes():
            raise RuleError(
                "Node '{}' does not exist in preserved "
                "part of the rule".format(n2)
            )

        if (n1, n2) not in self.p.edges():
            raise RuleError(
                "Edge '{}->{}' does not exist in the preserved "
                "part of the rule".format(n1, n2)
            )
        else:
            self.p.remove_edge_attrs(n1, n2, attrs)
            self.rhs.remove_edge_attrs(self.p_rhs[n1], self.p_rhs[n2], attrs)
        return

    def inject_add_node(self, node_id, attrs=None):
        """Inject an addition of a new node by the rule.

        This method adds a node with `node_id` (and the specified
        attributes `attrs`) to `rhs`.

        Parameters
        ----------
        node_id : hashable
            Id of a node to add
        attrs : dict, optional
            Attributes of the node.

        Raises
        ------
        RuleError
            If node with this id already exists in the `rhs`.
        """
        if node_id not in self.rhs.nodes():
            self.rhs.add_node(node_id, attrs)
        else:
            raise RuleError(
                "Node with the id '{}' already exists in the "
                "right hand side of the rule".format(node_id)
            )

    def inject_add_nodes_from(self, node_list):
        """Inject an addition of a new node by the rule.

        This method adds a nodes from the list (and the specified
        attributes `attrs`) to `rhs`.

        Parameters
        ----------
        node_list : iterable
            Collection of nodes to add, where every element is
            either a tuple of the form (<node_id>, <node_attrs>)
            or a single value <node_id>

        Raises
        ------
        RuleError
            If some node from the list already exists in the `rhs`.
        """
        for n in node_list:
            try:
                node_id, node_attrs = n
                self.inject_add_node(node_id, node_attrs)
            except (TypeError, ValueError):
                self.inject_add_node(node_id)
        return

    def inject_add_edge(self, n1, n2, attrs=None):
        """Inject addition of a new edge to the rule.

        This method adds an edge between two nodes of the
        `rhs`.

        Parameters
        ----------
        n1 : hashable
            Id of an edge's source node in `rhs`.
        n2 : hashable
            Id of an edge's target node in `rhs`.

        Raises
        ------
        RuleError
            If some of the nodes (`n1` or `n2`) do not exist
            or if there is already an edge between them in `rhs`.
        """
        if n1 not in self.rhs.nodes():
            raise RuleError(
                "Node with the id '{}' does not exist in the "
                "right-hand side of the rule".format(n1))
        if n2 not in self.rhs.nodes():
            raise RuleError(
                "Node with the id '{}' does not exist in the "
                "right-hand side of the rule".format(n2))
        if (n1, n2) in self.rhs.edges():
            raise RuleError(
                "Edge '{}->{}' already exists in the right-"
                "hand side of the rule".format(n1, n2)
            )
        self.rhs.add_edge(n1, n2, attrs)
        return

    def inject_add_edges_from(self, edge_list):
        """Inject addition of a new edge to the rule.

        This method injects addition of edges from the list.

        Parameters
        ----------
        edge_list : iterable
            Collection of edges to add, where every element is
            either a tuple of the form (<source_id>, <target_id>)
            or (<source_id>, <target_id>, <edge_attrs>). Here
            source and target nodes are assumed to be from the `rhs`.

        Raises
        ------
        RuleError
            If some of the nodes (`n1` or `n2`) do not exist
            or if there is already an edge between them in `rhs`.
        """
        for e in edge_list:
            if len(e) == 2:
                self.inject_add_edge(e[0], e[1])
            elif len(e) == 3:
                self.inject_add_edge(e[0], e[1], e[2])
            else:
                raise RuleError(
                    "Was expecting 2 or 3 elements per tuple, got {}.".format(
                        len(e))
                )

    def inject_merge_nodes(self, node_list, node_id=None):
        """Inject merge of a collection of nodes by the rule.

        Parameters
        ----------
        node_list : iterable
            Collection of ids of nodes from the preserved part.
        node_id : hashable
            Id of the new node corresponding to the result of merge.

        Returns
        -------
        new_name : hashable
            Id of the new node corresponding to the result of merge.

        Raises
        ------
        RuleError
            If a node with some id specified in `node_list` does not
            exist in the preserved part of the rule.
        """
        # Update graphs
        new_name = None

        nodes_to_merge = set()
        for n in node_list:
            if n in self.p.nodes():
                rhs_node = self.p_rhs[n]
            else:
                raise RuleError(
                    "Node with the id '{}' does not exist in the "
                    "preserved part of the rule".fromat(n)
                )
            nodes_to_merge.add(rhs_node)
        new_name = self.rhs.merge_nodes(
            list(nodes_to_merge),
            node_id=node_id
        )

        # Update mappings
        for n in node_list:
            if n in self.p.nodes():
                self.p_rhs[n] = new_name
        for r_node in nodes_to_merge:
            merged_ps = keys_by_value(self.p_rhs, r_node)
            for p in merged_ps:
                self.p_rhs[p] = new_name
        return new_name

    def inject_add_node_attrs(self, n, attrs):
        """Inject addition of  node attributes by the rule.

        Parameters
        ----------
        n : hashable
            Id of the node in the `rhs` to add attributes to.
        attrs : dict
            Dictionary with attrs to add

        Raises
        ------
        RuleError
            If node `n` does not exist in the rhs of the rule

        """
        if n not in self.rhs.nodes():
            raise RuleError(
                "Node '{}' exists in the RHS of the rule".format(n))

        self.rhs.add_node_attrs(n, attrs)
        return

    def inject_add_edge_attrs(self, n1, n2, attrs):
        """Inject addition of edge attributes by the rule.

        Parameters
        ----------
        n1 : hashable
            Source node in the RHS
        n2 : hashable
            Target node in the RHS
        attrs : dict
            Dictionary with attrs to add

        Raises
        ------
        RuleError
            If some of the nodes defining an edge are not found in neither
            `rhs`, or if an edge is incident to smth thats
            is going to be removed by the rule.
        """
        if (n1, n2) not in self.rhs.edges():
            raise RuleError(
                "Edge '{}->{}' does not exist in the "
                "right-hand side of the rule ".format(n1, n2)
            )
        self.rhs.add_edge_attrs(n1, n2, attrs)
        return

    def inject_update_node_attrs(self, n, attrs):
        """Inject an update of node attrs by the rule.

        Parameters
        ----------
        n : hashable
            Id of a node from the left-hand side whose attrs
            should be updated
        attrs : dict
            Dictionary of new attrs that will replace the old ones

        Raises
        ------
        RuleError
            If node `n` does not exist in the left-hand side or
            is being removed by the rule.
        """
        if n not in self.lhs.nodes():
            raise RuleError(
                "Node '%s' does not exist in the left hand "
                "side of the rule" % n)

        p_keys = keys_by_value(self.p_lhs, n)
        if len(p_keys) == 0:
            raise RuleError(
                "Node '%s' is being removed by the rule, "
                "cannot update attributes" % n)
        for k in p_keys:
            # self.p.node[k] = None
            self.p.set_node_attrs(k, {}, update=True)
            self.rhs.set_node_attrs(self.p_rhs[k], attrs, update=True)
        return

    def inject_update_edge_attrs(self, n1, n2, attrs):
        """Inject an update of edge attrs by the rule."""
        if n1 not in self.lhs.nodes():
            raise RuleError(
                "Node '%s' does not exist in the left hand side of the rule" %
                n1
            )
        if n2 not in self.lhs.nodes():
            raise RuleError(
                "Node '%s' does not exist in the left hand side of the rule" %
                n2
            )
        if (n1, n2) not in self.lhs.edges():
            raise RuleError(
                "Edge '%s->%s' does not exist in the left hand "
                "side of the rule" % (n1, n2)
            )

        p_keys_1 = keys_by_value(self.p_lhs, n1)
        p_keys_2 = keys_by_value(self.p_lhs, n2)

        if len(p_keys_1) == 0:
            raise RuleError(
                "Node '%s' is being removed by the rule, cannot update "
                "attributes from the incident edge" %
                n2
            )
        if len(p_keys_2) == 0:
            raise RuleError(
                "Node '%s' is being removed by the rule, cannot update "
                "attributes from the incident edge" %
                n1
            )
        for k1 in p_keys_1:
            for k2 in p_keys_2:
                self.p.update_edge_attrs(k1, k2, dict())
                self.rhs.update_edge_attrs(
                    self.p_rhs[k1],
                    self.p_rhs[k2],
                    attrs
                )
        return

    def to_json(self):
        """Convert the rule to JSON repr."""
        json_data = {}
        json_data["lhs"] = self.lhs.to_json()
        json_data["p"] = self.p.to_json()
        json_data["rhs"] = self.rhs.to_json()
        json_data["p_lhs"] = self.p_lhs
        json_data["p_rhs"] = self.p_rhs
        return json_data

    @classmethod
    def from_json(cls, json_data):
        """Create a rule obj from JSON repr."""
        lhs = NXGraph.from_json(json_data["lhs"])
        p = NXGraph.from_json(json_data["p"])
        rhs = NXGraph.from_json(json_data["rhs"])
        p_lhs = json_data["p_lhs"]
        p_rhs = json_data["p_rhs"]
        rule = cls(p, lhs, rhs, p_lhs, p_rhs)
        return rule

    # def apply_to(self, graph, instance=None, inplace=False):
    #     """Perform graph rewriting with the rule.

    #     Parameters
    #     ----------
    #     graph : nx.(Di)Graph
    #         Graph to rewrite with the rule.
    #     instance : dict
    #         Instance of the `lhs` pattern in the graph
    #         defined by a dictionary where keys are nodes
    #         of `lhs` and values are nodes of the graph.
    #     inplace : bool, optional
    #         If `True`, the rewriting will be performed
    #         in-place by applying primitve transformations
    #         to the graph object, otherwise the result of
    #         the rewriting is a new graph object.
    #         Default value is `False`.

    #     Returns
    #     -------
    #     g_prime : nx.(Di)Graph
    #         Result of the rewriting. If parameter
    #         `inplace` was `True`, `g_prime` is exactly
    #         the (transformed) input graph object `graph`.
    #     rhs_g_prime : dict
    #         Matching of the `rhs` in `g_prime`, a dictionary,
    #         where keys are nodes of `rhs` and values are
    #         nodes of `g_prime`.

    #     """
    #     if instance is None:
    #         instance = {
    #             n: n for n in self.lhs.nodes()
    #         }
    #     if isinstance(graph, nx.DiGraph):
    #         g_m, p_g_m, g_m_g = pullback_complement(
    #             self.p, self.lhs, graph, self.p_lhs, instance,
    #             inplace
    #         )
    #         g_prime, g_m_g_prime, rhs_g_prime = pushout(
    #             self.p, g_m, self.rhs, p_g_m, self.p_rhs, inplace)
    #     else:
    #         g_prime = graph
    #         rhs_g_prime = graph.rewrite(self, instance)

    #     return (g_prime, rhs_g_prime)
    def added_nodes(self):
        """Get nodes added by the rule.

        Returns
        -------
        nodes : set
            Set of nodes from `rhs` added by the rule.
        """
        nodes = set()
        for r_node in self.rhs.nodes():
            p_nodes = keys_by_value(self.p_rhs, r_node)
            if len(p_nodes) == 0:
                nodes.add(r_node)
        return nodes

    def added_edges(self):
        """Get edges added by the rule.

        Returns
        -------
        edges : set
            Set of edges from `rhs` added by the rule.
        """
        edges = set()
        for s, t in self.rhs.edges():
            s_p_nodes = keys_by_value(self.p_rhs, s)
            t_p_nodes = keys_by_value(self.p_rhs, t)
            if len(s_p_nodes) == 0 or len(t_p_nodes) == 0:
                edges.add((s, t))
            else:
                found_edge = False
                for s_p_node in s_p_nodes:
                    for t_p_node in t_p_nodes:
                        if (s_p_node, t_p_node) in self.p.edges():
                            found_edge = True
                if not found_edge:
                    edges.add((s, t))
        return edges

    def added_node_attrs(self):
        """Get node attributes added by the rule.

        Returns
        -------
        attrs : dict
            Dictionary where keys are nodes from `rhs`
            and values are attribute dictionaries to add.
        """
        attrs = dict()
        for node in self.rhs.nodes():
            p_nodes = keys_by_value(self.p_rhs, node)
            if len(p_nodes) == 0:
                if len(self.rhs.get_node(node)) > 0:
                    attrs[node] = self.rhs.get_node(node)
            new_attrs = {}
            for p_node in p_nodes:
                new_attrs = attrs_union(new_attrs, dict_sub(
                    self.rhs.get_node(node), self.p.get_node(p_node)))
            if len(new_attrs) > 0:
                attrs[node] = new_attrs
        return attrs

    def added_edge_attrs(self):
        """Get edge attributes added by the rule.

        Returns
        -------
        attrs : dict
            Dictionary where keys are edges from `rhs`
            and values are attribute dictionaries to add.
        """
        attrs = dict()
        for s, t in self.rhs.edges():
            s_p_nodes = keys_by_value(self.p_rhs, s)
            t_p_nodes = keys_by_value(self.p_rhs, t)
            if len(s_p_nodes) == 0 or len(t_p_nodes) == 0:
                if len(self.rhs.get_edge(s, t)) > 0:
                    attrs[(s, t)] = self.rhs.get_edge(s, t)
            new_attrs = {}
            for s_p_node in s_p_nodes:
                for t_p_node in t_p_nodes:
                    if (s_p_node, t_p_node) in self.p.edges():
                        new_attrs = attrs_union(
                            new_attrs,
                            dict_sub(
                                self.rhs.get_edge(s, t),
                                self.p.get_edge(s_p_node, t_p_node)
                            )
                        )
                    else:
                        new_attrs = self.rhs.get_edge(s, t)
            if len(new_attrs) > 0:
                attrs[(s, t)] = new_attrs
        return attrs

    def merged_nodes(self):
        """Get nodes merged by the rule.

        Returns
        -------
        nodes : dict
            Dictionary where keys are nodes from `rhs` and
            values are sets of nodes from `p` that are merged.
        """
        nodes = dict()
        for node in self.rhs.nodes():
            p_nodes = keys_by_value(self.p_rhs, node)
            if len(p_nodes) > 1:
                nodes[node] = set(p_nodes)
        return nodes

    def removed_nodes(self):
        """Get nodes removed by the rule.

        Returns
        -------
        nodes : set
            Set of nodes from `lhs` removed by the rule.
        """
        nodes = set()
        for node in self.lhs.nodes():
            p_nodes = keys_by_value(self.p_lhs, node)
            if len(p_nodes) == 0:
                nodes.add(node)
        return nodes

    def removed_edges(self):
        """Get edges removed by the rule.

        Returns
        -------
        edges : set
            Set of edges from `lhs` removed by the rule.
        """
        edges = set()
        for s, t in self.lhs.edges():
            s_p_nodes = keys_by_value(self.p_lhs, s)
            t_p_nodes = keys_by_value(self.p_lhs, t)
            if len(s_p_nodes) != 0 and len(t_p_nodes) != 0:
                for s_p_node in s_p_nodes:
                    for t_p_node in t_p_nodes:
                        if (s_p_node, t_p_node) not in self.p.edges():
                            edges.add((s_p_node, t_p_node))
        return edges

    def removed_node_attrs(self):
        """Get node attributes removed by the rule.

        Returns
        -------
        attrs : dict
            Dictionary where keys are nodes from `p`
            and values are attribute dictionaries to remove.
        """
        attrs = dict()
        for node in self.lhs.nodes():
            p_nodes = keys_by_value(self.p_lhs, node)
            for p_node in p_nodes:
                new_attrs = dict_sub(
                    self.lhs.get_node(node), self.p.get_node(p_node))
                if len(new_attrs) > 0:
                    normalize_attrs(new_attrs)
                    attrs[p_node] = new_attrs
        return attrs

    def removed_edge_attrs(self):
        """Get edge attributes removed by the rule.

        Returns
        -------
        attrs : dict
            Dictionary where keys are edges from `p`
            and values are attribute dictionaries to remove.
        """
        attrs = dict()
        for s, t in self.lhs.edges():
            s_p_nodes = keys_by_value(self.p_lhs, s)
            t_p_nodes = keys_by_value(self.p_lhs, t)
            for s_p_node in s_p_nodes:
                for t_p_node in t_p_nodes:
                    if (s_p_node, t_p_node) in self.p.edges():
                        new_attrs = dict_sub(
                            self.lhs.get_edge(s, t),
                            self.p.get_edge(s_p_node, t_p_node)
                        )
                        if len(new_attrs) > 0:
                            normalize_attrs(new_attrs)
                            attrs[(s_p_node, t_p_node)] = new_attrs
        return attrs

    def cloned_nodes(self):
        """Get nodes cloned by the rule.

        Returns
        -------
        nodes : dict
            Dictionary where keys are nodes from `lhs` and
            values are sets of corresponding nodes from `p`.
        """
        nodes = dict()
        for node in self.lhs.nodes():
            p_nodes = keys_by_value(self.p_lhs, node)
            if len(p_nodes) > 1:
                nodes[node] = set(p_nodes)
        return nodes

    def is_restrictive(self):
        """Check if the rule is  restrictive.

        Rule is restictive if it removes
        nodes/edges/attributes or clones nodes.

        Returns
        -------
        `True` if the rule is restrictive, `False`
        otherwise

        """
        return len(self.removed_nodes()) > 0 or\
            len(self.cloned_nodes()) > 0 or\
            len(self.removed_node_attrs()) > 0 or\
            len(self.removed_edges()) > 0 or\
            len(self.removed_edge_attrs()) > 0

    def is_relaxing(self):
        """Check if the rule is relaxing.

        Rule is relaxing if it adds
        nodes/edges/attributes or merges nodes.

        Returns
        -------
        `True` if the rule is relaxing, `False` otherwise

        """
        return len(self.added_nodes()) > 0 or\
            len(self.merged_nodes()) > 0 or\
            len(self.added_node_attrs()) > 0 or\
            len(self.added_edges()) > 0 or\
            len(self.added_edge_attrs()) > 0

    def to_commands(self):
        """Convert the rule to a list of commands.

        This method produces a list of commands
        corresponding to the rule. These commands
        follow a simple grammar of transformations
        that can be recognized by `regraph.parser` module.

        Returns
        -------
        commands : str
            Commands representing primitive transformations on the
            the `lhs` that are preformed in the rule.

        """
        commands = ""
        for lhs_node, p_nodes in self.cloned_nodes().items():
            new_names = set()
            for p_node in p_nodes:
                if p_node != lhs_node:
                    new_names.add(p_node)
            for name in new_names:
                commands += "CLONE %s AS %s.\n" % (lhs_node, name)
        for node in self.removed_nodes():
            commands += "DELETE_NODE %s.\n" % node
        for u, v in self.removed_edges():
            commands += "DELETE_EDGE %s %s.\n" % (u, v)
        for node, attrs in self.removed_node_attrs().items():
            commands += "DELETE_NODE_ATTRS %s %s.\n" % (node, attrs)
        for (u, v), attrs in self.removed_edge_attrs().items():
            commands += "DELETE_EDGE_ATTRS %s %s %s.\n" % (u, v, attrs)

        for node, p_nodes in self.merged_nodes().items():
            commands += "MERGE [%s] AS '%s'.\n" %\
                (", ".join([str(n) for n in p_nodes]), str(node))
        for node in self.added_nodes():
            commands += "ADD_NODE %s %s.\n" % (node, self.rhs.get_node(node))
        for (u, v) in self.added_edges():
            commands += "ADD_EDGE %s %s %s.\n" % (u, v, self.rhs.get_edge(u, v))
        for node, attrs in self.added_node_attrs().items():
            commands += "ADD_NODE_ATTRS %s %s.\n" % (node, attrs)
        for (u, v), attrs in self.added_edge_attrs().items():
            commands += "ADD_EDGE_ATTRS %s %s %s.\n" % (u, v, attrs)
        return commands

    def _add_node_lhs(self, node_id, attrs=None):
        if node_id not in self.lhs.nodes():
            self.lhs.add_node(node_id, attrs)
            new_p_node_id = node_id
            if new_p_node_id in self.p.nodes():
                new_p_node_id = self.p.generate_new_node_id(new_p_node_id)
            self.p.add_node(new_p_node_id, attrs)
            self.p_lhs[new_p_node_id] = node_id
            new_rhs_node_id = node_id
            if new_rhs_node_id in self.rhs.nodes():
                new_rhs_node_id = self.rhs.generate_new_node_id(
                    new_rhs_node_id)
            self.rhs.add_node(new_rhs_node_id, attrs)
            self.p_rhs[new_p_node_id] = new_rhs_node_id
            return new_p_node_id, new_rhs_node_id
        else:
            raise RuleError(
                "Node '%s' already exists in the left-hand side "
                "of the rule" % node_id)

    def _add_edge_lhs(self, source, target, attrs=None):
        if (source, target) not in self.lhs.edges():
            if source in self.lhs.nodes() and target in self.rhs.nodes():
                self.lhs.add_edge(source, target, attrs)
                p_sources = keys_by_value(self.p_lhs, source)
                p_targets = keys_by_value(self.p_lhs, target)
                if len(p_sources) > 0 and len(p_targets) > 0:
                    for p_s in p_sources:
                        for p_t in p_targets:
                            self.p.add_edge(p_s, p_t, attrs)
                            self.rhs.add_edge(
                                self.p_rhs[p_s],
                                self.p_rhs[p_t], attrs)
            else:
                raise RuleError(
                    "Cannot add an edge between nodes '{}' and '{}': "
                    "one of the nodes does not exist".format(source, target))
        else:
            raise RuleError(
                "Edge '{}'->'{}' already exists in the left-hand side "
                "of the rule".format(source, target))

    def _add_edge_attrs_lhs(self, source, target, attrs=None):
        if (source, target) in self.lhs.edges():
            self.lhs.add_edge_attrs(source, target, attrs)
            for s_p_node in keys_by_value(self.p_lhs, source):
                for t_p_node in keys_by_value(self.p_lhs, target):
                    if (s_p_node, t_p_node) in self.p.edges():
                        self.p.add_edge_attrs(s_p_node, t_p_node, attrs)
                        self.rhs.add_edge_attrs(
                            self.p_rhs[s_p_node], self.p_rhs[t_p_node], attrs)
        else:
            raise RuleError(
                "Edge '{}'->'{}' does not exists in the left-hand side "
                "of the rule".format(source, target))

    def _remove_node_lhs(self, node_id):
        """Remove a node from the `rhs`.

        This method removes a given node from the `rhs`,
        if there exist nodes from `p` that map to this node
        they are removed as well.
        """
        if node_id in self.lhs.nodes():
            self.lhs.remove_node(node_id)
            p_nodes = keys_by_value(self.p_lhs, node_id)
            for p in p_nodes:
                self.p.remove_node(p)
                self.rhs.remove_node(self.p_rhs[p])
                del self.p_lhs[p]
                del self.p_rhs[p]

    def _remove_node_rhs(self, node_id):
        """Remove a node from the `rhs`.

        This method removes a given node from the `rhs`,
        if there exist nodes from `p` that map to this node
        they are removed as well.
        """
        p_keys = keys_by_value(self.p_rhs, node_id)
        for p_node in p_keys:
            self.p.remove_node(p_node)
            del self.p_rhs[p_node]
            del self.p_lhs[p_node]
        self.rhs.remove_node(node_id)

    def _add_edge_rhs(self, n1, n2, attrs=None):
        """Add an edge in the rhs."""
        self.rhs.add_edge(n1, n2, attrs)

    def _remove_edge_p(self, node1, node2):
        """Remove edge from the p of the graph."""
        self.p.remove_edge(node1, node2)

    def _remove_edge_rhs(self, node1, node2):
        """Remove edge from the rhs of the graph."""
        self.rhs.remove_edge(node1, node2)
        for pn1 in keys_by_value(self.p_rhs, node1):
            for pn2 in keys_by_value(self.p_rhs, node2):
                if (pn1, pn2) in self.p.edges():
                    self.p.remove_edge(pn1, pn2)

    def _clone_rhs_node(self, node, new_name=None):
        """Clone an rhs node."""
        if node not in self.rhs.nodes():
            raise RuleError(
                "Node '%s' is not a node of right hand side" %
                node
            )
        p_keys = keys_by_value(self.p_rhs, node)
        if len(p_keys) == 0:
            self.rhs.clone_node(node, new_name)
        elif len(p_keys) == 1:
            self.rhs.clone_node(node, new_name)
            new_p_node = self.p.clone_node(p_keys[0])
            self.p_rhs[new_p_node] = new_name
            self.p_lhs[new_p_node] = self.p_lhs[p_keys[0]]
        else:
            raise RuleError("Cannot clone node that is result of merge!")

    def _merge_nodes_rhs(self, n1, n2, new_name):
        """Merge nodes in rhs."""
        if n1 not in self.rhs.nodes():
            raise RuleError("Node '%s' is not a node of the rhs" % n1)
        if n2 not in self.rhs.nodes():
            raise RuleError("Node '%s' is not a node of the rhs" % n2)
        self.rhs.merge_nodes([n1, n2], node_id=new_name)
        for (source, target) in self.p_rhs.items():
            if target == n1 or target == n2:
                self.p_rhs[source] = new_name

    def _add_node_attrs_rhs(self, n, attrs):
        """Add attrs to a node in the rhs."""
        if n not in self.rhs.nodes():
            raise RuleError(
                "Node %s does not exist in the right "
                "hand side of the rule" % n)
        self.rhs.add_node_attrs(n, attrs)

    def _remove_node_attrs_rhs(self, n, attrs):
        """Remove attrs of a node in the rhs."""
        if n not in self.rhs.nodes():
            raise RuleError(
                "Node '%s' does not exist in the right hand "
                "side of the rule" % n)

        p_keys = keys_by_value(self.p_rhs, n)
        for p_node in p_keys:
            self.p.remove_node_attrs(p_node, attrs)
        self.rhs.remove_node_attrs(n, attrs)

    def _remove_node_attrs_p(self, n, attrs):
        """Remove attrs of a node in the p."""
        if n not in self.p.nodes():
            raise RuleError(
                "Node '%s' does not exist in the preserved "
                "part of the rule" % n)
        self.p.remove_node_attrs(n, attrs)

    def _merge_node_list(self, node_list, node_name=None):
        """Merge a list of nodes."""
        if len(node_list) > 1:
            node_name = self.merge_nodes(
                node_list[0],
                node_list[1],
                node_name)
            for i in range(2, len(node_list)):
                node_name = self.merge_nodes(
                    node_list[i], node_name, node_name)
        else:
            warnings.warn(
                "Cannot merge less than two nodes!", ReGraphWarning
            )

    def _add_node_attrs_lhs(self, n, attrs):
        if n not in self.lhs.nodes():
            raise RuleError(
                "Node '%s' does not exist in the lhs "
                "of the rule" % n)
        self.lhs.add_node_attrs(n, attrs)
        p_nodes = keys_by_value(self.p_rhs, n)
        for p_node in p_nodes:
            self.p.add_node_attrs(p_node, attrs)
            self.rhs.add_node_attrs(self.p_rhs[p_node], attrs)

    def _remove_attrs(self):
        for n in self.lhs.nodes():
            self.lhs.set_node_attrs(n, dict(), update=True)
        for n in self.p.nodes():
            self.p.set_node_attrs(n, dict(), update=True)
        for n in self.rhs.nodes():
            self.rhs.set_node_attrs(n, dict(), update=True)

        for u, v in self.lhs.edges():
            self.lhs.set_edge_attrs(u, v, dict(), update=True)
        for u, v in self.p.edges():
            self.p.set_edge_attrs(u, v, dict(), update=True)
        for u, v in self.rhs.edges():
            self.rhs.set_edge_attrs(u, v, dict(), update=True)

    def _escape(self):
        lhs_relabel = {}
        for node in self.lhs.nodes():
            new_name = remove_forbidden(node)
            lhs_relabel[node] = new_name

        p_relabel = {}
        for node in self.p.nodes():
            new_name = remove_forbidden(node)
            p_relabel[node] = new_name

        rhs_relabel = {}
        for node in self.rhs.nodes():
            new_name = remove_forbidden(node)
            rhs_relabel[node] = new_name

        self.lhs.relabel_nodes(lhs_relabel, copy=False)
        self.p.relabel_nodes(p_relabel, copy=False)
        self.rhs.relabel_nodes(rhs_relabel, copy=False)

        new_p_lhs = dict()
        for k, v in self.p_lhs.items():
            new_key = remove_forbidden(k)
            new_v = remove_forbidden(v)
            new_p_lhs[new_key] = new_v

        new_p_rhs = dict()
        for k, v in self.p_rhs.items():
            new_key = remove_forbidden(k)
            new_v = remove_forbidden(v)
            new_p_rhs[new_key] = new_v

        self.p_lhs = new_p_lhs
        self.p_rhs = new_p_rhs

    def plot(self, filename=None, title=None):
        """Plot the rule."""
        plot_rule(self, filename, title)

    def refine(self, graph, instance):
        """Get refined (side-effect-free) version of the rule."""
        new_instance = {}
        for k, v in instance.items():
            new_instance[k] = v

        removed_attrs = self.removed_node_attrs()
        removed_edge_attrs = self.removed_edge_attrs()

        added_nodes = set()

        def add_neighbors_to_rule(n, removed_edges):

            def add_preserved_edges(lhs_source, lhs_target, edge_attrs, removed_edges):
                # Add preserved edges
                p_sources = keys_by_value(self.p_lhs, lhs_source)
                p_targets = keys_by_value(self.p_lhs, lhs_target)
                for sp in p_sources:
                    for tp in p_targets:
                        if (sp, tp) not in removed_edges:
                            if not self.p.exists_edge(sp, tp):
                                self.p.add_edge(sp, tp)
                                if not self.rhs.exists_edge(
                                        self.p_rhs[sp], self.p_rhs[tp]):
                                    self.rhs.add_edge(self.p_rhs[sp], self.p_rhs[tp])
                            # Compute preserved edge attributes
                            for k, v in edge_attrs.items():
                                if (sp, tp) not in removed_edge_attrs.keys() or\
                                   k not in removed_edge_attrs[(sp, tp)]:
                                    self.p.add_edge_attrs(sp, tp, {k: v})
                                    self.rhs.add_edge_attrs(
                                        self.p_rhs[sp], self.p_rhs[tp],
                                        {k: v})

            visited = set()
            # add successors
            for s in graph.successors(instance[n]):
                if s not in visited:
                    visited.add(s)
                    if s in new_instance.values():
                        # node 's' has already been added
                        lhs_s_node = keys_by_value(new_instance, s)[0]
                    else:
                        # we need to add 's'
                        lhs_s_node = self.lhs.generate_new_node_id(s)
                        self._add_node_lhs(lhs_s_node)
                        added_nodes.add(s)
                        new_instance[lhs_s_node] = s

                    edge_attrs = graph.get_edge(instance[n], s)
                    if not self.lhs.exists_edge(n, lhs_s_node):
                        self.lhs.add_edge(n, lhs_s_node, edge_attrs)
                    else:
                        self.lhs.add_edge_attrs(n, lhs_s_node, edge_attrs)
                    add_preserved_edges(n, lhs_s_node, edge_attrs, removed_edges)

            visited = set()
            # add predecessors
            for p in graph.predecessors(instance[n]):
                if p not in visited:
                    visited.add(p)
                    if p in new_instance.values():
                        # node 'p' has already been added
                        lhs_p_node = keys_by_value(new_instance, p)[0]
                    else:
                        # we need to add 'p'
                        lhs_p_node = self.lhs.generate_new_node_id(p)
                        self._add_node_lhs(lhs_p_node)
                        added_nodes.add(p)
                        new_instance[lhs_p_node] = p

                    edge_attrs = graph.get_edge(p, instance[n])
                    if not self.lhs.exists_edge(lhs_p_node, n):
                        self.lhs.add_edge(lhs_p_node, n, edge_attrs)
                    else:
                        self.lhs.add_edge_attrs(lhs_p_node, n, edge_attrs)
                    add_preserved_edges(lhs_p_node, n, edge_attrs, removed_edges)

        # Remove side-effects of node removal
        for n in self.removed_nodes():
            # Add nodes adjacent to removed nodes
            all_attrs = graph.get_node(instance[n])
            self.lhs.set_node_attrs(n, all_attrs, update=True)
            # Add nodes adjacent to removed nodes
            add_neighbors_to_rule(n, self.removed_edges())

        # Remove side-effects of edge removal
        visited_edges = set()
        for sp, tp in self.removed_edges():
            if (instance[self.p_lhs[sp]], instance[self.p_lhs[tp]]) not in visited_edges:
                visited_edges.add((
                    instance[self.p_lhs[sp]], instance[self.p_lhs[tp]]))
                all_edge_attrs = graph.get_edge(
                    instance[self.p_lhs[sp]], instance[self.p_lhs[tp]])
                self.lhs.set_edge(
                    self.p_lhs[sp], self.p_lhs[tp],
                    all_edge_attrs)

        # Remove side-effects of merges
        for rhs_node, p_nodes in self.merged_nodes().items():
            for p_node in p_nodes:
                all_attrs = graph.get_node(
                    instance[self.p_lhs[p_node]])
                self.lhs.set_node_attrs(
                    self.p_lhs[p_node], all_attrs, update=True)

                for k, v in all_attrs.items():
                    if p_node not in removed_attrs or\
                       k not in removed_attrs[p_node]:
                        self.p.add_node_attrs(
                            p_node, {k: v})
                        self.rhs.add_node_attrs(
                            rhs_node, {k: v})

                # Add nodes adjacent to removed nodes
                add_neighbors_to_rule(self.p_lhs[p_node], self.removed_edges())
        return new_instance

    def get_inverted_rule(self):
        """Get inverted rule with LHS and RHS swaped."""
        return Rule(self.p, self.rhs, self.lhs, self.p_rhs, self.p_lhs)

    @classmethod
    def identity_rule(cls):
        """Create an identity rule."""
        return cls(NXGraph(), NXGraph(), NXGraph())

    def is_identity(self):
        """Test if the rule is identity."""
        return not self.is_restrictive() and not self.is_relaxing() class NXGraph(Graph):
    """Wrapper for NetworkX directed graphs."""

    node_dict_factory = dict
    adj_dict_factory = dict

    def __init__(self, incoming_graph_data=None, **attr):
        """Initialize NetworkX graph."""
        super().__init__()
        if incoming_graph_data:
            if isinstance(incoming_graph_data, nx.DiGraph):
                self._graph = incoming_graph_data
            else:
                raise ReGraphError(
                    "The incoming_graph_data argument must be nx.DiGraph."
                )
        else:
            self._graph = nx.DiGraph()

    def nodes(self, data=False):
        """Return the list of nodes."""
        if data:
            return [(n, self.get_node(n)) for n in self._graph.nodes()]
        else:
            return self._graph.nodes()

    def edges(self, data=False):
        """Return the list of edges."""
        if data:
            return [(s, t, self.get_edge(s, t)) for s, t in self.edges()]
        return self._graph.edges()

    def get_node(self, n):
        """Get node attributes.

        Parameters
        ----------
        n : hashable
            Node id.
        """
        return self._graph.nodes[n]

    def get_edge(self, s, t):
        """Get edge attributes.

        Parameters
        ----------
        graph : networkx.(Di)Graph
        s : hashable, source node id.
        t : hashable, target node id.
        """
        return self._graph.adj[s][t]

    def add_node(self, node_id, attrs=None):
        """Abstract method for adding a node.

        Parameters
        ----------
        node_id : hashable
            Prefix that is prepended to the new unique name.
        attrs : dict, optional
            Node attributes.
        """
        if attrs is None:
            new_attrs = dict()
        else:
            new_attrs = safe_deepcopy_dict(attrs)
            normalize_attrs(new_attrs)
        if node_id not in self.nodes():
            self._graph.add_node(node_id, **new_attrs)
            return node_id
        else:
            raise GraphError("Node '{}' already exists!".format(node_id))

    def remove_node(self, node_id):
        """Remove node.

        Parameters
        ----------
        graph : networkx.(Di)Graph
        node_id : hashable, node to remove.
        """
        if node_id in self.nodes():
            self._graph.remove_node(node_id)
        else:
            raise GraphError("Node '{}' does not exist!".format(node_id))
        return

    def add_edge(self, s, t, attrs=None, **attr):
        """Add an edge to a graph.

        Parameters
        ----------
        graph : networkx.(Di)Graph
        s : hashable, source node id.
        t : hashable, target node id.
        attrs : dict
            Edge attributes.
        """
        if attrs is None:
            attrs = attr
        else:
            try:
                attrs.update(attr)
            except AttributeError:
                raise ReGraphError(
                    "The attr_dict argument must be a dictionary."
                )

        new_attrs = safe_deepcopy_dict(attrs)
        if s not in self.nodes():
            raise GraphError("Node '{}' does not exist!".format(s))
        if t not in self.nodes():
            raise GraphError("Node '{}' does not exist!".format(t))
        normalize_attrs(new_attrs)

        if (s, t) in self.edges():
            raise GraphError(
                "Edge '{}'->'{}' already exists!".format(s, t))
        self._graph.add_edge(s, t, **new_attrs)

    def remove_edge(self, s, t):
        """Remove edge from the graph.

        Parameters
        ----------
        graph : networkx.(Di)Graph
        s : hashable, source node id.
        t : hashable, target node id.
        """
        if (s, t) not in self.edges():
            raise GraphError(
                "Edge '{}->{}' does not exist!".format(s, t))
        self._graph.remove_edge(s, t)

    def update_node_attrs(self, node_id, attrs, normalize=True):
        """Update attributes of a node.

        Parameters
        ----------
        node_id : hashable, node to update.
        attrs : dict
            New attributes to assign to the node

        """
        new_attrs = safe_deepcopy_dict(attrs)
        if node_id not in self.nodes():
            raise GraphError(
                "Node '{}' does not exist!".format(node_id))
        elif new_attrs is None:
            warnings.warn(
                "You want to update '{}' attrs with an empty attrs_dict!".format(
                    node_id),
                GraphAttrsWarning
            )
        else:
            if normalize is True:
                normalize_attrs(new_attrs)
            attrs_to_remove = set()
            for k in self._graph.nodes[node_id].keys():
                if k not in new_attrs.keys():
                    attrs_to_remove.add(k)
            self._graph.add_node(node_id, **new_attrs)
            for k in attrs_to_remove:
                del self._graph.nodes[node_id][k]

    def update_edge_attrs(self, s, t, attrs, normalize=True):
        """Update attributes of a node.

        Parameters
        ----------
        s : hashable, source node of the edge to update.
        t : hashable, target node of the edge to update.
        attrs : dict
            New attributes to assign to the node

        """
        if not self._graph.has_edge(s, t):
            raise GraphError("Edge '{}->{}' does not exist!".format(
                             s, t))
        if attrs is None:
            warnings.warn(
                "You want to update '{}->{}' attrs with an empty attrs_dict".format(
                    s, t), GraphAttrsWarning
            )

        if normalize is True:
            normalize_attrs(attrs)
        attrs_to_remove = set()
        for k in self._graph.adj[s][t].keys():
            if k not in attrs.keys():
                attrs_to_remove.add(k)
        self._graph.add_edge(s, t, **attrs)
        for k in attrs_to_remove:
            del self._graph.adj[s][t][k]

    def successors(self, node_id):
        """Return the set of successors."""
        return self._graph.successors(node_id)

    def predecessors(self, node_id):
        """Return the set of predecessors."""
        if node_id not in self.nodes():
            raise GraphError(
                "Node '{}' does not exist in the graph".format(
                    node_id))

        return self._graph.predecessors(node_id)

    def get_relabeled_graph(self, mapping, raw=False):
        """Return a graph with node labeling specified in the mapping.

        Parameters
        ----------
        graph : networkx.(Di)Graph
        mapping: dict
            A dictionary with keys being old node ids and their values
            being new id's of the respective nodes.

        Returns
        -------
        g : networkx.(Di)Graph
            New graph object isomorphic to the `graph` with the relabled nodes.

        Raises
        ------
        ReGraphError
            If new id's do not define a set of distinct node id's.


        See also
        --------
        regraph.primitives.relabel_nodes
        """
        g = nx.DiGraph()
        old_nodes = set(mapping.keys())

        for old_node in old_nodes:
            try:
                new_node = mapping[old_node]
            except KeyError:
                pass
            try:
                g.add_node(
                    new_node,
                    **self.get_node(old_node))
            except KeyError:
                raise GraphError("Node '%s' does not exist!" % old_node)

        new_edges = list()
        attributes = dict()
        for s, t in self.edges():
            new_s = None
            new_t = None
            try:
                new_s = mapping[s]
            except KeyError:
                pass
            try:
                new_t = mapping[t]
            except KeyError:
                pass
            if new_s and new_t:
                new_edges.append((new_s, new_t))
                attributes[(new_s, new_t)] = self.get_edge(s, t)

        g.add_edges_from(new_edges)
        for s, t in g.edges():
            for k, v in attributes[(s, t)].items():
                g.adj[s][t][k] = v
        if not raw:
            new_obj = NXGraph()
            new_obj._graph = g
            return new_obj
        return g

    def subgraph(self, nodes):
        """Get a subgraph induced by the collection of nodes."""
        g = NXGraph()
        g.add_nodes_from([
            (n, attrs) for n, attrs in self.nodes(data=True)
            if n in nodes])
        for s, t, attrs in self.edges(data=True):
            if s in g.nodes() and t in g.nodes():
                g.add_edge(s, t, attrs)
        return g

    @classmethod
    def generate_subgraph(cls, graph, nodes):
        """Get a subgraph induced by the collection of nodes."""
        g = cls()
        g.add_nodes_from([
            (n, attrs) for n, attrs in graph.nodes(data=True)
            if n in nodes])
        for s, t, attrs in graph.edges(data=True):
            if s in g.nodes() and t in g.nodes():
                g.add_edge(s, t, attrs)
        return g

    def advanced_find_matching(self, pattern_dict,
                               nodes=None, graph_typing=None,
                               pattern_typing=None):
        """Find matching of a pattern in a graph in an advanced way."""
        patterns = []

        edge_combinations = [
            [(u_var, v_var, attrs), (v_var, u_var, attrs)]
            for (u_var, v_var, attrs) in pattern_dict["undirected_edges"]
        ]

        for new_edges in itertools.product(*edge_combinations):
            pattern = NXGraph()
            pattern.add_nodes_from(pattern_dict["nodes"])
            pattern.add_edges_from(pattern_dict["directed_edges"])
            pattern.add_edges_from(list(new_edges))
            patterns.append(pattern)
            plot_graph(pattern)

        instances = []
        for pattern in patterns:
            instances += self.find_matching(
                pattern, nodes, graph_typing, pattern_typing)
        return instances

    def find_matching(self, pattern, nodes=None,
                      graph_typing=None, pattern_typing=None):
        """Find matching of a pattern in a graph.

        This function takes as an input a graph and a pattern, optionally,
        it also takes a collection of nodes specifying the subgraph of the
        original graph, where the matching should be searched in, then it
        searches for a matching of the pattern inside of the graph (or induced
        subragh), which corresponds to solving subgraph matching problem.
        The matching is defined by a map from the nodes of the pattern
        to the nodes of the graph such that:

        * edges are preserved, i.e. if there is an edge between nodes `n1`
          and `n2` in the pattern, there is an edge between the nodes of
          the graph that correspond to the image of `n1` and `n2`,
          moreover, the attribute dictionary of the edge between `n1`
          and `n2` is the subdictiotary of the edge it corresponds to
          in the graph;
        * the attribute dictionary of a pattern node is a subdictionary of
          its image in the graph;

        Uses `networkx.isomorphism.(Di)GraphMatcher` class, which implements
        subgraph matching algorithm.

        In addition, two parameters `graph_typing` and `pattern_typing`
        can be specified. They restrict the space of admisible solutions
        by checking if an isomorphic subgraph found in the input graph respects
        the provided pattern typings according to the specified graph typings.

        Parameters
        ----------
        graph : nx.(Di)Graph
        pattern : nx.(Di)Graph
            Pattern graph to search for
        nodes : iterable, optional
            Subset of nodes to search for matching
        graph_typing : dict of dict, optional
            Dictionary defining typing of graph nodes
        pattern_typing : dict of dict, optional
            Dictionary definiting typing of pattern nodes

        Returns
        -------
        instances : list of dict's
            List of instances of matching found in the graph, every instance
            is represented with a dictionary where keys are nodes of the
            pattern, and values are corresponding nodes of the graph.

        """
        new_pattern_typing = dict()
        if pattern_typing:
            for graph, pattern_mapping in pattern_typing.items():
                new_pattern_typing[graph] = normalize_relation(
                    pattern_mapping)

        if graph_typing is None:
            graph_typing = {}

        # check graph/pattern typing is consistent
        for g, mapping in new_pattern_typing.items():
            if g not in graph_typing:
                raise ReGraphError(
                    "Graph is not typed by '{}' from the specified ".format(
                        g) +
                    "pattern typing")

        if nodes is not None:
            g = self._graph.subgraph(nodes)
        else:
            g = self._graph

        labels_mapping = dict([(n, i + 1) for i, n in enumerate(g.nodes())])
        g = self.get_relabeled_graph(labels_mapping, raw=True)
        inverse_mapping = dict(
            [(value, key) for key, value in labels_mapping.items()]
        )

        matching_nodes = set()

        # find all the nodes matching the nodes in pattern
        for pattern_node in pattern.nodes():
            for node in g.nodes():
                if new_pattern_typing:
                    # check types match
                    match = False
                    for graph, pattern_mapping in new_pattern_typing.items():
                        if node in graph_typing[graph].keys() and\
                           pattern_node in pattern_mapping.keys():
                            if graph_typing[graph][node] in pattern_mapping[
                                    pattern_node]:
                                if valid_attributes(
                                        pattern.get_node(pattern_node),
                                        g.nodes[node]):
                                    match = True
                        else:
                            if valid_attributes(
                                    pattern.get_node(pattern_node),
                                    g.nodes[node]):
                                match = True
                    if match:
                        matching_nodes.add(node)
                else:
                    if valid_attributes(
                            pattern.get_node(pattern_node),
                            g.nodes[node]):
                        matching_nodes.add(node)

        # find all the isomorphic subgraphs
        reduced_graph = g.subgraph(matching_nodes)
        instances = []
        isomorphic_subgraphs = []
        for sub_nodes in itertools.combinations(reduced_graph.nodes(),
                                                len(pattern.nodes())):
            subg = reduced_graph.subgraph(sub_nodes)
            for edgeset in itertools.combinations(subg.edges(),
                                                  len(pattern.edges())):
                edge_induced_graph = nx.DiGraph(list(edgeset))
                edge_induced_graph.add_nodes_from(
                    [n for n in subg.nodes()
                     if n not in edge_induced_graph.nodes()])
                if isinstance(pattern, Graph):
                    matching_obj = isomorphism.DiGraphMatcher(
                        pattern._graph, edge_induced_graph)
                else:
                    matching_obj = isomorphism.DiGraphMatcher(
                        pattern, edge_induced_graph)
                for isom in matching_obj.isomorphisms_iter():
                    isomorphic_subgraphs.append((subg, isom))

        for subgraph, mapping in isomorphic_subgraphs:
            # print(subgraph.nodes(), mapping)
            # check node matches
            # exclude subgraphs which nodes information does not
            # correspond to pattern
            for (pattern_node, node) in mapping.items():
                if new_pattern_typing:
                    for g, pattern_mapping in new_pattern_typing.items():
                        if inverse_mapping[node] in graph_typing[g].keys() and\
                           pattern_node in pattern_mapping.keys():
                            if graph_typing[g][
                                inverse_mapping[node]] not in pattern_mapping[
                                    pattern_node]:
                                break
                        if not valid_attributes(
                                pattern.get_node(pattern_node),
                                subgraph.nodes[node]):
                            break
                    else:
                        continue
                    break
                else:
                    if not valid_attributes(
                            pattern.get_node(pattern_node),
                            subgraph.nodes[node]):
                        break
            else:
                # check edge attribute matched
                for edge in pattern.edges():
                    pattern_attrs = pattern.get_edge(edge[0], edge[1])
                    target_attrs = subgraph.adj[
                        mapping[edge[0]]][mapping[edge[1]]]
                    if not valid_attributes(pattern_attrs, target_attrs):
                        break
                else:
                    instances.append(mapping)

        # bring back original labeling
        for instance in instances:
            for key, value in instance.items():
                instance[key] = inverse_mapping[value]

        return instances

    @classmethod
    def copy(cls, graph):
        """Copy the input graph object."""
        new_graph = cls()
        new_graph.add_nodes_from(graph.nodes(data=True))
        new_graph.add_edges_from(graph.edges(data=True))
        return new_graph

    def nodes_disconnected_from(self, node_id):
        """Find nodes disconnected from the input node."""
        components = nx.weakly_connected_components(
            self._graph)

        disconnected_components = []
        for comp in components:
            if node_id not in comp:
                disconnected_components.append(comp)
        return set([
            n
            for comp in disconnected_components
            for n in comp
        ]) class HierarchyError(ReGraphException):
    """Exceptions class for hierarchy handling.""" class InvalidHomomorphism(ReGraphException):
    """Exceptions class for invalid homomorphisms.""" class ReGraphError(ReGraphException):
    """Exception for errors in ReGraph.""" class ReGraphWarning(UserWarning):
    """Class for ReGraph warnings.""" class RewritingError(ReGraphException):
    """Exceptions class for errors in rewriting in a hierarchy.""" class Hierarchy(ABC):
    """Abstract class for graph hierarchy objects in ReGraph.

    A graph hierarchy is a DAG, where nodes are graphs with attributes and
    edges are homomorphisms representing graph typing in the system.
    """

    @abstractmethod
    def graphs(self, data=False):
        """Return a list of graphs in the hierarchy."""
        pass

    @abstractmethod
    def typings(self, data=False):
        """Return a list of graph typing edges in the hierarchy."""
        pass

    @abstractmethod
    def relations(self, data=False):
        """Return a list of relations."""
        pass

    @abstractmethod
    def successors(self, node_id):
        """Return the set of successors."""
        pass

    @abstractmethod
    def predecessors(self, node_id):
        """Return the set of predecessors."""
        pass

    @abstractmethod
    def get_graph(self, graph_id):
        """Get a graph object associated to the node 'graph_id'."""
        pass

    @abstractmethod
    def get_typing(self, source_id, target_id):
        """Get a typing dict associated to the edge 'source_id->target_id'."""
        pass

    @abstractmethod
    def get_relation(self, left_id, right_id):
        """Get a relation dict associated to the rel 'left_id->target_id'."""
        pass

    @abstractmethod
    def get_graph_attrs(self, graph_id):
        """Get attributes of a graph in the hierarchy.

        Parameters
        ----------
        graph_id : hashable
            Id of the graph
        """
        pass

    @abstractmethod
    def set_graph_attrs(self, node_id, attrs):
        """Set attributes of a graph in the hierarchy.

        Parameters
        ----------
        graph_id : hashable
            Id of the graph
        """
        pass

    @abstractmethod
    def get_typing_attrs(self, source, target):
        """Get attributes of a typing in the hierarchy.

        Parameters
        ----------
        source : hashable
            Id of the source graph
        target : hashable
            Id of the target graph
        """
        pass

    @abstractmethod
    def set_typing_attrs(self, source, target, attrs):
        """Set attributes of a typing in the hierarchy.

        Parameters
        ----------
        source : hashable
            Id of the source graph
        target : hashable
            Id of the target graph
        """
        pass

    @abstractmethod
    def get_relation_attrs(self, left, right):
        """Get attributes of a reltion in the hierarchy.

        Parameters
        ----------
        left : hashable
            Id of the left graph
        right : hashable
            Id of the right graph
        """
        pass

    @abstractmethod
    def set_relation_attrs(self, left, right, attrs):
        """Set attributes of a relation in the hierarchy.

        Parameters
        ----------
        left : hashable
            Id of the left graph
        right : hashable
            Id of the right graph
        """
        pass

    @abstractmethod
    def set_node_relation(self, left_graph, right_graph, left_node,
                          right_node):
        """Set relation for a particular node.

        Parameters
        ----------
        """
        pass

    @abstractmethod
    def add_graph(self, graph_id, graph, attrs=None):
        """Add a new graph to the hierarchy.

        Parameters
        ----------
        graph_id : hashable
            Id of a new node in the hierarchy
        graph : regraph.Graph
            Graph object corresponding to the new node of
            the hierarchy
        attrs : dict, optional
            Dictionary containing attributes of the new node
        """
        pass

    @abstractmethod
    def add_graph_from_data(self, graph_id, node_list, edge_list, attrs=None):
        """Add a new graph to the hierarchy from the input node/edge lists.

        Parameters
        ----------
        graph_id : hashable
            Id of a new node in the hierarchy
        node_list : iterable
            List of nodes (with attributes)
        edge_list : iterable
            List of edges (with attributes)
        graph_attrs : dict, optional
            Dictionary containing attributes of the new node
        """
        pass

    @abstractmethod
    def add_empty_graph(self, graph_id, attrs=None):
        """"Add a new empty graph to the hierarchy.

        Parameters
        ----------
        graph_id : hashable
            Id of a new node in the hierarchy
        graph_attrs : dict, optional
            Dictionary containing attributes of the new node
        """
        pass

    @abstractmethod
    def add_typing(self, source, target, mapping, attrs=None):
        """Add homomorphism to the hierarchy.

        Parameters
        ----------
        source : hashable
            Id of the source graph node of typing
        target : hashable
            Id of the target graph node of typing
        mapping : dict
            Dictionary representing a mapping of nodes
            from the source graph to target's nodes
        attrs : dict
            Dictionary containing attributes of the new
            typing edge

        Raises
        ------
        HierarchyError
            This error is raised in the following cases:

                * source or target ids are not found in the hierarchy
                * a typing edge between source and target already exists
                * addition of an edge between source and target creates
                a cycle or produces paths that do not commute with
                some already existing paths

        InvalidHomomorphism
            If a homomorphisms from a graph at the source to a graph at
            the target given by `mapping` is not a valid homomorphism.

        """
        pass

    @abstractmethod
    def add_relation(self, left, right, relation, attrs=None):
        """Add relation to the hierarchy.

        This method adds a relation between two graphs in
        the hierarchy corresponding to the nodes with ids
        `left` and `right`, the relation itself is defined
        by a dictionary `relation`, where a key is a node in
        the `left` graph and its corresponding value is a set
        of nodes from the `right` graph to which the node is
        related. Relations in the hierarchy are symmetric
        (see example below).

        Parameters
        ----------
        left
            Id of the hierarchy's node represening the `left` graph
        right
            Id of the hierarchy's node represening the `right` graph
        relation : dict
            Dictionary representing a relation of nodes from `left`
            to the nodes from `right`, a key of the dictionary is
            assumed to be a node from `left` and its value a set
            of ids of related nodes from `right`
        attrs : dict
            Dictionary containing attributes of the new relation

        Raises
        ------
        HierarchyError
            This error is raised in the following cases:

                * node with id `left`/`right` is not defined in the hierarchy;
                * node with id `left`/`right` is not a graph;
                * a relation between `left` and `right` already exists;
                * some node ids specified in `relation` are not found in the
                `left`/`right` graph.
        """
        pass

    @abstractmethod
    def remove_graph(self, graph_id, reconnect=False):
        """Remove graph from the hierarchy.

        Removes a graph from the hierarchy, if the `reconnect`
        parameter is set to True, adds typing from the
        predecessors of the removed node to all its successors,
        by composing the homomorphisms (for every predecessor `p`
        and for every successor 's' composes two homomorphisms
        `p`->`node_id` and `node_id`->`s`, then removes `node_id` and
        all its incident edges, by which makes node's
        removal a procedure of 'forgetting' one level
        of 'abstraction').

        Parameters
        ----------
        node_id
            Id of a graph to remove
        reconnect : bool
            Reconnect the descendants of the removed node to
            its predecessors

        Raises
        ------
        HierarchyError
            If graph with `node_id` is not defined in the hierarchy
        """
        pass

    @abstractmethod
    def remove_typing(self, s, t):
        """Remove a typing from the hierarchy."""
        pass

    @abstractmethod
    def remove_relation(self, left, right):
        """Remove a relation from the hierarchy."""
        pass

    @abstractmethod
    def bfs_tree(self, graph, reverse=False):
        """BFS tree from the graph to all other reachable graphs."""
        pass

    @abstractmethod
    def shortest_path(self, source, target):
        """Shortest path from 'source' to 'target'."""
        pass

    @abstractmethod
    def copy_graph(self, graph_id, new_graph_id, attach_graphs=[]):
        """Create a copy of a graph in a hierarchy."""
        pass

    @abstractmethod
    def relabel_graph_node(self, graph_id, node, new_name):
        """Rename a node in a graph of the hierarchy."""
        pass

    @abstractmethod
    def relabel_graph(self, graph_id, new_graph_id):
        """Relabel a graph in the hierarchy.

        Parameters
        ----------
        graph_id : hashable
            Id of the graph to relabel
        new_graph_id : hashable
            New graph id to assign to this graph
        """
        pass

    @abstractmethod
    def relabel_graphs(self, mapping):
        """Relabel graphs in the hierarchy.

        Parameters
        ----------
        mapping: dict
            A dictionary with keys being old graph ids and their values
            being new id's of the respective graphs.

        Raises
        ------
        ReGraphError
            If new id's do not define a set of distinct graph id's.
        """
        pass

    @abstractmethod
    def _update_mapping(self, source, target, mapping):
        """Update the mapping dictionary from source to target."""
        pass

    @abstractmethod
    def _update_relation(self, left, right, relation):
        """Update the relation dictionaries (left and right)."""
        pass

    # Implemented methods

    def __str__(self):
        """String representation of the hierarchy."""
        res = ""
        res += "\nGraphs:\n"
        for n, attrs in self.graphs(True):
            res += "\n{} {}\n".format(n, attrs)
        res += "\nTyping homomorphisms: \n"
        for n1, n2, attrs in self.typings(True):
            res += "{} -> {}: {}\n".format(
                n1, n2, attrs)
        res += "\nRelations:\n"
        for n1, n2, attrs in self.relations(True):
            res += "{}-{}: {}\n".format(
                n1, n2, attrs)

        return res

    def __eq__(self, hierarchy):
        """Hierarchy equality test."""
        for node, attrs in self.graphs(True):
            if node not in hierarchy.graphs():
                return False
            if attrs != hierarchy.get_graph_attrs(node):
                return False

        for s, t, attrs in self.typings(True):
            if (s, t) not in hierarchy.edges():
                return False
            if attrs != hierarchy.get_typing_attrs(s, t):
                return False

        for n1, n2, attrs in self.relations(True):
            if (n1, n2) not in hierarchy.relations() and\
               (n2, n1) not in hierarchy.relations():
                return False
            if attrs != hierarchy.get_relation_attrs(n1, n2):
                return False

        return True

    def __ne__(self, hierarchy):
        """Non-equality operator."""
        return not (self == hierarchy)

    def add_graph_from_json(self, graph_id, json_data, attrs=None):
        """Add a new graph to the hirarchy from its JSON-reprsentation.

        Parameters
        ----------
        graph_id : hashable
            Id of the new graph
        json_data : dict
            JSON-like dictionary containing the representation of the graph
        attrs : dict
            Attributes to attach to the new graph
        """
        node_list = []
        edge_list = []
        for n in json_data["nodes"]:
            node_list.append((n["id"], attrs_from_json(n["attrs"])))
        for e in json_data["edges"]:
            edge_list.append((e["from"], e["to"], attrs_from_json(e["attrs"])))
        self.add_graph_from_data(graph_id, node_list, edge_list, attrs)

    def to_json(self, rename_nodes=None):
        """Return json representation of the hierarchy.

        Parameters
        ----------
        rename_nodes : dict, optional
            Dictionary specifying mapping of node ids
            from the original graph to its JSON-representation
        """
        json_data = {
            "graphs": [],
            "typing": [],
            "relations": []
        }
        for node, attrs in self.graphs(True):
            if rename_nodes and node in rename_nodes.keys():
                node_id = rename_nodes[node]
            else:
                node_id = node

            json_data["graphs"].append({
                "id": node_id,
                "graph": self.get_graph(node).to_json(),
                "attrs": attrs_to_json(attrs)
            })

        for s, t, attrs in self.typings(True):
            if rename_nodes and s in rename_nodes.keys():
                s_id = rename_nodes[s]
            else:
                s_id = s
            if rename_nodes and t in rename_nodes.keys():
                t_id = rename_nodes[t]
            else:
                t_id = t
            json_data["typing"].append({
                "from": s_id,
                "to": t_id,
                "mapping": self.get_typing(s, t),
                "attrs": attrs_to_json(attrs)
            })

        visited = set()
        for u, v, attrs in self.relations(True):
            if rename_nodes and u in rename_nodes.keys():
                u_id = rename_nodes[u]
            else:
                u_id = u
            if rename_nodes and v in rename_nodes.keys():
                v_id = rename_nodes[v]
            else:
                v_id = v
            if not (u, v) in visited and not (v, u) in visited:
                visited.add((u, v))
                json_data["relations"].append({
                    "from": u_id,
                    "to": v_id,
                    "rel": {
                        a: list(b) for a, b in self.get_relation(u, v).items()
                    },
                    "attrs": attrs_to_json(attrs)
                })

        return json_data

    @classmethod
    def from_json(cls, json_data, ignore=None):
        """Create a hierarchy object from JSON-representation.

        Parameters
        ----------
        json_data : dict
            JSON-like dict containing representation of a hierarchy
        ignore : dict, optional
            Dictionary containing components to ignore in the process
            of converting from JSON, dictionary should respect the
            following format:
            {
                "graphs": <collection of ids of graphs to ignore>,
                "rules": <collection of ids of rules to ignore>,
                "typing": <collection of tuples containing typing
                    edges to ignore>,
                "rule_typing": <collection of tuples containing rule
                    typing edges to ignore>>,
                "relations": <collection of tuples containing
                    relations to ignore>,
            }

        Returns
        -------
        hierarchy : regraph.hierarchies.Hierarchy
        """
        hierarchy = cls()

        # add graphs
        for graph_data in json_data["graphs"]:
            if ignore is not None and\
               "graphs" in ignore.keys() and\
               graph_data["id"] in ignore["graphs"]:
                pass
            else:
                if "attrs" not in graph_data.keys():
                    attrs = dict()
                else:
                    attrs = attrs_from_json(graph_data["attrs"])
                hierarchy.add_graph_from_json(
                    graph_data["id"], graph_data["graph"], attrs)

        # add typing
        for typing_data in json_data["typing"]:
            if ignore is not None and\
               "typing" in ignore.keys() and\
               (typing_data["from"], typing_data["to"]) in ignore["typing"]:
                pass
            else:
                if "attrs" not in typing_data.keys():
                    attrs = dict()
                else:
                    attrs = attrs_from_json(typing_data["attrs"])
                hierarchy.add_typing(
                    typing_data["from"],
                    typing_data["to"],
                    typing_data["mapping"],
                    attrs)

        # add relations
        for relation_data in json_data["relations"]:
            from_g = relation_data["from"]
            to_g = relation_data["to"]
            if ignore is not None and\
               "relations" in ignore.keys() and\
               ((from_g, to_g) in ignore["relations"] or
                    (to_g, from_g) in ignore["relations"]):
                pass
            else:
                if "attrs" not in relation_data.keys():
                    attrs = dict()
                else:
                    attrs = attrs_from_json(relation_data["attrs"])
                if (from_g, to_g) not in hierarchy.relations():
                    hierarchy.add_relation(
                        relation_data["from"],
                        relation_data["to"],
                        {a: set(b) for a, b in relation_data["rel"].items()},
                        attrs
                    )
        return hierarchy

    @classmethod
    def load(cls, filename, ignore=None):
        """Load the hierarchy from a file.

        Parameters
        ----------
        filename : str
            Path to the file containing JSON-representation of the hierarchy
        ignore : dict
            Dictionary with graph elemenets to ignore when loading
        Returns
        -------
        hierarchy : regraph.hierarchies.Hierarchy
        """
        if os.path.isfile(filename):
            with open(filename, "r+") as f:
                json_data = json.loads(f.read())
                hierarchy = cls.from_json(json_data, ignore)
            return hierarchy
        else:
            raise ReGraphError("File '{}' does not exist!".format(filename))

    def export(self, filename):
        """Export the hierarchy to a file."""
        with open(filename, 'w') as f:
            j_data = self.to_json()
            json.dump(j_data, f)

    def adjacent_relations(self, g):
        """Return a list of related graphs."""
        if g not in self.graphs():
            raise HierarchyError(
                "Graph node '{}' does not exist in the hierarchy!".format(g))
        return [
            r
            for l, r in self.relations()
            if l == g
        ] + [
            l
            for l, r in self.relations()
            if r == g
        ]

    def node_type(self, graph_id, node_id):
        """Get a list of the immediate types of a node."""
        if graph_id not in self.graphs():
            raise HierarchyError(
                "Graph '{}' is not defined in the hierarchy!".format(graph_id)
            )
        if node_id not in self.get_graph(graph_id).nodes():
            raise HierarchyError(
                "Graph '{}'' does not have a node with id '{}'!".format(
                    graph_id, node_id)
            )
        types = dict()
        for successor in self.successors(graph_id):
            mapping = self.get_typing(graph_id, successor)
            if node_id in mapping.keys():
                types[successor] = mapping[node_id]
        return types

    def get_ancestors(self, graph_id):
        """Return ancestors of a graph with the typing morphisms."""
        ancestors = dict()
        for pred in self.predecessors(graph_id):
            typing = self.get_typing(pred, graph_id)
            pred_ancestors = self.get_ancestors(pred)
            if pred in ancestors.keys():
                ancestors.update(pred_ancestors)
            else:
                ancestors[pred] = typing
            for anc, anc_typing in pred_ancestors.items():
                if anc in ancestors.keys():
                    ancestors[anc].update(compose(anc_typing, typing))
                else:
                    ancestors[anc] = compose(anc_typing, typing)
        return ancestors

    def get_descendants(self, graph_id, maybe=None):
        """Return descendants of a graph with the typing morphisms."""
        descendants = dict()
        for successor in self.successors(graph_id):
            mapping = self.get_typing(graph_id, successor)
            typing_descendants = self.get_descendants(successor, maybe)
            if successor in descendants.keys():
                descendants[successor].update(mapping)
            else:
                descendants[successor] = mapping
            for anc, typ in typing_descendants.items():
                if anc in descendants.keys():
                    descendants[anc].update(compose(mapping, typ))
                else:
                    descendants[anc] = compose(mapping, typ)
        return descendants

    def compose_path_typing(self, path):
        """Compose homomorphisms along the path.

        Parameters
        ----------
        path : list
            List of nodes of the hierarchy forming a path

        Returns
        -------
        If source node of the path is a graph

        homomorphism : dict
            Dictionary containg the typing of the nodes
            from the source graph of the path by the nodes
            of the target graph

        if source node of the path is a rule

        lhs_homomorphism : dict
            Dictionary containg the typing of the nodes
            from the left-hand side of the source rule
            of the path by the nodes of the target graph
        rhs_homomorphism : dict
            Dictionary containg the typing of the nodes
            from the right-hand side of the source rule
            of the path by the nodes of the target graph
        """
        s = path[0]
        t = path[1]
        homomorphism = self.get_typing(s, t)
        for i in range(2, len(path)):
            s = path[i - 1]
            t = path[i]
            homomorphism = compose(
                homomorphism,
                self.get_typing(s, t)
            )
        return homomorphism

    def _get_backward_propagation_rule(self, origin_id, ancestor, rule,
                                       instance=None, p_typing=None):
        """Compute a propagation rule to the ancestor."""
        if p_typing is None:
            p_typing = {}

        origin_typing = self.get_typing(ancestor, origin_id)

        # Compute L_G
        l_g, l_g_g, l_g_l = pullback(
            self.get_graph(ancestor),
            rule.lhs,
            self.get_graph(origin_id),
            origin_typing,
            instance)

        # Compute canonical P_G
        canonical_p_g, p_g_l_g, p_g_p = pullback(
            l_g, rule.p, rule.lhs, l_g_l, rule.p_lhs)

        # Remove controlled things from P_G
        if ancestor in p_typing.keys():
            l_g_factorization = {
                keys_by_value(l_g_g, k)[0]: v
                for k, v in p_typing[ancestor].items()
            }
            p_g_nodes_to_remove = set()
            for n in canonical_p_g.nodes():
                l_g_node = p_g_l_g[n]
                # If corresponding L_G node is specified in
                # the controlling relation, remove all
                # the instances of P nodes not mentioned
                # in this relations
                if l_g_node in l_g_factorization.keys():
                    p_nodes = l_g_factorization[l_g_node]
                    if p_g_p[n] not in p_nodes:
                        del p_g_p[n]
                        del p_g_l_g[n]
                        p_g_nodes_to_remove.add(n)

            for n in p_g_nodes_to_remove:
                canonical_p_g.remove_node(n)
        rule = Rule(p=canonical_p_g, lhs=l_g, p_lhs=p_g_l_g)

        return rule, l_g_g, l_g_l, p_g_p

    def get_rule_hierarchy(self, origin_id, rule, instance=None,
                           p_typing=None, rhs_typing=None):
        """Find rule hierarchy corresponding to the input rewriting.

        Parameters
        ----------
        graph_id : hashable
            Id of the graph to rewrite
        rule : regraph.Rule
            Rewriting rule
        instance : dict, optional
            Instance of the rule in the graph. If not specified,
            the identity of the left-hand side is used
        p_typing : dict
            Relations controlling backward propagation. The keys are
            ancestors of the rewritten graph, values are dictionaries
            containing individual relations between the nodes of a given
            ancestor and the preserved part of the rule
        rhs_typing : dict
            Relation controlling forward propagation. The keys are
            descendants of the rewritten graph, values are dictionaries
            containing individual relations between the right-hand
            side of the rule and the nodes of a given
            descendant
        Returns
        -------
        rule_hierarchy : dictionary
            Dictionary contains two keys: (1) `rules` whose value is
            a dictionary with id's of the graphs in the hierarchy and
            the computed propagation rules; (2) `rule_homomorphisms` whose
            value is a dictionary with pairs of graphs in the hierarchy and
            the computed homomorphisms between rules.
        """
        instance, p_typing, rhs_typing = self._check_rule_instance_typing(
            origin_id, rule, instance, p_typing, rhs_typing, False)

        instances = {origin_id: instance}
        rule_hierarchy = {
            "rules": {origin_id: rule},
            "rule_homomorphisms": {}
        }

        # Compute rules and their map to the original rule
        l_g_ls = {}  # LHS's of rule liftings to LHS of the original rule
        p_g_ps = {}  # interfaces of rule liftings to LHS of the original rule

        ancestors = self.get_ancestors(origin_id)
        descendants = self.get_descendants(origin_id)

        # Compute rule liftings
        for ancestor, origin_typing in ancestors.items():
            # Compute L_G
            l_g, l_g_g, l_g_l = pullback(
                self.get_graph(ancestor),
                rule.lhs,
                self.get_graph(origin_id),
                origin_typing,
                instance)

            # Compute canonical P_G
            canonical_p_g, p_g_l_g, p_g_p = pullback(
                l_g, rule.p, rule.lhs, l_g_l, rule.p_lhs)

            # Remove controlled things from P_G
            if ancestor in p_typing.keys():
                l_g_factorization = {
                    keys_by_value(l_g_g, k)[0]: v
                    for k, v in p_typing[ancestor].items()
                }
                p_g_nodes_to_remove = set()
                for n in canonical_p_g.nodes():
                    l_g_node = p_g_l_g[n]
                    # If corresponding L_G node is specified in
                    # the controlling relation, remove all
                    # the instances of P nodes not mentioned
                    # in this relations
                    if l_g_node in l_g_factorization.keys():
                        p_nodes = l_g_factorization[l_g_node]
                        if p_g_p[n] not in p_nodes:
                            del p_g_p[n]
                            del p_g_l_g[n]
                            p_g_nodes_to_remove.add(n)

                for n in p_g_nodes_to_remove:
                    canonical_p_g.remove_node(n)
            rule_hierarchy["rules"][ancestor] =\
                Rule(p=canonical_p_g, lhs=l_g, p_lhs=p_g_l_g)

            instances[ancestor] = l_g_g
            l_g_ls[ancestor] = l_g_l
            p_g_ps[ancestor] = p_g_p

        l_l_ts = {}  # Original rule LHS to the LHS of rule projections
        p_p_ts = {}  # Original rule interface to the inter. of rule projections
        r_r_ts = {}  # Original rule RHS to the RHS of rule projections

        # Compute rule projections
        for descendant, origin_typing in descendants.items():
            # Compute canonical P_T
            l_t, l_l_t, l_t_t = image_factorization(
                rule.lhs, self.get_graph(descendant),
                compose(instance, origin_typing))

            # Compute canonical R_T
            r_t, l_t_r_t, r_r_t = pushout(
                rule.p, l_t, rule.rhs,
                compose(rule.p_lhs, l_l_t),
                rule.p_rhs)

            # Modify P_T and R_T according to the controlling
            # relation rhs_typing
            if descendant in rhs_typing.keys():
                r_t_factorization = {
                    r_r_t[k]: v
                    for k, v in rhs_typing[descendant].items()
                }
                for n in l_t.nodes():
                    if l_t_r_t[n] not in r_t_factorization:
                        r_t_factorization[l_t_r_t[n]] = {l_t_t[n]}
                    else:
                        if not {l_t_t[n]}.issubset(r_t_factorization[l_t_r_t[n]]):
                            r_t_factorization[l_t_r_t[n]].add(l_t_t[n])

                added_t_nodes = set()
                for n in r_t.nodes():
                    if n in r_t_factorization.keys():
                        # If corresponding R_T node is specified in
                        # the controlling relation add nodes of T
                        # that type it to P
                        t_nodes = r_t_factorization[n]
                        for t_node in t_nodes:
                            if t_node not in l_t_t.values() and\
                               t_node not in added_t_nodes:
                                new_p_node = l_t.generate_new_node_id(
                                    t_node)
                                l_t.add_node(new_p_node)
                                added_t_nodes.add(t_node)
                                l_t_r_t[new_p_node] = n
                                l_t_t[new_p_node] = t_node
                            else:
                                l_t_r_t[keys_by_value(l_t_t, t_node)[0]] = n

                # check if some nodes need merging
                inverse_factorization = dict()
                for k, v in r_t_factorization.items():
                    for vv in v:
                        if vv not in inverse_factorization:
                            inverse_factorization[vv] = set([k])
                        else:
                            inverse_factorization[vv].add(k)

                for k, v in inverse_factorization.items():
                    if len(v) > 1:
                        merged_node = r_t.merge_nodes(v)
                        for vv in v:
                            l_t_nodes = keys_by_value(l_t_r_t, vv)
                            for l_t_node in l_t_nodes:
                                l_t_r_t[l_t_node] = merged_node
                            r_nodes = keys_by_value(r_r_t, vv)
                            for r_node in r_nodes:
                                r_r_t[r_node] = merged_node

            rule_hierarchy["rules"][descendant] =\
                Rule(lhs=l_t, p=l_t, rhs=r_t, p_rhs=l_t_r_t)

            instances[descendant] = l_t_t
            l_l_ts[descendant] = l_l_t
            p_p_ts[descendant] = {k: l_l_t[v] for k, v in rule.p_lhs.items()}
            r_r_ts[descendant] = r_r_t

        # Compute homomorphisms between rules
        for graph_id, graph_rule in rule_hierarchy["rules"].items():
            if graph_id in ancestors:
                for successor in self.successors(graph_id):
                    old_typing = self.get_typing(graph_id, successor)
                    if successor == origin_id:
                        graph_lhs_successor_lhs = l_g_ls[graph_id]
                        graph_p_successor_p = p_g_ps[graph_id]
                        rule_hierarchy["rule_homomorphisms"][
                            (graph_id, successor)] = (
                                graph_lhs_successor_lhs,
                                graph_p_successor_p,
                                compose(
                                    graph_p_successor_p,
                                    rule_hierarchy["rules"][successor].p_rhs)
                        )
                    else:
                        l_graph_successor = compose(
                            instances[graph_id],
                            old_typing)
                        # already lifted to the successor
                        if successor in ancestors:
                            graph_rule = rule_hierarchy["rules"][graph_id]
                            suc_rule = rule_hierarchy["rules"][successor]
                            graph_lhs_successor_lhs = get_unique_map_to_pullback(
                                suc_rule.lhs.nodes(),
                                instances[successor],
                                l_g_ls[successor],
                                compose(
                                    instances[graph_id],
                                    old_typing),
                                l_g_ls[graph_id])
                            graph_p_successor_p = get_unique_map_to_pullback(
                                suc_rule.p.nodes(),
                                suc_rule.p_lhs,
                                p_g_ps[successor],
                                compose(
                                    graph_rule.p_lhs,
                                    graph_lhs_successor_lhs),
                                p_g_ps[graph_id])

                            rule_hierarchy["rule_homomorphisms"][
                                (graph_id, successor)] = (
                                    graph_lhs_successor_lhs,
                                    graph_p_successor_p,
                                    graph_p_successor_p
                            )
                        elif successor in descendants:
                            rule_hierarchy["rule_homomorphisms"][(graph_id, successor)] = (
                                compose(l_g_ls[graph_id],
                                        l_l_ts[successor]),
                                compose(p_g_ps[graph_id],
                                        p_p_ts[successor]),
                                compose(
                                    compose(p_g_ps[graph_id],
                                            rule.p_rhs),
                                    r_r_ts[successor])
                            )
                        # didn't touch the successor or projected to it
                        else:
                            pass

            if graph_id in descendants:
                for predecessor in self.predecessors(graph_id):
                    old_typing = self.get_typing(predecessor, graph_id)
                    if predecessor == origin_id:
                        predecessor_l_graph_l = l_l_ts[graph_id]
                        predecessor_p_graph_p = p_p_ts[graph_id]
                        predecessor_rhs_graph_rhs = r_r_ts[graph_id]
                        rule_hierarchy["rule_homomorphisms"][
                            (predecessor, graph_id)] = (
                                predecessor_l_graph_l,
                                predecessor_p_graph_p,
                                predecessor_rhs_graph_rhs
                        )
                    else:
                        # already projected to the predecessor
                        if predecessor in descendants:

                            l_pred_graph = compose(
                                instances[predecessor],
                                old_typing)
                            predecessor_l_graph_l = {}
                            for k, v in instances[
                                    predecessor].items():
                                predecessor_l_graph_l[k] = keys_by_value(
                                    instances[graph_id],
                                    l_pred_graph[k])[0]

                            predecessor_rhs_graph_rhs = get_unique_map_from_pushout(
                                rule_hierarchy["rules"][predecessor].rhs.nodes(),
                                rule_hierarchy["rules"][predecessor].p_rhs,
                                r_r_ts[predecessor],
                                compose(
                                    predecessor_l_graph_l,
                                    rule_hierarchy["rules"][graph_id].p_rhs),
                                r_r_ts[graph_id])

                            rule_hierarchy["rule_homomorphisms"][
                                (predecessor, graph_id)] = (
                                    predecessor_l_graph_l,
                                    predecessor_l_graph_l,
                                    predecessor_rhs_graph_rhs
                            )
                        # didn't touch the predecessor or lifter to it
                        else:
                            pass

        return rule_hierarchy, instances

    def refine_rule_hierarchy(self, rule_hierarchy, instances):
        """Refine the input rule hierarchy to its reversible version.

        Parameters
        ----------
        rule_hierarchy : dict
            Rule hierarchy to refine
        instances : dict of dict
            Dictionary containing ids of the graphs in the hierarchy as keys
            and dictionaries represening instances of the corresponding rules

        Returns
        -------
        new_instances : dict of dict
            Dictionary containing ids of the graphs in the hierarchy as keys
            and dictionaries represening new instances of the corresponding
            refined rules

        """
        new_lhs_instances = {}

        new_rules = {}
        new_rule_homomorphisms = {}

        # Refine individual rules
        for graph, rule in rule_hierarchy["rules"].items():
            # refine rule
            new_lhs_instance = rule.refine(
                self.get_graph(graph), instances[graph])
            new_lhs_instances[graph] = new_lhs_instance

        # Update rule homomorphisms
        for (source, target), (lhs_h, p_h, rhs_h) in rule_hierarchy[
                "rule_homomorphisms"].items():
            typing = self.get_typing(source, target)
            source_rule = rule_hierarchy["rules"][source]
            target_rule = rule_hierarchy["rules"][target]
            for node in source_rule.lhs.nodes():
                if node not in lhs_h.keys():
                    source_node = new_lhs_instances[source][node]
                    target_node = typing[source_node]

                    target_lhs_nodes = keys_by_value(
                        new_lhs_instances[target], target_node)
                    if len(target_lhs_nodes) == 1:
                        target_lhs_node = target_lhs_nodes[0]
                    else:
                        target_rule._add_node_lhs(target_node)
                        target_lhs_node = target_node
                        new_lhs_instances[target][target_lhs_node] = target_node

                    lhs_h[node] = target_lhs_node

                    if node in source_rule.p_lhs.values():
                        source_p_node = keys_by_value(
                            source_rule.p_lhs, node)[0]
                        target_p_node = keys_by_value(
                            target_rule.p_lhs, target_lhs_node)[0]
                        p_h[source_p_node] = target_p_node

                        source_rhs_node = source_rule.p_rhs[source_p_node]
                        target_rhs_node = target_rule.p_rhs[target_p_node]
                        rhs_h[source_rhs_node] = target_rhs_node
            # Add necessary node attrs
            for node in source_rule.lhs.nodes():
                t_node = lhs_h[node]
                target_rule._add_node_attrs_lhs(t_node, source_rule.lhs.get_node(node))
            # Add necessary edges
            for s_lhs_s, s_lhs_t in source_rule.lhs.edges():
                t_lhs_s = lhs_h[s_lhs_s]
                t_lhs_t = lhs_h[s_lhs_t]
                if not target_rule.lhs.exists_edge(t_lhs_s, t_lhs_t):
                    target_rule._add_edge_lhs(
                        t_lhs_s,
                        t_lhs_t,
                        source_rule.lhs.get_edge(s_lhs_s, s_lhs_t))
                else:
                    target_rule._add_edge_attrs_lhs(
                        t_lhs_s,
                        t_lhs_t,
                        source_rule.lhs.get_edge(s_lhs_s, s_lhs_t))

        # If merge is performed, add all the instances of the merged nodes
        for (source, target), (lhs_h, p_h, rhs_h) in rule_hierarchy[
                "rule_homomorphisms"].items():
            source_rule = rule_hierarchy["rules"][source]
            target_rule = rule_hierarchy["rules"][target]
            typing = self.get_typing(source, target)
            if len(target_rule.merged_nodes()) > 0:
                for rhs_node, p_nodes in target_rule.merged_nodes().items():
                    # rhs_node_instances = keys_by_value(typing, rhs_node)
                    for p_node in p_nodes:
                        lhs_node_instance = new_lhs_instances[target][
                            target_rule.p_lhs[p_node]]
                        source_nodes = [
                            n
                            for n in keys_by_value(typing, lhs_node_instance)
                        ]
                        source_nodes_to_add = [
                            s
                            for s in source_nodes
                            if s not in new_lhs_instances[source].values()
                        ]

                        for n in source_nodes_to_add:
                            lhs_s_node = source_rule.lhs.generate_new_node_id(n)
                            p_s_node, rhs_s_node = source_rule._add_node_lhs(
                                lhs_s_node)
                            # Add the instances of the new lhs node
                            new_lhs_instances[source][lhs_s_node] = n
                            # Add maps to the target for the new lhs node
                            lhs_h[lhs_s_node] = target_rule.p_lhs[p_node]
                            p_h[p_s_node] = p_node
                            rhs_h[rhs_s_node] = rhs_node

        # Add identity rules where needed
        if len(rule_hierarchy["rules"]) == 0:
            # if the are no rules in the rule hierarchy,
            # create the identity rule for every graph
            for graph in self.graphs():
                rule_hierarchy["rules"][graph] = Rule.identity_rule()
                new_lhs_instances[graph] = dict()
            for (s, t) in self.typings():
                rule_hierarchy["rule_homomorphisms"][(s, t)] = (
                    dict(), dict(), dict())
        else:
            # add identity rules where needed
            # to preserve the info on p/rhs_typing
            # add ancestors that are not included in rule hierarchy
            for graph, rule in rule_hierarchy["rules"].items():
                for ancestor, typing in self.get_ancestors(graph).items():
                    if ancestor not in rule_hierarchy["rules"] and\
                       ancestor not in new_rules:
                        if len(rule.merged_nodes()) > 0:
                            # We create a non-empty rule that preserves
                            # the info on typing
                            l_pred, l_pred_pred, l_pred_l_graph = pullback(
                                self.get_graph(ancestor), rule.lhs,
                                self.get_graph(graph), typing,
                                new_lhs_instances[graph])
                            new_rules[ancestor] = Rule(p=l_pred, lhs=l_pred)
                            new_lhs_instances[ancestor] = l_pred_pred
                            r_pred_r_graph = {
                                v: rule.p_rhs[k]
                                for k, v in l_pred_l_graph.items()
                            }
                        else:
                            # We create an empty rule if no merges are performed
                            new_rules[ancestor] = Rule.identity_rule()
                            new_lhs_instances[ancestor] = dict()
                            l_pred_l_graph = dict()
                            r_pred_r_graph = dict()
                        for successor in self.successors(ancestor):
                            if successor in rule_hierarchy["rules"]:
                                if successor == graph:
                                    new_rule_homomorphisms[
                                        (ancestor, graph)] = (
                                            l_pred_l_graph, l_pred_l_graph,
                                            r_pred_r_graph
                                    )
                                else:
                                    path = self.shortest_path(graph, successor)
                                    lhs_h, p_h, rhs_h = rule_hierarchy[
                                        "rule_homomorphisms"][
                                            (path[0], path[1])]
                                    for i in range(2, len(path)):
                                        new_lhs_h, new_p_h, new_rhs_h =\
                                            rule_hierarchy[
                                                "rule_homomorphisms"][
                                                    (path[i - 1], path[i])]
                                        lhs_h = compose(lhs_h, new_lhs_h)
                                        p_h = compose(p_h, new_p_h)
                                        rhs_h = compose(rhs_h, new_rhs_h)

                                    new_rule_homomorphisms[
                                        (ancestor, successor)] = (
                                            compose(l_pred_l_graph, lhs_h),
                                            compose(l_pred_l_graph, p_h),
                                            compose(r_pred_r_graph, rhs_h)
                                    )
                            if successor in new_rules:
                                lhs_h = {
                                    k: keys_by_value(
                                        new_lhs_instances[successor],
                                        self.get_typing(
                                            ancestor, successor)[v])[0]
                                    for k, v in new_lhs_instances[
                                        ancestor].items()
                                }
                                new_rule_homomorphisms[
                                    (ancestor, successor)] = (
                                        lhs_h, lhs_h, lhs_h
                                )
                        for predecessor in self.predecessors(ancestor):
                            if predecessor in rule_hierarchy["rules"] or\
                               predecessor in new_rules:
                                lhs_h = {
                                    k: keys_by_value(
                                        new_lhs_instances[ancestor],
                                        self.get_typing(
                                            predecessor, ancestor)[v])[0]
                                    for k, v in new_lhs_instances[
                                        predecessor].items()
                                }
                                new_rule_homomorphisms[
                                    (predecessor, ancestor)] = (
                                        lhs_h, lhs_h, lhs_h
                                )

                for descendant, typing in self.get_descendants(graph).items():
                    if descendant not in rule_hierarchy["rules"] and\
                       descendant not in new_rules:
                        l_suc, l_graph_l_suc, l_suc_suc = image_factorization(
                            rule.lhs, self.get_graph(descendant),
                            compose(
                                new_lhs_instances[graph],
                                typing))
                        new_rules[descendant] = Rule(p=l_suc, lhs=l_suc)
                        new_lhs_instances[descendant] = l_suc_suc
                        p_graph_p_suc = {
                            k: l_graph_l_suc[v]
                            for k, v in rule.p_lhs.items()
                        }
                        for predecessor in self.predecessors(descendant):
                            if predecessor in rule_hierarchy["rules"]:
                                if predecessor == graph:
                                    new_rule_homomorphisms[
                                        (predecessor, descendant)] = (
                                            l_graph_l_suc,
                                            p_graph_p_suc,
                                            p_graph_p_suc
                                    )
                                else:
                                    path = self.shortest_path(
                                        predecessor, graph)
                                    lhs_h, p_h, rhs_h = rule_hierarchy[
                                        "rule_homomorphisms"][
                                            (path[0], path[1])]
                                    for i in range(2, len(path)):
                                        new_lhs_h, new_p_h, new_rhs_h =\
                                            rule_hierarchy[
                                                "rule_homomorphisms"][
                                                    (path[i - 1], path[i])]
                                        lhs_h = compose(lhs_h, new_lhs_h)
                                        p_h = compose(p_h, new_p_h)
                                        rhs_h = compose(rhs_h, new_rhs_h)
                                    new_rule_homomorphisms[
                                        (predecessor, descendant)] = (
                                            compose(lhs_h, l_graph_l_suc),
                                            compose(p_h, p_graph_p_suc),
                                            compose(rhs_h, p_graph_p_suc)
                                    )
                            if predecessor in new_rules:
                                lhs_h = {
                                    k: keys_by_value(
                                        new_lhs_instances[descendant],
                                        self.get_typing(
                                            predecessor, descendant)[v])[0]
                                    for k, v in new_lhs_instances[
                                        predecessor].items()
                                }
                                new_rule_homomorphisms[
                                    (predecessor, descendant)] = (
                                    lhs_h, lhs_h, lhs_h
                                )

                        for successor in self.successors(descendant):
                            if successor in rule_hierarchy["rules"] or\
                               successor in new_rules:
                                lhs_h = {
                                    k: keys_by_value(
                                        new_lhs_instances[successor],
                                        self.get_typing(
                                            descendant, successor)[v])[0]
                                    for k, v in new_lhs_instances[
                                        descendant].items()
                                }
                                new_rule_homomorphisms[
                                    (descendant, successor)] = (
                                        lhs_h, lhs_h, lhs_h
                                )

        rule_hierarchy["rules"].update(new_rules)
        rule_hierarchy["rule_homomorphisms"].update(
            new_rule_homomorphisms)

        return new_lhs_instances

    def unique_graph_id(self, prefix):
        """Generate a new graph id starting with a prefix."""
        if prefix not in self.graphs():
            return prefix
        i = 0
        while "{}_{}".format(prefix, i) in self.graphs():
            i += 1
        return "{}_{}".format(prefix, i)

    def duplicate_subgraph(self, graph_dict, attach_graphs=[]):
        """Duplicate a subgraph induced by the set of nodes.

        Parameters
        ----------
        graph_dict : dict
            Dictionary contaning names of graphs to duplicate as keys
            and their new IDs in the hierarchy as values
        attach_graphs : list, optional
            List of not duplicated graph IDs that should be reattached to
            the duplicated graphs, if empty, duplicated subgraph
            is disconnected from the rest of the hierarchy
        """
        old_graphs = self.graphs()
        for original, new in graph_dict.items():
            if new in old_graphs:
                raise HierarchyError(
                    "Cannot duplicate the graph '{}' as '{}': ".format(
                        original, new) +
                    "the graph '{}' ".format(new) +
                    "already exists in the hierarchy!")

        # copy graphs
        for original, new in graph_dict.items():
            self.copy_graph(original, new, attach_graphs)

        # copy typing between duplicated graphs
        visited = set()
        for g in graph_dict.keys():
            preds = [
                p for p in self.predecessors(g)
                if p in graph_dict.keys() and (p, g) not in visited]
            sucs = [
                p for p in self.successors(g)
                if p in graph_dict.keys() and (g, p) not in visited]
            for s in sucs:
                self.add_typing(
                    graph_dict[g], graph_dict[s],
                    self.get_typing(g, s))
                visited.add((g, s))
            for p in preds:
                self.add_typing(
                    graph_dict[p], graph_dict[g],
                    self.get_typing(p, g))
                visited.add((p, g))

    def relation_to_span(self, left, right, edges=False, attrs=False):
        """Convert relation to a span.

        This method computes the span of the form
        `left` <- `common` -> `right` from a binary
        symmetric relation between two graphs in
        the hierarchy.

        Parameters
        ----------
        left
            Id of the hierarchy's node represening the `left` graph
        right
            Id of the hierarchy's node represening the `right` graph
        edges : bool, optional
            If True, maximal set of edges is added to the common
            part graph
        attrs : bool, optional
            If True, maximal dict of attrs is added to the nodes of
            the common part graph

        Returns
        -------
        common : nx.(Di)Graph
            Graph representing the common part graph induced
            by the relation
        left_h : dict
            Homomorphism from the common part graph to the left
            graph of the relation
        right_h : dict
            Homomorphism from the common part graph to the right
            graph of the relation

        Raises
        ------
        HierarchyError
            If nodes corresponding to either `left` or `right` ids
            do not exist in the hierarchy, or there is no relation
            between them.
        """
        if left not in self.nodes():
            raise HierarchyError(
                "Node '{}' is not defined in the hierarchy!".format(left))
        if right not in self.nodes():
            raise HierarchyError(
                "Node '{}' is not defined in the hierarchy!".format(right))

        if (left, right) not in self.relations() and\
           (right, left) not in self.relations():
            raise HierarchyError(
                "Relation between graphs '{}' and '{}' is not defined".format(
                    left, right)
            )
        common, left_h, right_h = relation_to_span(
            self.get_graph(left),
            self.get_graph(right),
            self.get_relation(left, right),
            edges,
            attrs)
        return common, left_h, right_h

    def _get_graph_pattern_typing(self, graph_id, pattern, pattern_typing,
                                  advanced=False):
        # Check that 'typing_graph' and 'pattern_typing' are correctly
        # specified
        descendants = self.get_descendants(graph_id)
        if pattern_typing is not None:
            for typing_graph, _ in pattern_typing.items():
                if typing_graph not in descendants.keys():
                    raise HierarchyError(
                        "Pattern typing graph '{}' is not in "
                        "the (transitive) typing graphs of '{}'!".format(
                            typing_graph, graph_id)
                    )

            # Check pattern typing is a valid homomorphism
            if not advanced:
                for typing_graph, mapping in pattern_typing.items():
                    try:
                        check_homomorphism(
                            pattern,
                            self.get_graph(typing_graph),
                            mapping
                        )
                    except InvalidHomomorphism as e:
                        raise ReGraphError(
                            "Specified pattern is not valid in the "
                            "hierarchy (it produces the following error: "
                            "{}) ".format(e)
                        )

        graph_typing = {
            typing_graph: self.get_typing(graph_id, typing_graph)
            for typing_graph in pattern_typing.keys()
        }
        return graph_typing

    def find_matching(self, graph_id, pattern,
                      pattern_typing=None, nodes=None):
        """Find an instance of a pattern in a specified graph.

        Parameters
        ----------
        graph_id : hashable
            Id of a graph in the hierarchy to search for matches
        pattern : Graph object
            A pattern to match
        pattern_typing : dict
            A dictionary that specifies a typing of a pattern,
            keys of the dictionary -- graph id that types a pattern, this graph
            should be among parents of the `graph_id` graph;
            values are mappings of nodes from pattern to the typing graph;
        nodes : iterable
            Subset of nodes where matching should be performed

        Returns
        -------
        instances : list of dict
            List of matched instances
        """
        if pattern_typing is None:
            pattern_typing = dict()

        graph_typing = self._get_graph_pattern_typing(
            graph_id, pattern, pattern_typing)
        instances = self.get_graph(graph_id).find_matching(
            pattern, nodes, graph_typing, pattern_typing)
        return instances

    def advanced_find_matching(self, graph_id, pattern_dict,
                               pattern_typing=None, nodes=None):
        """Find matching of a pattern in a graph in an advanced way."""
        if pattern_typing is None:
            pattern_typing = dict()

        graph_typing = self._get_graph_pattern_typing(
            graph_id, pattern_dict, pattern_typing, True)
        instances = self.get_graph(graph_id).advanced_find_matching(
            pattern_dict, nodes, graph_typing, pattern_typing)
        return instances

    def rewrite(self, graph_id, rule, instance,
                p_typing=None, rhs_typing=None, strict=False):
        """Rewrite and propagate the changes backward & forward.

        Rewriting in the hierarchy cosists of an application of the
        SqPO-rewriting rule (given by the 'rule' parameter) to a
        graph in the hierarchy. Such rewriting often triggers a set of
        changes that are applied to other graphs and homomorphisms in the
        hierarchy, which are necessary to ensure that the hierarchy stays
        consistent. If the rule is restrictive (deletes nodes/edges/attrs
        or clones nodes), in general, the respective changes to all the graphs
        (transitively) typed by the graph subject to rewriting are made.
        On the other hand, if the rule is relaxing (adds nodes/edges/attrs
        or merges nodes), in general, the respective changes to all the graphs
        that (tansitively) type the graph subject to rewriting are made.


        Parameters
        ----------
        graph_id
            Id of the graph in the hierarchy to rewrite
        rule : regraph.rule.Rule
            Rule object to apply
        instance : dict, optional
            Dictionary containing an instance of the lhs of the rule in
            the graph subject to rewriting, by default, tries to construct
            identity morphism of the nodes of the pattern
        p_typing : dict, optional
            Dictionary containing typing of graphs in the hierarchy by the
            interface of the rule, keys are ids of hierarchy graphs,
            values are dictionaries containing the mapping of nodes from
            the hierarchy graphs to the inteface nodes (note that a node
            from a graph can be typed by a set of nodes in
            the interface of the rule, e.g. if we want to perform
            cloning of some types, etc).
        rhs_typing : dict, optional
            Dictionary containing typing of the rhs by graphs of the hierarchy,
            keys are ids of hierarchy graphs, values are dictionaries
            containing the mapping of nodes from the rhs to the nodes of
            the typing graph given by the respective key of the value
            (note that a node from the rhs can be typed by a set of nodes of
            some graph, e.g. if we want to perform merging of some types, etc).
        strict : bool, optional
            Rewriting is strict when propagation down is not allowed

        Raises
        ------
        HierarchyError
            If the graph is not in the database
        RewritingError
            If the provided p and rhs typing are inconsistent
        """
        # Type check the input rule, its instance and typing
        instance, p_typing, rhs_typing = self._check_rule_instance_typing(
            graph_id, rule, instance, p_typing, rhs_typing, strict)

        # Perform a restrictive rewrite
        p_g_m, g_m_g = self._restrictive_rewrite(graph_id, rule, instance)

        # Propagate backward and fix broken homomorphisms
        self._propagate_backward(
            graph_id, rule, instance, p_g_m, g_m_g, p_typing)

        # Propagate forward and fix broken homomorphisms
        rhs_g_prime = self._expansive_rewrite_and_propagate_forward(
            graph_id, rule, instance, p_g_m, rhs_typing)

        return rhs_g_prime


    def apply_rule_hierarchy(self, rule_hierarchy, instances):
        """Apply rule hierarchy.

        Parameters
        ----------
        rule_hierarchy : dict
            Dictionary containing the input rule hierarchy
        instances : dict
            Dictionary containing an instance for every rule in the hierarchy

        Returns
        -------
        rhs_instances : dict
            Dictionary containing the RHS instances for every
            graph in the hierarchy
        """
        # Check if the rule hierarchy is applicable
        self._check_applicability(rule_hierarchy, instances)

        updated_graphs = {}
        # Apply rules to the hierarchy
        for graph_id, rule in rule_hierarchy["rules"].items():
            instance = instances[graph_id]
            graph_obj = self.get_graph(graph_id)

            if rule.is_restrictive():
                p_g_m, g_m_g = self._restrictive_rewrite(
                    graph_id, rule, instance)
            else:
                p_g_m = {
                    k: instance[v]
                    for k, v in rule.p_lhs.items()
                }
                g_m_g = {
                    n: n for n in graph_obj.nodes()
                }
            updated_graphs[graph_id] = {
                "p_g_m": p_g_m,
                "g_m_g": g_m_g
            }

        # Restore homomorphisms after restrictive rewrite
        # and backward propagation
        for (source, target), (_, p_h, _) in rule_hierarchy[
                "rule_homomorphisms"].items():
            old_typing = self.get_typing(source, target)
            source_m_target_m = get_unique_map_to_pullback_complement(
                updated_graphs[target]["p_g_m"],
                updated_graphs[target]["g_m_g"],
                p_h,
                updated_graphs[source]["p_g_m"],
                compose(
                    updated_graphs[source]["g_m_g"],
                    old_typing)
            )
            self._update_mapping(source, target, source_m_target_m)

        for graph_id, rule in rule_hierarchy["rules"].items():
            graph_obj = self.get_graph(graph_id)
            if rule.is_relaxing():
                r_g_prime, g_m_g_prime = self._expansive_rewrite(
                    graph_id, rule, updated_graphs[graph_id]["p_g_m"])
            else:
                g_m_g_prime = {
                    n: n for n in graph_obj.nodes()
                }
                r_g_prime = {
                    v: updated_graphs[graph_id]["p_g_m"][k]
                    for k, v in rule.p_rhs.items()
                }

            updated_graphs[graph_id] = {
                "g_m_g_prime": g_m_g_prime,
                "r_g_prime": r_g_prime
            }

        # Restore homomorphisms after expansive rewrite
        # and forward propagation
        for (source, target), (_, _, rhs_h) in rule_hierarchy[
                "rule_homomorphisms"].items():
            old_typing = self.get_typing(source, target)
            source_p_target_p = get_unique_map_from_pushout(
                self.get_graph(source).nodes(),
                updated_graphs[source]["g_m_g_prime"],
                updated_graphs[source]["r_g_prime"],
                compose(
                    old_typing,
                    updated_graphs[target]["g_m_g_prime"]),
                compose(
                    rhs_h,
                    updated_graphs[target]["r_g_prime"])
            )
            self._update_mapping(source, target, source_p_target_p)

        return {k: v["r_g_prime"] for k, v in updated_graphs.items()}

    def _check_rule_instance_typing(self, origin_id, rule, instance,
                                    p_typing, rhs_typing, strict):
        # Normalize the instance, p_typing and rhs_typing
        if instance is None:
            instance = {
                n: n for n in rule.lhs.nodes()
            }

        if p_typing is None:
            p_typing = dict()
        else:
            p_typing = normalize_typing_relation(p_typing)
        if rhs_typing is None:
            rhs_typing = dict()
        else:
            rhs_typing = normalize_typing_relation(rhs_typing)

        # Check that the instance is valid
        try:
            check_homomorphism(
                rule.lhs,
                self.get_graph(origin_id),
                instance,
                total=True
            )
        except InvalidHomomorphism as e:
            raise RewritingError(
                "Homomorphism from the pattern to the instance subgraph "
                "is not valid, got: '{}'".format(e))

        # Check that the instance is a mono
        if not is_monic(instance):
            raise RewritingError(
                "Homomorphism from the pattern to the instance subgraph "
                "is not injective")

        # Check p_typing does not retype nodes
        for graph_id, typing in p_typing.items():
            graph_to_origin = self.get_typing(graph_id, origin_id)
            for k, v in typing.items():
                for vv in v:
                    if graph_to_origin[k] != instance[rule.p_lhs[vv]]:
                        raise RewritingError(
                            "The specified typing of '{}' ".format(graph_id) +
                            "by the interface is not valid: "
                            "node '{}' is typed by '{}' ".format(
                                k, graph_to_origin[k]) +
                            "in the origin of rewriting, while the interface "
                            "node '{}' is typed by '{}'.".format(
                                vv, instance[rule.p_lhs[vv]]))

        # Check composability of p_typing
        for graph_id, typing in p_typing.items():
            predecessors = self.predecessors(graph_id)
            for pred in predecessors:
                if pred not in p_typing:
                    # check that the typing of 'graph_id' is canonical
                    canonical = False
                    for graph_n, p_nodes in typing.items():
                        if len(p_nodes) > 0:
                            lhs_n = rule.p_lhs[list(p_nodes)[0]]
                            canonical_clones = set(keys_by_value(rule.p_lhs, lhs_n))
                            if p_nodes == canonical_clones:
                                canonical = False
                    if not canonical:
                        raise RewritingError(
                            "Typing of '{}' by the interface ".format(
                                graph_id) +
                            "is not composable with the "
                            "typig of '{}': ".format(pred) +
                            "propagation to '{}' ".format(pred) +
                            "is canonical and produces instances for {}, ".format(
                                canonical_clones) +
                            "while propagation to '{}' ".format(
                                graph_id) +
                            "produces only for '{}' ".format(
                                p_nodes)
                        )
            successors = self.successors(graph_id)
            for suc in successors:
                suc_typing = self.get_typing(graph_id, suc)
                # check p_typing for suc is composable
                for graph_n, p_nodes in typing.items():
                    suc_n = suc_typing[graph_n]
                    if suc in p_typing and suc_n in p_typing[suc]:
                        suc_p_nodes = p_typing[suc][suc_n]
                        if not p_nodes.issubset(suc_p_nodes):
                            raise RewritingError(
                                "Typing of '{}' by the interface ".format(
                                    graph_id) +
                                "is not composable with the "
                                "typig of '{}': ".format(suc) +
                                "propagation to the node "
                                "'{}' of '{}' ".format(graph_n, graph_id) +
                                "will produce instances for {} ".format(
                                    p_nodes) +
                                "while propagation to '{}' ".format(
                                    suc_n) +
                                "typing it produces only {} ".format(
                                    suc_p_nodes)
                            )
                    else:
                        # ok, because suc_n is canonically cloned
                        pass

        # Autocomplete and check rhs_typing
        new_rhs_typing = {}
        for graph_id, typing in rhs_typing.items():
            for descendant, descendant_typing in self.get_descendants(
                    graph_id).items():
                if descendant not in rhs_typing:
                    # autocomplete descendant typing in the new rhs typing
                    new_rhs_typing[descendant] = {
                        rhs_n: {
                            descendant_typing[graph_n]
                            for graph_n in graph_ns
                        }
                        for rhs_n, graph_ns in typing.items()
                    }
                else:
                    # autocomplete descendant typing with missing rhs nodes
                    # and check that already specified types for descendant
                    # are composable with the typing for 'graph_id'
                    descendant_rhs_typing = rhs_typing[descendant]
                    for rhs_n, graph_ns in typing.items():
                        if rhs_n in descendant_rhs_typing:
                            descendant_ns = descendant_rhs_typing[rhs_n]
                            for graph_n in graph_ns:
                                if descendant_typing[graph_n] not in descendant_ns:
                                    raise RewritingError(
                                        "Typing of the RHS "
                                        "by '{}' is not composable ".format(
                                            graph_id) +
                                        "with its typing by '{}': ".format(
                                            descendant) +
                                        "node '{}' is typed by '{}' ".format(
                                            rhs_n, graph_n) +
                                        "in '{}' that is not typed by ".format(
                                            graph_id) +
                                        "either of {} from '{}'".format(
                                            descendant_ns, descendant)
                                    )

                        else:
                            new_rhs_typing[descendant] = rhs_typing[descendant]
                            new_rhs_typing[descendant][rhs_n] = {
                                descendant_typing[graph_n]
                                for graph_n in graph_ns
                            }

        for g, t in new_rhs_typing.items():
            rhs_typing[g] = t

        # Check rhs_typing does not retype nodes
        for graph_id, typing in rhs_typing.items():
            origin_to_graph = self.get_typing(origin_id, graph_id)
            for k, v in typing.items():
                p_nodes = keys_by_value(rule.p_rhs, k)
                if len(p_nodes) > 0:
                    graph_nodes = set([
                        origin_to_graph[instance[rule.p_lhs[p_node]]]
                        for p_node in p_nodes])
                    if graph_nodes != v:
                        raise RewritingError(
                            "The specified typing of the RHS "
                            "by the graph '{}' ".format(graph_id) +
                            "is not valid: "
                            "node '{}' is a typed by {} ".format(
                                k, graph_nodes) +
                            "in the origin of rewriting, while it is "
                            "typed by {} in the typing.".format(v))

        # If rewriting is strict, check p_typing types all clones,
        # there are no instances of removed elements and
        # and rhs typing types all new nodes and no different
        # types are merged
        if strict is True:
            test_strictness(self, origin_id, rule, instance, p_typing, rhs_typing)

        return instance, p_typing, rhs_typing

    def _restrictive_rewrite(self, graph_id, rule, instance):
        """Perform a restrictive rewrite of the specified graph.

        This method rewrites the graph and updates its typing by
        the immediate successors. Note that as the result of this
        update, some homomorphisms (from ancestors) are broken!
        """
        # Extract the restrictive part of the rule
        restrictive_rule = Rule(p=rule.p, lhs=rule.lhs, p_lhs=rule.p_lhs)
        g = self.get_graph(graph_id)
        p_g_m = g.rewrite(
            restrictive_rule, instance)
        g_m_g = {
            v: instance[restrictive_rule.p_lhs[k]] for k, v in p_g_m.items()
        }
        g_m_g.update(
            {
                n: n for n in g.nodes() if n not in p_g_m.values()
            })
        self._restrictive_update_incident_homs(graph_id, g_m_g)
        self._restrictive_update_incident_rels(graph_id, g_m_g)

        return p_g_m, g_m_g

    def _expansive_rewrite(self, graph_id, rule, instance):
        """Perform an expansive rewrite of the specified graph.

        This method rewrites the graph and updates its typing by
        the immediate predecessors. Note that as the result of this
        update, some homomorphisms (to descendants) are broken!
        """
        # Extract the expansive part of the rule
        expansive_rule = Rule(p=rule.p, rhs=rule.rhs, p_rhs=rule.p_rhs)
        g = self.get_graph(graph_id)

        pred_typings = {
            p: self.get_typing(p, graph_id)
            for p in self.predecessors(graph_id)
        }

        adj_relations = {
            a: self.get_relation(graph_id, a)
            for a in self.adjacent_relations(graph_id)
        }
        r_g_prime = g.rewrite(
            expansive_rule, instance)

        g_m_g_prime = {
            v: r_g_prime[expansive_rule.p_rhs[k]] for k, v in instance.items()
        }
        g_m_g_prime.update(
            {
                n: n for n in g.nodes() if n not in instance.values()
            })
        self._expansive_update_incident_homs(graph_id, g_m_g_prime, pred_typings)
        self._expansive_update_incident_rels(graph_id, g_m_g_prime, adj_relations)
        return r_g_prime, g_m_g_prime

    def _compose_backward(self, pred_id, graph_id, g_m_g, graph_m_origin_m,
                          pred_m_origin_m, pred_typing):
        graph_nodes = self.get_graph(graph_id).nodes()
        return get_unique_map_to_pullback(
            graph_nodes,
            g_m_g,
            graph_m_origin_m,
            pred_typing,
            pred_m_origin_m)

    def _propagate_backward(self, origin_id, rule, instance, p_origin_m,
                            origin_m_origin, p_typing):
        """Peform backward propagation of the original rewriting.

        Parameters
        ----------

        Returns
        -------
        """
        g_m_gs = {origin_id: origin_m_origin}
        g_m_origin_ms = {}

        for graph_id in self.bfs_tree(origin_id, reverse=True):
            graph_p_typing = {}
            if graph_id in p_typing.keys():
                graph_p_typing = p_typing[graph_id]

            origin_typing = self.get_typing(graph_id, origin_id)

            g_m_g = self._get_identity_map(graph_id)

            g_m_origin_m = copy.deepcopy(origin_typing)
            # Propagate node clones
            if len(rule.cloned_nodes()) > 0:
                self._propagate_clone(
                    origin_id, graph_id, p_origin_m,
                    origin_m_origin, graph_p_typing,
                    g_m_g, g_m_origin_m)

            # Propagate node deletes
            if len(rule.removed_nodes()) > 0:
                self._propagate_node_removal(
                    origin_id, graph_id, rule, instance,
                    g_m_g, g_m_origin_m)

            # Propagate node attrs deletes
            if len(rule.removed_node_attrs()) > 0:
                self._propagate_node_attrs_removal(
                    origin_id, graph_id, rule,
                    p_origin_m, g_m_origin_m)

            # Propagate edge deletes
            if len(rule.removed_edges()) > 0:
                self._propagate_edge_removal(
                    origin_id, graph_id, g_m_origin_m)

            # Propagate edge attrs deletes
            if len(rule.removed_edge_attrs()) > 0:
                self._propagate_edge_attrs_removal(
                    origin_id, graph_id, rule, p_origin_m,
                    g_m_origin_m)

            g_m_gs[graph_id] = g_m_g
            g_m_origin_ms[graph_id] = g_m_origin_m

        # Reconnect broken homomorphisms by composability
        for graph_id, g_m_g in g_m_gs.items():
            for pred in self.predecessors(graph_id):
                pred_typing = self.get_typing(pred, graph_id)
                if graph_id != origin_id:
                    pred_graph = self._compose_backward(
                        pred,
                        graph_id,
                        g_m_g,
                        g_m_origin_ms[graph_id],
                        g_m_origin_ms[pred],
                        pred_typing)
                else:
                    pred_graph = g_m_origin_ms[pred]

                self._update_mapping(pred, graph_id, pred_graph)

    def _expansive_rewrite_and_propagate_forward(self, origin_id, rule,
                                                 instance, p_origin_m,
                                                 rhs_typing):
        bfs_tree = self.bfs_tree(origin_id)
        bfs_tree.reverse()

        g_g_primes = {}
        rhs_g_primes = {}

        for graph in bfs_tree:

            origin_typing = self.get_typing(origin_id, graph)

            rhs_graph_typing = {}
            if graph in rhs_typing.keys():
                rhs_graph_typing = rhs_typing[graph]

            g_g_prime = {
                n: n for n in self.get_graph(graph).nodes()
            }

            rhs_g_prime = compose(p_origin_m, origin_typing)

            pred_typings = {
                p: self.get_typing(p, graph)
                for p in self.predecessors(graph)
            }
            adj_relations = {
                a: self.get_relation(graph, a)
                for a in self.adjacent_relations(graph)
            }

            # Propagate node merges
            if len(rule.merged_nodes()) > 0:
                self._propagate_merge(
                    origin_id, graph, rule,
                    p_origin_m, g_g_prime, rhs_g_prime)

            # Propagate node additions
            if len(rule.added_nodes()) > 0:
                self._propagate_node_addition(
                    origin_id, graph, rule,
                    rhs_graph_typing,
                    g_g_prime, rhs_g_prime)

            self._expansive_update_incident_homs(
                graph, g_g_prime, pred_typings)
            self._expansive_update_incident_rels(
                graph, g_g_prime, adj_relations)

            keys_to_remove = set()
            keys_to_add = dict()
            for k, v in rhs_g_prime.items():
                if k not in rule.rhs.nodes():
                    if k in rule.p.nodes():
                        keys_to_add[rule.p_rhs[k]] = v
                        keys_to_remove.add(k)
            for k in keys_to_remove:
                del rhs_g_prime[k]
            for k, v in keys_to_add.items():
                rhs_g_prime[k] = v

            # Propagate node attrs additions
            if len(rule.added_node_attrs()) > 0:
                self._propagate_node_attrs_addition(
                    origin_id, graph, rule,
                    rhs_g_prime)

            # Propagate edge additions
            if len(rule.added_edges()) > 0:
                self._propagate_edge_addition(
                    origin_id, graph, rule,
                    rhs_g_prime)

            # Propagate edge attrs additions
            if len(rule.added_edge_attrs()) > 0:
                self._propagate_edge_attrs_addition(
                    origin_id, graph, rule,
                    rhs_g_prime)

            g_g_primes[graph] = g_g_prime
            rhs_g_primes[graph] = rhs_g_prime

        # Perform an expansive rewrite
        rhs_origin_prime, origin_m_origin_prime = self._expansive_rewrite(
            origin_id, rule, p_origin_m)

        rhs_g_primes[origin_id] = rhs_origin_prime
        g_g_primes[origin_id] = origin_m_origin_prime

        # Reconnect broken homomorphisms by composability
        for graph_id, g_g_prime in g_g_primes.items():
            graph_nodes = self.get_graph(graph_id).nodes()
            for suc in self.successors(graph_id):
                suc_typing = self.get_typing(graph_id, suc)
                for rhs_node in rule.rhs.nodes():
                    g_nodes = keys_by_value(
                        g_g_prime, rhs_g_primes[graph_id][rhs_node])

                    suc_node = rhs_g_primes[suc][rhs_node]
                    for n in g_nodes:
                        suc_typing[n] = suc_node

                graph_suc = get_unique_map_from_pushout(
                    graph_nodes,
                    rhs_g_primes[graph_id],
                    g_g_prime,
                    rhs_g_primes[suc],
                    suc_typing)
                self._update_mapping(graph_id, suc, graph_suc)
        return rhs_origin_prime

    @staticmethod
    def _produce_clones(origin_clones, p_origin_m, g, origin_typing, graph_p,
                        local_g_m_g, local_g_m_origin_m):
        cloned_nodes = {}
        for n, clones in origin_clones.items():
            nodes_to_clone = keys_by_value(origin_typing, n)
            for node in nodes_to_clone:
                if node in graph_p.keys():
                    p_nodes = graph_p[node]
                else:
                    p_nodes = [
                        keys_by_value(p_origin_m, c)[0] for c in clones
                    ]
                for i, p_node in enumerate(p_nodes):
                    if i == 0:
                        cloned_nodes[node] = p_node
                        local_g_m_g[node] = node
                        local_g_m_origin_m[node] = p_origin_m[p_node]
                    else:
                        new_name = g.clone_node(node)
                        cloned_nodes[new_name] = p_node
                        local_g_m_g[new_name] = node
                        local_g_m_origin_m[new_name] = p_origin_m[p_node]
        return cloned_nodes

    def _propagate_clone(self, origin_id, node_id, p_origin_m,
                         origin_m_origin, p_typing,
                         g_m_g, g_m_origin_m):
        """Propagate clones from 'origin_id' to 'graph_id'.

        Perform a controlled propagation of clones to 'graph'

        Parameters
        ----------
        origin_id : hashable
            ID of the graph corresponding to the origin of rewriting
        graph_id : hashable
            ID of the graph where propagation is performed
        p_origin_m : dict
            Instance of rule's interface inside the updated origin
        origin_m_origin : dict
            Map from the updated origin to the initial origin
        p_typing : dict
            Controlling relation from the nodes of 'graph_id' to
            the nodes of the interfaces

        Returns
        -------
        g_m_g : dict
            Map from the updated 'graph_id' to the 'graph_id'
        """
        cloned_origin_nodes = {}
        for n in set(origin_m_origin.values()):
            clones = keys_by_value(origin_m_origin, n)
            if len(clones) > 1:
                cloned_origin_nodes[n] = clones

        graph = self.get_graph(node_id)
        origin_typing = self.get_typing(node_id, origin_id)

        cloned_origin_nodes = {}
        for n in set(origin_m_origin.values()):
            clones = keys_by_value(origin_m_origin, n)
            if len(clones) > 1:
                cloned_origin_nodes[n] = clones

        self._produce_clones(
            cloned_origin_nodes, p_origin_m,
            graph, origin_typing, p_typing,
            g_m_g, g_m_origin_m)

        self._restrictive_update_incident_homs(node_id, g_m_g)
        self._restrictive_update_incident_rels(node_id, g_m_g)

        return g_m_g, g_m_origin_m

    def _propagate_node_removal(self, origin_id, node_id, rule, instance,
                                g_m_g, g_m_origin_m):
        """Propagate node removal from 'origin_id' to 'graph_id'.

        Parameters
        ----------
        origin_id : hashable
            ID of the graph corresponding to the origin of rewriting
        graph_id : hashable
            ID of the graph where propagation is performed
        origin_m_origin : dict
            Map from the updated origin to the initial origin

        Returns
        -------
        g_m_g : dict
            Map from the updated 'graph_id' to the 'graph_id'
        """
        graph = self.get_graph(node_id)
        origin_typing = self.get_typing(node_id, origin_id)

        for lhs_node in rule.removed_nodes():
            origin_n = instance[lhs_node]
            graph_nodes = keys_by_value(origin_typing, origin_n)
            for node in graph_nodes:
                graph.remove_node(node)
                del g_m_g[node]
                del g_m_origin_m[node]

        for node in graph.nodes():
            if node not in origin_typing.keys():
                graph.remove_node(node)
                del g_m_g[node]
                del g_m_origin_m[node]

        self._restrictive_update_incident_homs(node_id, g_m_g)
        self._restrictive_update_incident_rels(node_id, g_m_g)

        return g_m_g, g_m_origin_m

    def _propagate_node_attrs_removal(self, origin_id, node_id, rule,
                                      p_origin_m, g_m_origin_m):
        """Propagate node attrs removal from 'origin_id' to 'graph_id'.

        Parameters
        ----------
        origin_id : hashable
            ID of the graph corresponding to the origin of rewriting
        graph_id : hashable
            ID of the graph where propagation is performed
        rule : regraph.Rule
            Original rewriting rule
        instance : dict
            Original instance
        """
        graph = self.get_graph(node_id)
        # origin_typing = self.get_typing(node_id, origin_id)
        for p_node, attrs in rule.removed_node_attrs().items():
            nodes_to_remove_attrs = keys_by_value(
                g_m_origin_m, p_origin_m[p_node])
            for node in nodes_to_remove_attrs:
                graph.remove_node_attrs(node, attrs)

    def _propagate_edge_removal(self, origin_id, node_id, g_m_origin_m):
        """Propagate edge removal from 'origin_id' to 'graph_id'.

        Parameters
        ----------
        origin_id : hashable
            ID of the graph corresponding to the origin of rewriting
        node_id : hashable
            ID of the node where propagation is performed
        p_origin_m : dict
            Instance of rule's interface inside the updated origin
        origin_m_origin : dict
            Map from the updated origin to the initial origin
        """
        graph = self.get_graph(node_id)
        origin_graph = self.get_graph(origin_id)

        edges_to_remove = set()
        for s, t in graph.edges():
            origin_s = g_m_origin_m[s]
            origin_t = g_m_origin_m[t]
            if (origin_s, origin_t) not in origin_graph.edges():
                edges_to_remove.add((s, t))

        for s, t in edges_to_remove:
            graph.remove_edge(s, t)

    def _propagate_edge_attrs_removal(self, origin_id, node_id, rule, p_origin_m,
                                      g_m_origin_m):
        """Propagate edge attrs removal from 'origin_id' to 'graph_id'.

        Parameters
        ----------
        origin_id : hashable
            ID of the graph corresponding to the origin of rewriting
        graph_id : hashable
            ID of the graph where propagation is performed
        rule : regraph.Rule
            Original rewriting rule
        p_origin_m : dict
            Instance of rule's interface inside the updated origin
        """
        graph = self.get_graph(node_id)

        for (p_u, p_v), attrs in rule.removed_edge_attrs().items():
            us = keys_by_value(g_m_origin_m, p_origin_m[p_u])
            vs = keys_by_value(g_m_origin_m, p_origin_m[p_v])
            for u in us:
                for v in vs:
                    if (u, v) in graph.edges():
                        graph.remove_edge_attrs(u, v, attrs)

    def _propagate_merge(self, origin_id, graph_id, rule, p_origin_m,
                         g_g_prime, rhs_g_prime):
        """Propagate merges from 'origin_id' to 'graph_id'.

        Perform a propagation of merges to 'graph'

        Parameters
        ----------
        origin_id : hashable
            ID of the graph corresponding to the origin of rewriting
        graph_id : hashable
            ID of the graph where propagation is performed
        rule : regraph.Rule
            Original rewriting rule
        p_origin_m : dict
            Instance of rule's interface inside the updated origin
        rhs_origin_prime : dict
            Instance of rule's rhs inside the updated origin
        g_g_prime : dict
            Map from the nodes of the graph 'graph_id' to the updated graph
        rhs_g_prime : dict
            Map from the RHS to the updated graph with 'graph_id'
        """
        graph = self.get_graph(graph_id)

        for rhs_node, p_nodes in rule.merged_nodes().items():
            graph_nodes = set([
                rhs_g_prime[p_node]
                for p_node in p_nodes
            ])
            if len(graph_nodes) > 1:
                merged_node_id = graph.merge_nodes(graph_nodes)
                for n in graph_nodes:
                    g_g_prime[n] = merged_node_id
                for p_node in p_nodes:
                    if p_node in rhs_g_prime:
                        del rhs_g_prime[p_node]
                rhs_g_prime[rhs_node] = merged_node_id
                map_to_merge_node = set()
                for rhs_n, g_prime_n in rhs_g_prime.items():
                    if g_prime_n in graph_nodes:
                        map_to_merge_node.add(rhs_n)
                for n in map_to_merge_node:
                    rhs_g_prime[n] = merged_node_id
            else:
                for p_node in p_nodes:
                    if p_node in rhs_g_prime:
                        del rhs_g_prime[p_node]
                rhs_g_prime[rhs_node] = list(graph_nodes)[0]

    def _propagate_node_addition(self, origin_id, graph_id, rule,
                                 rhs_typing, g_g_prime, rhs_g_prime):
        """Propagate node additions from 'origin_id' to 'graph_id'.

        Perform a propagation of additions to 'graph'

        Parameters
        ----------
        origin_id : hashable
            ID of the graph corresponding to the origin of rewriting
        graph_id : hashable
            ID of the graph where propagation is performed
        rule : regraph.Rule
            Original rewriting rule
        rhs_origin_prime : dict
            Instance of rule's rhs inside the updated origin
        rhs_typing : dict
            Typing of the nodes from the rhs in 'graph_id'
        rhs_g_prime : dict
            Map from the RHS to the updated graph with 'graph_id'
        """
        graph = self.get_graph(graph_id)

        for rhs_node in rule.added_nodes():
            if rhs_node in rhs_typing:
                if len(rhs_typing[rhs_node]) == 1:
                    rhs_g_prime[rhs_node] = list(
                        rhs_typing[rhs_node])[0]
                else:
                    nodes_to_merge = rhs_typing[rhs_node]
                    new_node_id = graph.merge_nodes(nodes_to_merge)
                    for n in nodes_to_merge:
                        g_g_prime[n] = new_node_id
                        p_nodes = keys_by_value(rhs_g_prime, n)
                        for p_node in p_nodes:
                            if p_node in rhs_g_prime:
                                del rhs_g_prime[p_node]
                    rhs_g_prime[rhs_node] = new_node_id
                    map_to_merge_node = set()
                    for rhs_n, g_prime_n in rhs_g_prime.items():
                        if g_prime_n in nodes_to_merge:
                            map_to_merge_node.add(rhs_n)
                    for n in map_to_merge_node:
                        rhs_g_prime[n] = new_node_id
            else:
                new_node_id = graph.generate_new_node_id(rhs_node)
                graph.add_node(new_node_id)
                rhs_g_prime[rhs_node] = new_node_id

    def _propagate_node_attrs_addition(self, origin_id, graph_id, rule,
                                       rhs_g_prime):
        """Propagate node attrs additions from 'origin_id' to 'graph_id'.

        Perform a propagation of additions to 'graph'

        Parameters
        ----------
        origin_id : hashable
            ID of the graph corresponding to the origin of rewriting
        graph_id : hashable
            ID of the graph where propagation is performed
        rule : regraph.Rule
            Original rewriting rule
        rhs_origin_prime : dict
            Instance of rule's rhs inside the updated origin
        origin_prime_g_prime : dict
            Map from the updated origin to the updated graph with 'graph_id'
        """
        graph = self.get_graph(graph_id)

        for rhs_node, attrs in rule.added_node_attrs().items():
            graph.add_node_attrs(
                rhs_g_prime[rhs_node],
                attrs)

    def _propagate_edge_addition(self, origin_id, graph_id, rule,
                                 rhs_g_prime):
        """Propagate edge additions from 'origin_id' to 'graph_id'.

        Perform a propagation of additions to 'graph'

        Parameters
        ----------
        origin_id : hashable
            ID of the graph corresponding to the origin of rewriting
        graph_id : hashable
            ID of the graph where propagation is performed
        rule : regraph.Rule
            Original rewriting rule
        rhs_origin_prime : dict
            Instance of rule's rhs inside the updated origin
        origin_prime_g_prime : dict
            Map from the updated origin to the updated graph with 'graph_id'
        """
        graph = self.get_graph(graph_id)
        for s, t in rule.added_edges():
            g_s = rhs_g_prime[s]
            g_t = rhs_g_prime[t]
            if (g_s, g_t) not in graph.edges():
                graph.add_edge(g_s, g_t)

    def _propagate_edge_attrs_addition(self, origin_id, graph_id, rule,
                                       rhs_g_prime):
        """Propagate edge attrs additions from 'origin_id' to 'graph_id'.

        Perform a propagation of additions to 'graph'

        Parameters
        ----------
        origin_id : hashable
            ID of the graph corresponding to the origin of rewriting
        graph_id : hashable
            ID of the graph where propagation is performed
        """
        graph = self.get_graph(graph_id)
        for (s, t), attrs in rule.added_edge_attrs().items():
            g_s = rhs_g_prime[s]
            g_t = rhs_g_prime[t]
            graph.add_edge_attrs(g_s, g_t, attrs)

    def _get_identity_map(self, graph_id):
        return {
            n: n for n in self.get_graph(graph_id).nodes()
        }

    def _restrictive_update_incident_homs(self, node_id, g_m_g):
        for suc in self.successors(node_id):
            typing = self.get_typing(node_id, suc)
            self._update_mapping(node_id, suc, compose(g_m_g, typing))

    def _restrictive_update_incident_rels(self, graph_id, g_m_g):
        for related_g in self.adjacent_relations(graph_id):
            rel = self.get_relation(graph_id, related_g)
            new_rel = dict()
            for node in self.get_graph(graph_id).nodes():
                old_node = g_m_g[node]
                ns = keys_by_value(g_m_g, old_node)
                if old_node in rel.keys():
                    new_rel[node] = rel[old_node]
            self._update_relation(graph_id, related_g, new_rel)

    def _expansive_update_incident_homs(self, graph_id, g_m_g_prime,
                                        pred_typings):
        for pred, typing in pred_typings.items():
            self._update_mapping(
                pred, graph_id, compose(typing, g_m_g_prime))

    def _expansive_update_incident_rels(self, graph_id, g_m_g_prime,
                                        adj_relations):
        for related_g, rel in adj_relations.items():
            new_rel = dict()

            for node in self.get_graph(graph_id).nodes():
                if node in g_m_g_prime:
                    new_node = g_m_g_prime[node]
                    if node in rel.keys():
                        new_rel[new_node] = rel[node]

            self._update_relation(graph_id, related_g, new_rel)

    def _check_applicability(self, rule_hierarchy, instances):
        """Check if a rule hierarchy is applicable."""
        # Check that instances commute
        for (s, t) in self.typings():
            if s in instances and t in instances:
                typing = self.get_typing(s, t)
                lhs_s_t1 = compose(instances[s], typing)
                lhs_s_t2 = compose(
                    rule_hierarchy["rule_homomorphisms"][(s, t)][0],
                    instances[t])
                if (lhs_s_t1 != lhs_s_t2):
                    raise RewritingError(
                        "Instance of a specified rule for '{}' ({}) ".format(
                            s, instances[s]) +
                        "is not compatible with such instance for '{}' ({})".format(
                            t, instances[t]))

                # Check the applicability
                t_rule = rule_hierarchy["rules"][t]
                if t_rule.is_restrictive():
                    # Check the square L_S -> S -> T and L_S -> L_T -> T is a PB
                    for lhs_t_node in t_rule.lhs.nodes():
                        t_node = instances[t][lhs_t_node]
                        s_nodes = keys_by_value(typing, t_node)
                        if lhs_t_node in t_rule.removed_nodes():
                            for s_node in s_nodes:
                                error = False
                                if s_node not in instances[s].values():
                                    error = True
                                elif keys_by_value(instances[s], s_node)[
                                        0] not in rule_hierarchy[
                                            "rules"][s].removed_nodes():
                                    error = True
                                if error:
                                    raise RewritingError(
                                        "Specified rule hierarchy is not applicable "
                                        "the typing of the node '{}' ".format(s_node) +
                                        "from the graph '{}' is removed ".format(s) +
                                        "by rewriting of '{}', but ".format(t) +
                                        "this node is not removed by the rule " +
                                        "applied to '{}'".format(s)
                                    )

                        if lhs_t_node in t_rule.cloned_nodes():
                            for s_node in s_nodes:
                                if s_node not in instances[s].values():
                                    raise RewritingError(
                                        "Specified rule hierarchy is not applicable "
                                        "the typing of the node '{}' ".format(s_node) +
                                        "from the graph '{}' is cloned ".format(s) +
                                        "by rewriting of '{}', but the ".format(t) +
                                        "retyping of this node is not specified, i.e. " +
                                        "'{}' is not in the instances of ".format(s_node) +
                                        "the rule applied to '{}'".format(s)
                                    )

    def relabel_nodes(self, graph, mapping):
        """Relabel nodes of a graph in the hierarchy."""
        graph = self.get_graph(graph)
        graph.relabel_nodes(mapping)

    def graphs_typed_by_node(self, graph_id, node_id):
        """Get graphs typed by 'node_id' in 'graph_id'."""
        graphs = []
        for p in self.predecessors(graph_id):
            p_typing = self.get_typing(p, graph_id)
            if node_id in p_typing.values():
                graphs.append(p)
        return graphs class Neo4jGraph(Graph):
    """Class implementing Neo4j graph instance.

    This class encapsulates neo4j.v1.GraphDatabase object.
    It provides an interface for accessing graph sitting
    in the DB. This interface is similar (in fact is
    intended to be as similar as possible) to the
    `networkx.DiGraph` object.

    Attributes
    ----------
    _driver :  neo4j.v1.GraphDatabase
        Driver providing connection to a Neo4j database
    _node_label : str
        Label of nodes inducing the manipulated subgraph.
    _edge_label : str
        Type of relations used in the manipulated subgraph.
    """

    def __init__(self, driver=None, uri=None,
                 user=None, password=None,
                 node_label="node",
                 edge_label="edge",
                 unique_node_ids=True):
        """Initialize Neo4jGraph object.

        Parameters
        ----------
        driver : neo4j.v1.direct.DirectDriver, optional
            Driver providing connection to a Neo4j database
        uri : str, optional
            Uri for a new Neo4j database connection (bolt)
        user : str, optional
            Username for the Neo4j database connection
        password : str, optional
            Password for the Neo4j database connection
        node_label : optional
            Label of nodes inducing the subgraph to scope.
            By default `"node"`.
        edge_label : optional
            Type of relations inducing the subgraph to scope.
            By default `"edge"`.
        unique_node_ids : bool, optional
            Flag, if True the uniqueness constraint on the property
            'id' of nodes is imposed, by default True

        If database driver is provided, uses it for
        connecting to database, otherwise creates
        a new driver object using provided credentials.
        """
        if driver is None:
            self._driver = GraphDatabase.driver(
                uri, auth=(user, password))
        else:
            self._driver = driver

        self._node_label = node_label
        self._edge_label = edge_label
        self.unique_node_ids = unique_node_ids
        if unique_node_ids:
            try:
                self._set_constraint('id')
            except:
                warnings.warn(
                    "Failed to create id uniqueness constraint")

    def _execute(self, query):
        """Execute a Cypher query."""
        with self._driver.session() as session:
            if len(query) > 0:
                result = session.run(query)
                return result

    def _close(self):
        """Close connection to the database."""
        self._driver.close()

    def _clear(self):
        """Clear graph database.

        Returns
        -------
        result : BoltStatementResult
        """
        query = generic.clear_graph(self._node_label)
        result = self._execute(query)
        return result

    def _set_constraint(self, prop):
        """Set a uniqueness constraint on the property.

        Parameters
        ----------
        prop : str
            Name of the property that is required to be unique
            for the nodes of the database


        Returns
        -------
        result : BoltStatementResult
        """
        query = "CREATE " + generic.constraint_query(
            'n', self._node_label, prop)
        result = self._execute(query)
        return result

    def _drop_constraint(self, prop):
        """Drop a uniqueness constraint on the property.

        Parameters
        ----------
        prop : str
            Name of the property

        Returns
        -------
        result : BoltStatementResult
        """
        try:
            query = "DROP " + generic.constraint_query('n', self._node_label, prop)
            result = self.execute(query)
            return result
        except:
            warnings.warn("Failed to drop constraint")

    def nodes(self, data=False):
        """Return a list of nodes of the graph."""
        query = generic.get_nodes(node_label=self._node_label, data=data)
        result = self._execute(query)

        node_list = []
        for d in result:
            node_id = d["node_id"]
            if data:
                attrs = d["attrs"]
                del attrs["id"]
                normalize_attrs(attrs)
                node_list.append((node_id, attrs))
            else:
                node_list.append(node_id)
        return node_list

    def edges(self, data=False):
        """Return the list of edges of the graph."""
        query = generic.get_edges(
            self._node_label,
            self._node_label,
            self._edge_label,
            data=data)
        result = self._execute(query)
        edges = []

        for d in result:
            if d["source_id"] not in self.nodes():
                s = int(d["source_id"])
            else:
                s = d["source_id"]
            if d["target_id"] not in self.nodes():
                t = int(d["target_id"])
            else:
                t = d["target_id"]
            if data:
                normalize_attrs(d["attrs"])
                edges.append((s, t, d["attrs"]))
            else:
                edges.append((s, t))

        return edges

    def get_node(self, node_id):
        """Get node attributes.

        Parameters
        ----------
        graph : networkx.(Di)Graph or regraph.neo4j.Neo4jGraph
        node_id : hashable, node id.
        """
        query = generic.get_node_attrs(
            node_id, self._node_label,
            "attributes")
        result = self._execute(query)
        attrs = generic.properties_to_attributes(
            result, "attributes")
        return attrs

    def get_edge(self, s, t):
        """Get edge attributes.

        Parameters
        ----------
        graph : networkx.(Di)Graph
        s : hashable, source node id.
        t : hashable, target node id.
        """
        query = generic.get_edge_attrs(
            s, t,
            self._node_label,
            self._edge_label,
            "attributes")
        result = self._execute(query)
        return generic.properties_to_attributes(
            result, "attributes")

    def add_node(self, node, attrs=None, ignore_naming=False):
        """Abstract method for adding a node.

        Parameters
        ----------
        node : hashable
            Prefix that is prepended to the new unique name.
        attrs : dict, optional
            Node attributes.
        """
        if attrs is None:
            attrs = dict()
        normalize_attrs(attrs)
        query =\
            rewriting.add_node(
                "n", node, 'new_id',
                node_label=self._node_label,
                attrs=attrs,
                literal_id=True,
                ignore_naming=ignore_naming)[0] +\
            generic.return_vars(['new_id'])

        result = self._execute(query)
        new_id = result.single()['new_id']
        return new_id

    def remove_node(self, node):
        """Remove node.

        Parameters
        ----------
        graph : networkx.(Di)Graph
        node_id : hashable, node to remove.
        """
        query =\
            generic.match_node(
                "n", node,
                node_label=self._node_label) +\
            rewriting.remove_node("n")
        result = self._execute(query)
        return result

    def add_edge(self, s, t, attrs=None, **attr):
        """Add an edge to a graph.

        Parameters
        ----------
        graph : networkx.(Di)Graph
        s : hashable, source node id.
        t : hashable, target node id.
        attrs : dict
            Edge attributes.
        """
        if attrs is None:
            attrs = dict()
        normalize_attrs(attrs)
        query = generic.match_nodes(
            {"s": s, "t": t},
            node_label=self._node_label)
        query += rewriting.add_edge(
            edge_var='new_edge',
            source_var="s",
            target_var="t",
            edge_label=self._edge_label,
            attrs=attrs)
        result = self._execute(query)
        return result

    def remove_edge(self, s, t):
        """Remove edge from the graph.

        Parameters
        ----------
        graph : networkx.(Di)Graph
        s : hashable, source node id.
        t : hashable, target node id.
        """
        query =\
            generic.match_edge(
                "s", "t", s, t, 'edge_var',
                self._node_label, self._node_label,
                edge_label='edge') +\
            rewriting.remove_edge('edge_var')
        result = self._execute(query)
        return result

    def update_node_attrs(self, node_id, attrs, normalize=True):
        """Update attributes of a node.

        Parameters
        ----------
        node_id : hashable, node to update.
        attrs : dict
            New attributes to assign to the node

        """
        normalize_attrs(attrs)
        query = (
            generic.match_node("n", node_id, self._node_label) +
            generic.set_attributes("n", attrs, update=True)
        )
        result = self._execute(query)
        return result

    def update_edge_attrs(self, s, t, attrs, normalize=True):
        """Update attributes of a node.

        Parameters
        ----------
        s : hashable, source node of the edge to update.
        t : hashable, target node of the edge to update.
        attrs : dict
            New attributes to assign to the node

        """
        normalize_attrs(attrs)
        query = (
            generic.match_edge(
                "s", "t", s, t, "rel",
                self._node_label, self._node_label,
                self._edge_label) +
            generic.set_attributes("rel", attrs, update=True)
        )
        result = self._execute(query)
        return result

    def successors(self, node_id):
        """Return the set of successors."""
        query = generic.successors_query(
            node_id, node_id,
            node_label=self._node_label,
            edge_label=self._edge_label)
        result = self._execute(query)
        succ = set()
        for record in result:
            if record["suc"] is not None:
                succ.add(record["suc"])
        return succ

    def predecessors(self, node_id):
        """Return the set of predecessors."""
        query = generic.predecessors_query(
            node_id, node_id,
            node_label=self._node_label,
            edge_label=self._edge_label)
        result = self._execute(query)
        pred = set()
        for record in result:
            if record["pred"] is not None:
                pred.add(record["pred"])
        return pred

    def advanced_find_matching(self, pattern_dict,
                               nodes=None, graph_typing=None,
                               pattern_typing=None):
        """Find matching of a pattern in a graph in an advanced way."""
        patterns = []

        pattern = NXGraph()
        pattern.add_nodes_from(pattern_dict["nodes"])
        pattern.add_edges_from(pattern_dict["directed_edges"])
        pattern.add_edges_from(pattern_dict["undirected_edges"])

        undirected_edges = [
            (u_var, v_var)
            for (u_var, v_var, _) in pattern_dict["undirected_edges"]
        ]

        instances = []
        for pattern in patterns:
            instances += self.find_matching(
                pattern, nodes, graph_typing, pattern_typing,
                undirected_edges=undirected_edges)
        return instances

    def find_matching(self, pattern, nodes=None,
                      graph_typing=None, pattern_typing=None,
                      undirected_edges=None):
        """Find matching of a pattern in a graph."""
        new_pattern_typing = dict()
        if pattern_typing:
            for graph, pattern_mapping in pattern_typing.items():
                new_pattern_typing[graph] = normalize_relation(
                    pattern_mapping)

        if len(pattern.nodes()) != 0:

            # filter nodes by typing
            matching_nodes = set()
            for pattern_node in pattern.nodes():
                for node in self.nodes():
                    type_matches = True
                    if new_pattern_typing:
                        # check types match
                        for graph, pattern_mapping in new_pattern_typing.items():
                            if node in graph_typing[graph].keys() and\
                               pattern_node in pattern_mapping.keys():
                                if graph_typing[graph][node] not in pattern_mapping[
                                        pattern_node]:
                                    type_matches = False
                    if type_matches and nodes and node in nodes:
                        matching_nodes.add(node)

            query = rewriting.find_matching(
                pattern,
                node_label=self._node_label,
                edge_label=self._edge_label,
                nodes=matching_nodes,
                pattern_typing=new_pattern_typing,
                undirected_edges=undirected_edges)

            result = self._execute(query)
            instances = list()

            for record in result:
                instance = dict()
                for k, v in record.items():
                    instance[k] = dict(v)["id"]

                new_instance = dict()
                for pattern_node, v in instance.items():
                    if pattern_node not in pattern.nodes():
                        new_instance[int(pattern_node)] = v
                    else:
                        new_instance[pattern_node] = v

                instances.append(new_instance)
        else:
            instances = []
        return instances

    def relabel_node(self, node_id, new_id):
        """Relabel a node in the graph.

        Parameters
        ----------
        node_id : hashable
            Id of the node to relabel.
        new_id : hashable
            New label of a node.
        """
        if new_id in self.nodes():
            raise ReGraphError(
                "Cannot relabel '{}' to '{}', '{}' ".format(
                    node_id, new_id, new_id) +
                "already exists in the graph")
        query = generic.set_id(self._node_label, node_id, new_id)
        result = self._execute(query)
        return result

    @classmethod
    def from_json(cls, driver=None, uri=None, user=None, password=None,
                  json_data=None, node_label="node", edge_label="edge"):
        """Create a Neo4jGraph from a json-like dictionary.

        Parameters
        ----------
        json_data : dict
            JSON-like dictionary with graph representation
        """
        graph = cls(
            driver=driver, uri=uri, user=user, password=password,
            node_label=node_label, edge_label=edge_label)
        graph.add_nodes_from(load_nodes_from_json(json_data))
        graph.add_edges_from(load_edges_from_json(json_data))
        return graph

    @classmethod
    def load(cls, driver=None, uri=None, user=None, password=None,
             filename=None, node_label="node", edge_label="edge"):
        """Load a Neo4jGraph from a JSON file.

        Create a graph object from
        a JSON representation stored in a file.

        Parameters
        ----------
        driver : neo4j.v1.direct.DirectDriver, optional
            Driver providing connection to a Neo4j database
        uri : str, optional
            Uri for a new Neo4j database connection (bolt)
        user : str, optional
            Username for the Neo4j database connection
        password : str, optional
            Password for the Neo4j database connection
        filename : str, optional
            Name of the file to load the json serialization of the graph
        node_label : optional
            Label of nodes inducing the subgraph to scope.
            By default `"node"`.
        edge_label : optional
            Type of relations inducing the subgraph to scope.
            By default `"edge"`.

        Returns
        -------
        Graph object

        Raises
        ------
        ReGraphError
            If was not able to load the file

        """
        if os.path.isfile(filename):
            with open(filename, "r+") as f:
                j_data = json.loads(f.read())
                return cls.from_json(
                    driver=driver, uri=uri, user=user, password=password,
                    json_data=j_data, node_label=node_label, edge_label=edge_label)
        else:
            raise ReGraphError(
                "Error loading graph: file '{}' does not exist!".format(
                    filename)
            )

    def nodes_disconnected_from(self, node_id):
        """Find nodes disconnected from the input node."""
        query = (
            "MATCH (n:{} {{id: '{}'}}), (m:{})\n".format(
                self._node_label, node_id, self._node_label) +
            "WHERE NOT (n)-[:{}*1..]-(m) AND n.id <> m.id\n".format(
                self._edge_label) +
            "RETURN collect(m.id) as disconnected_nodes"
        )
        res = self._execute(query)
        for record in res:
            return record["disconnected_nodes"] def constraint_query(node_var, node_label, node_property):
    """Generate query for creating a constraint on a property."""
    query = "CONSTRAINT ON ({}:{}) ASSERT {}.{} IS UNIQUE".format(
        node_var,
        node_label,
        node_var,
        node_property
    )
    return query def get_nodes(node_label, data=False):
    """Generate query returning ids of all nodes of the graph.

    Parameters
    ----------
    label
        Label of the nodes to match, default is 'node'
    """
    if data:
        query = "MATCH (n:{}) RETURN n.id as node_id, properties(n) as attrs\n".format(node_label)
    else:
        query = "MATCH (n:{}) RETURN n.id as node_id\n".format(node_label)
    return query def get_edges(source_label, target_label,
              edge_label, data=False):
    """Generate query for getting all the edges of the graph.

    Parameters
    ----------
    source_label : optional
        Label of the source nodes to match
    target_label : optional
        Label of the target nodes to match
    edge_label : iterable, optional
        Label of the edges to match
    """
    if data:
        query = "MATCH (n:{})-[r:{}]->(m:{})\nRETURN n.id as source_id, m.id as target_id, properties(r) as attrs\n".format(
                source_label,
                edge_label,
                target_label)
    else:
        query = "MATCH (n:{})-[r:{}]->(m:{})\nRETURN n.id as source_id, m.id as target_id\n".format(
                source_label,
                edge_label,
                target_label)
    return query def clear_graph(node_label=None):
    """Generate query for removing everything from the graph.

    Parameters
    ----------
    label
        Label of the graph to remove. If None, all the database is cleared
    """
    if node_label is None:
        query = "MATCH (n)\n"
    else:
        query = "MATCH (n:{})\n".format(node_label)
    query += \
        "OPTIONAL MATCH (n)-[r]-()\n" +\
        "DELETE n, r\n"
    return query def successors_query(var_name, node_id, node_label,
                     edge_label, successor_label=None,
                     undirected=False):
    """Generate query for getting the ids of all the successors of a node.

    Parameters
    ----------
    var_name
        Name of the variable corresponding to the node to match
    node_id
        Id of the node to match
    node_label : optional
        Label of the node to match, default is 'node'
    edge_label : optional
        Label of the edge to match, default is 'edge'
    successor_label : optional
        Label of the successors we want to find,
        'node_label' is used if None.
    """
    if successor_label is None:
        successor_label = node_label
    if undirected is False:
        arrow = ">"
    else:
        arrow = ""
    query = (
        "OPTIONAL MATCH (`{}`:{} {{id : '{}'}})-[:{}]-{}(suc:{})\n".format(
            var_name, node_label,
            node_id, edge_label,
            arrow,
            successor_label) +
        "RETURN suc.id as suc"
    )
    return query def predecessors_query(var_name, node_id, node_label,
                       edge_label, predecessor_label=None):
    """Generate query for getting the ids of all the predecessors of a node.

    Parameters
    ----------
    var_name
        Name of the variable corresponding to the node to match
    node_id
        Id of the node to match
    node_label
        Label of the node to match
    edge_label
        Label of the edge to match
    predecessor_label
        Label of the predecessors we want to find. node_label if None.
    """
    if predecessor_label is None:
        predecessor_label = node_label
    query = (
        "OPTIONAL MATCH (pred:{})-[:{}]-> (n:{} {{id : '{}'}})\n".format(
            predecessor_label,
            edge_label,
            node_label, node_id) +
        "RETURN pred.id as pred"
    )
    return query def get_edge_attrs(source_id, targe_id, node_label, edge_label, attrs_var):
    """Query for retreiving edge's attributes."""
    query = (
        "MATCH (n:{} {{ id: '{}' }})-[rel:{}]->(m:{} {{ id: '{}' }}) \n".format(
            node_label, source_id, edge_label, node_label, targe_id) +
        "RETURN properties(rel) as {}\n".format(attrs_var)
    )
    return query def properties_to_attributes(result, var_name):
    """Retrieve attributes from raw Neo4j property dict."""
    attrs = {}
    for record in result:
        if var_name in record.keys():
            raw_dict = record[var_name]
            if raw_dict:
                attrs = convert_props_to_attrs(raw_dict)
    return attrs def get_node_attrs(node_id, node_label, attrs_var):
    """Query for retreiving node's attributes."""
    query = (
        "MATCH (n:{} {{ id: '{}' }}) \n".format(
            node_label, node_id) +
        "RETURN properties(n) as {}\n".format(attrs_var)
    )
    return query def set_attributes(var_name, attrs=None, update=False):
    """Generate a subquery to set the attributes for some variable."""
    query = ""
    if not attrs:
        query += (
            "SET {} = apoc.map.clean(properties({}), \n".format(var_name, var_name) +
            "\tfilter(x IN keys({}) WHERE NOT x IN [] AND x <> 'id'), [])".format(
                var_name)
        )
    for k, value in attrs.items():
        if isinstance(value, IntegerSet):
            if value.is_universal:
                query += "\tSET {}.{} = ['IntegerSet']\n".format(var_name, k)
            else:
                raise ReGraphError(
                    "Non universal IntegerSet is not allowed as "
                    "an attribute value (not implemented)")
        elif isinstance(value, RegexSet):
            if value.is_universal:
                query += "\tSET {}.{} = ['StringSet']\n".format(var_name, k)
            else:
                raise ReGraphError(
                    "Non universal RegexSet is not allowed as "
                    "an attribute value (not implemented)")
        elif isinstance(value, FiniteSet):
            elements = []
            for el in value:
                if type(el) == str:
                    elements.append("'{}'".format(el.replace("'", "\\'")))
                else:
                    elements.append("{}".format(el))
            if value not in RESERVED_SET_NAMES:
                query += "SET {}.{}=[{}]\n".format(var_name, k, ", ".join(
                    el for el in elements))
            else:
                query += "SET {}.{}={}\n".format(var_name, k, ", ".join(
                    el for el in elements))
        else:
            raise ValueError(
                "Unknown type of attribute '{}': '{}'".format(
                    k, type(value)))
    if update is True:
        # remove all the attributes not mentioned in 'attrs'
        query += (
            "SET {} = apoc.map.clean(properties({}), \n".format(var_name, var_name) +
            "\tfilter(x IN keys({}) WHERE NOT x IN [{}] AND x <> 'id'), [])".format(
                var_name,
                ", ".join("'{}'".format(k) for k in attrs.keys()))
        )
    return query def match_nodes(var_id_dict, node_label=None):
    """Match a collection of nodes by their id.

    Parameters
    ----------
    var_id_dict : dict
        Dictionary whose keys are names of the variables to use for
        the matched nodes and whose values are the ids of the nodes
        to match
    label : str
        Label of the nodes to match
    """
    node_label_str = ""
    if node_label:
        node_label_str = ":{}".format(node_label)

    query =\
        "MATCH " +\
        ", ".join("({}{} {{ id : '{}'}}) ".format(
            var_name, node_label_str, node_id)
            for var_name, node_id in var_id_dict.items()) + " "
    return query def with_vars(carry_vars):
    """Generate WITH statement using the input variables to carry."""
    return "WITH {} ".format(", ".join(carry_vars)) def match_node(var_name, node_id, node_label):
    """Query to match a node into the variable.

    Parameters
    ----------
    var_name
        Variable name to use for the matched node
    node_id
        Id of the node to match
    label
        Label of the node to match, default is 'node'
    """
    return "MATCH ({}:{} {{ id : '{}' }})\n".format(
        var_name, node_label, node_id) def shortest_path_query(source_id, target_id, node_label, edge_label):
    return (
        "MATCH path=shortestPath((n:{} {{id: '{}'}})-[{}*1..]->(m:{} {{id: '{}'}})) \n".format(
            node_label, source_id, edge_label, node_label, target_id) +
        "RETURN REDUCE(p=[], l in nodes(path) | p + [l.id]) as path"
    ) def match_edge(u_var, v_var, u_id, v_id, edge_var, u_label, v_label,
               edge_label='edge'):
    """Query for matching an edge.

    Parameters
    ----------
    u_var
        Name of the variable corresponding to the source of
        the edge
    v_var
        Name of the variable corresponding to the target of
        the edge
    u_id
        Id of the source node
    v_id
        Id of the target node
    edge_var
        Name of the variable to use for the matched edge
    label
        Label of the edge to match, default is 'edge'
    """
    query =\
        "MATCH ({}:{} {{id: '{}'}})-[{}:{}]->({}:{} {{id: '{}'}})\n".format(
            u_var, u_label, u_id, edge_var, edge_label, v_var, v_label, v_id)
    return query def set_intergraph_edge(domain, codomain, domain_node,
                        codomain_node, typing_label,
                        attrs=None):
    query = (
        "MATCH (n:{} {{ id: '{}' }}), (m:{} {{ id: '{}' }})\n".format(
            domain, domain_node, codomain, codomain_node) +
        "MERGE (n)-[:{}  {{ {} }}]->(m)".format(typing_label, generic.generate_attributes(attrs))
    )
    return query def check_homomorphism(tx, domain, codomain, total=True):
    """Check if the homomorphism is valid.

    Parameters
    ----------
    tx
        Variable of a cypher transaction
    domain : str
        Label of the graph at the domain of the homomorphism
    codmain : str
        Label of the graph at the codomain of the homomorphism

    Raises
    ------
    InvalidHomomorphism
        This error is raised in the following cases:

            * a node at the domain does not have exactly 1 image
            in the codoamin
            * an edge at the domain does not have an image in
            the codomain
            * a property does not match between a node and its image
            * a property does not match between an edge and its image
    """
    # Check if all the nodes of the domain have exactly 1 image
    query1 = (
        "MATCH (n:{})\n".format(domain) +
        "OPTIONAL MATCH (n)-[:typing]->(m:{})\n".format(codomain) +
        "WITH n, collect(m) as images\n" +
        "WHERE size(images) <> 1\n" +
        "RETURN n.id as ids, size(images) as nb_of_img\n"
    )

    result = tx.run(query1)
    nodes = []

    for record in result:
        nodes.append((record['ids'], record['nb_of_img']))
    if len(nodes) != 0:
        raise InvalidHomomorphism(
            "Wrong number of images!\n" +
            "\n".join(
                ["The node '{}' of the graph {} have {} image(s) in the graph {}.".format(
                    n, domain, str(nb), codomain) for n, nb in nodes]))

    # Check if all the edges of the domain have an image
    query2 = (
        "MATCH (n:{})-[:edge]->(m:{})\n".format(
            domain, domain) +
        "MATCH (n)-[:typing]->(x:{}), (y:{})<-[:typing]-(m)\n".format(
            codomain, codomain) +
        "OPTIONAL MATCH (x)-[r:edge]->(y)\n" +
        "WITH x.id as x_id, y.id as y_id, r\n" +
        "WHERE r IS NULL\n" +
        "WITH x_id, y_id, collect(r) as rs\n" +
        "RETURN x_id, y_id\n"
    )

    result = tx.run(query2)
    xy_ids = []
    for record in result:
        xy_ids.append((record['x_id'], record['y_id']))
    if len(xy_ids) != 0:
        raise InvalidHomomorphism(
            "Edges are not preserved in the homomorphism from '{}' to '{}': ".format(
                domain, codomain) +
            "Was expecting edges {}".format(
                ", ".join(
                    "'{}'->'{}'".format(x, y) for x, y in xy_ids))
        )

    # "CASE WHEN size(apoc.text.regexGroups(m_props, 'IntegerSet\\[(\\d+|minf)-(\\d+|inf)\\]') AS value"

    # Check if all the attributes of a node of the domain are in its image
    query3 = (
        "MATCH (n:{})-[:typing]->(m:{})\n".format(
            domain, codomain) +
        "WITH properties(n) as n_props, properties(m) as m_props, " +
        "n.id as n_id, m.id as m_id\n" +
        "WITH REDUCE(invalid = 0, k in filter(k in keys(n_props) WHERE k <> 'id' AND k <> 'count') |\n" +
        "\tinvalid + CASE\n" +
        "\t\tWHEN NOT k IN keys(m_props) THEN 1\n" +
        "\t\tELSE REDUCE(invalid_values = 0, v in n_props[k] |\n" +
        "\t\t\tinvalid_values + CASE m_props[k]\n" +
        "\t\t\t\tWHEN ['IntegerSet'] THEN CASE WHEN toInt(v) IS NULL THEN 1 ELSE 0 END\n" +
        "\t\t\t\tWHEN ['StringSet'] THEN CASE WHEN toString(v) <> v THEN 1 ELSE 0 END\n" +
        "\t\t\t\tWHEN ['BooleanSet'] THEN CASE WHEN v=true OR v=false THEN 0 ELSE 1 END\n" +
        "\t\t\t\tELSE CASE WHEN NOT v IN m_props[k] THEN 1 ELSE 0 END END)\n" +
        "\t\tEND) AS invalid, n_id, m_id\n" +
        "WHERE invalid <> 0\n" +
        "RETURN n_id, m_id, invalid\n"
    )

    result = tx.run(query3)
    invalid_typings = []
    for record in result:
        invalid_typings.append((record['n_id'], record['m_id']))
    if len(invalid_typings) != 0:
        raise InvalidHomomorphism(
            "Node attributes are not preserved in the homomorphism from '{}' to '{}': ".format(
                domain, codomain) +
            "\n".join(["Attributes of nodes source: '{}' ".format(n) +
                       "and target: '{}' do not match!".format(m)
                       for n, m in invalid_typings]))

    # Check if all the attributes of an edge of the domain are in its image
    query4 = (
        "MATCH (n:{})-[rel_orig:edge]->(m:{})\n".format(
            domain, domain) +
        "MATCH (n)-[:typing]->(x:{}), (y:{})<-[:typing]-(m)\n".format(
            codomain, codomain) +
        "MATCH (x)-[rel_img:edge]->(y)\n" +
        "WITH n.id as n_id, m.id as m_id, x.id as x_id, y.id as y_id, " +
        "properties(rel_orig) as rel_orig_props, " +
        "properties(rel_img) as rel_img_props\n" +
        "WITH REDUCE(invalid = 0, k in keys(rel_orig_props) |\n" +
        "\tinvalid + CASE\n" +
        "\t\tWHEN NOT k IN keys(rel_img_props) THEN 1\n" +
        "\t\tELSE REDUCE(invalid_values = 0, v in rel_orig_props[k] |\n" +
        "\t\t\tinvalid_values + CASE rel_img_props[k]\n" +
        "\t\t\t\tWHEN ['IntegerSet'] THEN CASE WHEN toInt(v) IS NULL THEN 1 ELSE 0 END\n" +
        "\t\t\t\tWHEN ['StringSet'] THEN CASE WHEN toString(v) <> v THEN 1 ELSE 0 END\n" +
        "\t\t\t\tWHEN ['BooleanSet'] THEN CASE WHEN v=true OR v=false THEN 0 ELSE 1 END\n" +
        "\t\t\t\tELSE CASE WHEN NOT v IN rel_img_props[k] THEN 1 ELSE 0 END END)\n" +
        "\t\tEND) AS invalid, n_id, m_id, x_id, y_id\n" +
        "WHERE invalid <> 0\n" +
        "RETURN n_id, m_id, x_id, y_id, invalid\n"
    )
    result = tx.run(query4)
    invalid_edges = []
    for record in result:
        invalid_edges.append((record['n_id'], record['m_id'],
                              record['x_id'], record['y_id']))
    if len(invalid_edges) != 0:
        raise InvalidHomomorphism(
            "Edge attributes are not preserved!\n" +
            "\n".join(["Attributes of edges '{}'->'{}' ".format(n, m) +
                       "and '{}'->'{}' do not match!".format(x, y)
                       for n, m, x, y in invalid_edges])
        )

    return True def check_consistency(tx, source, target):
    """Check if the adding of a homomorphism is consistent."""
    query = (
        "// match all typing pairs between '{}' and '{}'\n".format(
            source, target) +
        "MATCH (s:{})-[:typing]->(t:{})\n".format(
            source, target) +
        "WITH s, t\n"
    )
    query += (
        "// match all the predecessors of 's' and successors of 't'\n"
        "MATCH (pred)-[:typing*0..]->(s), (t)-[:typing*0..]->(suc) \n"
        "WHERE NOT pred = s AND NOT suc = t\n" +
        "WITH s, t, collect(DISTINCT pred) as pred_list, " +
        "collect(DISTINCT suc) as suc_list\n"
    )
    query += (
        "// select all the pairs 'pred' 'suc' with a path between\n"
        "UNWIND pred_list as pred\n" +
        "UNWIND suc_list as suc\n" +
        "OPTIONAL MATCH (pred)-[r:typing*]->(suc)\n" +
        "WHERE NONE(rel in r WHERE rel.tmp = 'True')\n"
        "WITH s, t, r, labels(pred)[1] as pred_label, labels(suc)[1] as suc_label\n" +
        "WHERE r IS NOT NULL\n" +
        "WITH DISTINCT s, t, pred_label, suc_label\n"
    )
    query += (
        "// return the pairs 's' 't' where there should be a typing edge\n"
        "OPTIONAL MATCH (s)-[new_typing:typing]->(t)\n" +
        "WHERE new_typing.tmp IS NOT NULL\n" +
        "WITH pred_label, suc_label, s.id as s_id, t.id as t_id, new_typing\n" +
        "WHERE new_typing IS NULL\n" +
        "RETURN pred_label, suc_label, s_id, t_id\n"
    )
    result = tx.run(query)

    missing_typing = []
    for record in result:
        missing_typing.append((record['pred_label'], record['suc_label']))
    if len(missing_typing) != 0:
        raise InvalidHomomorphism(
            "Homomorphism does not commute with existing paths:\n" +
            ",\n".join(["\t- from {} to {}".format(
                s, t) for s, t in missing_typing]) + "."
        )

    return True def get_typing(domain, codomain, typing_label, attrs=None):
    query = (
        "MATCH (n:{})-[:{}*1..]->(m:{})\n".format(
            domain, typing_label, codomain) +
        "RETURN n.id as node, m.id as type"
    )
    return query def get_relation(domain, codomain, typing_label, attrs=None):
    query = (
        "MATCH (n:{})-[:{}]-(m:{})\n".format(
            domain, typing_label, codomain) +
        "RETURN n.id as node, m.id as type"
    )
    return query def add_edge(edge_var, source_var, target_var,
             edge_label, attrs=None, merge=False):
    """Generate query for edge creation.

    source_var
        Name of the variable corresponding to the source
        node
    target_var
        Name of the variable corresponding to the target
        node
    edge_label : optional
        Labels associated with the new edge
    attrs : dict, optional
        Attributes of the new edge
    """
    if merge:
        keyword = "MERGE"
    else:
        keyword = "CREATE"

    query = "{} ({})-[{}:{} {{ {} }}]->({})\n".format(
        keyword, source_var, edge_var, edge_label,
        generic.generate_attributes(attrs), target_var)
    return query def remove_nodes(var_names, breakline=True):
    """Query for deleting nodes corresponding to the input variables.

    Parameters
    ----------
    var_names : iterable
        Collection of variables corresponding to nodes to remove
    """
    n = ""
    if breakline is True:
        n = "\n"

    return "DETACH DELETE {}{}".format(', '.join(v for v in var_names), n) def remove_edge(edge_var, breakline=True):
    """Query for deleting an edge corresponding to the input variable.

    Parameters
    ----------
    edge_var
        Name of the variable corresponding to the edge to remove
    """
    return generic.delete_var(edge_var, False, breakline) def normalize_attrs(attrs):
    """Normalize node attributes."""
    if attrs is not None:
        for k, v in list(attrs.items()):
            if not isinstance(v, AttributeSet):
                attrs[k] = FiniteSet(v)
                if attrs[k].is_empty():
                    del attrs[k]
    return def attrs_from_json(json_data):
    """Retrieve attrs from json-like dict."""
    attrs = dict()
    for key, value in json_data.items():
        attrs[key] = AttributeSet.from_json(value)
    return attrs def normalize_relation(relation):
    new_relation_dict = dict()
    for key, values in relation.items():
        if type(values) == set:
            new_relation_dict[key] = values
        elif type(values) == str:
            new_relation_dict[key] = {values}
        else:
            try:
                new_set = set()
                for v in values:
                    new_set.add(v)
                new_relation_dict[key] = new_set
            except TypeError:
                new_relation_dict[key] = {values}
    relation = new_relation_dict
    return new_relation_dict def valid_attributes(source, target):
    """Test the validity of attributes."""
    for key, value in source.items():
        if key not in target:
            return False
        if not value.issubset(target[key]):
            return False
    return True def keys_by_value(dictionary, val):
    """Get keys of a dictionary by a value."""
    res = []
    for key, value in dictionary.items():
        if value == val:
            res.append(key)
    return res
import os
import json
import warnings
from neo4j import GraphDatabase
from neo4j.exceptions import ConstraintError
from regraph.rules import Rule
from regraph.backends.networkx.graphs import NXGraph
from regraph.exceptions import (HierarchyError,
                                InvalidHomomorphism,
                                ReGraphError,
                                ReGraphWarning,
                                RewritingError)
from regraph.hierarchies import Hierarchy
from regraph.backends.neo4j.graphs import Neo4jGraph
from .cypher_utils.generic import (constraint_query,
                                   get_nodes,
                                   get_edges,
                                   clear_graph,
                                   successors_query,
                                   predecessors_query,
                                   get_edge_attrs,
                                   properties_to_attributes,
                                   get_node_attrs,
                                   set_attributes,
                                   match_nodes,
                                   with_vars,
                                   match_node,
                                   shortest_path_query,
                                   match_edge,
                                   )
from .cypher_utils.propagation import (set_intergraph_edge,
                                       check_homomorphism,
                                       check_consistency,
                                       get_typing,
                                       get_relation)
from .cypher_utils.rewriting import (add_edge,
                                     remove_nodes,
                                     remove_edge)
from regraph.utils import (normalize_attrs,
                           attrs_from_json,
                           normalize_relation,
                           valid_attributes,
                           keys_by_value)
"""Neo4j-based persisent graph hierarchies.

This module implements data structures that allow working with persistent
graph hierarchies stored in an instance of the Neo4j database:

* `Neo4jHierarchy` -- class for persistent graph hierarchies.
* `TypedNeo4jGraph` -- class for schema-aware property graph.
"""




class Neo4jHierarchy(Hierarchy):
    """
    Class for persistent hierarchies.

    Attributes
    ----------

    """

    # Implementation of abstract methods

    def graphs(self, data=False):
        """Return a list of graphs in the hierarchy."""
        query = get_nodes(node_label=self._graph_label, data=data)
        result = self.execute(query)
        graphs = []
        for d in result:
            if data:
                normalize_attrs(d["attrs"])
                del d["attrs"]["id"]
                graphs.append((d["node_id"], d["attrs"]))
            else:
                graphs.append(d["node_id"])
        return graphs

    def typings(self, data=False):
        """Return a list of graph typing edges in the hierarchy."""
        query = get_edges(
            self._graph_label,
            self._graph_label,
            self._typing_label,
            data=data)
        result = self.execute(query)
        typings = []
        for d in result:
            if data:
                normalize_attrs(d["attrs"])
                typings.append((d["source_id"], d["target_id"], d["attrs"]))
            else:
                typings.append((d["source_id"], d["target_id"]))
        return typings

    def relations(self, data=False):
        """Return a list of relations."""

        query = get_edges(