# _ File: GraphRewritingSys.py _________________________________________________________________ # Implements : class GraphRewritingSys # Author : Juan de Lara # Description: A class that implements a simple graph rewriting system. # Modified : # - 20 Oct 2001. Added capability to execute in parallel or sequential modes # ________________________________________________________________________________________ from GGrule import * from executionControl import * class GraphRewritingSys: # flags that show the execution mode SEQ_RANDOM = 0 SEQ_MANUAL = 1 PARALLEL = 2 def __init__(self, parent, GGs = None, graph = None): "constructor, takes a list of GraphGrammars and a graph as inputs" self.parent = parent self.GraphGrammars = GGs self.graph = graph self.initialized = 0 # No initialization yet self.lastExecutedGG = 0 # last executed GG self.lastExecutedRule = 0 # last executed GG self.stepByStep = 0 # must execute SBS?? self.executed = 1 self.lastRule = 0 # show last executed rule self.executionMode = 0 # can be one of (SEQ_RANDOM, SEQ_MANUAL, PARALLEL) self.graphics = 1 # if we should update the graphics information # it should be 0 in the case for example of a graph-grammar acting on a non-visible model. def getCurrentGG(self): "returns the name of the current graph grammar" if self.lastExecutedGG < len (self.GraphGrammars): return self.GraphGrammars[self.lastExecutedGG].__class__.__name__ else: return "" def getLastRule(self): "returns the name of the last executed rule" if self.lastExecutedGG < len (self.GraphGrammars): gg = self.GraphGrammars[self.lastExecutedGG] if self.lastRule < len(gg.GGrules): rule = gg.GGrules[self.lastRule] return rule.__class__.__name__+" (order: "+str(rule.executionOrder)+")" return "" def evaluate(self, stepByStep, moveEntities, execute, graphics = 1): "executes each rule of each Graph Grammar until none of them is applicable" self.moveEntities = moveEntities # if entities should move self.stepByStep = stepByStep self.lastExecutedGG = 0 # last executed GG self.lastExecutedRule = 0 # last executed Rule self.initialized = 0 # last executed GG self.executionMode = execute self.graphics = graphics if not self.stepByStep: c = 0 while (c == 0): c = self.doStep() else: # present a window with a button to step through the GG rules ec = executionControl(self) def areDisjoint (self, graph1, graph2): "Test wether graph1 and graph2 are disjoints" for node in graph1: # for each node in the first graph, see if they appear in te other list... if node in graph2: return 0 return 1 def executeRule( self, subGraph, rule = None ): """ Executes current rule on the subgraph subGraph""" # first, determine the rule to be executed if not rule: rule2exec = self.GraphGrammars[self.lastExecutedGG].GGrules[self.lastExecutedRule] else: rule2exec = rule rule2exec.replaceSides(self.parent, subGraph, self.graph, self.moveEntities, self.graphics) # Perform substitution on each morphism graph rule2exec.action(subGraph[0], subGraph[1], self.parent) # Execute associated action... rule2exec.unMatch(self.graph) # restore graph if self.parent.console: self.parent.console.appendText('Rule '+str(rule2exec.executionOrder)+ '('+rule2exec.__class__.__name__+') was executed!') self.lastRule = self.lastExecutedRule self.lastExecutedRule = 0 # begin again return 0 def doStep(self): if self.lastExecutedGG >= len(self.GraphGrammars): # We've finished return 0 gg = self.GraphGrammars[self.lastExecutedGG] if not self.initialized: self.initialized = 1 # sets an extra label to each node in the host graph, with a list of links to matched LHS rule nodes for tip in self.graph.listNodes.keys(): for node in self.graph.listNodes[tip]: node._matched = [] self.executed = 1 # flag that indicates if some rule has been applied self.lastExecutedRule = 0 # index to the last executed rule... # set a pointer to myself in each graph grammar... gg.setGraphRewritingSystem(self) # execute the initial action method gg.initialAction(self.graph) executed = 0 while (not executed) and self.lastExecutedRule < len(gg.GGrules): # If we still have some rules to execute... rule = gg.GGrules[self.lastExecutedRule] if self.parent.console: self.parent.console.appendText('Trying rule '+str(rule.executionOrder)+ '('+rule.__class__.__name__+')') matchings = rule.evaluate(self.graph) # evaluate rule on graph, get all matchings condMatchings = [] # filter the isographs that don't fulfil the condition... executedGraphs = {} if self.executionMode == self.SEQ_MANUAL and len(matchings)>0: # Sequential Manual, so must choose one if there's more than one... condTrue = [] for isograph in matchings: # See how many graphs make the condition true if rule.condition(isograph[0], isograph[1], self.parent): # the condition is hold! condTrue.append(isograph) # Add graph to list of graphs that make condition true if len (condTrue) > 1: # if we have several graphs, highlight them and the user must choose one print "conditions hold for :", condTrue self.parent.highLightGraphs(condTrue) return elif len (condTrue) == 1: # only one, so apply the rule rightaway rule.replaceSides(self.parent, condTrue[0], self.graph, self.moveEntities, self.graphics)# Perform substitution on each morphism graph rule.action(condTrue[0][0], condTrue[0][1], self.parent) # Execute associated action... condMatchings.append(condTrue[0]) executed = 1 else: for isograph in matchings: doExecute = 1 if self.executionMode == self.PARALLEL: graphBeforeReplacement = []+isograph[1] # keep a copy of the graph before replacement (make a new list...) for graphID in executedGraphs.keys(): # for all the graphs that have been executed if not self.areDisjoint(isograph[1], executedGraphs[graphID]): doExecute = 0 # do not try this subgraph because it is not disjoint! break if doExecute and rule.condition(isograph[0], isograph[1], self.parent): # the condition is hold! rule.replaceSides(self.parent, isograph, self.graph, self.moveEntities, self.graphics) # Perform substitution on each morphism graph rule.action(isograph[0], isograph[1], self.parent) # Execute associated action... condMatchings.append(isograph) executed = 1 if self.executionMode == self.SEQ_RANDOM: break # execute only one executedGraphs[isograph[0]] = graphBeforeReplacement # mark the graph befor the replacement subraph as executed, and store it for subsequent comparisons... rule.unMatch(self.graph) # restore graph if executed == 1: # if rule has been executed... if self.parent.console: self.parent.console.appendText('Rule '+str(rule.executionOrder)+ '('+rule.__class__.__name__+') was executed!') self.lastRule = self.lastExecutedRule self.lastExecutedRule = 0 # begin again return 0 else: self.lastExecutedRule = self.lastExecutedRule + 1 # else try next rule else: # execute the initial action method gg.finalAction(self.graph) # Try a new GG (if any) self.lastExecutedGG = self.lastExecutedGG+1 self.lastExecutedRule = 0 self.initialized = 0 return 1