draw_hierarchy() not always working for filtered graphs

Hi there. I spotted that the draw_hierarchy() for plotting states that are an output of state = minimise_nested_blockmodel_dl(G,...) doesn't always seem to work if G is a GraphView object.

I say "doesn't always" because I tried to make a minimal example for this using a network of one connected triangle and an isolated edge to try and get a minimal example but the error didn't reproduce.

An example that's roughly equivalent to what I'm doing (not sure if this is minimal but enough to throw the error) is:

import graph_tool.all as gt

# network science co-authorships
G = gt.collection.data['netscience']

# LCC a graphview object containing largest conn. comp.
LCC = gt.extract_largest_component(G)

state = gt.minimize_nested_blockmodel_dl(LCC)
gt.draw_hierarchy(state)

This throws the runtime error + stacktrace:

---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
/Users/naomiarnold/CODE/Raphtory/raphtory-research/wordsem/semeval/example.ipynb Cell 1' in <module>
      8 LCC = gt.extract_largest_component(LCC)
     10 state = gt.minimize_nested_blockmodel_dl(LCC)
---> 11 gt.draw_hierarchy(state)

File /opt/homebrew/lib/python3.9/site-packages/graph_tool/draw/cairo_draw.py:1850, in draw_hierarchy(state, pos, layout, beta, node_weight, vprops, eprops, hvprops, heprops, subsample_edges, rel_order, deg_size, vsize_scale, hsize_scale, hshortcuts, hide, bip_aspect, empty_branches, **kwargs)
   1846     hvvisible.fa = dist.fa >= hide
   1848 pos = g.own_property(tpos.copy())
-> 1850 cts = get_hierarchy_control_points(g, t, tpos, beta,
   1851                                    max_depth=len(state.levels) - hshortcuts)
   1853 vprops_orig = vprops
   1854 eprops_orig = eprops

File /opt/homebrew/lib/python3.9/site-packages/graph_tool/draw/cairo_draw.py:1480, in get_hierarchy_control_points(g, t, tpos, beta, cts, is_tree, max_depth)
   1478 tu = GraphView(tu, skip_vfilt=True)
   1479 tpos = tu.own_property(tpos)
-> 1480 libgraph_tool_draw.get_cts(u._Graph__graph,
   1481                            tu._Graph__graph,
   1482                            _prop("v", tu, tpos),
   1483                            _prop("e", u, beta),
   1484                            _prop("e", u, cts),
   1485                            is_tree, max_depth)
   1486 return cts

RuntimeError: Invalid hierarchical tree: No path from source to target.

To give as much info as possible, here are some other things I found with this example:

  • If I replace minimize_nested_blockmodel_dl() with minimize_blockmodel_dl(), no error is thrown.
  • If minimise_nested_blockmodel_dl() is run on G (unfiltered graph) instead of LCC (filtered graph), no error is thrown.

Graph-tool setup

I'm running graph-tool 2.44 installed via Homebrew, on Mac OS 12.0.1 Monterey. My Python version is 3.9.9.

By the way, I managed to find a workaround in my situation which was to just plot the whole graph not just the largest conn. comp since it didn't seem to make a difference visually, I just thought I'd document the issue here in case it's helpful. Many thanks!

Edited by Naomi Arnold