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
        ]) def plot_rule(rule, filename=None, title=None):
    """Plot ReGraph's rule object.

    This function plots a rule object, it produces three
    separate plots: for the left-hand side of the rule,
    preserved part and the right-hand side, where the two
    homomorphsisms p->lhs, p->rhs are encoded with colors
    of nodes.

    Parameters
    ----------
    rule : regraph.rules.Rule
        Rule object to plot
    filename : str, optional
        Path to file to save the plot
    """
    fig = plt.figure(figsize=(14, 3))
    if title is not None:
        st = fig.suptitle(title, fontsize=14)

    # generate colors
    p_colors_dict = {}
    p_colors = []
    for node in rule.p.nodes():
        lhs_node = rule.p_lhs[node]
        all_p_keys = keys_by_value(rule.p_lhs, lhs_node)
        if len(all_p_keys) > 1:
            found = None
            for p_key in all_p_keys:
                if p_key != node and p_key in p_colors_dict.keys():
                    found = p_key
                    break
            if found:
                p_colors_dict[node] = p_colors_dict[found]
                p_colors.append(p_colors_dict[found])
            else:
                p_colors_dict[node] = np.random.rand(3,)
                p_colors.append(p_colors_dict[node])
        else:
            p_colors_dict[node] = np.random.rand(3,)
            p_colors.append(p_colors_dict[node])

    lhs_colors = []
    for node in rule.lhs.nodes():
        p_keys = keys_by_value(rule.p_lhs, node)
        if len(p_keys) > 0:
            lhs_colors.append(p_colors_dict[p_keys[0]])
        else:
            lhs_colors.append(np.random.rand(3,))

    rhs_colors = []
    for node in rule.rhs.nodes():
        p_keys = keys_by_value(rule.p_rhs, node)
        if len(p_keys) > 0:
            rhs_colors.append(p_colors_dict[p_keys[0]])
        else:
            rhs_colors.append(np.random.rand(3,))

    # generate positions
    p_pos = nx.spring_layout(rule.p._graph, k=0.8, scale=1.0)

    lhs_pos = dict()
    lhs_fixed = []
    for node in rule.lhs.nodes():
        p_keys = keys_by_value(rule.p_lhs, node)
        if len(p_keys) > 0:
            lhs_pos[node] = p_pos[p_keys[0]]
            lhs_fixed.append(node)
    if len(lhs_pos) == 0:
        lhs_fixed = None
        lhs_pos = None
    lhs_pos = nx.spring_layout(
        rule.lhs._graph, pos=lhs_pos, fixed=lhs_fixed, k=0.05, scale=1.0, iterations=10)

    rhs_pos = dict()
    rhs_fixed = []
    for node in rule.rhs.nodes():
        p_keys = keys_by_value(rule.p_rhs, node)
        if len(p_keys) > 0:
            rhs_pos[node] = p_pos[p_keys[0]]
            rhs_fixed.append(node)
    if len(rhs_pos) == 0:
        rhs_fixed = None
        rhs_pos = None
    rhs_pos = nx.spring_layout(
        rule.rhs._graph, pos=rhs_pos, fixed=rhs_fixed, k=0.05, scale=1.0, iterations=10)

    all_pos = {
        **lhs_pos,
        **p_pos,
        **rhs_pos}

    min_y = min(
        [v[1] for v in all_pos.values()])
    max_y = max(
        [v[1] for v in all_pos.values()])

    # generate label positions
    normalized_node_size = (max_y - min_y) * 0.2
    offset_factor = 0.7

    lhs_labels = {}
    for node in rule.lhs.nodes():
        lhs_labels[node] = str(node)

    lhs_label_pos = copy.deepcopy(lhs_pos)
    for p in lhs_pos:  # raise text positions
        lhs_label_pos[p][1] += offset_factor * normalized_node_size

    p_labels = {}
    for node in rule.p.nodes():
        p_labels[node] = str(node)
    p_label_pos = copy.deepcopy(p_pos)
    for p in p_pos:  # raise text positions
        p_label_pos[p][1] += offset_factor * normalized_node_size

    rhs_labels = {}
    for node in rule.rhs.nodes():
        rhs_labels[node] = str(node)
    rhs_label_pos = copy.deepcopy(rhs_pos)
    for p in rhs_pos:  # raise text positions
        rhs_label_pos[p][1] += offset_factor * normalized_node_size

    all_label_pos = {
        **lhs_label_pos,
        **p_label_pos,
        **rhs_label_pos
    }

    # draw subplots
    plt.subplot(1, 3, 1)
    plt.title("LHS")
    _ticks_off()
    _set_limits(all_pos, all_label_pos)
    nx.draw_networkx_nodes(rule.lhs._graph, lhs_pos,
                           node_color=lhs_colors,
                           node_size=100, arrows=True)
    nx.draw_networkx_edges(rule.lhs._graph, lhs_pos, alpha=0.4, node_size=100)
    nx.draw_networkx_labels(rule.lhs._graph, lhs_label_pos, lhs_labels, font_size=11)

    plt.subplot(1, 3, 2)
    plt.title("P")
    _ticks_off()
    _set_limits(all_pos, all_label_pos)
    nx.draw_networkx_nodes(rule.p._graph, p_pos,
                           node_color=p_colors,
                           node_size=100, arrows=True)
    nx.draw_networkx_edges(rule.p._graph, p_pos, alpha=0.4, node_size=100)
    nx.draw_networkx_labels(rule.p._graph, p_label_pos, p_labels, font_size=11)

    plt.subplot(1, 3, 3)
    plt.title("RHS")
    _ticks_off()
    _set_limits(all_pos, all_label_pos)
    nx.draw_networkx_nodes(rule.rhs._graph, rhs_pos,
                           node_color=rhs_colors,
                           node_size=100, arrows=True)
    nx.draw_networkx_edges(rule.rhs._graph, rhs_pos, alpha=0.4, node_size=100)
    nx.draw_networkx_labels(rule.rhs._graph, rhs_label_pos, rhs_labels, font_size=11)

    if title is not None:
        st.set_y(0.95)
        fig.subplots_adjust(top=0.75)

    if filename is not None:
        with open(filename, "w") as f:
            plt.savefig(f)
            plt.clf()
    else:
        plt.show()
    return 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 def make_canonical_commands(g, commands, di=False):
    """Convert commands to the canonical form.

    Takes commands and the graph it refers to and returns a list of
    canonical transformations that have the same behaviour.
    The canonical form of a transformation follows this pattern :
    DELETIONS (DELETE_NODE, DELETE_NODE_ATTRS, DELETE_EDGE,
    DELETE_EDGE_ATTRS) CLONING (CLONE)
    ADDING and MERGING (ADD_NODE, ADD_NODE_ATTRS, ADD_EDGE,
    ADD_EDGE_ATTRS, MERGE)
    """
    res = []

    # We do multiple steps of simplification, until we found a fixed-point

    aux = commands
    next_step = simplify_commands(commands, di)
    while next_step != aux:
        aux = next_step
        next_step = simplify_commands(aux, di)

    # We keep updated an environment with our nodes and our edges

    env_nodes = [n for n in g.nodes()]
    env_edges = [e for e in g.edges()]

    if not di:
        for e in g.edges():
            if not (e[1], e[0]) in env_edges:
                env_edges.append((e[1], e[0]))

    # For each transformation we choose if we do it in this step or if we
    # keep it for later

    while next_step != '':
        command_strings = [c for c in next_step.splitlines() if len(c) > 0]
        actions = []
        for command in command_strings:
            try:
                parsed = parser.parseString(command).asDict()
                actions.append(parsed)
            except:
                raise ParsingError("Cannot parse command '%s'" % command)

        next_step = ''

        # We have 3 strings for each line of the canonical pattern

        add_step = ''
        del_step = ''
        clone_step = ''

        # Added is the list of elements we will add at to our environment
        # at the end of the step, we add them at the end so they are not
        # taken into account in the current step

        added = []
        cloned = []

        # If a node is in clone_wait, every cloning operation on it will
        # be delayed to next step. Same for other lists

        clone_wait = []
        merge_wait = []
        del_wait = []
        ad_wait = []

        # If we can't add a node with name n in this step, we don't want
        # another node with the same name to be added before it

        protected_names = []

        # For each action we update our lists and we chose what to do

        for i in range(len(actions)):
            action = actions[i]
            if action["keyword"] == "add_node":
                if action["node"] not in protected_names:
                    add_step += command_strings[i] + "\n"
                    added.append(action["node"])
            elif action["keyword"] == "delete_node":
                if action["node"] in env_nodes and\
                   action["node"] not in del_wait:
                    del_step += command_strings[i] + "\n"
                    env_nodes.remove(action["node"])
                else:
                    next_step += command_strings[i] + "\n"
                    ad_wait.append(action["node"])
            elif action["keyword"] == "add_node_attrs":
                if action["node"] in env_nodes and\
                   action["node"] not in ad_wait:
                    add_step += command_strings[i] + "\n"
                    added.append(action["node"])
                    clone_wait.append(action["node"])
                else:
                    next_step += command_strings[i] + "\n"
                    ad_wait.append(action["node"])
                    clone_wait.append(action["node"])
            elif action["keyword"] == "delete_node_attrs":
                if action["node"] in env_nodes and\
                   action["node"] not in del_wait:
                    del_step += command_strings[i] + "\n"
                else:
                    next_step += command_strings[i] + "\n"
                    clone_wait.append(action["node"])
                    ad_wait.append(action["node"])
            elif action["keyword"] == "add_edge":
                e = (action["node_1"], action["node_2"])
                if e[0] in env_nodes and\
                   e[1] in env_nodes and\
                   e[0] not in ad_wait and\
                   e[1] not in ad_wait:
                    add_step += command_strings[i] + "\n"
                    added.append(e)
                    if not di:
                        added.append((e[1], e[0]))
                    clone_wait.append(action["node_1"])
                    clone_wait.append(action["node_2"])
                else:
                    next_step += command_strings[i] + "\n"
                    clone_wait.append(action["node_1"])
                    clone_wait.append(action["node_2"])
                    merge_wait.append(action["node_1"])
                    merge_wait.append(action["node_2"])
            elif action["keyword"] == "delete_edge":
                e = (action["node_1"], action["node_2"])
                if (e in env_edges or
                    (not di and (e[1], e[0]) in env_edges)) and\
                   e[0] not in del_wait and\
                   e[1] not in del_wait:
                    is_cloned = False
                    for l in cloned:
                        if e[0] in l:
                            next_step += command_strings[i] + "\n"
                            clone_wait.append(action["node_1"])
                            clone_wait.append(action["node_2"])
                            merge_wait.append(action["node_1"])
                            merge_wait.append(action["node_2"])
                            is_cloned = True
                            break
                    if not is_cloned:
                        del_step += command_strings[i] + "\n"
                        clone_wait.append(action["node_1"])
                        clone_wait.append(action["node_2"])
                        env_edges.remove(e)
                        if not di:
                            env_edges.remove((e[1], e[0]))
                else:
                    next_step += command_strings[i] + "\n"
                    clone_wait.append(action["node_1"])
                    clone_wait.append(action["node_2"])
                    merge_wait.append(action["node_1"])
                    merge_wait.append(action["node_2"])
            elif action["keyword"] == "add_edge_attrs":
                e = (action["node_1"], action["node_2"])
                if (e in env_edges or
                    (not di and (e[1], e[0]) in env_edges)) and\
                   e[0] not in ad_wait and\
                   e[1] not in ad_wait:
                    add_step += command_strings[i] + "\n"
                    added.append(e)
                    if not di:
                        added.append((e[1], e[0]))
                    clone_wait.append(action["node_1"])
                    clone_wait.append(action["node_2"])
                else:
                    next_step += command_strings[i] + "\n"
                    clone_wait.append(action["node_1"])
                    clone_wait.append(action["node_2"])
                    merge_wait.append(action["node_1"])
                    merge_wait.append(action["node_2"])
            elif action["keyword"] == "delete_edge_attrs":
                e = (action["node_1"], action["node_2"])
                if (e in env_edges or
                    (not di and (e[1], e[0]) in env_edges)) and\
                   e[0] not in del_wait and\
                   e[1] not in del_wait:
                    is_cloned = False
                    for l in cloned:
                        if e[0] in l:
                            next_step += command_strings[i] + "\n"
                            clone_wait.append(action["node_1"])
                            clone_wait.append(action["node_2"])
                            merge_wait.append(action["node_1"])
                            merge_wait.append(action["node_2"])
                            is_cloned = True
                        elif e[1] in l:
                            next_step += command_strings[i] + "\n"
                            clone_wait.append(action["node_1"])
                            clone_wait.append(action["node_2"])
                            merge_wait.append(action["node_1"])
                            merge_wait.append(action["node_2"])
                            is_cloned = True
                    if not is_cloned:
                        del_step += command_strings[i] + "\n"
                        clone_wait.append(action["node_1"])
                        clone_wait.append(action["node_2"])
                else:
                    next_step += command_strings[i] + "\n"
                    clone_wait.append(action["node_1"])
                    clone_wait.append(action["node_2"])
                    merge_wait.append(action["node_1"])
                    merge_wait.append(action["node_2"])
            elif action["keyword"] == "clone":
                node = action["node"]
                if "node_name" in action.keys():
                    new_node = action["node_name"]
                else:
                    j = 1
                    new_node = str(node) + str(j)
                    while new_node in env_nodes or new_node in added:
                        j += 1
                        new_node = str(node) + str(j)
                if node in env_nodes and\
                   node not in clone_wait and\
                   new_node not in protected_names and\
                   fold_left(lambda e, acc: (e != node or
                                             (type(e) == tuple and
                                              e[1] != node and
                                                 e[0] != node)) and
                             acc,
                             True,
                             added):
                    clone_step += command_strings[i] + "\n"
                    added.append(new_node)
                    del_wait.append(node)
                    found = False
                    for i in range(len(cloned)):
                        if node in cloned[i]:
                            cloned[i].append(new_node)
                            found = True
                    if not found:
                        cloned.append([new_node, node])
                    to_add = []
                    for e in env_edges:
                        if e[0] == node:
                            to_add.append((new_node, e[1]))
                        elif e[1] == node:
                            to_add.append((e[0], new_node))
                    for e in added:
                        if type(e) == tuple:
                            if e[0] == node and\
                               e[1] != node:
                                to_add.append((new_node, e[1]))
                            elif e[1] == node and e[0] != node:
                                to_add.append((e[0], new_node))
                    for e in to_add:
                        added.append(e)
                else:
                    next_step += command_strings[i] + "\n"
                    del_wait.append(node)
                    merge_wait.append(node)
                    ad_wait.append(node)
                    protected_names.append(new_node)
            elif action["keyword"] == "merge":
                if "node_name" in actions[i].keys():
                    node_name = actions[i]["node_name"]
                else:
                    node_name = "_".join(actions[i]["nodes"])
                if fold_left(lambda n, acc: (n in env_nodes and
                                             n not in merge_wait) and
                             acc,
                             True,
                             action["nodes"]) and\
                        node_name not in protected_names:
                    add_step += command_strings[i] + "\n"

                    added.append(node_name)
                    clone_wait.append(node_name)

                    rem_el = []
                    for e in env_edges:
                        if e[0] in action["nodes"] and\
                           e[1] in action["nodes"]:
                            if e not in rem_el:
                                rem_el.append(e)
                        if e[0] in action["nodes"]:
                            if e not in rem_el:
                                rem_el.append(e)
                            if e[1] not in action["nodes"]:
                                added.append((node_name, e[1]))
                        elif e[1] in action["nodes"]:
                            if e not in rem_el:
                                rem_el.append(e)
                            if e[0] not in action["nodes"]:
                                added.append((e[0], node_name))
                    for e in rem_el:
                        while e in env_edges:
                            env_edges.remove(e)
                            if not di:
                                env_edges.remove((e[1], e[0]))
                    rem_el = []
                    for e in added:
                        if type(e) == tuple:
                            if e[0] in action["nodes"] and\
                               e[1] in action["nodes"]:
                                if e not in rem_el:
                                    rem_el.append(e)
                            if e[0] in action["nodes"]:
                                if e not in rem_el:
                                    rem_el.append(e)
                                if e[1] not in action["nodes"]:
                                    added.append((node_name, e[1]))
                            elif e[1] in action["nodes"]:
                                if e not in rem_el:
                                    rem_el.append(e)
                                if e[0] not in action["nodes"]:
                                    added.append((e[0], node_name))
                    for e in rem_el:
                        while e in added:
                            added.remove(e)
                            if not di:
                                added.remove((e[1], e[0]))
                else:
                    next_step += command_strings[i] + "\n"
                    protected_names.append(node_name)

        for el in added:
            if type(el) == tuple:
                env_edges.append(el)
            else:
                env_nodes.append(el)

        if len(next_step) != 0 and len(del_step + clone_step + add_step) == 0:
            raise ReGraphError(
                "Cannot find any new transformations and" +
                "the sequence of actions is non-empty : {}".format(next_step)
            )

        res.append(del_step + clone_step + add_step)

    return res def dict_sub(attrs1, attrs2):
    """Remove attributes `attrs2` from `attrs1`."""
    new_dict = {}
    for key in attrs1:
        if key in attrs2:
            new_set = attrs1[key].difference(attrs2[key])
            if new_set:
                new_dict[key] = new_set
        else:
            new_dict[key] = attrs1[key]
    return new_dict def attrs_union(attrs1, attrs2):
    """Find a union of two dictionaries with attrs."""
    if attrs1 is None:
        if attrs2 is not None:
            return attrs2
        else:
            return {}

    if attrs2 is None:
        return attrs1

    res = dict()
    for key in attrs1:
        if key in attrs2:
            res[key] = attrs1[key].union(attrs2[key])
        else:
            res[key] = attrs1[key]
    for key in attrs2:
        if key not in attrs1:
            res[key] = attrs2[key]
    return res def remove_forbidden(string):
            return string.replace(" ", "_").replace(
                "-", "_").replace(",", "_").replace(
                "/", "_").replace(".", "_") 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 identity(a, b):
    """Return identity homomorphism from a to b."""
    dic = {}
    for n in a.nodes():
        if n in b.nodes():
            dic[n] = n
        else:
            raise ReGraphError(
                "Cannot construct morphism by names: "
                "node '%s' not found in the second graph!" % n
            )
    return dic def check_homomorphism(source, target, dictionary, total=True):
    """Check if the homomorphism is valid.

    Valid homomorphism preserves edges,
    and attributes if requires.
    """
    # check if there is mapping for all the nodes of source graph
    if total:
        check_totality(source.nodes(), dictionary)
    if not set(dictionary.values()).issubset(target.nodes()):
        raise InvalidHomomorphism(
            "The image nodes {} do not exist ".format(
                set(dictionary.values()) - set(target.nodes())) +
            "in the target graph (existing nodes '{}') ".format(
                target.nodes()) +
            "in dictionary '{}'".format(dictionary)
        )

    # check connectivity
    for s, t in source.edges():
        try:
            if (s in dictionary.keys() and
                    t in dictionary.keys() and
                    not (dictionary[s], dictionary[t])
                    in target.edges()):
                raise InvalidHomomorphism(
                    "Connectivity is not preserved!"
                    " Was expecting an edge between '{}' and '{}'".format(
                        dictionary[s], dictionary[t]))
        except KeyError:
            pass

    for s, t in dictionary.items():
            # check sets of attributes of nodes (here homomorphism = set
            # inclusion)
        if not valid_attributes(source.get_node(s), target.get_node(t)):
            raise InvalidHomomorphism(
                "Attributes of nodes source: '{}' {} and ".format(
                    s, source.get_node(s)) +
                "target: '{}' {} do not match!".format(
                    t, target.get_node(t))
            )

    # check sets of attributes of edges (homomorphism = set inclusion)
    for s1, s2 in source.edges():
        try:
            if (s1 in dictionary.keys() and s2 in dictionary.keys() and
                    not valid_attributes(
                        source.get_edge(s1, s2),
                        target.get_edge(dictionary[s1], dictionary[s2]))):
                raise InvalidHomomorphism(
                    "Attributes of edges ({})-({}) ({}) and ".format(
                        s1, s2, source.get_edge(s1, s2)) +
                    "({})-({}) ({}) do not match!".format(
                        dictionary[s1],
                        dictionary[s2],
                        target.get_edge(dictionary[s1], dictionary[s2])))
        except KeyError:
            pass
    return True def pullback_complement(a, b, d, a_b, b_d, inplace=False):
    """Find the final pullback complement from a->b->d.

    Makes changes to d inplace.
    """
    check_homomorphism(a, b, a_b, total=True)
    check_homomorphism(b, d, b_d, total=True)

    if not is_monic(b_d):
        raise InvalidHomomorphism(
            "Second homomorphism is not monic, "
            "cannot find final pullback complement!"
        )

    if inplace is True:
        c = d
    else:
        c = NXGraph()
        c.add_nodes_from(d.nodes(data=True))
        c.add_edges_from(d.edges(data=True))

    a_c = dict()
    c_d = id_of(c.nodes())

    # Remove/clone nodes
    for b_node in b.nodes():
        a_keys = keys_by_value(a_b, b_node)
        # Remove nodes
        if len(a_keys) == 0:
            c.remove_node(b_d[b_node])
            del c_d[b_d[b_node]]
        # Keep nodes
        elif len(a_keys) == 1:
            a_c[a_keys[0]] = b_d[b_node]
        # Clone nodes
        else:
            i = 1
            for k in a_keys:
                if i == 1:
                    a_c[k] = b_d[b_node]
                    c_d[b_d[b_node]] = b_d[b_node]
                else:
                    new_name = c.clone_node(b_d[b_node])
                    a_c[k] = new_name
                    c_d[new_name] = b_d[b_node]
                i += 1

    # Remove edges
    for (b_n1, b_n2) in b.edges():
        a_keys_1 = keys_by_value(a_b, b_n1)
        a_keys_2 = keys_by_value(a_b, b_n2)
        if len(a_keys_1) > 0 and len(a_keys_2) > 0:
            for k1 in a_keys_1:
                for k2 in a_keys_2:
                    if (k1, k2) not in a.edges() and\
                       (a_c[k1], a_c[k2]) in c.edges():
                        c.remove_edge(a_c[k1], a_c[k2])

    # Remove node attrs
    for a_node in a.nodes():
        attrs_to_remove = dict_sub(
            b.get_node(a_b[a_node]),
            a.get_node(a_node)
        )
        c.remove_node_attrs(a_c[a_node], attrs_to_remove)
        # removed_node_attrs[a_c[a_node]] = attrs_to_remove

    # Remove edge attrs
    for (n1, n2) in a.edges():
        attrs_to_remove = dict_sub(
            b.get_edge(a_b[n1], a_b[n2]),
            a.get_edge(n1, n2)
        )
        c.remove_edge_attrs(a_c[n1], a_c[n2], attrs_to_remove)
        # removed_edge_attrs[(a_c[n1], a_c[n2])] = attrs_to_remove

    return (c, a_c, c_d) def get_unique_map_from_pushout(p, a_p, b_p, a_z, b_z):
    """Find a unique map to pushout."""
    p_z = dict()
    for value in p:
        z_values = set()

        a_values = set(keys_by_value(a_p, value))
        for a_value in a_values:
            if a_value in a_z.keys():
                z_values.add(a_z[a_value])

        b_values = set(keys_by_value(b_p, value))
        for b_value in b_values:
            if b_value in b_z.keys():
                z_values.add(b_z[b_value])

        if len(z_values) > 0:
            if len(z_values) > 1:
                raise ReGraphError("Cannot construct a unique map!")
            p_z[value] = z_values.pop()
    return p_z def get_unique_map_to_pullback(p, p_a, p_b, z_a, z_b):
    """Find a unique map to pullback."""
    z_p = dict()
    for value in p:
        z_keys_from_a = set()
        if value in p_a.keys():
            a_value = p_a[value]
            z_keys_from_a = set(keys_by_value(z_a, a_value))

        z_keys_from_b = set()
        if value in p_b.keys():
            b_value = p_b[value]
            z_keys_from_b.update(keys_by_value(z_b, b_value))

        z_keys = z_keys_from_a.intersection(z_keys_from_b)
        for z_key in z_keys:
            z_p[z_key] = value

    return z_p def get_unique_map_to_pullback_complement(a_p, p_c,
                                          a_prime_a, a_prime_z,
                                          z_c):
    """Find morphism z->p using the UP of PBC."""
    # Preliminary checks
    if not is_monic(a_p):
        raise ReGraphError(
            "Morphism 'a_p' is required to be a mono "
            "to use the UP of the pullback complement")
    z_p = {}
    for z_element, c_element in z_c.items():
        a_prime_elements = keys_by_value(a_prime_z, z_element)
        p_elements1 = set()  # candidate p elements
        for a_prime_element in a_prime_elements:
            p_elements1.add(a_p[a_prime_a[a_prime_element]])
        # resolve ambiguity going the other way
        p_elements2 = keys_by_value(p_c, c_element)
        if len(p_elements1) == 0:
            if len(p_elements2) == 1:
                z_p[z_element] = list(p_elements2)[0]
            else:
                raise ValueError(
                    "Cannot apply the universal property, " +
                    "check if the conditions to apply it are satisfied, " +
                    "problem: element '{}' from Z ".format(z_element) +
                    "corresponds to more than one element " +
                    "from P (i.e. corresponds to {}) and A'->A->P doesn't ".format(p_elements2) +
                    "resolve the conflict"
                )
        else:
            intersection = p_elements1.intersection(p_elements2)
            if len(intersection) == 1:
                z_p[z_element] = list(intersection)[0]
            elif len(intersection) == 0:
                raise ValueError(
                    "Cannot apply the universal property, " +
                    "check if the conditions to apply it are satisfied, " +
                    "problem: element '{}' from Z ".format(z_element) +
                    "corresponds to '{}' ".format(p_elements1) +
                    "from P following A'->A->P ".format(
                        intersection) +
                    "to '{}' following (P->C)^{{-1}} composed with (Z -> C)".format(
                        p_elements2)
                )
            else:
                raise ValueError(
                    "Cannot apply the universal property, " +
                    "check if the conditions to apply it are satisfied, " +
                    "problem: element '{}' from Z ".format(z_element) +
                    "doesn't corresponds to exactly one element " +
                    "from P (i.e. corresponds to {}) in both A'->A->P ".format(
                        intersection) +
                    "and (P->C)^{{-1}} composed with (Z -> C)"
                )
    return z_p def pushout(a, b, c, a_b, a_c, inplace=False):
    """Find the pushour of the span b <- a -> c."""
    def get_classes_to_merge():
        pass

    check_homomorphism(a, b, a_b)
    check_homomorphism(a, c, a_c)

    if inplace is True:
        d = b
    else:
        d = NXGraph()
        d.add_nodes_from(b.nodes(data=True))
        d.add_edges_from(b.edges(data=True))

    b_d = id_of(b.nodes())
    c_d = dict()

    # Add/merge nodes
    merged_nodes = dict()
    for c_n in c.nodes():
        a_keys = keys_by_value(a_c, c_n)
        # Add nodes
        if len(a_keys) == 0:
            if c_n not in d.nodes():
                new_name = c_n
            else:
                new_name = d.generate_new_node_id(c_n)
            d.add_node(new_name, c.get_node(c_n))
            c_d[c_n] = new_name
        # Keep nodes
        elif len(a_keys) == 1:
            c_d[a_c[a_keys[0]]] = b_d[a_b[a_keys[0]]]
        # Merge nodes
        else:
            nodes_to_merge = set()
            # find the nodes that need to be merged
            for k in a_keys:
                nodes_to_merge.add(a_b[k])

            # find if exists already some merged node to
            # which the new node should be merged
            groups_to_remove = set()
            new_groups = set()
            merge_done = False
            for k in merged_nodes.keys():
                if nodes_to_merge.issubset(merged_nodes[k]):
                    merge_done = True
                else:
                    intersect_with_group = nodes_to_merge.intersection(
                        merged_nodes[k])
                    if len(intersect_with_group) > 0:
                        new_nodes_to_merge =\
                            nodes_to_merge.difference(merged_nodes[k])
                        if len(new_nodes_to_merge) > 0:
                            new_nodes_to_merge.add(k)
                            new_name = d.merge_nodes(new_nodes_to_merge)
                            merged_nodes[new_name] = merged_nodes[k].union(
                                nodes_to_merge)
                            groups_to_remove.add(k)
                            new_groups.add(new_name)

            if len(groups_to_remove) > 0:
                new_name = d.merge_nodes(new_groups)
                merged_nodes[new_name] = set()
                for g in new_groups:
                    merged_nodes[new_name] = merged_nodes[new_name].union(
                        merged_nodes[g])
                for group in groups_to_remove:
                    del merged_nodes[group]
            elif not merge_done:
                if len(nodes_to_merge) > 1:
                    new_name = d.merge_nodes(nodes_to_merge)
                    merged_nodes[new_name] = nodes_to_merge
                else:
                    new_name = list(nodes_to_merge)[0]

            c_d[c_n] = new_name

            for node in nodes_to_merge:
                b_d[node] = new_name

            for k in c_d.keys():
                for vv in keys_by_value(a_c, k):
                    if b_d[a_b[vv]] == new_name:
                        c_d[k] = new_name

    # Add edges
    for (n1, n2) in c.edges():
        if (c_d[n1], c_d[n2]) not in d.edges():
            d.add_edge(
                c_d[n1], c_d[n2],
                c.get_edge(n1, n2))

    # Add node attrs
    for c_n in c.nodes():
        a_keys = keys_by_value(a_c, c_n)
        # Add attributes to the nodes which stayed invariant
        if len(a_keys) == 1:
            attrs_to_add = dict_sub(
                c.get_node(c_n),
                a.get_node(a_keys[0])
            )
            d.add_node_attrs(c_d[c_n], attrs_to_add)
        # Add attributes to the nodes which were merged
        elif len(a_keys) > 1:
            merged_attrs = {}
            for k in a_keys:
                merged_attrs = merge_attributes(
                    merged_attrs,
                    a.get_node(k)
                )
            attrs_to_add = dict_sub(c.get_node(c_n), merged_attrs)
            d.add_node_attrs(c_d[c_n], attrs_to_add)

    # Add edge attrs
    for (n1, n2) in c.edges():
        d_n1 = c_d[n1]
        d_n2 = c_d[n2]
        attrs_to_add = dict_sub(
            c.get_edge(n1, n2),
            d.get_edge(d_n1, d_n2)
        )
        d.add_edge_attrs(
            c_d[n1], c_d[n2],
            attrs_to_add
        )
    return (d, b_d, c_d) def pullback(b, c, d, b_d, c_d):
    """Find the pullback from b -> d <- c.

    Given h1 : B -> D; h2 : C -> D returns A, rh1, rh2
    with rh1 : A -> B; rh2 : A -> C and A the pullback.
    """
    a = NXGraph()

    # Check homomorphisms
    check_homomorphism(b, d, b_d)
    check_homomorphism(c, d, c_d)

    a_b = {}
    a_c = {}

    f = b_d
    g = c_d

    for n1 in b.nodes():
        for n2 in c.nodes():
            if f[n1] == g[n2]:
                new_attrs = merge_attributes(b.get_node(n1),
                                             c.get_node(n2),
                                             'intersection')
                if n1 not in a.nodes():
                    a.add_node(n1, new_attrs)
                    a_b[n1] = n1
                    a_c[n1] = n2
                else:
                    i = 1
                    new_name = str(n1) + str(i)
                    while new_name in a.nodes():
                        i += 1
                        new_name = str(n1) + str(i)
                    # if n2 not in a.nodes():
                    a.add_node(new_name, new_attrs)
                    a_b[new_name] = n1
                    a_c[new_name] = n2

    for n1 in a.nodes():
        for n2 in a.nodes():
            if (a_b[n1], a_b[n2]) in b.edges():
                if (a_c[n1], a_c[n2]) in c.edges():
                    a.add_edge(n1, n2)
                    a.set_edge(
                        n1,
                        n2,
                        merge_attributes(
                            b.get_edge(a_b[n1], a_b[n2]),
                            c.get_edge(a_c[n1], a_c[n2]),
                            'intersection'))
    check_homomorphism(a, b, a_b)
    check_homomorphism(a, c, a_c)
    return (a, a_b, a_c) def compose(d1, d2):
    """Compose two homomorphisms given by dicts."""
    res = dict()
    for key, value in d1.items():
        if value in d2.keys():
            res[key] = d2[value]
    return res class ReGraphWarning(UserWarning):
    """Class for ReGraph warnings.""" class ParsingError(ReGraphException):
    """Exceptions class for error in command parsing.""" class RuleError(ReGraphException):
    """Exceptions class for errors in rules."""
import copy
import warnings
from regraph.backends.networkx.graphs import NXGraph
from regraph.backends.networkx.plotting import plot_rule
from regraph.command_parser import parser
from regraph.utils import (keys_by_value,
                           make_canonical_commands,
                           dict_sub,
                           attrs_union,
                           remove_forbidden,
                           normalize_attrs)
from regraph.category_utils import (identity,
                                    check_homomorphism,
                                    pullback_complement,
                                    get_unique_map_from_pushout,
                                    get_unique_map_to_pullback,
                                    get_unique_map_to_pullback_complement,
                                    pushout,
                                    pullback,
                                    compose)
from regraph.exceptions import (ReGraphWarning, ParsingError,
                                RuleError)
    # That performs the merge from both sides
    # Then the left rule is L -> R', and the right one is R -> R'
    new_rhs, lhs_new_rhs, rhs_new_rhs = pushout(
        rule.p, rule.lhs, rule.rhs, rule.p_lhs, rule.p_rhs)

    left_rule = Rule(rule.lhs, rule.lhs, new_rhs, p_rhs=lhs_new_rhs)
    right_rule = Rule(rule.rhs, rule.rhs, new_rhs, p_rhs=rhs_new_rhs)
    return left_rule, right_rule


def _create_merging_rule_hierarchy(rule_hierarchy, lhs_instances, rhs_instances):

    left_hierarchy = {
        "rules": {},
        "rule_homomorphisms": {}
    }
    right_hierarchy = {
        "rules": {},
        "rule_homomorphisms": {}
    }
    for graph, rule in rule_hierarchy["rules"].items():
        left_rule, right_rule = _create_merging_rule(
            rule, lhs_instances[graph], rhs_instances[graph])
        left_hierarchy["rules"][graph] = left_rule
        right_hierarchy["rules"][graph] = right_rule

    for (source, target), (lhs_h, p_h, rhs_h) in rule_hierarchy[
            "rule_homomorphisms"].items():
        new_rhs_h = get_unique_map_from_pushout(
            left_hierarchy["rules"][source].rhs.nodes(),
            left_hierarchy["rules"][source].p_rhs,
            right_hierarchy["rules"][source].p_rhs,
            compose(
                lhs_h,
                left_hierarchy["rules"][target].p_rhs),
            compose(
                rhs_h,
                right_hierarchy["rules"][target].p_rhs)
        )
        left_hierarchy["rule_homomorphisms"][(source, target)] = (
            rule_hierarchy["rule_homomorphisms"][(source, target)][0],
            rule_hierarchy["rule_homomorphisms"][(source, target)][0],
            new_rhs_h
        )
        right_hierarchy["rule_homomorphisms"][(source, target)] = (
            rule_hierarchy["rule_homomorphisms"][(source, target)][2],
            rule_hierarchy["rule_homomorphisms"][(source, target)][2],
            new_rhs_h
        )
    return left_hierarchy, right_hierarchy


def compose_rule_hierarchies(rule_hierarchy1, lhs_instances1, rhs_instances1,
                             rule_hierarchy2, lhs_instances2, rhs_instances2):
    """Compose two rule hierarchies."""
    if len(rule_hierarchy1["rules"]) == 0:
        return rule_hierarchy2, lhs_instances2, rhs_instances2
    if len(rule_hierarchy2["rules"]) == 0:
        return rule_hierarchy1, lhs_instances1, rhs_instances1

    graphs = set(rule_hierarchy1["rules"].keys()).union(
        rule_hierarchy2["rules"].keys())
    homomorphisms = set(rule_hierarchy1["rule_homomorphisms"].keys()).union(
        rule_hierarchy2["rule_homomorphisms"].keys())

    new_rule_hierarchy = {
        "rules": {},
        "rule_homomorphisms": {}
    }
    new_lhs_instances = {}
    new_rhs_instances = {}

    composition_data = {}

    # Compose rules
    for graph in graphs:
        if graph in rule_hierarchy1["rules"]:
            rule1 = rule_hierarchy1["rules"][graph]
            lhs_instance1 = lhs_instances1[graph]
            rhs_instance1 = rhs_instances1[graph]
        else:
            rule1 = Rule.identity_rule()
            lhs_instance1 = {}
            rhs_instance1 = {}
        if graph in rule_hierarchy2["rules"]:
            rule2 = rule_hierarchy2["rules"][graph]
            lhs_instance2 = lhs_instances2[graph]
            rhs_instance2 = rhs_instances2[graph]
        else:
            rule2 = Rule.identity_rule()
            lhs_instance2 = {}
            rhs_instance2 = {}

        new_rule, new_lhs_instance, new_rhs_instance, data = compose_rules(
            rule1, lhs_instance1, rhs_instance1,
            rule2, lhs_instance2, rhs_instance2, return_all=True)
        new_rule_hierarchy["rules"][graph] = new_rule
        new_lhs_instances[graph] = new_lhs_instance
        new_rhs_instances[graph] = new_rhs_instance
        composition_data[graph] = data

    # Compute rule homomorphisms
    for source, target in homomorphisms:
        lhs_hom1, p_hom1, rhs_hom1 = rule_hierarchy1["rule_homomorphisms"][
            (source, target)]
        lhs_hom2, p_hom2, rhs_hom2 = rule_hierarchy2["rule_homomorphisms"][
            (source, target)]

        source_data = composition_data[source]
        target_data = composition_data[target]

        # H_G -> H_T
        h_hom = get_unique_map_from_pushout(
            source_data["h"].nodes(),
            source_data["rhs1_h"],
            source_data["lhs2_h"],
            compose(rhs_hom1, target_data["rhs1_h"]),
            compose(lhs_hom2, target_data["lhs2_h"])
        )
        # P*G_1 -> P*T_1

        p1_p_hom = get_unique_map_to_pullback_complement(