Hi John,

On 07/19/2013 12:58 PM, John Reid wrote:

Hi,

I have a tripartite graph. I.e. one with 3 layers. Nodes in the first later are only connected to nodes in the second layer. Similarly nodes in the third layer are only connected to the nodes in the second layer. I'd like to try and layout the graph. I was imagining something where the nodes in each layer are positioned in the same horizontal or vertical plane but how to choose the ordering and spacing between the nodes in this plane? The number of edge cross-overs would be a good objective function to minimise. The three layers have about 700, 50 and 1500 nodes respectively. Does graph-tool offer me any layout options for this sort of graph? I don't mind implementing something if it is not too complicated.

graph-tool currently does not have anything along these lines. I'm not aware of any leading algorithm which works well for bi- or multipartite graphs. Most spring-block algorithms work terribly for such graphs... However the graph drawing literature is huge, so it is quite possible that I am simply not aware of some useful algorithm in this case.

As far a trying some things out, there are a couple of things you could perhaps try... The sfdp_layout() function has a 'groups' parameter, with which you can pass a vertex property map. All vertex belonging to the same group (i.e. the same property value) receive an additional force pulling them together, so that they remain close in the layout. You could try this with your layers. However the groups tend to look circular... Another option would be to do a spring block layout, and then manually separate the layers in the y-direction afterwards. The layout could be refined later by keeping each layer fixed with the "pin" option. But I have no idea if this will look pleasing...

Cheers, Tiago