Load a tree from file

Question

Load a tree from file

Navigation

#1 by (2 votes)

2

I have a tree with the following structure:

Which I have stored in a file, with the following content:

1 - 2 3 4 * 2 - 5 6 7 * 5 - 11 12 13 14 * 11 - * 12 - * 13 - * 14 - * 6 - * 7 - * 3 - * 4 - 8 9 10 * 8 - 15 16 * 15 - * 16 - * 9 - * 10 - *

The structure is as follows:

" * ": separates "node families" that is, composite structures of a parent and their children.
" - * ": indicates that a node has no children.
" - ": indicates the children of a node.

Next I specify its implementation in Python:

class node(object):
    def __init__(self, data):
        self.data = data
        self.children = []

    def add_child(self, obj):
        self.children.append(obj)

And the code to generate the tree presented:

#A continuación defino todos los nodos
a = node(1)
b = node(2)
c = node(3)
d = node(4)
e = node(5)
f = node(6)
g = node(7)
h = node(8)
i = node(9)
j = node(10)
k = node(11)
l = node(12)
ll = node(13)
m = node(14)
n = node(15)
o = node(16)
# A continuación defino las relaciones de parentesco
a.add_child(b)
a.add_child(c)
a.add_child(d)
b.add_child(e)
b.add_child(f)
b.add_child(g)
d.add_child(h)
d.add_child(i)
d.add_child(j)
h.add_child(n)
h.add_child(o)
e.add_child(k)
e.add_child(l)
e.add_child(ll)
e.add_child(m)

I have functions that run through the tree implemented in python and I save it in a file in the format indicated at the beginning of this post. But now, what I want to do is load it from that format into a program, and for that I have to use the code of the node class presented above. Next I write the code that I am developing:

#1. Genero todos los nodos
#1.2 Reduzco la cadena a elementos que no se repitan
cadena2 = list(set(cadena.split()))
#print(cadena2)
#1.3 Elimino de la cadena los símbolos '*' y '-'
cadena2.remove("*")
cadena2.remove("-")
#print(cadena2)
#1.4 Genero todos los nodos
listanodos = []
i = 0
while i < len(cadena2):
    listanodos = listanodos + [node(cadena2[i])]
    i = i + 1
#2 Vinculo los nodos hijos a los padres
# ¿Cómo lo hago?

Since I can generate the nodes, keeping them in a list, now I just need to create kinship relationships between them, I guess you have to go through cadena for it.

python

asked by Mr. Baldan 22.01.2018 в 08:19

source

1 answer

how can I retrieve values from an EditTextPreference? Can you define the name of a structure with a variable?

score 2 · Answer 1

As you tried, str.split is a simple way to do what you want (regular expressions could be another option). However, you must first separate each node (parent-child pair) by split('*') , then iterate over each node to separate the father of the children by split ('-') and finally use split(' ') on children .

Using a dictionary to store each identifier of the node (1, 2, 3, 4, etc) with the corresponding instance of the class can be a simple way to solve the problem:

cad = ('1 - 2 3 4 * 2 - 5 6 7 * 5 - 11 12 13 14 * 11 - * '
       '12 - * 13 - * 14 - * 6 - * 7 - * 3 - * 4 - 8 9 10 * '
       '8 - 15 16 * 15 - * 16 - * 9 - * 10 - *')

class Node(object):
    def __init__(self, data):
        self.data = data
        self.children = []

    def add_child(self, obj):
        self.children.append(obj)


nodes = [n.split('-') for n in cad.split('*')][:-1]
nodes = {int(parent): [int(child) for child in children.split()]
                                      for parent, children in nodes}
nodes_instances = {n: Node(n) for n in nodes}

for parent, children in nodes.items():
    for child in children:
        nodes_instances[parent].add_child(nodes_instances[child])

listanodos = nodes_instances.values()

The key is in:

nodes = {int(parent): [int(child) for child in children.split()]
                                      for parent, children in nodes}

This returns to us a dictionary in which each key is the identifier of a node and the value a list with the identifiers of its children. In this example, it returns us:

{1: [2, 3, 4], 2: [5, 6, 7], 5: [11, 12, 13, 14], 11: [], 12: [],13: [], 14: [],
 6: [], 7: [], 3: [], 4: [8, 9, 10], 8: [15, 16],15: [], 16: [], 9: [], 10: []}

Now we can use the dictionary keys to instantiate each node and store it in another dictionary:

nodes_instances = {n: Node(n) for n in nodes}

to later be able to add each instance of the child nodes to the instances of their respective parents in for .

The output is a list with the instantiated nodes just like you originally did:

>>> for n in listanodos:
>>>    print('{:<2} ---> {}'.format(n.data,
           (', '.join(str(c.data) for c in n.children) if n.children else None)))

1  ---> 2, 3, 4
2  ---> 5, 6, 7
5  ---> 11, 12, 13, 14
11 ---> None
12 ---> None
13 ---> None
14 ---> None
6  ---> None
7  ---> None
3  ---> None
4  ---> 8, 9, 10
8  ---> 15, 16
15 ---> None
16 ---> None
9  ---> None
10 ---> None

Note: I have renamed class nodo so that it starts with a capital letter according to the conventions and PEP-8.