Can one get hierarchical graphs from networkx with python 3?

Question

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 1

Here is a solution for large trees. It is a modification of Joel's recursive approach that evenly spaces nodes at each level.

def hierarchy_pos(G, root, levels=None, width=1., height=1.):
    '''If there is a cycle that is reachable from root, then this will see infinite recursion.
       G: the graph
       root: the root node
       levels: a dictionary
               key: level number (starting from 0)
               value: number of nodes in this level
       width: horizontal space allocated for drawing
       height: vertical space allocated for drawing'''
    TOTAL = "total"
    CURRENT = "current"
    def make_levels(levels, node=root, currentLevel=0, parent=None):
        """Compute the number of nodes for each level
        """
        if not currentLevel in levels:
            levels[currentLevel] = {TOTAL : 0, CURRENT : 0}
        levels[currentLevel][TOTAL] += 1
        neighbors = G.neighbors(node)
        for neighbor in neighbors:
            if not neighbor == parent:
                levels =  make_levels(levels, neighbor, currentLevel + 1, node)
        return levels

    def make_pos(pos, node=root, currentLevel=0, parent=None, vert_loc=0):
        dx = 1/levels[currentLevel][TOTAL]
        left = dx/2
        pos[node] = ((left + dx*levels[currentLevel][CURRENT])*width, vert_loc)
        levels[currentLevel][CURRENT] += 1
        neighbors = G.neighbors(node)
        for neighbor in neighbors:
            if not neighbor == parent:
                pos = make_pos(pos, neighbor, currentLevel + 1, node, vert_loc-vert_gap)
        return pos
    if levels is None:
        levels = make_levels({})
    else:
        levels = {l:{TOTAL: levels[l], CURRENT:0} for l in levels}
    vert_gap = height / (max([l for l in levels])+1)
    return make_pos({})

Joel's example will look like this:

And this is a more complex graph (rendered using plotly):

Answer 2

The simplest way to get a nice-looking tree graph display in Python 2 or 3 without PyGraphviz is to use PyDot (https://pypi.python.org/pypi/pydot). Whereas PyGraphviz provides an interface to the whole of Graphviz, PyDot only provides an interface to Graphviz's Dot tool, which is the only one you need if what you're after is a hierarchical graph / a tree. If you want to create your graph in NetworkX rather than PyDot, you can use NetworkX to export a PyDot graph, as in the following:

import networkx as nx

g=nx.DiGraph()
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)])
p=nx.drawing.nx_pydot.to_pydot(g)
p.write_png('example.png')

Note that Graphviz and PyDot need to be installed for the above to work correctly.

Warning: I have experienced problems when using PyDot to draw graphs with node attribute dictionaries exported from NetworkX - sometimes the dictionaries seem to be exported with quotation marks missing from strings, which causes the write method to crash. This can be avoided by leaving out the dictionaries.

Answer 3

I modified slightly so that it would not infinitely recurse.

import networkx as nx

def hierarchy_pos(G, root, width=1., vert_gap = 0.2, vert_loc = 0, xcenter = 0.5 ):
    '''If there is a cycle that is reachable from root, then result will not be a hierarchy.

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

    def h_recur(G, root, width=1., vert_gap = 0.2, vert_loc = 0, xcenter = 0.5, 
                  pos = None, parent = None, parsed = [] ):
        if(root not in parsed):
            parsed.append(root)
            if pos == None:
                pos = {root:(xcenter,vert_loc)}
            else:
                pos[root] = (xcenter, vert_loc)
            neighbors = G.neighbors(root)
            if parent != None:
                neighbors.remove(parent)
            if len(neighbors)!=0:
                dx = width/len(neighbors) 
                nextx = xcenter - width/2 - dx/2
                for neighbor in neighbors:
                    nextx += dx
                    pos = h_recur(G,neighbor, width = dx, vert_gap = vert_gap, 
                                        vert_loc = vert_loc-vert_gap, xcenter=nextx, pos=pos, 
                                        parent = root, parsed = parsed)
        return pos

    return h_recur(G, root, width=1., vert_gap = 0.2, vert_loc = 0, xcenter = 0.5)

Answer 4

I used grandalf for a python-only solution that uses neither graphviz nor pygraphviz.

Also, this type of visualization is called a layered graph drawing or Sugiyama-style graph drawing, which can display many kinds of graphs, including non-trees.

import grandalf as grand
from grandalf.layouts import SugiyamaLayout


G = nx.DiGraph() # Build your networkx graph here


g = grandalf.utils.convert_nextworkx_graph_to_grandalf(G) # undocumented function

class defaultview(object):
    w, h = 10, 10
for v in V: v.view = defaultview()

sug = SugiyamaLayout(g.C[0])
sug.init_all() # roots=[V[0]])
sug.draw() # This is a bit of a misnomer, as grandalf doesn't actually come with any visualization methods. This method instead calculates positions

poses = {v.data: (v.view.xy[0], v.view.xy[1]) for v in g.C[0].sV} # Extracts the positions
nx.draw(G, pos=poses, with_labels=True)
import matplotlib.pyplot as plt
plt.show()

Answer 5

For a directed graph, Since neighbors(x) include only the succesors(x), so you have to remove the lines:

if parent != None:
        neighbors.remove(parent)

Also, a better option would be this:

pos=nx.graphviz_layout(G,prog='dot')

Answer 6

Very simple hacky topology-based heirachical plot. Only works with DiGraphs. Offsetting is helpful if you have long labels:

def topo_pos(G):
    """Display in topological order, with simple offsetting for legibility"""
    pos_dict = {}
    for i, node_list in enumerate(nx.topological_generations(G)):
        x_offset = len(node_list) / 2
        y_offset = 0.1
        for j, name in enumerate(node_list):
            pos_dict[name] = (j - x_offset, -i + j * y_offset)

    return pos_dict

# Same example data as top answer, but directed
G=nx.DiGraph()
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 = topo_pos(G)

nx.draw(G, pos)
nx.draw_networkx_labels(G, pos, horizontalalignment="left")