#!/usr/bin/python
"""
/**************************************************************************
* GraphSynth is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* GraphSynth is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with GraphSynth. If not, see .
*
* Please find further details and contact information on GraphSynth
* at: http://graphsynth.com/
*
* Original author: Matthew Ira Campbell
* Python translation by: Bryan Bishop
*************************************************************************/
"""
import math
import os
import yaml #maybe one day?
from numpy import identity, multiply
from copy import copy
import functools
import unittest
#for xml
from xml.dom import minidom
campbell_message = "campbell didnt implement this"
bryan_message = "bryan hasnt got this far yet"
def bryan_message_generator(path): return bryan_message + (" (%s)" % (path))
#in the original graphsynth codebase, there were a lot of properties
#these need to be reincorporated into this python version
def _set_property(self, value=None, attribute_name=None, attr_index=None):
assert attribute_name, "_set_property must have an attribute name to work with"
if attr_index is not None:
self.__getattribute__(attribute_name)[attr_index] = value
else:
setattr(self, attribute_name, value)
def _get_property(self, attribute_name=None, attr_index=None):
assert attribute_name, "_get_attribute must have an attribute name to work with"
if attr_index is not None:
return self.__getattribute__(attribute_name)[attr_index]
return getattr(self, attribute_name)
class PropertyExample:
x = property(fget=functools.partial(_set_property, attribute_name='x'), fset=functools.partial(_get_property, attribute_name='x'), doc="represents the x coordinate of the PropertyExample object")
class TestPythonStuff(unittest.TestCase):
def test_properties(self):
test_message = "testing 123"
prop_ex = PropertyExample()
self.assertTrue(prop_ex.x == None)
prop_ex.x = test_message
self.assertTrue(prop_ex.x == test_message)
if __name__ == "__main__":
unittest.main()
class TestGraphSynth(unittest.TestCase):
def test_graph(self):
g1 = Graph()
def test_node(self):
n1 = Node()
def test_arc(self):
a1 = Arc()
def test_rule(self):
r1 = Rule()
def test_rule_set(self):
r1 = Rule()
r2 = Rule()
s1 = RuleSet()
def test_recognize_choose_apply(self):
pass
def find_delegate(some_list, example):
'''returns a sublist of some_list where the attributes of the elements match those of the example
for example:
>>>class Foo:
>>> def __init__(self, name=""):
>>> self.name = name
>>>class Bar:
>>> name = "hello"
>>>find_delegate([Foo(name="hello"), Foo(name="hello1")], Bar())
'''
assert hasattr(example, "__dict__"), "find_delegate: matching object must have a __dict__"
#get a list of extra attributes
relevant_keys = []
for key in example.__dict__.keys():
if key.count("_") == 0:
relevent_keys.append(key)
if len(relevant_keys)==0: return some_list
results = []
for option in some_list:
assert hasattr(option, "__dict__"), "find_delegate: objects to search must have a __dict__"
for key in relevant_keys:
if option.__dict__.has_key(key):
if option.__dict__[key] == example.__dict__[key]:
results.append(option)
return results
class NextGenerationSteps:
loop = 1
go_to_next = 2
go_to_previous = 3
class CandidatesAre:
unspecified = 1
def set_list(self, variable, index, label):
'''called a few times in Arc, like in set_label and set_variable'''
while len(variable) <= index:
variable.append("")
variable[index] = label
def make_identity(size):
return identity(size)
class Arc:
graphsynth_path = "GraphSynth.Representation/BasicGraphClasses/arc.cs"
def __init__(self, name="", from_node=None, to_node=None, directed=False, doubly_directed=False, local_labels=[], local_variables=[], old_data={'style_key': "", 'x': "", 'y': ""}):
self.name = name
self._from = from_node #tail
self._to = to_node #head
self.directed = directed
self.doubly_directed = doubly_directed
self.local_labels = local_labels
self.local_variables = local_variables
self.old_data = old_data
def set_to(self, to):
self._to = to
def set_from(self, from1):
self._from = from1
def get_from(self):
return self._from
def get_to(self):
return self._to
def length(self):
'''if _to and _from are not nodes, calculate a distance'''
assert not isinstance(self._to, Node)
assert not isinstance(self._from, Node)
v1 = self._from
v2 = self._to
return math.sqrt((v1.X - v2.X) * (v1.X - v2.X) + (v1.Y - v2.Y) * (v1.Y - v2.Y))
def other_node(self, node1):
'''returns the other node that this edge connects to.
returns True if both nodes are the same as the input node'''
if self._to == self._from and self._from == node1: return True
if node1 == self._to: return self._from
elif node1 == self._from: return self._to
else: raise ValueError, "Arc.other_node thinks this node isn't the 'to' and it isn't the 'from'. what is it?"
def set_label(self, index, label):
'''set the label with an index of 'index' to label'''
set_list(self.local_labels, index, label)
def set_variable(self, index, variable):
set_list(self.local_variables, index, variable)
def to_gxml(self):
'''returns gxml including and '''
output = "\n"
#name
output = output + "" + str(self.name) + "\n"
#localVariables
if len(self.local_variables) == 0: output = output + "\n"
else:
output = output + "\n"
for local_var in self.local_variables:
output = output + "" + str(local_var) + "\n"
output = output + "\n"
#localLabels
if len(self.local_labels) == 0: output = output + "\n"
else:
output = output + "\n"
for local_label in self.local_labels:
output = output + "" + str(local_label) + "\n"
output = output + "\n"
#From
if self._from == None: output = output + "\n"
else: output = output + "" + str(self._from[0].name) + "\n" #FIXME: how do you do multiple _from nodes?
#To
if self._to == None: output = output + "\n"
else: output = output + "" + str(self._to[0].name) + "\n"
#directed
output = output + "" + str(self.directed).lower() + "\n"
#doublyDirected
output = output + "" + str(self.doubly_directed).lower() + "\n"
output = output + "\n"
return output
class Edge(Arc):
'''Originally, I created a separate edge and vertex class to allow for the future expansion of GraphSynth into shape grammars. I now have decided that the division is not useful, since it simply deprived nodes of X,Y,Z positions. Many consider edge and arc, and vertex and node to be synonymous anyway but I prefer to think of edges and vertices as arcs and nodes with spatial information. At any rate there is no need to have these inherited classes, but I keep them for backwards-compatible purposes.'''
#there isn't actually any code for an Edge
graphsynth_path = "GraphSynth.Representation/BasicGraphClasses/arc.cs"
pass
class Node:
graphsynth_path = "GraphSynth.Representation/BasicGraphClasses/node.cs"
#none of this has to be here, it's just for reference
arcs = [] #list of arcs connecting to this node
arcs_to = [] #those arcs where arc._to points to this node. "head of the arc".
arcs_from = [] #those arcs where arc._from points to this node. "tail of the arc".
X, Y, Z = 0,0,0 #In an effort to move towards shape grammars, I have decided to make the X, Y, and Z positions of a node permanent members of the node class. This transition will not affect any existing graph grammars, but will allow future graph grammars to take advantage of relative positioning of new nodes. Additionally, it solves the problem of getting X, Y, and Z into the ruleNode class.
old_data = {'screenX': 0, 'screenY': 0}
def __init__(self, name="", local_labels=[], local_variables=[], arcs=[], arcs_to=[], arcs_from=[], X=0, Y=0, Z=0, old_data={'screenX':0, 'screenY':0}):
self.name = name
self.local_labels = local_labels
self.local_variables = local_variables
self.arcs = arcs
self.arcs_to = arcs_to
self.arcs_from = arcs_from
self.X = X
self.Y = Y
self.Z = Z
self.old_data = old_data
def degree(self):
'''the degree or valence of a node is the number of arcs attached to it.
currently this is used in recognition of rule when the strictDegreeMatch is True.'''
return len(self.arcs)
def to_gxml(self):
'''returns gxml including and '''
output = "\n"
#name
output = output + "" + str(self.name) + "\n"
#localVariables
if len(self.local_variables) == 0: output = output + "\n"
else:
output = output + "\n"
for local_var in self.local_variables:
output = output + "" + str(local_var) + "\n"
output = output + "\n"
#localLabels
if len(self.local_labels) == 0: output = output + "\n"
else:
output = output + "\n"
for local_label in self.local_labels:
output = output + "" + str(local_label) + "\n"
output = output + "\n"
#do X, Y, Z if it has that information
if hasattr(self, "X"): output = output + "" + str(self.X) + "\n"
if hasattr(self, "Y"): output = output + "" + str(self.Y) + "\n"
if hasattr(self, "Z"): output = output + "" + str(self.Z) + "\n"
output = output + "\n"
return output
set_label = Arc.set_label
set_variable = Arc.set_variable
class Vertex(Node):
#this was blank in the graphsynth codebase for some reason?
graphsynth_path = "GraphSynth.Representation/BasicGraphClasses/node.cs"
pass
class Graph:
graphsynth_path = "GraphSynth.Representation/BasicGraphClasses/designGraph.cs"
def __init__(self, count=None, nodes=None, arcs=None, global_labels=[], global_variables=[]):
'''set count to some number to make this a complete graph of that many nodes.
note: average_degree is currently not implemented (to make a graph with an average degree on each node)
'''
self.global_labels = global_labels
self.global_variables = global_variables
self.arcs = []
self.nodes = []
if count is not None:
assert isinstance(count, int)
for i in range(count):
self.add_node()
for node in self.nodes:
for node2 in self.nodes[1:]:
self.add_arc("seed arc " + len(self.arcs), node, node2)
return
if nodes is not None and arcs is not None:
self.nodes.extend(nodes)
self.arcs.extend(arcs)
@staticmethod
def _check_for_repeat_names(the_array):
'''warning: this also fixes the repeat names.'''
any_name_changed = False
for node1 in the_array:
name_changed = False
for node2 in the_array[1:]:
if node1.name == node2.name:
node2.name = node2.name + str(the_array.index(node2))
name_changed = True
any_name_changed = True
if name_changed:
node1.name = node1.name + str(the_array.index(node1))
return any_name_changed
def check_for_repeat_names(self):
'''warning: this checks and fixes the repeat names of the graph's nodes and edges'''
return (self._check_for_repeat_names(self.nodes) and self._check_for_repeat_names(self.arcs))
@staticmethod
def _make_unique_name(some_list):
latest = 0
for each in some_list:
if some_list.name.isdigit():
latest = some_list.name
newest = str(int(latest)+1)
return newest
def make_unique_node_name(self):
return self._make_unique_name(self.nodes)
def make_unique_arc_name(self):
return self._make_unique_name(self.arcs)
def internally_connect_graph(self):
raise NotImplementedError, bryan_message
def last_node(self):
return self.nodes[-1:]
def last_arc(self):
return self.arcs[-1:]
def graphic(self):
'''returns a list of the degrees of the nodes in the graph.'''
return_value = []
for current_node in self.nodes:
return_value.append(current_node.degree())
return return_value
def max_degree(self):
return max(self.graphic())
#methods for properly linking nodes and arcs together
def add_arc(self, arc_name="", from_node=None, to_node=None, arc=None):
#first case: only arc is given
if arc_name is None and from_node is None and to_node is None and arc is not None:
self.arcs.append(arc)
return
#catch when arc_name is ""
if arc_name == "": arc_name = self.make_unique_arc_name()
#complain when we don't get anything
if arc_name == "" and from_node is None and to_node is None:
raise ValueError, "Graph.add_arc must be given at least one parameter."
#construct a new arc
temp = Arc(name=arc_name, from_node=from_node, to_node=to_node)
self.arcs.append(temp)
temp._from = from_node
temp._to = to_node
#self.last_arc()._from = from_node
#self.last_arc()._to = to_node
return temp
def remove_arc(self, identifier):
if isinstance(identifier, Arc):
self.arcs.remove(identifier)
elif isinstance(identifier, int):
self.arcs.pop(identifier)
else:
raise IndexError, "Graph.remove_arc: identifier not in list."
return
def add_node(self, new_name="", node_ref=None):
if node_ref is not None and new_name is not None:
raise ValueError, "Graph.add_node: can't both add the node and make a node with the new name, do it yourself."
if node_ref is not None:
self.nodes.append(node_ref)
if new_name == "": new_name = self.make_unique_node_name()
temp = Node(name=new_name)
self.nodes.append(temp)
return temp
def remove_node(self, node_ref=None, node_index=None, remove_arcs_too=False, remove_node_ref=True):
'''removing a node is a little more complicated than removing arcs
since we need to decide what to do with dangling arcs. As a result
there are two booleans that specify how to handle the arcs.
removeArcToo will simply delete the attached arcs if true, otherwise it
will leave them dangling (default is false).
removeNodeRef will change the references within the attached arcs to null
if set to true, or will leave them if false (default is true).'''
#some initial logic to deal with the given parameters
if node_index is None and node_ref is None: raise ValueError, "Graph.remove_node: must be given either a node or a node_index"
if node_index is not None:
if node_index > len(self.nodes)-1: raise IndexError, "Graph.remove_node: node_index is bad."
node_ref = self.nodes[node_index]
if remove_arcs_too:
for connected_arc in node_ref.arcs:
self.remove_arc(connected_arc)
self.nodes.remove(node_ref)
elif remove_node_ref:
for connected_arc in node_ref.arcs:
if connected_arc._from == node_ref:
connected_arc._from = None
else: connected_arc._to = None
self.nodes.remove(node_ref)
else: self.nodes.remove(node_ref)
def save_gxml(self, file_path, version=2.0, mode="w"):
#assert not (mode=="w" and os.path.exists(file_path)), "Graph.save_gxml: file path (%s) already exists. try write mode (mode=w)?" % (file_path)
#assert version==2.0, "Graph.save_gxml: only able to save GraphSynth 2.0 gxml files (version=2.0)"
#this is a terrible xml output method. don't try this at home kids :(
output = ""
output = output + '' + '\n'
output = output + '' + '\n'
#global labels
if len(self.global_labels) == 0: output = output + '\n'
else:
output = output + '' + '\n'
for label in self.global_labels:
output = output + '' + label + '' + '\n'
output = output + '' + '\n'
#global variables
if len(self.global_variables) == 0: output = output + '\n'
else:
output = output + '' + '\n'
for var in self.global_variables:
output = output + '' + var + '' + '\n'
output = output + '' + '\n'
#arcs
if len(self.arcs) == 0: output = output + '\n'
else:
output = output + '' + '\n'
for arc in self.arcs:
output = output + arc.to_gxml()
output = output + '' + '\n'
#nodes
if len(self.nodes) == 0: output = output + '\n'
else:
output = output + '' + '\n'
for node in self.nodes:
output = output + node.to_gxml()
output = output + '' + '\n'
output = output + '' + '\n'
output = output + ''
#save output
fh = open(file_path, mode)
fh.write(output)
fh.close()
return output #just because we're friendly
@staticmethod
def load_gxml(file_path, version=2.0, debug=False):
'''input: gxml file path
output: new Graph object'''
#check that the path exists
assert os.path.exists(file_path), "Graph.load_gxml: file path (%s) must exist." % (file_path)
if debug: print "warning: canvas graphics will not be loaded"
#open it up
doc = minidom.parse(open(file_path, "r"))
if version==2.0:
result = Graph()
result.filename = file_path
page = doc.getElementsByTagName("Page")[0]
#print (page.getElementsByTagName("name")[0].childNodes[0].data)
#page_name = page.getElementsByTagName("name")[0].wholeText #name of the entire file (sort of)
#page_name = page.getElementsByTagName("name")[0].childNodes[0].data
page_name = os.path.basename(file_path)
graph = page.getElementsByTagName("GraphSynth:designGraph")[0] #assume there is only one graph present
try:
graphics = page.getElementsByTagName("GraphSynth:Canvas")[0]
except:
graphics = None
#set up the variables for the for loop
graph_name, global_labels, global_variables, arcs, nodes = None, [], [], [], []
for child in graph.childNodes:
if child.nodeName == "name":
graph_name = child.childNodes[0].wholeText
elif child.nodeName == "globalLabels":
global_labels = child
elif child.nodeName == "globalVariables":
global_variables = child
elif child.nodeName == "arcs":
arcs = child
elif child.nodeName == "nodes":
nodes = child
#now process the results
if len(global_labels.childNodes) > 0: print "TODO: implement global_labels for graphs" #TODO
if len(global_variables.childNodes) > 0: print "TODO: implement global_variables for graphs" #TODO
for global_label in global_labels.childNodes:
#process each label
result.global_labels.append(global_label)
for global_variable in global_variables.childNodes:
#process each variable
result.global_variables.append(global_variable)
#read in the nodes first
for node in nodes.childNodes:
name, local_labels, local_variables, x, y, z = "", [], [], 0, 0, 0
for child in node.childNodes:
if child.nodeName == "name": name = child.childNodes[0].data
elif child.nodeName == "localLabels":
ll_xml = child
for label_xml in ll_xml.childNodes:
if len(label_xml.childNodes) > 0:
local_labels.append(label_xml.childNodes[0].data)
elif child.nodeName == "localVariables":
lv_xml = child
for variable_xml in lv_xml.childNodes:
if len(variable_xml.childNodes) > 0:
local_variables.append(variable_xml.childNodes[0].data)
elif child.nodeName == "X": x = child.childNodes[0].data
elif child.nodeName == "Y": y = child.childNodes[0].data
elif child.nodeName == "Z": z = child.childNodes[0].data
#for some reason there's a lot of crap in the xml file?
#nodes with blank names?? but i don't see any when i look
if name == "\n " or name == "": continue
new_node = Node(name)
new_node.local_labels = local_labels
new_node.local_variables = local_variables
new_node.x, new_node.y, new_node.z = x, y, z
result.nodes.append(new_node)
#arcs are done after the nodes so the references can be used
for arc in arcs.childNodes:
name, local_labels, local_variables, directed, doubly_directed, _from, _to = "", [], [], False, False, None, None
for child in arc.childNodes:
if child.nodeName == "name":
name = child.childNodes[0].data
elif child.nodeName == "localLabels":
ll_xml = child
for label_xml in ll_xml.childNodes:
if len(label_xml.childNodes) > 0:
local_labels.append(label_xml.childNodes[0].data)
elif child.nodeName == "localVariables":
lv_xml = child
for variable_xml in lv_xml.childNodes:
if len(variable_xml.childNodes) > 0:
local_variables.append(variable_xml.childNodes[0].data)
elif child.nodeName == "directed":
if len(child.childNodes) > 0:
val = child.childNodes[0].data
if val == "true": directed = True
elif val == "false": directed = False
else: print "GraphSynth.load_gxml: unknown value for 'directed' on an arc: ", val
elif child.nodeName == "doublyDirected":
if len(child.childNodes) > 0:
val = child.childNodes[0].data
if val == "true": doubly_directed = True
elif val == "false": doubly_directed = False
else: print "GraphSynth.load_gxml: unknown value for 'doublyDirected' on an arc: ", val
elif child.nodeName == "From" or child.nodeName == "To":
if len(child.childNodes) > 0:
node_name = child.childNodes[0].data
if node_name == "": continue #ok we're fine with a dangling arc
the_node = None
#now find the node in the current list
for node in result.nodes:
if node.name == node_name:
the_node = node
break
if the_node == None: raise ValueError, "GraphSynth.load_gxml: arc points to an imaginary node (it's not just dangling)"
if child.nodeName.lower() == "from": _from = [the_node]
elif child.nodeName.lower() == "to": _to = [the_node]
if name == "": continue #this arc doesn't have a node name. this probably an xml data artifact
new_arc = Arc(name)
new_arc.directed = directed
new_arc.doubly_directed = doubly_directed
new_arc.local_labels = local_labels
new_arc.local_variables = local_variables
new_arc._from = _from
new_arc._to = _to
result.arcs.append(new_arc)
result.name = graph_name
result.page_name = page_name
#TODO: append global variables, global labels into the graph
return result
class Candidate:
graphsynth_path = "GraphSynth.Representation/BasicGraphClasses/candidate.cs"
#just for my reference
previous_states = [] #a list of Graph objects
current_state = None #a Graph
age = -1 #the number of iterations this graph has gone through (set by the search process)
def __init__(self, graph=None, previous_states=[], current_state=None, recipe=[], performance_params=[], active_rule_set=-1, age=-1, generation_status=[]):
self._graph = graph
self.previous_states = previous_states
self.current_state = current_state
self.recipe = recipe
self.performance_params = performance_params
self.active_rule_set = active_rule_set
self.age = age
self.generation_status = generation_status
def graph(self, some_other_graph):
self.previous_states.append(self.graph)
self.graph = some_other_graph
def num_rules_called(self):
return len(self.recipe)
def last_rule_set_index(self):
return self.recipe[len(self.recipe) - 1].ruleset_index
def rule_numbers_in_recipe(self):
return set(self.recipe)
def rule_set_indices_in_recipe(self):
indices = []
for rule in self.recipe:
indices.append(rule.ruleset_index)
return set(indices)
def option_numbers_in_recipe(self):
options = []
for rule in self.recipe:
options.append(rule.option_number)
return set(options)
def parameters_in_recipe(self):
params = []
for rule in self.recipe:
params.extend(rule.parameters)
return params
def save_current(self):
if self.current_state:
self.prev_states.append(copy(self))
def add_to_recipe(self, rule_option):
self.recipe.append(deepcopy(rule_option)) #use deepcopy because we cant predict the future of a search algorithm
def undo_last_rule(self):
assert len(self.prev_states)>0, "Candidate.undo_last_rule: requires a previous state to revert back to."
self.active_rule_set_index = self.last_rule_set_index
self.current_state = self.prev_states[-1:]
self.prev_states.remove(self.prev_states[-1:])
self.recipe.pop(len(self.recipe)-1) #or self.recipe.remove(self.recipe[-1:]
self.performance_params = [] #TODO: should the size of this list be preserved?
def save_to_xml(self, filename=None):
'''exports this graph into the graphsynth gxml format'''
assert NotImplementedError, bryan_message
def save_to_yaml(self, filename=None):
'''not guaranteed to be pretty'''
assert NotImplementedError, "Candidate.save_to_yaml: " + bryan_message
handler = open(filename, 'w')
handler.write(yaml.dump(self, default_flow_style=False))
handler.close()
class Rule: #GrammarRule
base_path = "GraphSynth.Representation/RuleClasses/"
graphsynth_path = [base_path + "grammarRule.Basic.cs", base_path + "grammarRule.RecognizeApply.cs", base_path + "grammarRule.ShapeMethods.cs"]
name = ""
spanning = False
induced = False
negate_labels = []
contains_all_global_labels = False
ordered_global_labels = False
embedding_rules = [] #a list of EmbeddingRule objects
recognize_functions = []
recognize_funcs = []
apply_functions = []
apply_funcs = []
DLLofFunctions = None
locations = [] #list of Graph objects
L = None #Graph
R = None #Graph
def no_other_arcs_in_host(self, host_graph, located_nodes, located_arcs):
'''are there any arcs in the host between recognized nodes?'''
#check each arc of the host
#if the arc is not in located nodes but connects two located in nodes then return false
for arc in host_graph.arcs:
if not (arc in located_arcs) and arc._from in located_nodes and arc._to in located_nodes:
return False
#if the check makes it through all arcs, return true
return True
def labels_match(self, host_labels=[]):
if self.ordered_global_labels: return self.order_labels_match(host_labels)
else: return self.unordered_labels_match(host_labels)
def order_labels_match(self, host_labels=[]):
any_found = False
found = True
#first an easy check to see if any negating labels exist in host_labels
#if so, return false
for label in self.negate_labels:
if label in host_labels: return False
for label in host_labels:
if not (host_labels.index(label) == self.L.global_labels.index(label)):
found = False
break
if found:
loc = Graph()
any_found = True
#TODO: confirm if this is right (see grammarRule.Basic.cs line 137)
loc.global_labels.extend(host_labels)
self.locations.append(loc)
return any_found
def unordered_labels_match(self, host_labels=[]):
for label in self.negate_labels:
if label in host_labels: return False
#note: you may have multiple identical labels
temp_labels = copy(host_labels)
for label in self.L.global_labels:
if label in temp_labels:
temp_labels.remove(label)
else: return False
#if there are no more temp_labels, then the two match up completely
#else return false
if self.contains_all_global_labels and not len(temp_labels)==0: return False
return True
@staticmethod
def _make_unique_name(some_list, other_list):
'''generates a unique name based off of the contents in some_list and other_list'''
total_set = set()
for x in [some_list, other_list]:
for each in x:
if some_list.name.isdigit():
total_set.add(name)
return str(int(list(total_set).pop()) + 1)
def make_unique_node_name(self):
return Rule._make_unique_name(self.L.nodes, self.R.nodes)
def make_unique_arc_name(self):
return Rule._make_unique_name(self.L.nodes, self.R.arcs)
def recognize(self, host, transform_matrices=[]):
'''here is the big one! Although it looks compact, a lot of time can be spent in
the recursion that it invokes. Before we get to that, we wanna make sure that
our time there is well spent. As a result, we try to rule out whether the rule
can even be applied at first -- hence the series of nested if-thens. If you don't
meet the first, leave now! likewise for the second. The third is a little trickier.
if there are no nodes or arcs in this rule, then it has already proven to be valid
by the global labels - thus return a single location labeled "anywhere".
if there are no nodes in the rule, then jump to the special function recognizeInitialArcInHost
finally, if the node with the highest degree is higher than the highest degree
of the host, then no need to recurse any further. Else, get into recognizeInitialNodeInHost,
which further calls recognizeRecursion.'''
self.locations = []
if self.labels_match(host.global_labels):
if not self.spanning or self.spanning and (len(self.L.nodes) == len(host.nodes)):
if len(self.L.nodes)==0 and len(self.L.arcs)==0: self.locations.append(Graph())
elif len(self.L.nodes)==0: self.recognize_initial_arc_in_host(host)
elif self.L.max_degree() < host.max_degree(): self.recognize_initial_node_in_host(host)
i = 0
length = len(self.locations) #we dont have to do -1 because while is < and not <=
while i < length:
location = self.locations[i]
T = self.find_transform(location.nodes)
if not self.use_shape_restrictions or (self.valid_transform(T) and self.other_nodes_comply(T, location.nodes)):
transform_matrices.append(T)
i+=1
else: locations.pop(i)
return locations
def recognize_initial_node_in_host(self, host):
starting_L_node = self.L.nodes[0]
#if the first node of L (L.nodes[0]) is not in the host, then we can stop
#as a rule of thumb, the creator of the grammar rules should always put the
#most restrictive node FIRST in L, this will allow for a more efficient recognize routine.
for current_host_node in host.nodes:
#see if it matches with each node in host
if starting_L_node.match_with(current_host_node):
'''we will be storing potential locations in these two lists.
it will be necessary to keep making copies of these lists as
we discover new potential subgraphs. So, I wanna make sure these
are as light as possible. Instead of making a whole designGraph
instance, we will just move around these 2 lists. The lists will
point to the actual elements in host, but will correspond in size
and position to those in 'this' L. Since we know the size ahead
of time, we can preset the 'capacity' of the list. however this doesn't
mean the lists are actually that size, so we need to explicitly
initialize the lists.'''
located_nodes = []
located_arcs = []
for i in range(len(self.L.nodes)):
located_nodes.append(None)
for i in range(len(self.L.arcs)):
located_arcs.append(None)
located_nodes[0] = current_host_node
#we've made one match so set that up before invoking the recursion
self.recognize_recursion(host, located_nodes, located_arcs, starting_L_node, current_host_node)
def recognize_initial_arc_in_host(self, host):
starting_L_arc = self.L.arcs[0]
for current_host_arc in host.arcs:
if starting_L_arc.match_with(current_host_arc):
located_nodes = []
located_arcs = []
for i in range(len(self.L.nodes)):
located_nodes.append(None)
for i in range(len(self.L.arcs)):
located_arcs.append(None)
located_arcs[0] = current_host_arc
self.recognize_recursion(host, located_nodes, located_arcs, None, None) #ok positional args really do suck
def recognize_recursion(self, located_nodes, located_arcs, from_L_node, from_host_node):
'''Here is the main recursive function. Based on the current conditions within the recursion
one of four cases maybe invoked.
1. (case1LocationFound) All nodes and arcs within locatedNodes and locatedArcs have been
filled with pointers to nodes and arcs in the host. If this is the case, then we can add
the location. however, you will need to check the enigmatic INDUCED condition.
'''
if not None in located_nodes and not None in located_arcs: self.case_1_location_found(host, located_nodes, located_arcs)
else:
'''
the last thing the recursion did was find a new node to start from.
see if there are any valid arcs on the L that still need to be matched with
the host. Here, currentLArcIndex is used instead of the actual reference
to the L arc. Why? Because, the index is useful both to the L and to locatedArcs
which lists arcs in the same way as they appear in the L.
'''
current_L_arc_index = -1
traverse_forward = False
#this odd little boolean is used to indicate whether or not we are following the
#arc in the proper direction regardless of the direction. We want to be able to follow
#arcs backwards for recognition sake, so this is only useful in the eventual matchWith
#method if direction is important.
for the_arc in self.L.arcs:
#this for loop seeks a L node leaving our fromLNode. If there is more than one arc, than
#the loop may re-write currentLArcIndex and traverseForward. That's okay. Because we only
#want one at this point. The recursion will eventually come around to any others that may
#be skipped over here.
i = self.L.arcs.index(the_arc)
if the_arc._from == from_L_node and located_arcs[i]==None:
current_L_arc_index = i
traverse_forward = True
elif the_arc._to == from_L_node and located_arcs[i]==None:
current_L_arc_index = i
traverse_forward = False
if current_l_arc_index == -1:
#2. (case2FindNewFromNode) if you get here, then it means that then were no more arcs
# leaving the last node. Unfortunately, since Case 1 was not met, there are still
# openings in the locations - either arcs and/or nodes.
self.case_2_find_new_from_node(host, located_nodes, located_arcs, from_L_nodes)
else:
#so, currentLArcIndex now, points to a LArc that has yet to be recognized. What we do from
#this point depends on whether that LArc points to an L node we have yet to recognize, an L
#node we have recognized, or null.
next_L_node = self.L.arcs[current_L_arc_index].other_node(from_L_node)
if next_L_node is None:
#3. (case3DanglingNodes) If nextLNode is null then we need to simply find a match for
#the arc indicated by currentLArcIndex. Similar to case2, this function will need to
#find a new starting point in matching the graphs.
self.case_3_dangling_L_node(host, located_nodes, located_arcs, from_L_node, from_host_node, current_L_arc_index, traverse_forward)
elif located_nodes[self.L.nodes.index(next_L_node)] is not None:
#4. (case4ConnectingBackToPrevRecNode) So, a proper arc was found leaving the
# last L node. Problem is, it points back to a node that we've already located.
# That means that we also already found what host node it connects to.
self.case_4_connecting_back_to_prev_rec_node(host, located_nodes, located_arcs, next_L_node, from_host_node, current_L_arc_index, traverse_forward)
else:
#5. (case5FindingNewNodes) Okay, so nothing strange here. You are following an arc
# that is leading to a yet undiscovered node. Good luck!
self.case_5_finding_new_nodes(host, located_nodes, located_arcs, next_L_node, from_host_node, current_L_arc_index, traverse_forward)
def case1_location_found(self, host, located_nodes, located_arcs):
'''a complete subgraph has been found. However, there is two more conditions to check.
The induced boolean indicates that if there are any arcs in the host between the
nodes of the subgraph that are not in L then this is not a valid location. After this we
check the variables for a violation.
'''
param_functions_violated=False
if not self.induced or (self.induced and self.no_other_arcs_in_host(host, located_nodes, located_arcs)):
recognize_arguments = [self.L, host, located_nodes, located_arcs]
#FIXME dll stuff omitted (!) -- probably very important?
for recognize_function in self.recognize_funcs:
if recognize_function(recognize_arguments):
param_functions_violated = True
break
if not param_functions_violated: self.locations.append(Graph(located_nodes, located_arcs))
def case2_find_new_from_node(self, host, located_nodes, located_arcs):
next_L_node_index = self.L.nodes.index(from_L_node) + 1
if len(self.L.nodes) == next_L_node_index:
next_L_node_index = 0 #these 3 prev.lines simply go to the next node in L
# - if you're at the end then wraparound to 0.
next_L_node = self.L.nodes[next_L_node_index]
if located_nodes[next_L_node_index] == None:
#this acts like a mini-recognizeInitialNodeInHost function, we are forced to jump to a new starting
#point in L - careful, though, that we don't check it with a node that has already been included
#as part of the location.
for current_host_node in host.nodes:
if not (current_host_node in located_nodes) and next_L_node.match_with(current_host_node):
new_located_nodes = [] #copy the locatedNodes to a new list.
#just in case the above foreach statement
#find several matches for our new
#starting node - we wouldnt want to alter
#locatedNodes to affect that but rather
#merely to re-invoke the recusion.
for i in range(len(located_nodes)):
new_located_nodes.append(None)
new_located_nodes[next_L_node_index] = current_host_node
self.recognize_recursion(host, new_located_nodes, located_arcs, next_L_node, current_host_node)
#so the next L node has already been recognized. Well, then we can restart the recursion as if we are
#coming from this node. It's possible that recognizeRecursion will just throw you back into this function
#but that's okay. we just advance to the next node and look for new 'openings'.
else: recognize_recursion(host, located_nodes, located_arcs, next_L_node, located_nodes[next_L_node_index])
def case3_dangling_nodes(self, host, located_nodes, located_arcs, from_L_node, from_host_node, current_L_arc_index, traverse_forward):
current_L_arc = self.L.arcs[current_L_arc_index] #first we must match the arc to a possible arc
#leaving the from_host_node
next_host_node = None
neighbor_host_arcs = []
for each in host.arcs: #FIXME this used to be a "delegate" call of some sort?
if (each in located_arcs) and current_L_arc.match_with(each, from_host_node, traverse_forward):
neighbor_host_arcs.append(each)
if len(neighbor_host_arcs) > 0: #if there are no recognized arcs we just leave
for host_arc in neighbor_host_arcs:
#for each arc that was recognized, we now need to check that the destination node matches.
next_host_node = host_arc.other_node(from_host_node)
if not current_L_arc.null_means_null or next_host_node is None:
#if nullMeansNull is false than ANY host node is fine even if its also null. If nullMeansNull
#is true, however, than we need to make sure fromHostNode is also null.
new_located_arcs = []
for i in range(current_L_arc_index):
new_located_arcs.append(None)
new_located_arcs[current_L_arc_index] = host_arc
#re-invoking the recursion is "tough" from this point. since we just hit a dead end in L.
#the best thing to do is just use the very same fromLnode and fromHostNode that were
#used in the previous recognizeRecursion.
self.recognize_recursion(host, located_nodes, new_located_arcs, from_L_node, from_host_node)
def case4_connecting_back_to_prev_rec_node(self, host, located_nodes, located_arcs, next_L_node, from_host_node, current_L_arc_index, traverse_forward):
current_L_arc = self.L.arcs[current_L_arc_index] #first we must match the arc to a possible arc
#leaving the from_host_node
next_host_node = located_nodes[self.L.nodes.index(next_L_node)]
neighbor_host_arcs = []
for some_arc in host.arcs: #there may be several possible arcs that match with current_L_arc so we make a list called neighbor_host_arcs
if not (some_arc in located_arcs) and current_L_arc.match_with(some_arc, from_host_node, next_host_node, traverse_forward):
neighbor_host_arcs.append(some_arc)
if len(neighbor_host_arcs) > 0: #if there are no recognized arcs we just leave
for host_arc in neighbor_host_arcs:
new_located_nodes = []
new_located_nodes[L.nodes.index(next_L_node)] = next_host_node #FIXME was a 'delegate' in the original graphsynth source
new_located_arcs[current_L_arc_index] = host_arc
self.recognize_recursion(host, new_located_nodes, new_located_arcs, next_L_node, next_host_node)
def case5_finding_new_nodes(self, host, located_nodes, located_arcs, next_L_node, from_host_node, current_L_arc_index, traverse_forward):
#this function starts very similar to Case 4. It is, however, more comlex since we need to match
#the next node in L to a node in the host. The function begin the same as above by gathering the
#potential arcs leaving the host and checking them for compatibility.
current_L_arc = self.L.arcs[current_L_arc_index]
next_host_node = None
for each in host.arcs:
if (not each in located_arcs) and current_L_arc.match_with(each, from_host_node, traverse_forward):
neighbor_host_arcs.append(each)
if len(neighbor_host_arcs) > 0:
for host_arc in neighbor_host_arcs:
#for each arc that was recognized, we now need to check that the destination node matches.
next_host_node = host_arc.other_node(from_host_node)
if next_L_node.match_with(next_host_node) and not (next_host_node in located_nodes):
#if the nodes match than we can update locations and re-invoke the recursion. It is important
#to copy the locatedNodes to a new list, just in case the above foreach statement finds
#several matches for our new new L node.
new_located_nodes = copy(located_nodes)
for i in range(len(self.L.nodes)):
new_located_nodes.append(None)
for a in self.L.nodes:
if a == next_L_node:
new_located_nodes[self.L.nodes.index(a)] = next_host_node
new_located_arcs = copy(located_arcs)
new_located_arcs[current_L_arc_index] = host_arc
self.recognize_recursion(host, new_located_nodes, new_located_arcs, next_L_node, next_host_node)
def apply(self, L_mapping, host, position_t, parameters=[]):
for a in self.L.global_labels:
if not self.R.contains(a):
host.global_labels.remove(a) #removing the lables in L but not in R
#if there are multiple identical R.global_labels, they are not added
for a in self.R.global_labels:
if not self.R.contains(a):
host.global_lables.append(a) #and adding the label in R but not in L
#do the same now, for the variables.
for a in self.L.global_variables:
if not self.R.global_variables.contains(a):
host.global_variables.remove(a) #removing the variables in L but not in R
for a in self.R.global_variables:
if not self.L.global_variables.contains(a):
host.global_variables.append(a) #and adding the variables in R but not in L
#First set up the Rmapping, which is a list of nodes within the host
#that corresponds in length and position to the nodes in R, just as
#Lmapping contains lists of nodes and arcs in the order they are
#referred to in L.
R_mapping = Graph()
#we do not know what these will point to yet, so just
#make it of proper length at this point.
#DEBUG HINT: you should check R_mapping at the end of
#the function - it should contain no None values.
for node in self.R.nodes:
R_mapping.nodes.append(None)
for arc in self.R.arcs:
R_mapping.arcs.append(None)
self.remove_L_diff_K_from_host(L_mapping, host)
self.add_R_diff_K_to_D(L_mapping, R_mapping, position_T)
'''these two lines correspond to the two "pushouts" of the double pushout algorithm.
L <--- K ---> R this is from freeArc embedding (aka edNCE)
| | | | this is from the parametric update
| | | | |
host <-- D ---> H1 ---> H2 ---> H3
The first step is to create D by removing the part of L not found in K (the commonality).
Second, we add the elements of R not found in K to D to create the updated host, H. Note,
that in order to do this, we must know what subgraph of the host we are manipulating - this
is the location mapping found by the recognize function.'''
self.free_arc_embedding(L_mapping, host, R_mapping)
#however, there may still be a need to embed the graph with other arcs left dangling,
#as in the "edge directed Node Controlled Embedding approach", which considers the neighbor-
#hood of nodes and arcs of the recognized Lmapping.
self.update_parameters(L_mapping, host, R_mapping, parameters)
def remove_L_diff_K_from_host(self, L_mapping, host):
'''foreach node in L - see if it "is" also in R - if it is in R than it "is" part of the
commonality subgraph K, and thus should not be deleted as it is part of the connectivity
information for applying the rule. Note that what we mean by "is" is that there is a
node with the same name. The name tag in a node is not superficial - it contains
useful connectivity information. We use it as a stand in for referencing the same object
this is different than the local lables which are used for recognition and the storage
any important design information.
'''
for some_node in self.L.nodes:
i = self.L.nodes.index(some_node)
exists = False
for node in self.R.nodes:
if node.name == self.L.node.name:
exists = True
break
#if a node with the same name does not exist in R, then it is safe to remove it.
#The removeNode should is invoked with the "false false" switches of this function.
#This causes the arcs to be unaffected by the deletion of a connecting node. Why
#do this? It is important in the edNCE approach that is appended to the DPO approach
#(see the function freeArcEmbedding) in connecting up a new R to the elements of L
#a node was connected to.
if not exists: host.remove_node(L_mapping.nodes[i], False, False)
for some_arc in self.L.arcs:
i = self.L.arcs.index(some_arc)
exists = False
for arc in self.R.arcs:
if some_arc.name == arc.name:
exists=True
break
if not exists: host.remove_arc(L_mapping.arcs[i])
def add_R_diff_K_to_D(self, L_mapping, D, R_mapping, position_T):
'''in this adding and gluing function, we are careful to distinguish
the Lmapping or recognized subgraph of L in the host - heretofore
known as Lmapping - from the mapping of new nodes and arcs of the
graph, which we call Rmapping. This is a complex function that goes
through 4 key steps:
1. add the new nodes that are in R but not in L.
2. update the remaining nodes common to L&R (aka K nodes) that might
have had some label changes.
3. add the new arcs that are in R but not in L. These may connect to
either the newly connected nodes from step 1 or from the updated nodes
of step 2.
4. update the arcs common to L&R (aka K arcs) which might now be connected
to new nodes created in step 1 (they are already connected to
nodes in K). Also make sure to update their labels just as K nodes were
updated in step 2.'''
#here are some placeholders used in this bookeeping. Many are used multiple times
#so we might as well declare them just once at the start.
index1, index2, from_node, to_node, k_node, k_arc = None, None, None, None, None, None
for r_node in self.R.nodes:
#step 1. add new nodes to D
exists = False
for each in self.L.nodes:
if each.name == r_node.name:
exists=True
break
if not exists:
D.add_node(r_node.node_type) #create a new node #FIXME do "node_type" the python way
R_mapping.nodes[i] = D.last_node #make sure it's referenced in R_mapping
#labels cannot be set equal, since that merely sets the reference of this list
#to the same value. So, we need to make a complete copy.
r_node = copy(D.last_node) #FIXME: should this be deepcopy?
#give that new node a name and labels to match with the R.
self.update_position_of_node(D.last_node, position_T, r_node)
#step 2. update K nodes.
else:
#else, we may need to modify or update the node. In the pure graph
#grammar sense this is merely changing the local labels. In a way,
#this is a like a set grammar. We need to find the labels in L that
#are no longer in R and delete them, and we need to add the new labels
#that are in R but not already in L. The ones common to both are left
#alone.
index1 = None
for each in self.L.nodes: #find index of the common node in L
if each.name == r_node.name:
index1 = self.L.nodes.index(each)
k_node = L_mapping.nodes[index1] #... and then set k_node to the actual node in D.
R_mapping.nodes[i] = k_node #also, make sure that the R_mapping is the same node
for a in self.L.nodes[index1].local_labels:
if not (a in r_node.local_labels): k_node.local_labels.remove(a) #removing the labels in L but not in R...
for a in r_node.local_labels:
if not (a in self.L.nodes[index1].local_labels): k_node.local_labels.append(a) #...and adding the label in R but not in L.
for a in self.L.nodes[index1].local_variables:
if not (a in r_node.local_variables): k_node.local_variables.remove(a) #removing the variables in L but not in R
for a in r_node.local_variables:
if not (a in self.L.nodes[index1].local_variables): k_node.local_variables.append(a) #and adding the variable in R but not in L
k_node.display_shape = copy(r_node.display_shape)
self.update_position_of_node(k_node, position_T, r_node)
#now moving onto the arcs (a little more challenging actually)
for r_arc in self.R.arcs:
i = self.R.arcs.index(r_arc)
#step 3. add new arcs to D
exists = False
for test_arc in self.L.arcs:
if test_arc.name == r_arc.name:
exists=True
break
if not exists:
#setting up where the arc comes from
if r_arc._from == None: From = None
else: #this should be reworked into an elif to be honest
#if the arc is coming from a node that is in K, then it must've been
#part of the location (or L_mapping) that was originally recognized.
exist1 = False
for ea in self.L.nodes:
if ea.name == r_arc._from.name:
exist1 = True
index1 = self.L.nodes.index(ea)
From = L_mapping.nodes[index1]
break
if not exist1:
#if not in K then the arc connects to one of the new nodes that were
#created at the beginning of this function (see step 1) and is now
#one of the references in R_mapping.
index1 = self.R.find_index_of_node_with(name=r_arc._from.name)
From = R_mapping.nodes[index1]
#setting up where the arc goes
#this code is the same of "setting up where arc comes from - except here
#we do the same for the to connection of the arc.
if r_arc._to is None: To = None
else:
index1 = self.L.find_index_of_node_with(name=r_arc._to.name)
if index1 is not None and index1 is not False:
To = L_mapping.nodes[index1]
else:
index1 = self.R.find_index_of_node_with(name=r_arc._to.name)
To = R_mapping.nodes[index1]
D.add_arc(r_arc.name, r_arc.arc_type, From, To)
R_mapping.arcs[i] = D.last_arc
r_arc.copy(D.last_arc)
#step 4. update K arcs.
else: #line 579 ish
index2 = self.L.find_index_of_arc_with(name=r_arc.name)
#first find the position of the same arc in L
current_L_arc = self.L.arcs[index2]
k_arc = L_mapping.arcs[index2] #then find the actual arc in D that is to be changed
#one very subtle thing just happened here! (07/06/06) if the direction is reversed, then
#you might mess-up this k_arc. We need to establish a boolean so that references
#incorrectly altered.
k_arc_is_reversed = False
if not (L_mapping.nodes.index(k_arc._from) == self.L.nodes.index(current_L_arc._from)) and not (L_mapping.nodes.index(k_arc._to) == self.L.nodes.index(current_L_arc._to)):
k_arc_is_reversed = True
R_mapping.arcs[i] = k_arc
#similar to step 3. we first find how to update the from and to.
if current_L_arc._from is not None and r_arc._from is None:
#this is a rare case in which you actually want to break an arc from its attached
#node. If the corresponding L arc is not null only! if it is null then it may be
#actually connected to something in the host, and we are in no place to remove it.
if k_arc_is_reversed: k_arc._to = None
else: k_arc._from = None
elif r_arc._from is not None:
index1 = self.R.nodes.find_index_of_node_with(name=r_arc._from.name)
#find the position of node that this arc is supposed to connect to in R
if k_arc_is_reversed: k_arc._to = R_mapping.nodes[index1]
else: k_arc._from = R_mapping.nodes[index1]
#now do the same for the To connection.
if current_L_arc._to is not None and r_arc._to is None:
if k_arc_is_reversed: k_arc._from = None
else: k_arc._to = None
elif r_arc._to is not None:
index1 = self.R.find_index_of_node_with(name=r_arc.To.name)
if k_arc_is_reversed: k_arc._from = R_mapping.nodes[index1]
else: k_arc._to = R_mapping.nodes[index1]
#just like in step 2, we may need to update the labels of the arc.
for a in current_L_arc.local_labels:
if not a in r_arc.local_labels: k_arc.local_labels.remove(a)
for a in r_arc.local_labels:
if not a in current_L_arc.local_labels: k_arc.local_labels.append(a)
for a in current_L_arc.local_variables:
if not a in r_arc.local_variables: k_arc.local_variables.remove(a)
for a in r_arc.local_variables:
if not a in current_L_arc.local_variables: k_arc.local_variables.append(a)
if (not k_arc.directed) or (k_arc.directed and current_L_arc.direction_is_equal):
k_arc.directed = r_arc.directed
#if the k_arc is currently undirected or if it is and direction is equal
#then the directed should be inherited from R.
if (not k_arc.doubly_directed) or (k_arc.doubly_directed and current_L_arc.direction_is_equal):
k_arc.doubly_directed = r_arc.doubly_directed
k_arc.display_shape = copy(r_arc.display_shape)
def free_arc_embedding(self, L_mapping, host, R_mapping):
'''There are nodes in host which may have been left dangling due to the fact that their
connected nodes were part of the L-R deletion. These now need to be either 1) connected
up to their new nodes, 2) their references to old nodes need to be changed to null if
intentionally left dangling, or 3) the arcs are to be removed. In the function
removeLdiffKfromHost we remove old nodes but leave their references intact on their
connected arcs. This allows us to quickly find the list of freeArcs that are candidates
for the embedding rules. Essentially, we are capturing the neighborhood within the host
for the rule application, that is the arcs that are affected by the deletion of the L-R
subgraph. Should one check non-dangling non-neighborhood arcs? No, this would seem to
cause a duplication of such an arc. Additionally, what node in host should the arc remain
attached to? There seems to be no rigor in applying these more global (non-neighborhood)
changes within the literature as well for the general edNCE method.'''
free_end_identifier = None
new_node_to_connect, node_removed_in_L_diff_R_deletion, to_node, from_node = None, None, None, None
neighbor_node = None
num_of_arcs = len(host.arcs)
for arc in host.arcs:
#first, check to see if the arc is really a freeArc that needs updating.
if self.embedding_rule.arc_is_free(arc, host, free_end_identifier, neighbor_node): #the last two are apparently return values? wtf FIXME
free_arc = arc
#For each of the embedding rules, we see if it is applicable to the identified freeArc.
#The rule then modifies the arc by simply pointing it to the new node in R as indicated
#by the embedding Rule's RNodeName. NOTE: the order of the rules are important. If two
#rules are 'recognized' with the same freeArc only the first one will modify it, as it
#will then remove it from the freeArc list. This is useful in that rules may have precedence
#to one another. There is an exception if the rule has allowArcDuplication set to true,
#since this would simply create a copy of the arc.
for e_rule in self.embedding_rules: #FIXME where is embedding_rules defined? see line 683 in grammarRule.RecognizeApply.cs
new_node_to_connect = e_rule.find_new_node_to_connect(R, R_mapping)
node_removed_in_L_diff_R_deletion = e_rule.find_deleted_node(L, L_mapping)
if e_rule.rule_is_recognized(free_end_identifier, free_arc, neighbor_node, node_removed_in_L_diff_R_deletion):
#set up new connection points
if free_end_identifier >= 0:
if e_rule.new_direction >= 0:
to_node = new_node_to_connect
from_node = free_arc._from
else:
to_node = free_arc._from
from_node = new_node_to_connect
else:
if e_rule.new_direction <= 0:
from_node = new_node_to_connect
to_node = free_arc._to
else:
from_node = free_arc._to
to_node = new_node_to_connect
#if making a copy of arc, duplicate it and all the characteristics
if e_rule.allow_arc_duplication:
#under the allowArcDuplication section, we will be making a copy of the
#freeArc. This seems a little error-prone at first, since if there is only
#one rule that applies to freeArc then we will have good copy and the old
#bad copy. However, at the end of this function, we go through the arcs again
#and remove any arcs that still appear free. This also serves the purpose to
#delete any dangling nodes that were not recognized in any rules.
host.add_arc(copy(free_arc), from_node, to_node)
#else, just update the old free_arc
else:
free_arc._from = from_node
free_arc._to = to_node
break #skip the next arc
#this is done so that no more embedding rules will be checked with this free_arc
#clean up (i.e. delete) any free_arcs that are still in host.arcs
for arc in host.arcs:
#this seems a little archaic to use this i-counter instead of foreach.
#the issue is that since we are removing nodes from the list as we go
#through it, we very well can't use foreach. The countdown allows us to
#disregard problems with the deleting.
#.. but this doesn't apply in python. :)
if (arc._from is not None and arc._from not in host.nodes) or (arc._to is not None and arc._to not in host.nodes):
host.remove_arc(arc)
def update_parameters(self, L_mapping, host, R_mapping, parameters):
apply_arguments = [L_mapping, host, R_mapping, parameters, self]
#If you get an error in this function, it is most likely due to
#an error in the compilted DLLofFunctions. Open your code for the
#rules and leave this untouched - it's simply the messenger.
#FIXME: omitted some DLLofFunctions stuff here
#from grammarRule.ShapeMethods.cs
epsilon = 0.000001
regularization_matrix = []
def reset_regularization_matrix(self):
self.regularization_matrix = []
def calculate_regularization_matrix(self):
assert NotImplementedError, bryan_message_generator("GraphSynth.Representation/RuleClasses/grammarRule.ShapeMethods.cs")
use_shape_restrictions = False
transform_node_shapes = False
translate, scale, skew, flip = None, None, None, None
rotate, projection = None, None
def find_transform(self, located_nodes):
#if there are no nodes, simply return the identity matrix
if len(located_nodes) == 0: return make_identity(3)
x1, x2, x3, x4, y1, y2, y3, y4 = 0, 0, 0, 0, 0, 0, 0, 0
tx, ty, wX, wY, a, b, c, d = 0, 0, 0, 0, 0, 0, 0, 0
k1, k2, k3, k4 = 0, 0, 0, 0
u3, u4, v3, v4 = 0, 0, 0, 0
x1 = located_nodes[0].X
y1 = located_nodes[0].Y
if len(self.L.nodes) >= 2:
x2 = located_nodes[1].X
y2 = located_nodes[1].Y
if len(self.L.nodes) >= 3:
x3 = located_nodes[2].X
y3 = located_nodes[2].Y
temp = [self.L.nodes[2].X, self.L.nodes[2].Y, 1.0]
temp = multiply(self.regularization_matrix, temp)
u3 = temp[0] #this is going to be a whole row. is this right?
u4 = temp[1] #FIXME
if len(self.L.nodes) >= 4:
x4 = located_nodes[3].X
y4 = located_nodes[3].Y
temp = [self.L.nodes[3].X, self.L.nodes[3].Y, 1.0]
temp = multiply(self.regularization_matrix, temp)
u4 = temp[0]
v4 = temp[1]
#set values for tx and ty
tx = x1
ty = y1
#calculate projection terms
if len(self.L.nodes) <= 3:
wX, wY = 0, 0
elif self.same_close_zero(v3 * v4):
wX, wY = 0, 0
else:
#calculate intermediate values used only in this class or method
k1 = u4 * v3 * (y4 - y2) - u3 * v4 * (y3 - y2)
if same_close_zero(k1): k1 = 0
else: k1 /= v3 * v4
k2 = v4 * (y3 - y2 * u3 + ty * u3 - ty) + v3 * (-y4 - ty * u4 + y2 * u4 + ty)
if same_close_zero(k2): k2 = 0
else: k2 /= v3 * v4
k3 = u3 * v4 * (x3 - x2) - u4 * v3 * (x4 - x2)
if same_close_zero(k3): k3 = 0
else: k3 /= v3 * v4
k4 = v3 * (x4 - x2 * u4 + tx * u4 - tx) - v4 * (x3 + tx * u3 - x2 * u3 - tx)
if same_close_zero(k4): k4 = 0
else: k4 /= v3 * v4
#calculate wY and wX
wY = (k1 * k4) - (k2 * k3)
if same_close_zero(wY): wY = 0
else: wY /= k3 * (y3 - y4) + k1 * (x3 - x4) #equation 7
wX = wY * (y3 - y4) + k2
if same_close_zero(wX): wX = 0
else: wX /= k1 #equation 8
#region Calculate rotate, scale, skew terms
if len(self.L.nodes) <= 1:
a, d = 1, 1
b, c = 0, 0
else:
#calculate a
a = x2 * (wX + 1) - tx;
#calculate c
c = y2 * (wX + 1) - ty;
if len(self.L.nodes) <= 2:
"""in order for the validTransform to function, b and d are set as
if there is a rotation as opposed to a Skew in X. It is likely that
isotropic transformations like rotation are more often intended than skews."""
theta = math.atan2(-c, a)
b = -c
d = a
else:
#calculate b
b = x3 * (wX * u3 + wY * v3 + 1) - a * u3 - tx
if same_close_zero(b): b = 0
else: b /= v3
#calculate d
d = y3 * (wX * u3 + wY * v3 + 1) - c * u3 - ty
if same_close_zero(d): d = 0
else: d /= v3
T = [
[a, b, tx], #row 0
[c, d, ty], #row 1
[wX, wY, 1] #row 3
]
T = multiply(T, self.regularization_matrix)
T[0][0] /= T[2][2]
T[0][1] /= T[2][2]
T[0][2] /= T[2][2]
T[1][0] /= T[2][2]
T[1][1] /= T[2][2]
T[1][2] /= T[2][2]
T[2][0] /= T[2][2]
T[2][1] /= T[2][2]
T[2][2] = 1
return T
def valid_transform(self, T, theta=None):
'''in this function the candidate transform T "runs the gauntlet"
the long set of if statements each return false, and if T makes it all
the way through, we return true
it's easy to check the translation and projection constraints first
since there's a one-to-one match wtih variables in the matrix and the flags.'''
if theta is not None: return self.valid_transform_theta(T, theta)
if not same_close_zero(T[0][2]) and (self.translate == self.transform_type.only_x or self.translate == self.transform_type_prohibited):
return False
elif not same_close_zero(T[1][2]) and (self.translate == self.transform_type.only_x or self.translate == self.transform_type_prohibited):
return False
elif not same_close_zero(T[0][2], T[1][2]) and (self.translate == self.transform_type.only_x or self.translate == self.transform_type_prohibited):
return False
#now for projection
if not same_close_zero(T[2][0]) and (self.projection == self.transform_type.only_x or self.projection == self.transform_type.prohibited):
return False
elif not same_close_zero(T[2][1]) and (self.projection == self.transform_type.only_x or self.projection == self.transform_type.prohibited):
return False
elif not same_close_zero(T[2][0], T[2][1]) and (self.projection == self.transform_type.only_x or self.projection == self.transform_type.prohibited):
return False #FIXME (CHECKME)
#Now, it's a little more complicated since the rotation occupies the same cells
#in T as skewX, skewY, scaleX, and scaleY. The approach taken here is to solve
#for theta (the amount of rotation) and then call/return what the overload produces
#which requires theta and solves for skewX, skewY, scaleX, and scaleY.
elif not self.rotate: return self.valid_transform(T, 0.0)
#skew restrictions are easier than scale, because they default to (as in the identity matrix) 0 whereas scale is 1
elif self.skew == self.transform_type.prohibited or self.skew == self.transform_type.only_y:
return self.valid_transform(T, math.atan2(T[0][1], T[1][1]))
elif self.skew == self.transform_type.only_x:
return self.valid_transform(T, math.atan2(-T[1][0], T[0][0]))
elif self.skew == self.transform_type.both_uniform:
return self.valid_transform(T, math.atan2((T[0][1] - T[1][0]), (T[0][0] + T[1][1]))) #FIXME
#Lastly, and most challenging, we look at Scale Restrictions. Flip is basically
#the same and handled in the overload below.
elif self.scale == self.transform_type.prohibited or self.scale == self.transform_type.only_y:
#wtf are these variable names?
TooPlusTio2 = T[0][0] * T[0][0] + T[1][0] * T[1][0]
sqrtt2pt2 = math.sqrt(Too2PlusTio2)
Ky = math.sqrt(Too2PlusTio2 - 1)
return self.valid_transform(T, theta=math.acos(T[0][0] / sqrtt2pt2) + math.atan2(Ky, 1))
elif self.scale == self.transform_type.only_y:
Toi2PlusTii2 = T[0][1] * T[0][1] + T[1][1] * T[1][1]
sqrtt2pt2 = math.sqrt(Toi2PlusTii2)
Kx = math.sqrt(Toi2PlusTii2 - 1)
return self.valid_transform(T, theta=math.acos(T[0][1] / sqrtt2pt2) + math.atan2(1, Kx))
elif self.scale == self.transform_type.both_uniform: #FIXME
return self.valid_transform(T, theta=math.atan2((T[0][0] - T[1][1]), (T[0][1] + T[1][0])))
def valid_transform_theta(self, T, theta):
#now with theta known, we can find the values for Sx, Sy, Kx, and Ky
Kx = T[0][1] * math.cos(theta) - T[1][1] * math.sin(theta)
Ky = T[0][0] * math.sin(theta) - T[1][0] * math.cos(theta)
Sx = T[0][0] * math.cos(theta) - T[1][0] * math.sin(theta)
Sy = T[0][1] * math.sin(theta) + T[1][1] * math.cos(theta)
#now check the skew restrictions, once an error is found return false
if same_close_zero(Kx) and ((self.skew == self.transform_type.prohibited) or (self.skew == self.transform_type.only_y)):
return False
elif not same_close_zero(Ky) and ((self.skew == self.transform_type.prohibited) or (self.skew == self.transform_type.only_y)):
return False
elif not same_close_zero(Kx, Ky) and self.skew == self.transform_type.both_uniform:
return False
#now we check scaling restrictions.
elif not same_close_zero(math.abs(Sx), 1) and ((self.scale == self.transform_type.prohibited) or (self.scale == self.transform_type.only_y)):
return False
elif not same_close_zero(math.abs(Sy), 1) and ((self.scale == self.transform_type.prohibited) or (self.scale == self.transform_type.only_x)):
return False
elif not same_close_zero(math.abs(Sx), math.abs(Sy)) and self.scale == self.transform_type.both_uniform:
return False
#finally, we check if the shape has to be flipped
if Sx<0 and ((self.flip == self.transform_type.prohibited) or (self.flip == self.transform_type.only_y)):
return False
if Sy<0 and ((self.flip == self.transform_type.prohibited) or (self.flip == self.transform_type.only_x)):
return False
if (Sx*Sy<0) and (self.flip == self.transform_type.both_uniform):
return False
else: return True
def other_nodes_comply(self, T, located_nodes):
if len(self.located_nodes) <= 3: return True
else:
i = 3
while True:
if i == len(self.located_nodes): break #FIXME does this go at the top or bottom of the while loop?
vLVect = [self.L.nodes[i].X, self.L.nodes[i].Y, 1.0]
vLVect = multiply(T, vLVect)
vHostVect = [located_nodes[i].X, located_nodes[i].Y, 1.0]
if (not same_close_zero(vLVect[0], vHostVect[0])) or (not same_close_zero(vLVect[1], vHostVect[1])):
return False
i+=1
return True
def same_close_zero(self, x1, x2=None):
if x2 is not None: return self.same_close_zero(x1 - x2)
if math.abs(x1) < epsilon: return True
else: return False
def update_position_of_node(self, update, T, given): #given is a ruleNode
pt = [given.X, given.Y, 1]
pt = multiply(T, pt)
newT = make_identity(3)
newT[0][2] = update.X = pt[0] / pt[2]
newT[1][2] = update.Y = pt[1] / pt[2]
update.DisplayShape.transform_shape(newT)
def update_shape_qualities_of_node(self, update, T, given):
raise NotImplementedYet, campbell_message
#here we define additional qualities used only by arcs in the grammar rules.
#TODO: check if this is used anywhere
class RuleArc(Arc):
graphsynth_path = "GraphSynth.Representation/RuleClasses/ruleArc.cs"
def __init__(name="", all_local_labels=False, direction_is_equal=False, null_means_null=True, negate_labels=[]):
self.name = name
#The following booleans capture the possible ways in which an arc may/may not be a subset
#(boolean set to false) or is equal (in this respective quality) to the host (boolean set
#to true). These are special subset or equal booleans used by recognize. For this
#fundamental arc classes, only these three possible conditions exist.
self.contains_all_local_labels = all_local_labels
#if true then all the localLabels in the lArc match with those in the host arc, if false
#then lArc only needs to be a subset on host arc localLabels.
self.direction_is_equal = direction_is_equal
#this boolean is to distinguish that the directionality
#within an arc matches perfectly. If false then all (singly)-directed arcs
#will match with doubly-directed arcs, and all undirected arcs will match with all
#directed and doubly-directed arcs. Of course, a directed arc going one way will
#still not match with a directed arc going the other way.
#If true, then undirected only matches with undirected, directed only with directed (again, the
#actual direction must match too), and doubly-directed only with doubly-directed.
self.null_means_null = null_means_null #FIXME what should the default be?
#for a lack of a better name - this play on "no means no" applies to dangling arcs that point
#to null instead of pointing to another node. If this is set to false, then we are saying a
#null reference on an arc can be matched with a null in the graph or any node in the graph.
#Like the above, a false value is like a subset in that null is a subset of any actual node.
#And a true value means it must match exactly or in otherwords, "null means null" - null
#matches only with a null in the host. If you want the rule to be recognized only when an actual
#node is present simply add a dummy node with no distinguishing characteristics. That would
#in turn nullify this boolean since this boolean only applies when a null pointer exists in
#the rule.
self.negate_labels = negate_labels #In GraphSynth 1.8, I added these to ruleNode, ruleArc, and embedding rule classes. This is
#a simple fix and useful in many domains.
#TODO: figure out whether or not it's import to override __deepcopy__ here
def match_with(self, host_arc, from_host_node=None, to_host_node=None, traverse_forward=None):
'''returns a True/False based on if the host arc matches with this rule_arc.
host_arc = the host arc
from_host_node = from host node
to_host_node = to host node
traverse_forward = since the host connecting nodes are provided, we need to
check whether direction is an issue and that the host arc is connected forward (from
_from to _to) or backwards.'''
if host_arc is not None and from_host_node is not None and to_host_node is not None and traverse_forward is not None:
if self.match_with(host_arc):
if (self.directed and (((host_arc._to == to_host_node) and (host_arc._from == from_host_node) and traverse_forward) or ((host_arc._from == to_host_node) and (host_arc._to == from_host_node) and not traverse_forward))):
return True
elif (((host_arc._to == to_host_node) and (host_arc._from == from_host_node)) or ((host_arc._from == to_host_node) and (host_arc._to == from_host_node))):
return True
else: return False
else: return False
#what if we lack the to_node?
if host_arc is not None and from_host_node is not None and traverse_forward is not None and to_node is None:
if match_with(host_arc):
if self.directed:
if (((host_arc._from == from_host_node) and traverse_forward is True) or ((host_arc._to == from_host_node) and not traverse_forward)): return True
else: return False
elif ((host_arc._from == from_host_node) or (host_arc._to == from_host_node)): return True
else: return False
else: return False
#what if we only have host_arc?
if host_arc is not None and from_host_node is None and traverse_forward is None and to_node is None:
#returns a true/false based on if the host arc matches with this rule_arc. This overload
#is mostly used in the above overloads. It calls the next two functions to complete
#the matching process.
if host_arc is not None:
if ((self.direction_is_equal and self.doubly_directed == host_arc.doubly_directed) and (self.directed == host_arc.directed) or (not self.direction_is_equal and (host_arc.doubly_directed or not self.directed or (self.directed and host_arc.directed and not self.doubly_directed)))):
#pardon my french, but this statement is a bit of a mindf**k. What it says is if
#directionIsEqual, then simply the boolean state of the doublyDirected and directed
#must be identical in L and in the host. Otherwise, one of three things must be equal.
#first, hostArc's doublyDirected is true so whatever LArc's qualities are, it is a subset of it.
#second, LArc's not directed so it is a subset with everything else.
#third, they both are singly directed and LArc is not doublyDirected.
if self.labels_match(host_arc.local_labels) and self.intended_types_match(self.arc_type, host_arc.arc_type):
return True
else: return False
else: return False
def labels_match(self, host_labels):
#first an easy check to see if any negating labels exist
#in the host_labels. if so, immediately return false.
for label in self.negate_labels:
if label in host_labels: return False
#next, set up a temp_labels so that we don't change the
#host's actual labels. We delete an instance of the label.
#this is new in version 1.8. It's important since one may
#have multiple identical labels.
temp_labels = []
temp_labels.extend(copy(host_labels))
for label in self.local_labels:
if label in temp_labels: temp_labels.remove(label)
else: return False
#this new approach actually simplifies and speeds up the containAllLabels
#check. If there are no more tempLabels than the two match completely - else
#return false.
if self.contains_all_local_labels and len(temp_labels)>0: return False
return True
def intended_types_match(self, L_arc_type, host_arc_type):
'''not sure what to do with this. python is dynamically typed, making all this Type stuff kinda useless.'''
if L_arc_type is None or isinstance(L_arc_type, Arc) or isinstance(L_arc_type, RuleArc) or L_arc_type == host_arc_type:
return True
else: return False
@staticmethod
def convert_from_arc(arc):
rule_arc = RuleArc(name=arc.name)
rule_arc.arc_type = arc.arc_type #FIXME
rule_arc.directed = arc.directed
rule_arc.display_shape = arc.display_shape
rule_arc._from = arc._from
rule_arc.local_labels.extend(copy(arc.local_labels))
rule_arc.local_variables.extend(copy(arc.local_variables))
rule_arc._to = arc._to
rule_arc.xml_arc_type = arc.xml_arc_type
return rule_arc
class RuleNode(Node):
'''here we define additional qualities used only by nodes in the grammar rules.'''
graphsynth_path = "GraphSynth.Representation/RuleClasses/ruleNode.cs"
intended_types_match = RuleArc.intended_types_match
def __init__(self, name="", contains_all_local_labels=False, strict_degree_match=False, negate_labels=[]):
#The following booleans capture the possible ways in which a node may/may not be a subset
#(boolean set to false) or is equal (in this respective quality) to the host (boolean set
#to true). These are special subset or equal booleans used by recognize. For this
#fundamental node classes, only these two possible conditions exist.
self.contains_all_local_labels = contains_all_local_labels
#if true then all the localLabels in the lNode match with those in the host node, if false
#then lNode only needs to be a subset on host node localLabels.
self.strict_degree_match = strict_degree_match
#this boolean is to distinguish that a particular node
#of L has all of the arcs of the host node. Again,
#if True then use equal
#if False then use subset
#NOTE: this is commonly misunderstood to be the same as induced. The difference is that this
#applies to each node in the LHS and includes arcs that reference nodes not found on the LHS
#In GraphSynth 1.8, I added these to ruleNode, ruleArc, grammarRule (as global Negabels) and
#embedding rule (both for freeArc and NeighborNode) classes. This is a simple fix and useful in
#many domains. If the host item, contains a negabel then it is not a valid match.
self.negate_labels = negate_labels
def match_with(self, host_node):
'''returns True/False based on if the host node matches with this RuleNode.
this calls the next two functions which check labels and type.'''
if host_node is not None:
if (((self.strict_degree_match and (self.degree == host_node.degree)) or
(not self.strict_degree_match and (self.degree <= host_node.degree))) and
(self.labels_match(host_node.local_labels)) and
(self.intended_types_match(self.node_type, host_node.node_type))):
return True
else: return False
else: return False
def labels_match(self, host_labels):
#first an easy check to see if any negating labels exist
#in the host_labels. If so, immediately return False.
for label in self.negate_labels:
if label in host_labels: return False
#next, set up a tempLabels so that we don't change the
#host's actual labels. We delete an instance of the label.
#this is new in version 1.8. It's important since one may
#have multiple identical labels.
temp_labels = []
temp_labels.extend(copy(host_labels))
for label in self.local_labels:
if label in temp_labels: temp_labels.remove(label)
else: return False
#this new approach actually simplifies and speeds up the containAllLabels
#check. If there are no more tempLabels than the two match completely - else
#return False.
if self.contains_all_local_labels and len(temp_labels)>0: return False
return True
@staticmethod
def convert_from_node(n): #can't we just copy the dictionary?
rule_node = RuleNode()
for key in n.__dict__.keys():
val = copy(n.__dict__[key])
setattr(rule_node, key, val)
return rule_node
class Option:
'''these are presented in the choice for which rule to apply.
option contains references to the location where the rule is
applicable, the rule itself, along with its number in the rule_set
and the rule_set's number when there are multiple rule_sets.'''
graphsynth_path = "GraphSynth.Representation/RuleClasses/option.cs"
properties = ["option_number", "rule_set_index", "rule", "location", "position_transform"]
def __init__(self):
#set up the properties
for prop in self.properties:
setattr(self, prop, property(fget=functools.partial(_get_property, attribute_name=prop), fset=functools.partial(_set_property, prop, attribute_name=prop)))
self.option_number, self.rule_set_index, self.rule_number, self.rule, self.location, self.position_transform, self.parameters = None, None, None, None, None, None, []
def apply(self, host, parameters=[]):
self.rule.apply(self.location, host, self.position_transform, self.parameters)
class RuleSet: #not done yet
'''As far as I can tell, this is the first time the idea of a rule set
has been developed to this degree. In many applications we find that
different sets of rules are needed. Many of these characteristics
are built into our current generation process.'''
graphsynth_path = "GraphSynth.Representation/RuleClasses/ruleSet.Basic.cs"
choice_method = property(fget=functools.partial(_get_property, attribute_name="choice_method"), fset=functools.partial(_set_property, attribute_name="choice_method")) #why does this have to be a property?
def __init__(self, name="", rules=[], rule_file_names=[], trigger_rule_number=-1, next_generation_steps=NextGenerationSteps(), rule_set_index=None):
'''
Please note that rule numbers are *not* zero-based. The first rule is number 1.
name: #an arbitrary name for the RuleSet - usually set to the filename
trigger_rule_number: A ruleSet can have one rule set to the triggerRule. If there is no
triggerRule, then this should stay at negative one (or any negative
number). When the trigger rule is applied, the generation process, will
exit to the specified generationStep (as described below).
next_generation_steps: For a particular set of rules, we need to specify what generation should
do if any of five conditions occur during the recognize->choose->apply
cycle. The enumerator, nextGenerationSteps, listed in globalSettings.cs
indicates what to do. The five correspond directly to the five elements
of another enumerator called GenerationStatuses. These five possibilties are:
Normal, Choice, CycleLimit, NoRules, TriggerRule. So, following normal operation
of RCA (normal), we perform the first operation stated below, nextGenerationStep[0]
this will likely be to LOOP and contine apply rules. Defaults for these are
specified in App.config.
rule_set_index: For multiple ruleSets, a value to store its place within the set of ruleSets
proves a useful indicator.
'''
#cheap way of not having to type a lot to make up properties with the same generational structure, syntax and function
_compress_props = [("generation_after_normal", 0), ("generation_after_choice", 1), ("generation_after_cycle_limit", 2), ("generation_after_no_rules", 3), ("generation_after_trigger_rule", 4)]
for each in _compress_props:
setattr(self, each[0], property(fget=functools.partial(_get_property, attribute_name=each[0], attr_index=each[1]), fset=functools.partial(_set_property, attribute_name=each[0], attr_index=each[1])))
self.name = name
self.choice_method = ChoiceMethods.design
#Often when multiple ruleSets are used, some will produce feasible candidates,
#while others will only produce steps towards a feasible candidate. Here, we
#classify a particular ruleSet as one of these.
self.interim_candidates = CandidatesAre.unspecified
self.final_candidates = CandidatesAre.unspecified
#the rules are clearly part of the set, but these are not stored
#in the XML, only the ruleFileNames. In ruleSetXMLIO.cs the
#loading of rules is accomplished.
self.rules = rules
self.rule_file_names = rule_file_names
self._trigger_rule_number = trigger_rule_number
self.next_generation_steps = next_generation_steps
self.rule_set_index = rule_set_index
self.filer = None
def next_rule_set(self, status):
'''A helper function to RecognizeChooseApplyCycle. This function returns what the new ruleSet
will be. Here the enumerator nextGenerationSteps and GenerationStatuses is used to great
affect. Understand that if a negative number is returned, the cycle will be stopped.'''
if self.next_generation_step[status] == NextGenerationSteps.loop: return self.rule_set_index
elif self.next_generation_step[status] == NextGenerationSteps.go_to_next: return self.rule_set_index + 1
elif self.next_generation_step[status] == NextGenerationSteps.go_to_previous: return self.rule_set_index - 1
else: return int(self.next_generation_step[status])
def recognize(self, host):
'''This is the recognize function called within the RCA generation. It is
fairly straightforward method that basically invokes the more complex
recognize function for each rule within it, and returns a list of options.'''
options = []
if len(self.rules) == 0: return options
option_num = 0
i = 0
for rule in self.rules:
i = self.rules.index(rule)
transform_matrices = []
locations = [] #a list of Graphs
locations = self.rules[i].recognize(host, transform_matrices)
j = 0
for loc in locations:
j = locations.index(loc)
option = Option()
options.append(option)
temp=option_num+1
option.option_number = temp #FIXME or should option_num be set to option_num+1? see GS codebase
option.rule_set_index = self.rule_set_index
option.rule_number = i + 1
option.rule = rule
option.location = loc
option.position_transform = transform_matrices[j]
if self.choice_method == choiceMethods.Automatic: return options
#this is merely for efficiency - once we get one valid option for
#an Automatic ruleset we can exit and invoke that option.
return options
class EmbeddingRule:
'''the freeArc can be identified by one of the following
1. label of dangling arc in D (freeArcLabel)
2. name of node in L-R that arc was recently attached to (note the name is from L not G) (L_node_name)
3. label of node in G that is currently attached to dangling arc in D (neighborNodeLabel)
-----
the RHS of the rule is simply the name of the R-node that the arc is to connect to. Since
this exists within the rule, there is no need to include any other defining character - of
course we still need to find the corresponding node in H1 to connect it to. Note, this is
also the main quality that distinguishes the approach as NCE or NLC, as the control is given
to the each individual of R-L (or the daughter graph in the NCE lingo) as opposed to simply
a label based method.'''
def __init__(self, free_arc_labels=[], free_arc_negabels=[], neighbor_node_labels=[], neighbor_node_negabels=[], L_node_name=None, original_direction=None, new_direction=None, allow_arc_duplication=False):
'''
allow_arc_duplication: if True, then for each rule that matches with the arc the arc will be duplicated.
'''
self.free_arc_labels = free_arc_labels
self.free_arc_negabels = free_arc_negabels
self.neighbor_node_labels = neighbor_node_labels
self.neighbor_node_negabels = neighbor_node_negabels
self.L_node_name = L_node_name
self.original_direction = original_direction
self.new_direction = new_direction
#in order to give the edNCE approach the "ed" quality, we must allow for the possibility of
#recognizing arcs having a particular direction. The original direction can be either +1 meaning
#"to", or -1 meaning "from", or 0 meaning no imposed direction - this indicates what side of the
#arc is dangling. Furthermore, the newDirection, can specify a new direction of the arc ("to",
#or "from" being the new connection) or "" (unspecified) for updating the arc. This allows us
#to change the direction of the arc, or keep it as is.
self.allow_arc_duplication = allow_arc_duplication
def arc_is_free(self, arc, host):
if arc._from is not None and arc._to is not None and (arc._from not in host.nodes) and (arc._to not in host.nodes):
self.free_end_identifier=0
#if the nodes on either end of the freeArc are pointing to previous nodes
#that were deleted in the first pushout then neighborNode is null (and as
#a result any rules using the neighborNodeLabel will not apply) and the
#freeEndIdentifier is zero.
self.neighbor_node = None
return True
elif arc._from is not None and arc._from not in host.nodes:
self.free_end_identifier = -1
#freeEndIdentifier set to -1 means that the From end of the arc must be the free end.
self.neighbor_node = arc._to
return True
elif arc._to is not None and arc._to not in host.nodes:
self.free_end_identifier = +1
#freeEndIdentifier set to +1 means that the To end of the arc must be the free end.
self.neighbor_node = arc._from
return True
else:
#else, the arc is not a free arc after all and we simply break out
#of this loop and try the next arc.
self.free_end_identifier = 0
self.neighbor_node = None
return False
def find_new_node_to_connect(self, R, R_mapping):
#find R-L node that is to be connected with freeArc as well as old L-R node name
if self.R_node_name is not None and self.R_node_name is not "":
#take the RNodeName from within the rule and get the proper reference to the new node.
#If there is no RNodeName, then the embedding rule will set the reference to null.
index = R.find_index_of_node_with(name=self.R_node_name)
return R_mapping.nodes[index]
else: return None
def find_deleted_node(self, L, L_mapping):
#similarly, we can find the LNodeName (if one exists in this particular rule). Setting this
#up now saves time and space in the below recognition if-then's.
if self.L_node_name is not None and self.L_node_name is not "":
index = L.find_index_of_node_with(name=self.L_node_name)
return L_mapping.nodes[index]
else: return None
def rule_is_recognized(free_end_identifier, free_arc, neighbor_node, node_removed):
#this one is a little bit of enigmatic but clever coding if I do say so myself. Both
#of these variables can be either +1, 0, -1. If in multiplying the two together you
#get -1 then this is the only incompability. Combinations of +1&+1, or +1&0, or
#-1&-1 all mean that the arc has a free end on the requested side (From or To).
raise NotImplementedError, bryan_message
#########
#land of no implementations
#########
class SearchProcess:
def __init__(self):
pass
def run(self):
'''implements a random search'''
pass
def is_current_the_goal(self, m):
if m.f2 == 0.0: return True
return False
def transfer_L_mapping_to_child(self, child, current, L_mapping):
'''this is a subtle issue with recognize-choose-apply in a Tree Search.
The locations within each option are pointing to nodes and arcs within the current.graph,
but we would like to retain the current so we make a deep copy of it. This is fine but now
the locations need to be transfered to the child. That is why this function was created.'''
raise NotImplementedError, bryan_message_generator("GraphSynthSourceFiles/GraphSynth.Search/searchProcess.cs")
#delegate
for arc in L_mapping.arcs:
i = L_mapping.arcs.index(arc)
the_arc = find_delegate(current.arcs, arc)[0] #[0] because we want the first
position = current.arcs.index(the_arc)
L_mapping.arcs[i] = child.arcs[position]
for node in L_mapping.nodes:
i = L_mapping.nodes.index(node)
the_node = find_delegate(current.nodes, node)
position = current.nodes.index(the_node)[0]
L_mapping.nodes[i] = child.nodes[position]
def next_rule_set(self, rule_set_index, status):
'''A helper function to RecognizeChooseApplyCycle. This function returns what the new ruleSet
will be. Here the enumerator nextGenerationSteps and GenerationStatuses is used to great
affect. Understand that if a negative number is returned, the cycle will be stopped.'''
if self.rulesets[rule_set_index].nextGenerationStep[int(status)] == nextGenerationSteps.Loop:
return rule_set_index
elif self.rulesets[rule_set_index].nextGenerationStep[int(status)] == nextGenerationSteps.GoToNext:
return rule_set_index+1
elif self.rulesets[rule_set_index].nextGenerationStep[int(status)] == nextGenerationSteps.GoToPrevious:
return rule_set_index-1
else:
return int(self.rulesets[rule_set_index].nextGenerationStep[int(status)])
@staticmethod
def calculate_f0(f1, f2, average_time):
return ((20.0 * f1 / average_time) + f2)
def add_new_cand_to_pareto(self, candidate, pareto_cands):
for pc in pareto_cands:
if self.dominates(candidate, pc):
pareto_cands.remove(pc)
print "g: ", c.f1, ", h: ", c.f2
elif self.dominates(pc, c): return
pareto_cands.append(candidate)
return pareto_cands
@staticmethod
def add_child_to_sorted_cand_list(candidates, child):
if len(canddiates)==0: candidates.append(child)
else:
i = 0
f_child = child.f0
while i= candidates[i].f0:
i=i+1
canddiates.insert(i, child)
@staticmethod
def kill_off_clones(new_children):
last_rule_position = len(new_children[0].recipe)-1
raise NotImplementedError, bryan_message #line 104 in searchProcess.cs