Creating heirarchical graphs w/clusters

[emazurek]

I’m trying to create a network graph that needs to be hierarchical. The thingxa and thingxb are two seperate nodes but need to be joined side by side. There are 3 levels as shown. There might be up to 20 or so thing groups. I am using neato with the heirarchical layout and it doesn’t join the thingxa and b together and there aren’t the 3 distinct levels like I would like to have. Steve Roush asked for a larger example so here is one.

I had to start this new topic since it wouldn’t let me reply (more than 3 times?) to the previous one.

Thanks in advance!

Ed Mazurek

[jjlong]

Ed,

You can achieve the look you desire by using the osage layout.

The osage layout algorithm is designed for large undirected graphed with multiple subgraphs. It separates the graph into “levels” (clusters) and lays out each level in a rectangle. The rectangles are then packed together. Within each rectangle, the subgraph/cluster is laid out.

It is not as simple as a dot layout. You will need to have knowledge of the desired output, and place attributes to control the number of elements (clusters or nodes) in a array row, the sort order, and margin spacing.

Here is an example of the sample you provided rendered with osage.

graph {
    layout=osage;

    // Set default node shape as a fixed size rectange with blue filled background
    node[ shape=rect style=filled fontname=helvetica fontsize=10 height=0.5 width=1.0 fixedsize=true fillcolor=deepskyblue ];

    // This is the outermost cluster. packmode=array_u1 says clusters will be in a 1 
    // column array, using the sortv attribute to specify the order of nested clusters
    subgraph "cluster_1" {  color=invis pack=18 packmode=array_u1

        // Row 1
        subgraph "cluster_2" {  color=invis sortv=1 packmode=array_u2  sortv=100
            a [ sortv=1 label="Thing A" ];
            b [ sortv=2 label="Thing B" ];
        }

        // Row 2
        subgraph "cluster_3" {  color=invis pack=18 packmode=array_u3 sortv=200

            // First dashed cluster for Thing 1a, Thing 1b
            subgraph "cluster_4" {  color=black pack= 16 style=dashed sortv=10

                // Cluster the 2 nodes without a margin
                subgraph "cluster_5" {  color=invis pack=0 packmode=array_u2
                    thing1a [ sortv=1 label="Thing 1a" ];
                    thing1b [ sortv=2 label="Thing 1b" ];
                }
            }

            // Second dashed cluster for Thing 2a, Thing 2b
            subgraph "cluster_6" {  color=black pack=18 style=dashed sortv=20

                // Cluster the two nodes without a margin
                subgraph "cluster_7" {  color=invis pack=0 packmode=array_u2
                    thing2a [ sortv=1 label="Thing 2a" ];
                    thing2b [ sortv=2 label="Thing 2b" ];
                }
            }

            // Third dashed cluster for Thing 3a, Thing 3b
            subgraph "cluster_8" {  color=black pack=18 style=dashed sortv=30

                // Cluster the two nodes without a margin
                subgraph "cluster_9" {  color=invis pack=0 packmode=array_u2
                    thing3a [ sortv=1 label="Thing 3a" ];
                    thing3b [ sortv=2 label="Thing 3b" ];
                }
            }
        }

        // Row 3
        subgraph "cluster_10" {  color=invis pack=18 sortv=300 packmode=array_u3
            thing1c [ sortv=1 label="Thing 1c" ];
            thing2c [ sortv=2 label="Thing 2c" ];
            thing3c [ sortv=3 label="Thing 3c" ];
        }
    }
    a:s -- thing1a:n;
    a:s -- thing2a:n;
    a:s -- thing3a:n;
    b:s -- thing1b:n;
    b:s -- thing2b:n;
    b:s -- thing3b:n;
    thing1a:s -- thing1c;
    thing1b:s -- thing1c;
    thing2a:s -- thing2c;
    thing2b:s -- thing2c;
    thing3a:s -- thing3c;
    thing3b:s -- thing3c;
}

In the graph above I used invisible colors on clusters which made up array rows. Here is the same graph with the borders drawn in gray to help you see how the clusters are really laid out.

The key attributes are:

1. pack - If pack has an integral value, this is used as the size, in points, of a margin around each part; otherwise, a default margin of 8 is used. There are 72 points to 1 inch, so where you see I have specified pack=18 I am assigning a 1/4" margin around the array row. I also use pack=0 to pull the 2 nodes tightly against each other.

2. packmode - This attribute indicates how connected components should be packed. Values such as packmode=array_u3 indicates that the components which follow should be packed into an array of graphs. By default, the components are in row-major order; the integer suffix specifies the number of columns for row-major.
   
   Thus, the mode array_u3 indicates array packing, with 3 columns going from left to right. Once 3 elements are fulfilled, another row begins. This layout repeats until all components are used.
   
   The flags also contain the letter u. This setting causes the insertion order of elements in the array to be determined by user-supplied values using the sortv attribute.

3. sortv - Each component can specify its sort value by a non-negative integer using the sortv attribute. Components are inserted in order, starting with the one with the smallest sort value. If no sort value is specified, zero is used.

The thing to remember about sortv is that the value you assign to it is interpreted by the packmode setting of the cluster which precedes it.

I used sortv values of:

• 100, 200, 300 for the 3 main rows
• 10, 20, 30 for the dashed clusters
• 1, 2, 3 for individual nodes within a cluster,

In the following code there are 2 placements occuring. The cluster for the row is being placed in the 3rd position, and at the same time defining packmode=array_u3 saying to place what follows inside the cluster with 3 columns per row. In this case nodes follow for Thing 1c, Thing 2c, and Thing 3c with assigned sortv values of 1, 2, 3.

        // Row 3
        subgraph "cluster_10" {  color=invis pack=18 sortv=300 packmode=array_u3
            thing1c [ sortv=1 label="Thing 1c" ];
            thing2c [ sortv=2 label="Thing 2c" ];
            thing3c [ sortv=3 label="Thing 3c" ];
        }

I hope this helps. osage is not the easiest thing to understand at first, but I’ve found this layout to come in very handy in specialized uses such as creating heat maps, and taxonomy diagrams where there is an implicit grid.

Best regards,
Jeff

[emazurek]

Wow thank you Jeff!

I’m using pygraphviz and it’s funny osage even mentioned. I do see some reference to it being supported but in the doc I normally use it’s not there.

AGraph Class — PyGraphviz 1.14 documentation

Let me try and map what you gave to the python stuff I’m doing and change to G.layout(prog=‘osage’) and see what I can do.

Thanks again!

Ed

[emazurek]

Hi,

I started playing with this using pygraphviz and add_subgraph. Something like this but it doesn’t seem to do anything. It doesn’t generate an error or anything just doesn’t seem to do anything.

Here’s my code snip:

“”"
G=pgv.AGraph(strict=False, size=1000)
G.add_node(‘A’, label=‘A’, shape=‘box’) # adds node ‘A’
G.add_node(‘B’, label=‘B’, shape=‘box’) # adds node ‘B’’
G.add_subgraph(name=‘cluster_1’, nbunch=[‘A’,‘B’], packmode=‘array_u2’, sortv=100, rank=‘source’)

G.add_node('Thing 1A', label='Thing 1A', shape='box') # adds node 'Thing 1A'
G.add_node('Thing 1B', label='Thing 1B', shape='box') # adds node 'Thing 1B'
G.add_subgraph(name='cluster_2', nbunch=['Thing 1A','Thing 1B'], packmode='array_u3', sortv=200)

G.add_edge('A', 'Thing 1A')
G.add_edge('B', 'Thing 1B')

Here’s what it looks like using osage:

Any help is appreciated!

Thanks, Ed

[emazurek]

If I change to dot I get really close. I added the other nodes/clusters:

G=pgv.AGraph(strict=False, size=1000)
G.add_node('A', label='A', shape='box') # adds node 'A'
G.add_node('B', label='B', shape='box') # adds node 'B''

G.add_node('Thing 1A', label='Thing 1A', shape='box', sortv=1) # adds node 'Thing 1A'
G.add_node('Thing 1B', label='Thing 1B', shape='box', sortv=2) # adds node 'Thing 1B'
G.add_subgraph(name='cluster_2', nbunch=['Thing 1A','Thing 1B'], packmode='array_u3', sortv=200, style='dashed')

G.add_edge('A', 'Thing 1A')
G.add_edge('B', 'Thing 1B')

G.add_node('Thing 1C', label='Thing 1C', shape='box') # adds node 'Thing 1C'
G.add_edge('Thing 1A', 'Thing 1C')
G.add_edge('Thing 1B', 'Thing 1C')

G.add_node('Thing 2A', label='Thing 2A', shape='box', sortv=1) # adds node 'Thing 2A'
G.add_node('Thing 2B', label='Thing 2B', shape='box', sortv=2) # adds node 'Thing 2B'
G.add_subgraph(name='cluster_3', nbunch=['Thing 2A','Thing 2B'], packmode='array_u3', sortv=200, style='dashed')

G.add_edge('A', 'Thing 2A')
G.add_edge('B', 'Thing 2B')

G.add_node('Thing 2C', label='Thing 2C', shape='box') # adds node 'Thing 1C'
G.add_edge('Thing 2A', 'Thing 2C')
G.add_edge('Thing 2B', 'Thing 2C')

G.add_node('Thing 3A', label='Thing 3A', shape='box', sortv=1) # adds node 'Thing 2A'
G.add_node('Thing 3B', label='Thing 3B', shape='box', sortv=2) # adds node 'Thing 2B'
G.add_subgraph(name='cluster_4', nbunch=['Thing 3A','Thing 3B'], packmode='array_u3', sortv=200, style='dashed')

G.add_edge('A', 'Thing 3A')
G.add_edge('B', 'Thing 3B')

G.add_node('Thing 3C', label='Thing 3C', shape='box') # adds node 'Thing 1C'
G.add_edge('Thing 3A', 'Thing 3C')
G.add_edge('Thing 3B', 'Thing 3C')

#G.layout()
G.layout(prog='dot')

It looks good except for the middle row isn’t in the correct order left to right:

Thanks!

Ed

[steveroush]

dot seems to have an ordering bug if clusters are involved.
The order should be corrected if:

• you add ordering=out attribute to node A or B
• you add invisible edges from Thing1A->Thing1B->Thing2A…

But, I won’t hold my breath

Order will (90% sure) be correct if you use the HTML label suggestion in the previous question instead of clusters.

The osage solution does work well, but I am an old dog & it is a challenging new trick - for me.

Note that the 3-layer layout gets awkward as it approaches 20 Thing2

Here are 20 (layout needs work, but quite wide & full of edges)

Here are 20, but split above & below:

Both were done with osage (but need work)

[jjlong]

Ed,

I believe 2 things are going on here.

1. You have not specified pack=18 as an attribute to get a 1/4 inch margin around your subclusters or nodes.
2. You are missing an overall cluster which surrounds the graph with the specification packmode=array_u1 to force all nested clusters into one stacked column.

Back to my previous example, lets look at the hierarchy of clusters in the diagram. I’ve erased the nodes and edges, and made annotations using MS Paint.

This should help you understand the packmode and sortv settings at each level.

I know you are using a Python package to build the graph. I don’t know Python, but I can understand what is going on in your code. You are building an object tree, emitting dot source, then pumping the dot source through Graphviz.

You need to make your calls in such a way that you add nodes to clusters, and add clusters to clusters.

The tree that corresponds to the structure in the picture above would look like this:

Translating the tree to code, write the code from the bottom of the tree to the top. I’m speculating that the code will look something like this (no guarantees that this works).

G.add_node('node_thing1a', label='Thing 1A', shape='box', sortv=1)
G.add_node('node_thing1b', label='Thing 1B', shape='box', sortv=2) 
G.add_subgraph(name='cluster_nomargin1', nbunch=['node_thing1a','node_thing1b'], packmode='array_u2', pack=0)

G.add_node('node_thing2a', label='Thing 2A', shape='box', sortv=1)
G.add_node('node_thing2b', label='Thing 2B', shape='box', sortv=2) 
G.add_subgraph(name='cluster_nomargin2', nbunch=['node_thing2a','node_thing2b'], packmode='array_u2', pack=0)

G.add_node('node_thing3a', label='Thing 3A', shape='box', sortv=1)
G.add_node('node_thing3b', label='Thing 3B', shape='box', sortv=2) 
G.add_subgraph(name='cluster_nomargin3', nbunch=['node_thing3a','node_thing3b'], packmode='array_u2', pack=0)

G.add_subgraph(name='cluster_dashed1', nbunch=['cluster_nomargin1'], style='dashed', sortv=10)
G.add_subgraph(name='cluster_dashed2', nbunch=['cluster_nomargin2'], style='dashed', sortv=20)
G.add_subgraph(name='cluster_dashed3', nbunch=['cluster_nomargin3'], style='dashed', sortv=30)

G.add_node('node_thinga', label='Thing A', shape='box', sortv=1)
G.add_node('node_thingb', label='Thing B', shape='box', sortv=2) 
G.add_subgraph(name='cluster_row1', nbunch=['node_thinga,node_thingb'],  packmode='array_u', sortv=100)

G.add_subgraph(name='cluster_row2', nbunch=['cluster_nomargin1,cluster_nomargin2,cluster_nomargin3'], packmode='array_u3', sortv=200)

G.add_node('node_thing1c', label='Thing 1C', shape='box', sortv=1)
G.add_node('node_thing2c', label='Thing 2C', shape='box', sortv=2) 
G.add_node('node_thing3c', label='Thing 3C', shape='box', sortv=3) 
G.add_subgraph(name='cluster_row3', nbunch=['node_thing1c,node_thing2c,node_thing3c'],  packmode='array_u3', sortv=300)

G.add_subgraph(name='cluster_page', nbunch=['cluster_row1,cluster_row2,cluster_row3'],  packmode='array_u1', pack=18)

I hope this is fairly close to being accurate. The technique is to create the nodes, then attach them to a parent cluster. Then create more clusters, attaching these child clusters to them until you reach the root cluster which wraps the entire page. Then execute your code to draw the graph.

I’m not sure how attribute inheritance works here, so you may have to specify pack=0 or pack=18 in places if your margins needs adjustments.

Let me know if this works for you,
Jeff