从二叉树在 pygraphviz 中创建 DOT 边

Question

我正在创建符号回归遗传算法，但无法将其转换为 DOT-compliant 格式。每个解决方案都表示为具有以下 class:

的二叉树结构

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

在每个节点，有一个操作（'mul' 乘法，'add'，'sub' 等）或一个值（静态数字或形式'val' 在评估时被替换，基本上像 'x' 或 'y').

我试图在生成解决方案后对其进行可视化。我当前的代码可以生成树的线性格式，但它很难阅读。我的 DOT 代码生成每个节点都有一个唯一的 ID，但我不知道如何递归地 link 每个节点。

代码

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
}

我是递归的新手，所以当 ID 不一定是连续的时，我不知道如何 link parents 和 children。感谢您提供的任何帮助。

Answer 1

任何寻找答案的人，都在这里。我相信我的问题是我没有保持父 ID 一致，这导致 ID 重复或丢失。

代码：

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

从二叉树在 pygraphviz 中创建 DOT 边

Creating DOT edges in pygraphviz from a binary tree

python

recursion

tree

dot

pygraphviz