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

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

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:

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

Answer 2

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