I want to recursevly generate a graph thath starts from (for example) [0,0,0] and generate his children: [1,0,0], [0,1,0] and [0,0,1]. Then theese children will become parents so we'll have (from [1,0,0]) -> [2,0,0], [1,1,0], [1,0,1] and so on until the i iteration.
The code that i've implemented, given the child generator function (that generate children) is this:
positions = numpy.array(list(range(k))) 1;
minimum_targets = [];
tau = list(numpy.zeros(len(p)-1));
ls1 = []
ls1.append(tau)
ls=[]
initial = 1
l = 0
i = 1
# Parte la prima iterazione e genera padre [0,0,0] e figli con le possibili permutazioni [1,0,0], [0,1,0], [0,0,1]
graph, root = child_generator_2(len(p), i, p ,a, tau)
temp = copy.copy(root)
temp_root = copy.copy(root)
i = 2
while i <= 5:
l = 0
# forse lo devi fare con i while perché ti serve un contatore:
while l < len(list(temp.children)):
graph, root = child_generator_2(len(p), i, p ,a, list(temp.children)[l].name)
temp.children[l].children = root.children
for elemento in list(temp.children[l].children):
graph,root = child_generator_2(len(p), i 1, p ,a, elemento.name)
elemento.children = root.children
l = l 1
temp = copy.copy(temp.children[l-1])
i = i 1;
can you please give me a simple code example (with this structure) to do this?
CodePudding user response：
I created a script to simulate your idea. However, I don't know wether you can repeat nodes in the graph or they must be unique. As you didn't specify it must be a tree, the problem becomes ambiguous.
In order to solve this problem, I've placed a flag that allows you to choose wether the nodes that will be generated should be unique or not.
If the nodes are not unique, whenever a new node is requested, it will be generated and inserted at the graph, even if it already exists inside the graph. This way, each node will contain only one parent at a time. This allows you to generate a tree structure.
If the nodes are unique, copies of them will not be inserted on the graph. This means that one node might have more than one parent at the same time. Just like this:
Here's the script I've made:
def pattern(node, index):
pat = []
for n in node:
pat.append(n)
pat[index] = 1
return tuple(pat)
def generate_graph(nodes, parent, node, depth, nodes_unique=False):
if (depth > 0):
nChildren = range(len(node))
if (nodes_unique):
found = False
for nd in nodes:
if (nd['Node'] == node['Node']):
found = True
print(node['Node'], [p['Node'] for p in node['Parent']])
node = nd
break
if (not found):
nodes.append(node)
else:
nodes.append(node)
if (parent is not None):
parent['Children'].append(node)
node['Parent'].append(parent)
for i in nChildren:
child = pattern(node['Node'], i)
generate_graph(nodes, node, {"Node": child, "Children": [], "Parent": []}, depth-1, nodes_unique)
return True
else:
return False
if __name__ == '__main__':
root = {"Parent": [], "Node": (0, 0, 0), "Children": []}
nodes = []
# Regarding the parameter: nodes_unique
#
# If nodes are not unique (False), all parents may contain a
# set of children, and each child will be linked to a single parent.
#
# --------------------------------------------------------
#
# If nodes are unique (True), repeated nodes will not be reiserted
# in the nodes list. This means that if a repeated node is requested,
# its reference from nodes list will be taken.
#
# As new instances of the same node will not be generated, nodes
# might come from different parents at the same time.
generate_graph(nodes, None, root, 3, True)
for nd in nodes:
par = ''
for p in nd['Parent']:
par = (str(p['Node']) ' ')
if (par == ''):
par = 'None'
print("Node: ", nd['Node'], " Parents: ", par)
print()
print('Graph Structure: ', root)
Output when nodes are not unique (single parenting):
Node: (0, 0, 0) Parents: None
Node: (1, 0, 0) Parents: (0, 0, 0)
Node: (2, 0, 0) Parents: (1, 0, 0)
Node: (1, 1, 0) Parents: (1, 0, 0)
Node: (1, 0, 1) Parents: (1, 0, 0)
Node: (0, 1, 0) Parents: (0, 0, 0)
Node: (1, 1, 0) Parents: (0, 1, 0)
Node: (0, 2, 0) Parents: (0, 1, 0)
Node: (0, 1, 1) Parents: (0, 1, 0)
Node: (0, 0, 1) Parents: (0, 0, 0)
Node: (1, 0, 1) Parents: (0, 0, 1)
Node: (0, 1, 1) Parents: (0, 0, 1)
Node: (0, 0, 2) Parents: (0, 0, 1)
Graph Structure: {'Parent': [], 'Node': (0, 0, 0), 'Children': [{'Node': (1, 0, 0), 'Children': [{'Node': (2, 0, 0), 'Children': [], 'Parent': [{...}]}, {'Node': (1, 1, 0), 'Children': [], 'Parent': [{...}]}, {'Node': (1, 0, 1), 'Children': [], 'Parent': [{...}]}], 'Parent': [{...}]}, {'Node': (0, 1, 0), 'Children': [{'Node': (1, 1, 0), 'Children': [], 'Parent': [{...}]}, {'Node': (0, 2, 0), 'Children': [], 'Parent': [{...}]}, {'Node': (0, 1, 1), 'Children': [], 'Parent': [{...}]}], 'Parent': [{...}]}, {'Node': (0, 0, 1), 'Children': [{'Node': (1, 0, 1), 'Children': [], 'Parent': [{...}]}, {'Node': (0, 1, 1), 'Children': [], 'Parent': [{...}]}, {'Node': (0, 0, 2), 'Children': [], 'Parent': [{...}]}], 'Parent': [{...}]}]}
Output when the nodes are unique (multi parenting):
(1, 1, 0) []
(1, 0, 1) []
(0, 1, 1) []
Node: (0, 0, 0) Parents: None
Node: (1, 0, 0) Parents: (0, 0, 0)
Node: (2, 0, 0) Parents: (1, 0, 0)
Node: (1, 1, 0) Parents: (1, 0, 0) (0, 1, 0)
Node: (1, 0, 1) Parents: (1, 0, 0) (0, 0, 1)
Node: (0, 1, 0) Parents: (0, 0, 0)
Node: (0, 2, 0) Parents: (0, 1, 0)
Node: (0, 1, 1) Parents: (0, 1, 0) (0, 0, 1)
Node: (0, 0, 1) Parents: (0, 0, 0)
Node: (0, 0, 2) Parents: (0, 0, 1)
Graph Structure: {'Parent': [], 'Node': (0, 0, 0), 'Children': [{'Node': (1, 0, 0), 'Children': [{'Node': (2, 0, 0), 'Children': [], 'Parent': [{...}]}, {'Node': (1, 1, 0), 'Children': [], 'Parent': [{...}, {'Node': (0, 1, 0), 'Children': [{...}, {'Node': (0, 2, 0), 'Children': [], 'Parent': [{...}]}, {'Node': (0, 1, 1), 'Children': [], 'Parent': [{...}, {'Node': (0, 0, 1), 'Children': [{'Node': (1, 0, 1), 'Children': [], 'Parent': [{...}, {...}]}, {...}, {'Node': (0, 0, 2), 'Children': [], 'Parent': [{...}]}], 'Parent': [{...}]}]}], 'Parent': [{...}]}]}, {'Node': (1, 0, 1), 'Children': [], 'Parent': [{...}, {'Node': (0, 0, 1), 'Children': [{...}, {'Node': (0, 1, 1), 'Children': [], 'Parent': [{'Node': (0, 1, 0), 'Children': [{'Node': (1, 1, 0), 'Children': [], 'Parent': [{...}, {...}]}, {'Node': (0, 2, 0), 'Children': [], 'Parent': [{...}]}, {...}], 'Parent': [{...}]}, {...}]}, {'Node': (0, 0, 2), 'Children': [], 'Parent': [{...}]}], 'Parent': [{...}]}]}], 'Parent': [{...}]}, {'Node': (0, 1, 0), 'Children': [{'Node': (1, 1, 0), 'Children': [], 'Parent': [{'Node': (1, 0, 0), 'Children': [{'Node': (2, 0, 0), 'Children': [], 'Parent': [{...}]}, {...}, {'Node': (1, 0, 1), 'Children': [], 'Parent': [{...}, {'Node': (0, 0, 1), 'Children': [{...}, {'Node': (0, 1, 1), 'Children': [], 'Parent': [{...}, {...}]}, {'Node': (0, 0, 2), 'Children': [], 'Parent': [{...}]}], 'Parent': [{...}]}]}], 'Parent': [{...}]}, {...}]}, {'Node': (0, 2, 0), 'Children': [], 'Parent': [{...}]}, {'Node': (0, 1, 1), 'Children': [], 'Parent': [{...}, {'Node': (0, 0, 1), 'Children': [{'Node': (1, 0, 1), 'Children': [], 'Parent': [{'Node': (1, 0, 0), 'Children': [{'Node': (2, 0, 0), 'Children': [], 'Parent': [{...}]}, {'Node': (1, 1, 0), 'Children': [], 'Parent': [{...}, {...}]}, {...}], 'Parent': [{...}]}, {...}]}, {...}, {'Node': (0, 0, 2), 'Children': [], 'Parent': [{...}]}], 'Parent': [{...}]}]}], 'Parent': [{...}]}, {'Node': (0, 0, 1), 'Children': [{'Node': (1, 0, 1), 'Children': [], 'Parent': [{'Node': (1, 0, 0), 'Children': [{'Node': (2, 0, 0), 'Children': [], 'Parent': [{...}]}, {'Node': (1, 1, 0), 'Children': [], 'Parent': [{...}, {'Node': (0, 1, 0), 'Children': [{...}, {'Node': (0, 2, 0), 'Children': [], 'Parent': [{...}]}, {'Node': (0, 1, 1), 'Children': [], 'Parent': [{...}, {...}]}], 'Parent': [{...}]}]}, {...}], 'Parent': [{...}]}, {...}]}, {'Node': (0, 1, 1), 'Children': [], 'Parent': [{'Node': (0, 1, 0), 'Children': [{'Node': (1, 1, 0), 'Children': [], 'Parent': [{'Node': (1, 0, 0), 'Children': [{'Node': (2, 0, 0), 'Children': [], 'Parent': [{...}]}, {...}, {'Node': (1, 0, 1), 'Children': [], 'Parent': [{...}, {...}]}], 'Parent': [{...}]}, {...}]}, {'Node': (0, 2, 0), 'Children': [], 'Parent': [{...}]}, {...}], 'Parent': [{...}]}, {...}]}, {'Node': (0, 0, 2), 'Children': [], 'Parent': [{...}]}], 'Parent': [{...}]}]}
I made these images on GIMP using the output of each execution. That's what each console print is telling you.