pyTCore/core/himesis.py

"""
Core logic for Himesis. Based on the code in AToMPM and earlier work by Marc Provost.

Himesis is a hierarchical, directed and labelled graph kernel, built on top of the ModelVerse State.
The name Himesis has etymological roots from genesis for "origin", mimesis for "representation" and
the syllable "Hi" stands for "Hierarchical".

.. See Also:
    http://modelverse.uantwerpen.be/people/mprovost/projects/himesis/index.html
"""

import uuid, copy
from state.base import State


class HConstants:
    """
    Himesis constants must start with '$' to ensure there are no name clashes
    with user-attributes (which are prohibited from starting with '$')
    """
    GUID                = '$GUID__'
    METAMODELS          = '$mms__'
    MISSING_METAMODELS  = '$missing_mms__'
    FULLTYPE            = '$ft__'
    CONNECTOR_TYPE      = '$ct__'
    ATTRIBUTES          = "$attr__"
    MT_LABEL            = '$MT_label__'
    MT_CONSTRAINT       = '$MT_constraint__'
    MT_ACTION           = '$MT_action__'
    MT_SUBTYPE_MATCH    = '$MT_subtypeMatching__'
    MT_SUBTYPES         = '$MT_subtypes__'
    MT_DIRTY            = '$MT_dirty__'
    MT_PIVOT_IN         = '$MT_pivotIn__'
    MT_PIVOT_OUT        = '$MT_pivotOut__'



class Himesis:
    """
    Creates a typed, attributed, directed, hierarchical, multi-graph.

    Args:
        name (str):     The name of this graph.
        mvs (State):    The backend to use for the graph representations.
    """
    Constants = HConstants
    EDGE_LIST_THRESHOLD = 10**3

    def __init__(self, name, mvs):
        if not name:
            name = self.__class__.__name__
        self.name = name

        self.state = mvs
        self.attrib = {}
        self.vcount = 0
        self.edges = []

        # mmTypeData: enables add_node() to properly initialize to-be nodes s.t. they reflect the default values specified by their metamodels
        # _index2guid: a fast lookup of the node's guid by its index
        # session: area which provides a clean and efficient way to remember information across rules
        self.mmTypeData = {}
        self._index2guid = {}
        self.session = {}

    @staticmethod
    def is_RAM_attribute(attr_name):
        return not attr_name.startswith('$')

    def copy(self):
        mvs = copy.deepcopy(self.state)
        cpy = Himesis(self.name, mvs)
        cpy._index2guid = copy.deepcopy(self._index2guid)
        ''' hergin :: motif-integration FIX for mmTypeData bug '''
        cpy.mmTypeData = copy.deepcopy(self.mmTypeData)
        cpy.session = copy.deepcopy(self.session)

        cpy.name = copy.deepcopy(self.name)
        return cpy

    def __copy__(self):
        return self.copy()

    def __deepcopy__(self, memo):
        return self.__copy__()

    def __getitem__(self, item):
        return self.attrib[item]

    def __setitem__(self, key, value):
        self.attrib[key] = value

    def __str__(self):
        s = super(Himesis, self).__str__()
        return self.name + ' ' + s[s.index('('):] + ' ' + str(self[Himesis.Constants.GUID])

    def get_id(self):
        """
        Returns the unique identifier of the graph
        """
        return self[Himesis.Constants.GUID]

    def vertex_count(self):
        return len(self._index2guid)

    def edge_count(self):
        return len(self.edges)

    def node_iter(self):
        """
        Iterates over the nodes in the graph, by index
        """
        return range(self.vertex_count())

    def node_guid_iter(self):
        """
        Iterates over the nodes in the graph, by guid index
        """
        return (self.get_node(ix) for ix in self.node_iter())

    def edge_iter(self):
        """
        Iterates over the edges in the graph, by index
        """
        return iter(self.edges)

    def follow_edge(self, node, label):
        return self.state.read_dict(node, label)

    def node_set_attribute(self, node, key, value):
        if Himesis.Constants.ATTRIBUTES not in self.state.read_dict_keys(node):
            attrs = self.state.create_node()
            self.state.create_dict(node, Himesis.Constants.ATTRIBUTES, attrs)
        else:
            attrs = self.follow_edge(node, Himesis.Constants.ATTRIBUTES)
        if key in self.state.read_dict_keys(attrs):
            target = self.follow_edge(attrs, key)
            self.state.delete_node(target)
        target = self.state.create_nodevalue(value)
        self.state.create_dict(attrs, key, target)

    def node_get_attribute(self, node, key):
        if Himesis.Constants.ATTRIBUTES not in self.state.read_dict_keys(node):
            return None
        attrs = self.follow_edge(node, Himesis.Constants.ATTRIBUTES)
        if key in self.state.read_dict_keys(attrs):
            target = self.follow_edge(attrs, key)
            return self.state.read_value(target)
        return None

    def node_get_attributes(self, node):
        if Himesis.Constants.ATTRIBUTES not in self.state.read_dict_keys(node):
            return []
        attrs = self.follow_edge(node, Himesis.Constants.ATTRIBUTES)
        res = {}
        for key in self.state.read_dict_keys(attrs):
            target = self.follow_edge(attrs, key)
            res[key] = self.state.read_value(target)
        return res

    def node_has_attribute(self, node, key):
        attr = self.node_get_attribute(node, key)
        return attr is not None

    def get_first_node_with_attribute_equals(self, key, value):
        for node in self.node_guid_iter():
            attr = self.node_get_attribute(node, key)
            if attr == value:
                return node
        return None

    def add_node(self, fulltype=None, isConnector=None):
        # ALL NODES ARE NOW IDENTIFIED WITH A UUID!

        # newNodeIndex = self.vertex_count()
        # if newNodeGuid is None:
        #     newNodeGuid = uuid.uuid4()
        nid = self.state.create_node()
        # self.node_set_attribute(nid, Himesis.Constants.GUID, newNodeGuid)
        self.node_set_attribute(nid, Himesis.Constants.FULLTYPE, fulltype)
        self.node_set_attribute(nid, Himesis.Constants.CONNECTOR_TYPE, isConnector)
        # self.add_vertices(1)
        # self.vs[newNodeIndex][Himesis.Constants.GUID] = newNodeGuid
        # self.vs[newNodeIndex][Himesis.Constants.FULLTYPE] = fulltype
        # self.vs[newNodeIndex][Himesis.Constants.CONNECTOR_TYPE] = isConnector
        if fulltype in self.mmTypeData :
            for attr, val in self.mmTypeData[fulltype].items():
                self.node_set_attribute(nid, str(attr), val)
                # self.vs[newNodeIndex][str(attr)] = val
        self._index2guid[self.vcount] = nid
        self.vcount += 1
        return nid

    def delete_nodes(self, nodes):
        td = []
        for n in nodes:
            self.state.delete_node(n)
            td += [k for k, v in self._index2guid.items() if v == n]
        # self.delete_vertices(nodes)
        # Regenerate the lookup because node indices have changed
        for t in td:
            del self._index2guid[t]
        # self._guid2index = dict((self.vs[node][Himesis.Constants.GUID], node) for node in self.node_iter())

    def get_node(self, index):
        if index in self._index2guid:
            return self._index2guid[index]
        raise KeyError('Node not found with specified id. Make sure to only create nodes via Himesis.add_node().')

    def edge_get_source(self, edge):
        return self.state.read_edge(edge)[0]

    def edge_get_target(self, edge):
        return self.state.read_edge(edge)[1]

    def link_nodes(self, A, B, label=None):
        if label is None:
            self.state.create_edge(A, B)
        else:
            self.state.create_dict(A, label, B)

    def unlink_nodes(self, A, B, label=""):
        if self.state.read_reverse_dict(B, label) != A:
            raise ValueError("No connection with label '%s' found between nodes %s and %s" % (label, A, B))
        edge = self.state.read_dict_edge(A, label)
        self.state.delete_edge(edge)

    # def get_node(self, guid):
    #     """
    #         Retrieves the node instance with the specified guid
    #         @param guid: The guid of the node.
    #     """
    #     if guid in self._guid2index:
    #         if self._guid2index[guid] >= self.vcount() or \
    #                 self.vs[self._guid2index[guid]][Himesis.Constants.GUID] != guid :
    #             self._guid2index = dict((self.vs[node][Himesis.Constants.GUID], node) for node in self.node_iter())
    #         try:
    #             return self._guid2index[guid]
    #         except KeyError:
    #             #TODO: This should be a TransformationLanguageSpecificException
    #             raise KeyError('Invalid node id. Make sure to only delete nodes via Himesis.delete_nodes(): ' + str(guid))
    #     else :
    #         #TODO: This should be a TransformationLanguageSpecificException
    #         raise KeyError('Node not found with specified id. Make sure to only create nodes via Himesis.add_node(): ' + str(guid))

    # def draw(self, visual_style={}, label=None, show_guid=False, show_id=False, debug=False, width=600, height=900):
    #     """
    #     Visual graphic rendering of the graph.
    #
    #     Args:
    #     @param label: The attribute to use as node label in the figure.
    #                   If not provided, the index of the node is used.
    #     @param visual_style: More drawing options
    #     (see http://igraph.sourceforge.net/doc/python/igraph.Graph-class.html#__plot__ for more details).
    #     """
    #     if 'layout' not in visual_style:
    #         visual_style["layout"] = 'fr'
    #     if 'margin' not in visual_style:
    #         visual_style["margin"] = 10
    #
    #     # Set the labels
    #     if not label:
    #         if show_guid:
    #             visual_style["vertex_label"] = [str(self.vs[i][Himesis.Constants.GUID])[:4] for i in self.node_iter()]
    #         elif show_id:
    #             visual_style["vertex_label"] = [str(i) for i in self.node_iter()]
    #         else:
    #             visual_style["vertex_label"] = [''] *  self.vcount()
    #     else:
    #         try:
    #             visual_style["vertex_label"] = self.vs[label]
    #             for n in self.node_iter():
    #                 if not visual_style["vertex_label"][n]:
    #                     visual_style["vertex_label"][n] = self.vs[n][Himesis.Constants.FULLTYPE]
    #                     if debug:
    #                         visual_style["vertex_label"][n] = str(n) + ':' + visual_style["vertex_label"][n]
    #                 elif debug:
    #                     visual_style["vertex_label"][n] = str(n) + ':' + visual_style["vertex_label"][n]
    #         except:
    #             raise Exception('%s is not a valid attribute' % label)
    #
    #     return ig.plot(self, bbox=(0, 0, width, height), **visual_style)

    def execute(self, *args):
        raise AttributeError('This method is not implemented')


class HimesisPattern(Himesis):
    def __init__(self, name, mvs):
        super(HimesisPattern, self).__init__(name, mvs)

        # Caches
        self.nodes_label = {}
        self.nodes_pivot_out = {}

    def get_node_with_label(self, label):
        """
        Retrieves the index of the node with the specified label.

        Args:
            label: The label of the node.
        """
        if not self.nodes_label:
            self.nodes_label = {}
            self.nodes_label = { self.node_get_attribute(n, Himesis.Constants.MT_LABEL): n \
                                    for n in self.node_guid_iter() \
                                    if self.node_has_attribute(n, Himesis.Constants.MT_LABEL) }
            # self.nodes_label = dict([(self.vs[i][Himesis.Constants.MT_LABEL], i) for i in self.node_iter()])
        if label in self.nodes_label:
            return self.nodes_label[label]

    def get_pivot_out(self, pivot):
        """
        Retrieves the index of the pivot node.

        Args:
            pivot: The label of the pivot.
        """
        if not self.nodes_pivot_out:
            self.nodes_pivot_out = { self.node_get_attribute(n, Himesis.Constants.MT_PIVOT_OUT): n \
                                        for n in self.node_guid_iter() \
                                        if self.node_has_attribute(n, Himesis.Constants.MT_PIVOT_OUT) }
            # self.nodes_pivot_out = dict([(i, self.vs[i][Himesis.Constants.MT_PIVOT_OUT]) for i in self.node_iter()])
        if pivot in self.nodes_pivot_out:
            return self.nodes_pivot_out[pivot]


class HimesisPreConditionPattern(HimesisPattern):
    def __init__(self, name, mvs):
        super(HimesisPreConditionPattern, self).__init__(name, mvs)
        self.nodes_pivot_in = {}

    def get_pivot_in(self, pivot):
        """
        Retrieves the index of the pivot node.

        Args:
            pivot: The label of the pivot.
        """
        if not self.nodes_pivot_in:
            self.nodes_pivot_in = { self.node_get_attribute(n, Himesis.Constants.MT_PIVOT_IN): n \
                                    for n in self.node_guid_iter() \
                                    if self.node_has_attribute(n, Himesis.Constants.MT_PIVOT_IN) }
            # self.nodes_pivot_in = dict([(self.vs[i][Himesis.Constants.MT_PIVOT_IN], i) for i in self.node_iter()])
        if pivot in self.nodes_pivot_in:
            return self.nodes_pivot_in[pivot]

    def constraint(self, mtLabel2graphIndexMap, graph): # TODO??
        """
            If a constraint shall be specified, the corresponding Himesis graph must override this method.
            The condition must be specified in the pattern graph and not the input graph.
            By default, the constraint evaluates to True.
            @param PreMatch: The current match, before the rewriting.
            @param graph: The whole input graph.
        """
        raise NotImplementedError('Use graph[Himesis.Constants.MT_CONSTRAINT]() instead')


class HimesisPreConditionPatternLHS(HimesisPreConditionPattern):
    def __init__(self, name, mvs):
        super(HimesisPreConditionPatternLHS, self).__init__(name, mvs)
        self.NACs = []
        self.bound_start_index = 0  # index of first bound NAC in NACs list

    def addNAC(self, nac):
        """
        Appends the NAC to this LHS pattern
        """
        if nac.LHS != self:
            nac.LHS = self
        if nac.bridge is None:
            nac.bridge = nac.compute_bridge()
        self.NACs.append(nac)

    def addNACs(self, NACs):
        """
        Stores the list of NACs in decreasing order of their size
        @param nacs: list of NACs
        @postcondition: the NACs will be stored in decreasing order of their bridge sizes
        """
        bound = []
        unbound = []
        for nac in NACs:
            nac.LHS = self
            nac.bridge_size = nac.compute_bridge().vertex_count()
            if nac.bridge_size > 0:
                bound.append(nac)
            else:
                unbound.append(nac)
        bound.sort(key=lambda nac: (nac.bridge_size, nac.vertex_count()), reverse=True)
        unbound.sort(key=lambda nac: nac.vertex_count(), reverse=True)
        self.NACs = unbound + bound
        self.bound_start_index = len(unbound)

    def getUnboundNACs(self):
        return self.NACs[:self.bound_start_index]

    def getBoundNACs(self):
        return self.NACs[self.bound_start_index:]

    def hasBoundNACs(self):
        return self.bound_start_index < len(self.NACs)


class HimesisPreConditionPatternNAC(HimesisPreConditionPattern):
    def __init__(self, LHS, name, mvs):
        super(HimesisPreConditionPatternNAC, self).__init__(name, mvs)
        self.LHS = LHS
        self.bridge_size = 0

    def set_bridge_size(self):
        """
        Computes the bridge and stores the number of its nodes.
        """
        if self.LHS is None:
            raise Exception('Missing LHS to compute bridge')
        self.bridge_size = self.compute_bridge().vertex_count()

    def compute_bridge(self):
        """
        Creates a HimesisPreConditionPattern defined as the intersection of graph with this instance.
        This is called the 'bridge'.
        From a topological point of view, this method computes the largest common subgraph of these two graphs.
        However, the similarity of nodes of the bridge relies on the meta-model type of the nodes.
        Furthermore, every attribute value is the conjunction of the constraints defined in each graph.
        """
        # G1 is the smallest graph and G2 is the bigger graph
        G1 = self
        G2 = self.LHS
        if G1.vertex_count() > G2.vertex_count():
            # Swap
            G1, G2 = G2, G1
        # The bridge
        G = HimesisPreConditionPattern('', self.state)
        G[Himesis.Constants.GUID] = uuid.uuid4()

        # We don't need to actually solve the largest common subgraph (LCS) problem
        # because we assume that the nodes are labelled uniquely in each graph
        # and that if a label is in G1 and in G2, then it will be in G
        if G1.vertex_count() == 0:
            return G

        for v1 in G1.node_guid_iter():
            label = G1.node_get_attribute(v1, Himesis.Constants.MT_LABEL)
            v2 = G2.get_first_node_with_attribute_equals(Himesis.Constants.MT_LABEL, label)
            if v2 is None: continue
            newNodeIndex = G.add_node()
            # Now do a conjunction of the attributes
            for attr, val in G1.node_get_attributes(v1).items():
                G.node_set_attribute(newNodeIndex, attr, val)
            for attr, val in G2.node_get_attributes(v2).items():
                if not G.node_has_attribute(newNodeIndex, attr):
                    G.node_set_attribute(newNodeIndex, attr, val)
                # Ignore non-RAM attributes ('special' and HConstants attributes)
                elif not Himesis.is_RAM_attribute(attr): continue
                # Handle normal attribute
                else:
                    if not val:
                        # There is no constraint for this attribute
                        continue

                    # The attribute constraint code is the conjunction of the LHS constraint
                    # with the NAC constraint for this attribute
                    def get_evalAttrConditions(_attr, _v1, _v2):
                        def evalAttrConditions(mtLabel2graphIndexMap, graph):
                            return G1.node_get_attribute(_v1, _attr)(mtLabel2graphIndexMap, graph) and \
                                   G2.node_get_attribute(_v2, _attr)(mtLabel2graphIndexMap, graph)

                        return evalAttrConditions

                    G.node_set_attribute(newNodeIndex, attr, get_evalAttrConditions(attr, v1, v2))
                    # G.vs[newNodeIndex][attr] = get_evalAttrConditions(attr, v1.index, v2.index)

        # Now add the edges
        # We only need to go through the edges of the smaller graph
        for e in G1.edge_iter():
            src, tgt = self.state.read_edge(e)
            src_label = self.node_get_attribute(src, Himesis.Constants.MT_LABEL)
            tgt_label = self.node_get_attribute(tgt, Himesis.Constants.MT_LABEL)
            src = G.get_first_node_with_attribute_equals(Himesis.Constants.MT_LABEL, src_label)
            tgt = G.get_first_node_with_attribute_equals(Himesis.Constants.MT_LABEL, tgt_label)
            G.link_nodes(src, tgt)



        # Labels2 = G2.vs[Himesis.Constants.MT_LABEL]
        # for label in G1.vs[Himesis.Constants.MT_LABEL]:
        #     if label in Labels2:
        #         # Get the corresponding node from G1
        #         v1 = G1.vs.select(lambda v : v[Himesis.Constants.MT_LABEL] == label)
        #         if len(v1) == 1:
        #             v1 = v1[0]
        #         elif len(v1) == 0:
        #             #unreachable line...
        #             raise Exception('Label does not exist :: ' + str(label))
        #         else:
        #             raise Exception('Label is not unique :: ' + str(label))
        #         # Get the corresponding node from G2
        #         v2 = G2.vs.select(lambda v : v[Himesis.Constants.MT_LABEL] == label)
        #         if len(v2) == 1:
        #             v2 = v2[0]
        #         elif len(v2) == 0:
        #             # Unreachable line...
        #             raise Exception('Label does not exist :: ' + str(label))
        #         else:
        #             raise Exception('Label is not unique :: ' + str(label))
        #         newNodeIndex = G.add_node()
        #         # Now do a conjunction of the attributes
        #         for attr in v1.attribute_names():
        #             G.vs[newNodeIndex][attr] = v1[attr]
        #         for attr in v2.attribute_names():
        #             # The attribute is not in v1
        #             if attr not in G.vs[newNodeIndex].attribute_names():
        #                 G.vs[newNodeIndex][attr] = v2[attr]
        #             # Give this node its own GUID attribute
        #             elif attr == Himesis.Constants.GUID:
        #                 G.vs[newNodeIndex][Himesis.Constants.GUID] = uuid.uuid4()
        #                 continue
        #             # Ignore non-RAM attributes ('special' and HConstants attributes)
        #             elif not Himesis.is_RAM_attribute(attr):
        #                 continue
        #             # Handle normal attribute
        #             else :
        #                 if not v2[attr]:
        #                     # There is no constraint for this attribute
        #                     continue
        #
        #                 # The attribute constraint code is the conjunction of the LHS constraint
        #                 # with the NAC constraint for this attribute
        #                 def get_evalAttrConditions(_attr,_v1,_v2) :
        #                     def evalAttrConditions(mtLabel2graphIndexMap,graph):
        #                         return G1.vs[_v1][_attr](mtLabel2graphIndexMap, graph) and \
        #                                G2.vs[_v2][_attr](mtLabel2graphIndexMap, graph)
        #                     return evalAttrConditions
        #                 G.vs[newNodeIndex][attr] = get_evalAttrConditions(attr,v1.index,v2.index)
        #             #else: v1[attr] == v2[attr], so we don't need to do anything more
        # # Now add the edges
        # # We only need to go through the edges of the smaller graph
        # for e in G1.edge_iter():
        #     src_label = G1.vs[G1.es[e].source][Himesis.Constants.MT_LABEL]
        #     tgt_label = G1.vs[G1.es[e].target][Himesis.Constants.MT_LABEL]
        #     src = G.vs.select(lambda v : v[Himesis.Constants.MT_LABEL] == src_label)
        #     tgt = G.vs.select(lambda v : v[Himesis.Constants.MT_LABEL] == tgt_label)
        #     if len(src) == len(tgt) == 1:
        #         src = src[0]
        #         tgt = tgt[0]
        #         G.add_edges([(src.index, tgt.index)])
        #     elif len(src) == 0 :
        #         #                raise Exception('Label does not exist :: '+str(src_label))
        #         pass
        #     elif len(tgt) == 0 :
        #         #                raise Exception('Label does not exist :: '+str(tgt_label))
        #         pass
        #     elif len(src) > 1 :
        #         raise Exception('Label is not unique :: ' + str(src_label))
        #     elif len(tgt) > 1 :
        #         raise Exception('Label is not unique :: ' + str(tgt_label))
        return G



class HimesisPostConditionPattern(HimesisPattern):
    def __init__(self, name, mvs):
        super(HimesisPostConditionPattern, self).__init__(name, mvs)
        self.pre = None

    def action(self, mtLabel2graphIndexMap, graph):
        """
        If an action shall be specified, the corresponding Himesis graph must override this method.
        The action must be specified in the pattern graph and not the input graph.
        """
        raise NotImplementedError('Use graph[Himesis.Constants.MT_ACTION]() instead')

    # This method implements the rewriting part of the rule.
    '''    
        NOTE 
            certain rule applications may have side-effects that aren't caused by
            the rewriting per se... at present, the only instance of this is when a
              rule produces entities of a formalism not loaded on the asworker... in 
            this case, we prepend appropriate {'op':'LOADMM','name':...} entries to
            packet.deltas 
            

        NOTE     
            when creating new nodes, information about the match is bundled so that
            the said new nodes' icons get created near the icons of nodes matched
            in the LHS 
            
        
        NOTE
            deletes must be performed last because they alter igraph indices and 
            which we use to map __pLabels to source graph nodes... however, to 
            avoid violating maximum association multiplicities, deletes in the 
            source model must be performed first... thus, RM* operations, if any,
            are placed at the start of packet.deltas 
    '''
    def execute(self, packet, match):
        graph = packet.graph

        # Changes to packet.graph are logged in packet.deltas
        packet.deltas = []

        # Init deltas with rule side-effects (see NOTE)
        for mm in self[Himesis.Constants.MISSING_METAMODELS]() :
            packet.deltas.append({'op':'LOADMM','name':mm})


        # Set the attributes of graph.vs[graphNodeIndex] to match those of self.vs[rhsNodeIndex]
        def set_attributes(rhsNodeIndex, graphNodeIndex, newNode, pLabel2graphIndexMap) :
            changedSomething = False
            for attrName, attrVal in self.node_get_attributes(rhsNodeIndex).items():
            # for attrName in self.vs[rhsNodeIndex].attribute_names() :
                if Himesis.is_RAM_attribute(attrName) :
                    # attrVal = self.vs[rhsNodeIndex][attrName]
                    if attrVal is None :
                        # Not 'really' an attribute
                        continue
                    oldVal = None
                    try :
                        if not newNode:
                            # oldVal = graph.vs[graphNodeIndex][attrName]
                            oldVal = graph.node_get_attribute(graphNodeIndex, attrName)

                        # newVal = self.vs[rhsNodeIndex][attrName](pLabel2graphIndexMap, graph)
                        newVal = self.node_get_attribute(rhsNodeIndex, attrName)(pLabel2graphIndexMap, graph)
                        if oldVal != newVal:
                            graph.node_set_attribute(graphNodeIndex, attrName, newVal)
                            # graph.vs[graphNodeIndex][attrName] = newVal
                            packet.deltas.append(
                                {'op':'CHATTR',
                                 'guid':graphNodeIndex,
                                 'attr':attrName,
                                 'old_val':oldVal,
                                 'new_val':newVal})
                            changedSomething = True
                    except Exception as e :
                        raise Exception("An error has occurred while computing the value of the attribute '%s' :: %s" % (attrName, e))
            return changedSomething

        # Build a dictionary {label: node index} mapping each label of the pattern to a node in the graph to rewrite.
        # Because of the uniqueness property of labels in a rule, we can store all LHS labels
        # and subsequently add the labels corresponding to the nodes to be created.
        labels = match.copy()

        # Update attribute values
        LHS_labels = self.pre_labels
        for label in LHS_labels:
            rhsNodeIndex = self.get_node_with_label(label)
            if rhsNodeIndex is None:
                continue        # not in the interface graph (LHS n RHS)
            if set_attributes(rhsNodeIndex, labels[label], False, labels):
                graph.node_set_attribute(labels[label], Himesis.Constants.MT_DIRTY, True)
                # graph.vs[labels[label]][Himesis.Constants.MT_DIRTY] = True

        # Create new nodes (non-connectors first)
        if self.vertex_count() == 0 :
            RHS_labels = []
        else:
            RHS_labels = []
            for node in self.node_guid_iter():
                RHS_labels.append(self.node_get_attribute(node, Himesis.Constants.MT_LABEL))
            # RHS_labels = self.vs[Himesis.Constants.MT_LABEL]
            # sort non-connectors first
            RHS_labels.sort(key=lambda x: self.node_get_attribute(self.get_node_with_label(x), Himesis.Constants.CONNECTOR_TYPE) or False)
            # RHS_labels.sort(key=lambda x: self.vs[ self.get_node_with_label(x) ][Himesis.Constants.CONNECTOR_TYPE] or False)
            neighborhood = [graph.node_get_attributes(labels[l]) for l in LHS_labels]

        new_labels = []
        for label in RHS_labels:
            rhsNodeIndex = self.get_node_with_label(label)
            if label not in LHS_labels:
                new_labels += [label]
                newNodeIndex = graph.add_node(
                    self.node_get_attribute(rhsNodeIndex, Himesis.Constants.FULLTYPE),
                    self.node_get_attribute(rhsNodeIndex, Himesis.Constants.CONNECTOR_TYPE))
                packet.deltas.append(
                    {'op':'MKNODE',
                     'neighborhood':neighborhood,
                     'guid':graph.node_get_attribute(newNodeIndex, Himesis.Constants.GUID)})
                labels[label] = newNodeIndex
                set_attributes(rhsNodeIndex, newNodeIndex, True, labels)

        # Link new nodes (Create new edges)
        visited_edges = []
        for label in sorted(new_labels):
            edges = [e for e in self.edge_iter() if (e not in visited_edges and
                                                     (label == self.node_get_attribute(self.edge_get_source(e), Himesis.Constants.MT_LABEL) or
                                                      label == self.node_get_attribute(self.edge_get_target(e), Himesis.Constants.MT_LABEL)))]
            for edge in edges:
                # src_label = self.node_get_attribute(self.edge_get_source(edge), Himesis.Constants.MT_LABEL)
                # tgt_label = self.node_get_attribute(self.edge_get_target(edge), Himesis.Constants.MT_LABEL)
                graph.link_nodes(self.edge_get_source(edge), self.edge_get_target(edge))
                # graph.add_edges([(labels[src_label], labels[tgt_label])])
                packet.deltas.append(
                    {'op':'MKEDGE',
                     'guid1':self.edge_get_source(edge),
                     'guid2':self.edge_get_target(edge)})
                visited_edges.append(edge.index)

        # Set the output pivots
        for node in self.node_guid_iter():
            pivot_out = self.node_get_attribute(node, Himesis.Constants.MT_PIVOT_OUT)
            if pivot_out:
                label = self.node_get_attribute(node, Himesis.Constants.MT_LABEL)
                packet.global_pivots[pivot_out] = labels[label]

        # Perform the post-action
        try:
            packet.deltas.extend(self[Himesis.Constants.MT_ACTION](labels, graph))
        except Exception as e:
            raise Exception('An error has occurred while applying the post-action', e)

        # Delete nodes (automatically deletes adjacent edges)
        labels_to_delete = []
        rmnodes = []
        rmedges = []
        for label in LHS_labels:
            if label not in RHS_labels:
                labels_to_delete.append(labels[label])
                rmnodes.append({'op':'RMNODE','attrs': graph.node_get_attributes(labels[label]),'guid': labels[label]})
                edges = [e for e in graph.edge_iter() if labels[label] == graph.edge_get_source(e) or labels[label] == graph.edge_get_target(e)]
                for edge in edges:
                # for edge in graph.es.select(lambda e: (labels[label] == e.source or labels[label] == e.target)) :
                #     found = False
                    for rmedge in rmedges :
                        if rmedge['guid1'] == graph.edge_get_source(edge) and \
                                rmedge['guid2'] == graph.edge_get_target(edge):
                            # found = True
                            break
                    else:
                        rmedges.append({'op':'RMEDGE',
                                        'guid1':graph.edge_get_source(edge),
                                        'guid2':graph.edge_get_target(edge)})
        if len(labels_to_delete) > 0 :
            packet.deltas = rmedges + rmnodes + packet.deltas
            graph.delete_nodes(labels_to_delete)

            ''' hergin :: motif-integration start :: remove the deleted nodes from pivots list '''
            for uuid in packet.global_pivots:
                deleted=False
                for toBeDeleted in rmnodes:
                    if toBeDeleted['guid'] == packet.global_pivots[uuid]:
                        del packet.global_pivots[uuid]
                        deleted=True
                        continue
                if deleted:
                    continue
            ''' hergin :: motif-integration end '''