Search code examples
pythongraphvizgraph-visualization

Python graphviz: how to order nodes at the same depth of a rooted tree

I don't know how to enforce order on to nodes at the same depth in a rooted tree. It had been asked in this thread but not solved. The thing is, just like what that question's author has said, graphviz (at least graphviz's python library) fails to maintain the creation order.

For example:

g = Graph(format="png")
g.node("x", shape="doublecircle")
g.node("y", shape="circle")  # removed in graph 2
g.node("z", shape="circle")  # removed in graph 2
g.node("nil1", shape="none", label="NIL")
g.node("nil2", shape="none", label="NIL")
g.edge("x", "nil1")
g.edge("x", "y")
g.edge("y", "z")
g.edge("y", "nil2")

The code above produces this graph on my computer

Graph 1

as you can see y node and nil1 node swapped places but they shouldn't.

But after I removed line 3 and 4 from the code above, the output changed!

Graph 2

This is hilarious. I have no idea why removing two lines that define two nodes and their shapes can change the output. Even if the two lines did impact the output, the expected output is different from either of the two produced output anyway. Any idea what happened and what's wrong with my code?

Solution

  • On the same rank Graphviz draws the nodes in the order they were defined. In TB (top to bottom) layout nodes on the same rank are drawn in left-to-right order.

    In your situation, if you want nil1 node to appear before (to the left of) the y node — you have to define it before. Same with z and nil2.

    This should work:

    g = Graph(format="png")
g.node("x", shape="doublecircle")
g.node("nil1", shape="none", label="NIL")
g.node("y", shape="circle")  # removed in graph 2
g.node("nil2", shape="none", label="NIL")
g.node("z", shape="circle")  # removed in graph 2
g.edge("x", "nil1")
g.edge("x", "y")
g.edge("y", "z")
g.edge("y", "nil2")

    To clarify, here's a basic example.

    digraph name {
    rankdir=TB
    a b c d
}

    Here we've defined the nodes in alphabetic order, as the result we will get the same order on the graph:

    If we reverse the order:

    digraph name {
    rankdir=TB
    d c b a
}

    The order on the graph will be reversed too:

    To answer the question about why removing node definitions affect order. You can actually omit defining nodes if they don't need special attributes. In this case graphviz will implicitly add node definitions when it sees the edge statement with undefined nodes, e.g. this:

    digraph {
  a -> b
  c -> d
}

    Translates to this:

    digraph {
  a
  b
  a -> b
  c
  d
  c -> d
}

    So in your case removing the definitions of y and z from the beginning made them appear later, just before their edge definitions. Which implicitly put the nil1 and nil2 definitions on top of y and z. This has the same effect as the explicit solution I suggested at the beginning.