Создание ребер DOT в pygraphviz из двоичного дерева - PullRequest
Новая
       67

Создание ребер DOT в pygraphviz из двоичного дерева

0 голосов
/ 14 июня 2019

Я создаю генетический алгоритм символьной регрессии, и у меня возникают проблемы с преобразованием его в DOT-совместимый формат.Каждое решение представлено в виде двоичной древовидной структуры со следующим классом: 

class Node:
    def __init__(self,val):
        self.left = None
        self.right = None
        self.data = val

В каждом узле есть либо операция ('mul' для умножения, 'add', 'sub' и т. Д.)или значение (либо статическое число, либо форма 'val', которая заменяется при оценке, в основном, как 'x' или 'y').

Я пытаюсь визуализировать решения после того, как они былигенерироваться.Мой текущий код может генерировать линейный формат дерева, но его довольно сложно прочитать.Мой код DOT генерирует каждый из узлов с уникальным идентификатором, но я не могу понять, как рекурсивно связать каждый из узлов.

Код 

def transcribe(root,DOT=False):
    temp = None
    if (DOT):
        temp = Graph(comment='Solution',format='svg')
        DOTForm(root,temp,0)
        return temp
    else:
        temp = []
        programForm(root,temp)
        return temp

def programForm (root,array):
    if root:
        array.append(root.data)
        programForm(root.left,array)
        programForm(root.right,array)

def DOTForm (root,dot,increment):
    if root:
        dot.node(str(increment),str(root.data))
        increment += 1
        increment = DOTForm(root.left,dot,increment)
        increment = DOTForm(root.right,dot,increment)
    return increment

Вывод: 

>>> print(transcribe(root)) # This works fine
['mul', 'mul', 5, 2, ['ifn', 'val'], 'mul', -10, 'val', 'mul', 10, 'val']

>>> print(transcribe(root,True)) # Nodes work okay
// Solution
graph {
    0 [label=mul]
    1 [label=mul]
    2 [label=5]
    3 [label=2]
    4 [label="['ifn', 'val']"]
    5 [label=mul]
    6 [label=-10]
    7 [label=val]
    8 [label=mul]
    9 [label=10]
    10 [label=val]
}

Ожидаемый вывод 

// Solution
graph {
    0 [label=mul]
    0 -- 1
    0 -- 4
    1 [label=mul]
    1 -- 2
    2 [label=5]
    1 -- 3
    3 [label=2]
    4 [label="['ifn', 'val']"]
    4 -- 5
    4 -- 8
    5 [label=mul]
    5 -- 6
    6 [label=-10]
    5 -- 7
    7 [label=val]
    8 [label=mul]
    8 -- 9
    9 [label=10]
    8 -- 10
    10 [label=val]
}

Я, честно говоря, не уверен, как это сделать.Я попробовал несколько комбинаций вышеупомянутой рекурсии, чтобы попытаться добавить рабочие края, но все они оказались короткими.Например:

Код 

def DOTForm (root,dot,increment):
    if root:
        dot.node(str(increment),str(root.data))
        parent = increment
        increment += 1
        increment = DOTForm(root.left,dot,increment)
        dot.edge(str(parent),str(increment))
        increment = DOTForm(root.right,dot,increment)
        dot.edge(str(parent),str(increment))
    return increment

Выход 

// Solution
graph {
    0 [label=mul]
    1 [label=mul]
    2 [label=5]
    2 -- 3
    2 -- 3
    1 -- 3
    3 [label=2]
    3 -- 4
    3 -- 4
    1 -- 4
    0 -- 4
    4 [label="['ifn', 'val']"]
    5 [label=mul]
    6 [label=-10]
    6 -- 7
    6 -- 7
    5 -- 7
    7 [label=val]
    7 -- 8
    7 -- 8
    5 -- 8
    4 -- 8
    8 [label=mul]
    9 [label=10]
    9 -- 10
    9 -- 10
    8 -- 10
    10 [label=val]
    10 -- 11
    10 -- 11
    8 -- 11
    4 -- 11
    0 -- 11
}

Я новичок в рекурсии, поэтому японятия не имею, как связать родителей и детей как таковые, когда идентификатор не обязательно является последовательным.Спасибо за любую помощь, которую вы можете предложить.

1 Ответ

0 голосов
/ 23 июня 2019

Для тех, кто ищет ответ, вот он.Я считаю, что моя проблема заключалась в том, что я не поддерживал согласованность родительского идентификатора, что приводило к повторным или отсутствующим идентификаторам.

Код: 

def DOTForm (root,dot,increment,parent):
    if root:
        temp = root.data # To avoid repeated memory calls
        if (isinstance(temp,list)): # This is just formatting for my data structure
            dot.node(str(increment),str(temp[0]+" "+str(temp[1])),shape="box")
        elif(isinstance(temp,str)):
            dot.node(str(increment),str(temp),shape="box")
        else:
            dot.node(str(increment),str(temp))
        del temp # Just so it doesn't interfere with following recursions
        parent = increment
        increment += 1
        if root.left:
            dot.edge(str(parent),str(increment))
        increment = DOTForm(root.left,dot,increment,parent)
        if root.right:
            dot.edge(str(parent),str(increment))
        increment = DOTForm(root.right,dot,increment,parent)
    return increment # Return the increased increment counter
...