Can one get hierarchical graphs from networkx with python 3?

NickDanger66 picture NickDanger66 · Apr 12, 2015 · Viewed 28.6k times · Source

I am trying to display a tree graph of my class hierarchy using networkx. I have it all graphed correctly, and it displays fine. But as a circular graph with crossing edges, it is a pure hierarchy, and it seems I ought to be able to display it as a tree.

I have googled this extensively, and every solution offered involves using pygraphviz... but PyGraphviz does not work with Python 3 (documentation from the pygraphviz site).

Has anyone been able to get a tree graph display in Python 3?

Answer

Joel picture Joel · Apr 13, 2015

[scroll down a bit to see what kind of output the code produces]

edit (7 Nov 2019) I've put a more refined version of this into a package I've been writing: https://epidemicsonnetworks.readthedocs.io/en/latest/_modules/EoN/auxiliary.html#hierarchy_pos. The main difference between the code here and the version there is that the code here gives all children of a given node the same horizontal space, while the code following that link also considers how many descendants a node has when deciding how much space to allocate it.

edit (19 Jan 2019) I have updated the code to be more robust: It now works for directed and undirected graphs without any modification, no longer requires the user to specify the root, and it tests that the graph is a tree before it runs (without the test it would have infinite recursion - see user2479115's answer for a way to handle non-trees).

edit (27 Aug 2018) If you want to create a plot with the nodes appearing as rings around the root node, the code right at the bottom shows a simple modification to do this

edit (17 Sept 2017) I believe the trouble with pygraphviz that OP was having should be fixed by now. So pygraphviz is likely to be a better solution that what I've got below.


Here is a simple recursive program to define the positions. The recursion happens in _hierarchy_pos, which is called by hierarchy_pos. The main role of hierarcy_pos is to do a bit of testing to make sure the graph is appropriate before entering the recursion:

import networkx as nx
import random

    
def hierarchy_pos(G, root=None, width=1., vert_gap = 0.2, vert_loc = 0, xcenter = 0.5):

    '''
    From Joel's answer at https://stackoverflow.com/a/29597209/2966723.  
    Licensed under Creative Commons Attribution-Share Alike 
    
    If the graph is a tree this will return the positions to plot this in a 
    hierarchical layout.
    
    G: the graph (must be a tree)
    
    root: the root node of current branch 
    - if the tree is directed and this is not given, 
      the root will be found and used
    - if the tree is directed and this is given, then 
      the positions will be just for the descendants of this node.
    - if the tree is undirected and not given, 
      then a random choice will be used.
    
    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
    '''
    if not nx.is_tree(G):
        raise TypeError('cannot use hierarchy_pos on a graph that is not a tree')

    if root is None:
        if isinstance(G, nx.DiGraph):
            root = next(iter(nx.topological_sort(G)))  #allows back compatibility with nx version 1.11
        else:
            root = random.choice(list(G.nodes))

    def _hierarchy_pos(G, root, width=1., vert_gap = 0.2, vert_loc = 0, xcenter = 0.5, pos = None, parent = None):
        '''
        see hierarchy_pos docstring for most arguments

        pos: a dict saying where all nodes go if they have been assigned
        parent: parent of this branch. - only affects it if non-directed

        '''
    
        if pos is None:
            pos = {root:(xcenter,vert_loc)}
        else:
            pos[root] = (xcenter, vert_loc)
        children = list(G.neighbors(root))
        if not isinstance(G, nx.DiGraph) and parent is not None:
            children.remove(parent)  
        if len(children)!=0:
            dx = width/len(children) 
            nextx = xcenter - width/2 - dx/2
            for child in children:
                nextx += dx
                pos = _hierarchy_pos(G,child, width = dx, vert_gap = vert_gap, 
                                    vert_loc = vert_loc-vert_gap, xcenter=nextx,
                                    pos=pos, parent = root)
        return pos

            
    return _hierarchy_pos(G, root, width, vert_gap, vert_loc, xcenter)

and an example usage:

import matplotlib.pyplot as plt
import networkx as nx
G=nx.Graph()
G.add_edges_from([(1,2), (1,3), (1,4), (2,5), (2,6), (2,7), (3,8), (3,9), (4,10),
                  (5,11), (5,12), (6,13)])
pos = hierarchy_pos(G,1)    
nx.draw(G, pos=pos, with_labels=True)
plt.savefig('hierarchy.png')

enter image description here

Ideally this should rescale the horizontal separation based on how wide things will be beneath it. I'm not attempting that but this version does: https://epidemicsonnetworks.readthedocs.io/en/latest/_modules/EoN/auxiliary.html#hierarchy_pos

Radial expansion

Let's say you want the plot to look like:

enter image description here

Here's the code for that:

pos = hierarchy_pos(G, 0, width = 2*math.pi, xcenter=0)
new_pos = {u:(r*math.cos(theta),r*math.sin(theta)) for u, (theta, r) in pos.items()}
nx.draw(G, pos=new_pos, node_size = 50)
nx.draw_networkx_nodes(G, pos=new_pos, nodelist = [0], node_color = 'blue', node_size = 200)

edit - thanks to Deepak Saini for noting an error that used to appear in directed graphs