preserving the left and right child while printing python graphs using networkx

Question

I am trying to print the binary tree using networkx library in python.

But, I am unable to preserve the left and right childs. Is there a way to tell the Graph to print left child first and then the right child?

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



EDIT 1: On using the pygraphwiz, it results in a directed graph atleast. So, I have better picture of the root node.

Below is the code I am using:

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')

But, this is still far from a structured format. I will post on what I find out next. The new graph looks like below (atleast we know the root):

EDIT 2: For those who are facing issues with installation, please refer to this post. The answer to this - its very helpful if you want to install pygraphviz on windows 64 bit.

Answer 1

I believe Networkx is not suited to binary trees but you can set the node positions yourself. I have wrote the following algorithm to setup node positions but it works fine for full or complete binary trees where key nodes are ordered [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()

which gave the following graph.

Answer 2

Note If you use networkx version 1.11 or earlier, see the note at the end.

The following assumes that each node has an attribute assigned to it telling whether it is the left or right child of its parent. So you'll have to assign this - by default a graph does not have any concept of this. Perhaps it might be possible to convince the networkx people to make a new class of graph which is a binary tree and stores this information automatically, but at present, it's not there. I don't know whether there would be enough interest to justify this.

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

Here is a sample call where I made even nodes into left children.

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)

---

edit notes An earlier version of this answer worked for networkx version 1.11 and earlier. If you need it, please open the edit history and use the 2nd version of this answer.