How to iterate through all permutations of valid links between nodes

Question

Imagine a 2D area, with a number (array) of nodes (or points) defined within it, in arbitrary (but known) positions (integer x,y coordinates), like this:

From there I want to be able to, programmatically, add as many "links" as possible. A "link" is a straight line between any two nodes, but a link cannot cross another link. I already have a method created that can verify if two links cross. eg

With any given set of nodes, there is a finite number of ways that links can be laid out and I want to be able to generate all of those possible (valid) combinations.

However, I have absolutely no idea where to start on this. I could randomly fill the nodes with valid links, but I don't know how to iteratively generate each possible permutation.

I'm guessing that some kind of algorithm exists for problems like this, probably based around recursion, but my searches so far have been fruitless.

I'm not looking for a coded solution, I can do that part. What I need is the high level design process, or algorithm, that can be followed to solve this problem.

Answer 1

You've got quite hard a problem here.

I'm thinking of a method resembling Sieve of Eratosthenes .

First, you can "name" or "number" each link. Let's assume we just have 5 nodes, so we'll have 10 links. Number each one from 1 until 10.

Now, we can put them all into an array.

Let's assume we have this list represents two links who intersect each other:

• 1 - 3
• 1 - 4
• 1 - 7
• 1 - 10
• 2 - 4
• 2 - 8
• 3 - 4
• 6 - 9
• 6 - 10

Now let's visualize this. First, I choose to draw link 1.

*For the images below, green means I choose to draw the link, red means the link cannot be drawn (because it intersects a selected link), and white means the link can be drawn.

Then, check each element from link #2 to link #10: does it intersect link #1? If yes, we should eliminate them (means we must not draw them). In this case : links #3, #4, #7, #10 (from the list above)

Now, you can choose which one is the next to draw: either #2, #5, #6, #8, or #9? Let's say you choose #2, then you do the same procedure. Check the rest of the element: If it's already red then you may skip it, but if it's white (can still be drawn), check if it intersects link #2. Link #2 intersects with #4 and #8, but since #4 is already eliminated, we just eliminate #8.

Then, pick another link, and so on. Note that we can make use of two arrays: one integer array containing the links, and the other a boolean array to check if it's eliminated or not.

You can do this in iteration: picking which link to draw and eliminate the ones intersecting them. This way, you can avoid drawing unnecessary links.

Well, it's just an idea that might work. But, I neither think this way is easy to implement, nor do I think it can be considered "efficient" in terms of complexity.

Answer 2

To cut down on the count of recursive calls I thought of introducing a strict ordering of links to be able to eliminate duplicates in the initialization phase (before any recursion):

• on the links define any (arbitrary) strict ordering order
• on the links define a method doesNotCrossWith() returning the set of links of higher order which this link does not cross (capable of executing in constant time after initialization)
• on the links define a method doesNotCrossWithIntersectionOf(Set<Link>) returning the intersection of the parameter and doesNotCrossWith()

• define the main recursive method getValidPermutations(Link link, Set<Link> linksNotForbidden) (Pseudocode):

  Set<Set<Link>> validPermutationsIncludingLink;
  
  // add the current link (alone) itself to the possible permutations (to be added to):
  validPermutations.add(new Set(link));
  
  Set<Link> linksStillAllowed = link.doesNotCrossWithIntersectionOf(linksAllowed);
  
  for (Link otherLink : linksStillAllowed) {
      Set<Set<Link>> validPermutationsOfOther;
  
      //recursive call:
      for (Set<Link> validPermutation : getValidPermutations(otherLink, linksStillAllowed)) {
          validPermutation.add(otherLink);
          validPermutationsOfOther.add(validPermutation);
      }
      validPermutations.addAll(validPermutationsOfOther);
  }
  
  return validPermutations;
  

• call getValidPermutations for each link and build a union of the results.

The maximum recursive depth is the number of (possible) links n.

P.S.: With 7 nodes roughly arranged as in your example I get ~150ms running time with this implementation on my machine resulting in 37055 possible permutations, for a large number of nodes additional optimizations might be needed.