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.
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...