1
$\begingroup$

Assuming I have a list L of lists. Each list in L has four entries [North, Ost, South, West] which represents the neighbours of a point i on a grid. If the entry is 0, the grid neighbour is not occupied by another point.

For example L[0] = [0,3,8,0].

This means that point 1 (which is represented by the first list in L), has point 3 on the right side and point 8 below. On the left and the top, there is no point, these grid places are not occupied.

I am struggling with transforming from this list L representation to a coordinate representation for each point.

The points can be separated, they can form clusters but they don't have to.

With neighbour, I am only referring to one unit above/below/right/left. Any neighbours further apart are not considered.

I think this problem should be known, but I don't know what I should search for.

This task is part of an optimization problem I am trying to solve with a genetic algorithm. I am looking for the optimal arrangement of points on a grid. Since the solution is translational invariant I am trying to find an intrinsic representation of the points on the grid. The representation above is such a trial. Now I have the problem that I cant map from this intrinsic representation back to the grid representation.

Improve this question
$\endgroup$
1
  • $\begingroup$ @D.W I deleted the question on StackOverflow. I also edit the question here. $\endgroup$
    – nuemlouno
    Dec 4, 2021 at 21:14

1 Answer 1

Reset to default
1
$\begingroup$

Pick an arbitrary node. Assign it the coordinates $(0,0)$. Now run any graph traversal algorithm -- say, depth-first search. When you visit a node, you know its coordinates. Now you can look at its neighbors and assign coordinates to each of its neighbors (if they already have coordinates, check that the old ones and the new ones are consistent; if not, then it's impossible to lay out the graph in the plane), and visit the neighbors (if not already visited). This will let you reconstruct all of the coordinates with running time linear in the size of the graph.

For nodes with no neighbors, you have almost no information about their location. You can keep track of these nodes and at the end put them anywhere off to the side (as long as they are not next to any other existing node or next to each other; but they can be as far away as you want).

Improve this answer
$\endgroup$
2
  • $\begingroup$ What is if a node has no neighbours $\endgroup$
    – nuemlouno
    Dec 5, 2021 at 0:44
  • $\begingroup$ @nuemlouno, Thank you for highlighting that. See the last paragraph of my edited answer. $\endgroup$
    – D.W. ♦
    Dec 5, 2021 at 3:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.