This is a follow-on from my post about the Tower of London test. Using the advice received there I have modeled the problem space as a graph.
What I’m looking for now is advice on any existing algorithms for drawing the TOL graph. I made a somewhat arbitrary choice in how I numbered the nodes, that made sense in helping me create the graph, but results in the first 12 out of 36 nodes in the resulting number scheme having the fewest numbers of edges. What I’m thinking of is to start by sorting the nodes by numbers of edges, and then grouping these by numbers of common edges. If I then start displaying these most connected nodes and edges first in the center of the display, and then adding remaining lower edge count nodes further out, will I prevent the problem of really long edge lines, or worse, intersecting edge lines?
I’ve tried a search, but “displaying a graph” and variants have given examples, but no instructions.
I see no one has answered this. Are you trying to implement an algorithm from scratch, or looking for a Javascript or Python or whatever library that will lay out your graph, or just looking for a program that will export an image?
Here is a non-comprehensive list of some well-known utilities. Eg “neato” uses a “spring model” and attempts to minimize the global energy.
@DPRK, thanks, I will check out the references in the link. From a quick read it looks like I was contemplating something like the force-based layout approach, but its good to know about the alternatives.
For my particular question, the version of the Tower of London test that I am helping to develop is going to be administered to participants strongly predisposed to anxiety. I have an idea that their anxiety may be reduced if I can present a few of the practice examples with the 3 post setup that lets them move the balls, while at the same time displaying the graph with the current node and the target node highlighted. This way they will be able to judge from where the new current node is on the display if they are moving towards or away from the target. This will make the practice part of the test like a game. This also makes the graph display simpler, because I’d only need to include the start and target node, the intervening nodes for the shortest path solution, and the neighboring nodes for these. This might be more easily handled with the circular layout approach.
@DPRK I found a paper - Berg and Boyd, 2002 (PDF) which proposes a standard nomenclature for naming the arrangements of the balls on the posts for the Tower of London test. Figure 2 in the paper displays the resulting graph of the problem space arranged as a hexagon. Rather than re-inventing the wheel, I think that I can adapt their work to my purpose.
@Chronos, you might be pleased to note that Table 1 in the paper uses your colour permutation idea to derive the node numbering scheme.
I think it depends what you are trying to emphasize. If you arrange the graph as a hexagon, it emphasizes that symmetry. If you pick a random layout you get something like, here goes, https://a.tmp.ninja/bmyqkABh.png