Context
I am developing UI for a skill web for a mobile game. Each skill may have requirements from other skills, or sometimes no requirement at all.
The problem
The description above is perfectly captured in a directed graph. I want to display this graph as aesthetically pleasing as possible, along with functionality and interactivity.
Guidelines
Obviously that is the vaguest question ever. But after I sat down to analyse what I actually meant by "aesthetically pleasing", as well as what interactivity I want from the final result, I came up with concrete guidelines:
- Minimise longest edge between any two nodes. Of course this will be a value after normalisation.
- Avoid edges crossing each other where possible.
- Basic interactions: rotation, scaling, and moving the graph. Keep in mind that these don't actually concern the final algorithm, but they are good to keep in mind.
Approaches
So with those guidelines in mind, I thought about how to render this graph. I came up with two approaches:
- Put nodes on the graph one at a time, and use the greedy approach to make sure each new node is in the best position available.
- Dump all nodes randomly (for example, in a grid) first, then try iterate through all the nodes by moving connected nodes closer together and thus try to reduce the maximum normalised edge length in the graph.
As for preventing edges from crossing, I thought about grouping nodes in clusters/communities based on the number of connecting edges with other nodes in the same group, but I'm not exactly sure how that would incorporate in the solution.
Drawbacks
Both methods have drawbacks. Method 1 can never move other vertices during the process, and may result in lack of space. Imagine we are drawing a rectangle-shaped graph. The algorithm only sees single nodes so it doesn't know we are trying to draw a rectangle. We might end up with a shape that looks like:
And obviously the square would be the one minimising all the edge lengths (after normalisation, if you will).
Method 2, on the other hand, does not actually rotate stuff, so if we are trying to draw a triangle-shaped graph that looks like:
after initial random layout, and we try to move vertices together, that will just give the same layout on a smaller scale.
The question
I need to get a hold on a good sorting/clustering algorithm, or at least a good idea/approach, that can display a list of nodes in a directed graph on a plane such that the above guidelines are met.