Algorithm for topology and map analysis

Dec 28, 2015 at 1:11 AM
I've been using your Excel template as a tool for game and map design, particularly when trying to determine adjacency between map regions. A prime example of this is mapping out connections for the board game Diplomacy and its variants.

However, I haven't been able to find a node-arrangement algorithm in the excel template that works really well for this. Mostly I just have to lock a few nodes as I go and keep untangling.

Is there an algorithm or setting that I'm missing that might make this easier? Specifically, I'm looking for a vertex-spacing algorithm that would minimize the number of intersections between the line segments, minimizing the number of "tangles" in the web of adjacent points.
Dec 28, 2015 at 7:30 PM

Thank you for the interest in NodeXL!

We have a variety of layout algorithms available in NodeXL but they may not meet your needs.

Untangling a 3D mesh is an interesting use case! We have not yet focused on directly supporting this data type.

Can you share some suggested algorithms that do this task effectively for you in other applications/environments?

We are always interested in new use cases for NodeXL!


Dec 28, 2015 at 8:35 PM
Thanks for your quick reply!

Here's an academic paper that describes roughly the type of algorithm I'd be interested in:

It seems that most of the folks recently working on such things are doing it for surface meshes of objects, rather than tangled webs of arbitrary nodes. However, I think what they show on page 555 (14 of the pdf) resembles most closely what I'm looking for.

The point would be to try to reduce the number of instances where edges cross or overlap one another (outside of the vertices themselves, of course).

I'm thinking along the lines of an algorithm that for each node would stochastically pick a few possible locations, then choose the least tangled one. Additional passes could be made on the entire mesh once all are placed in order to attempt relocation of the most tangled nodes. There could be a user option for the number of passes the algorithm makes.

(Pardon my awful pseudocode)
// Where fixedVertices is always a subset of placedVertices, but the "fixed" comes from the user-set lock.
PlaceVertex( vertexToPlace, placedVertices[], fixedVertices[], allEdges[], placedEdges[])
  edgesToVertex[] = edges.FindEdgesFor(vertexToPlace);

  adjacentVertices[] = edgesToVertex.AllPointsExcept(vertexToPlace);

  newEdgesToPlace[] = edgesToVertex.edgesTo(set.overlap(adjacentVertices, placedVertices));

  trialLocations[] = ChoosePossibleLocationsBasedOn(adjacentVertices, placedVertices);  // Using some existing spacing algorithm to start with.

  foreach(location in triallocations)
    edgesTrialLocations[] = newEdgesToPlace.calculateEdgesFor(location);

    tangles = 0;

    foreach(edge in edgesTrialLocations)
       tangles += placedEdges[].thatIntersectWith(edge).count;
    location.tangles = tangles;

  vertexToPlace.location = triallocations.locationsWithZeroOrLeastTangles().locationWithBestSpacing() //Spacing judged by some other algorithm.