python - 使用networkx打印python图时保留左右孩子

Question

我正在尝试使用 python 中的 networkx 库打印二叉树。

但是，我无法保护左右孩子。有没有办法告诉图表先打印左孩子，然后是右孩子？

import networkx as nx
G = nx.Graph()
G.add_edges_from([(10,20), (11,20)])
nx.draw_networkx(G)

</p>

编辑 1：在使用 pygraphwiz 时，它至少会产生一个有向图。所以，我对根节点有更好的了解。

下面是我正在使用的代码：

import pygraphviz as pgv
G = pgv.AGraph()
G.add_node('20')
G.add_node('10')
G.add_node('11')
G.add_edge('20','10')
G.add_edge('20','11')
G.add_edge('10','7')
G.add_edge('10','12')

G.layout()
G.draw('file1.png')
from IPython.display import Image
Image('file1.png')

但是，这仍然远非结构化格式。我将发布我接下来发现的内容。新图如下所示（至少我们知道根）：

编辑 2：对于那些遇到安装问题的人，请参阅这篇文章。 答案- 如果您想在 Windows 64 位上安装 pygraphviz，它非常有用。

Answer 1

我相信 Networkx 不适合二叉树，但您可以自己设置节点位置。我编写了以下算法来设置节点位置，但它适用于关键节点排序为 [0,1,...] 的完整或完整二叉树。

def full_tree_pos(G):
    n = G.number_of_nodes()
    if n == 0 : return {}
    # Set position of root
    pos = {0:(0.5,0.9)}
    if n == 1:
        return pos
    # Calculate height of tree
    i = 1
    while(True):
        if n >= 2**i and n<2**(i+1):
            height = i 
            break
        i+=1
    # compute positions for children in a breadth first manner
    p_key = 0
    p_y = 0.9
    p_x = 0.5
    l_child = True # To indicate the next child to be drawn is a left one, if false it is the right child
    for i in xrange(height):
        for j in xrange(2**(i+1)):
            if 2**(i+1)+j-1 < n:
                print 2**(i+1)+j-1
                if l_child == True:
                    pos[2**(i+1)+j-1] = (p_x - 0.2/(i*i+1) ,p_y - 0.1)
                    G.add_edge(2**(i+1)+j-1,p_key)
                    l_child = False
                else:
                    pos[2**(i+1)+j-1] = (p_x + 0.2/(i*i+1) ,p_y - 0.1)
                    l_child = True
                    G.add_edge(2**(i+1)+j-1,p_key)
                    p_key += 1
                    (p_x,p_y) = pos[p_key]

    return pos

G = nx.Graph()
G.add_nodes_from(xrange(25))
pos = full_tree_pos(G)
nx.draw(G, pos=pos, with_labels=True)
plt.show()

给出了下图。

Answer 2

注意如果您使用 networkx 1.11 或更早版本，请参阅末尾的注释。

以下假设每个节点都有一个分配给它的属性，告诉它是其父节点的左孩子还是右孩子。所以你必须分配这个 - 默认情况下，图表没有任何概念。也许有可能说服 networkx 的人们制作一类新的图，它是二叉树并自动存储这些信息，但目前还没有。我不知道是否有足够的兴趣来证明这一点。

import networkx as nx

def binary_tree_layout(G, root, width=1., vert_gap = 0.2, vert_loc = 0, xcenter = 0.5, 
                  pos = None, parent = None):
    '''If there is a cycle that is reachable from root, then this will see infinite recursion.
       G: the graph
       root: the root node of current branch
       width: horizontal space allocated for this branch - avoids overlap with other branches
       vert_gap: gap between levels of hierarchy
       vert_loc: vertical location of root
       xcenter: horizontal location of root
       pos: a dict saying where all nodes go if they have been assigned
       parent: parent of this branch.
       each node has an attribute "left: or "right"'''
    if pos == None:
        pos = {root:(xcenter,vert_loc)}
    else:
        pos[root] = (xcenter, vert_loc)
    neighbors = list(G.neighbors(root))
    if parent != None:
        neighbors.remove(parent)
    if len(neighbors)!=0:
        dx = width/2.
        leftx = xcenter - dx/2
        rightx = xcenter + dx/2
        for neighbor in neighbors:
            if G.nodes[neighbor]['child_status'] == 'left':
                pos = binary_tree_layout(G,neighbor, width = dx, vert_gap = vert_gap, 
                                    vert_loc = vert_loc-vert_gap, xcenter=leftx, pos=pos, 
                    parent = root)
            elif G.nodes[neighbor]['child_status'] == 'right':
                pos = binary_tree_layout(G,neighbor, width = dx, vert_gap = vert_gap, 
                                    vert_loc = vert_loc-vert_gap, xcenter=rightx, pos=pos, 
                    parent = root)
    return pos

这是一个示例调用，我将偶数节点设置为左子节点。

G= nx.Graph()
G.add_edges_from([(0,1),(0,2), (1,3), (1,4), (2,5), (2,6), (3,7)])
for node in G.nodes():
    if node%2==0:
        G.nodes[node]['child_status'] = 'left'  #assign even to be left
    else:
        G.nodes[node]['child_status'] = 'right' #and odd to be right
pos = binary_tree_layout(G,0)
nx.draw(G, pos=pos, with_labels = True)

---

编辑注释此答案的早期版本适用于 networkx 版本 1.11 及更早版本。如果需要，请打开编辑历史记录并使用此答案的第二个版本。