Given a lattice graph without spatial embedding, how to identify the location of nodes in lattice?

Question

Suppose I have such a graph:

SeedRandom[3];
g = GridGraph[{5, 6}];
graph = Graph[RandomSample[VertexList@g], EdgeList@g, VertexLabels -> "Name"]

We know that it is a lattice graph, but we do not know its dimensions ($5\times 6$) or the location $(i,j)$ of each node within the lattice.

How can we compute this information? How to get such matrix?

$$\left( \begin{array}{cccccc} 26 & 21 & 16 & 11 & 6 & 1 \\ 27 & 22 & 17 & 12 & 7 & 2 \\ 28 & 23 & 18 & 13 & 8 & 3 \\ 29 & 24 & 19 & 14 & 9 & 4 \\ 30 & 25 & 20 & 15 & 10 & 5 \\ \end{array} \right)$$

Answer 1

Original answer is below. Here's something different. The virtue of this is that it is simple to implement in Mathematica.

Let's make a test graph. Note that below we will never make use of the special vertex or edge ordering that the GridGraph function produces. The same method will for any graph that is a regular 2D lattice, regardless of how the vertices are named or ordered.

g = GridGraph[{5,6}];

There are 4 corners of the lattice, all with degree 2:

{c1, c2, c3, c4} = Pick[VertexList[g], VertexDegree[g], 2];    

Pick two into the variables c1 and c2, in such a way that they are not diagonally opposite. This can be ensured by making sure that their distance is not the highest:

If[GraphDistance[g, c1, c2] > GraphDistance[g, c1, c3], c2 = c3]

Compute vertex distances from both corners:

a = GraphDistance[g, c1];
b = GraphDistance[g, c2];

Using the sum and differences of these distances as vertex coordinates gives a nice lattice embedding:

SetProperty[g, VertexCoordinates -> Transpose[{a - b, a + b}]]

We can also use these coordinates as indices into a matrix. We just need to make sure that they start at 1.

coord = (1 + Transpose[{a - b, a + b}])/2;
min = Min /@ Transpose[coord];
coord = # - min & /@ coord + 1;

MatrixForm@SparseArray@Thread[coord -> VertexList[g]]

Wy does this work?

If we think about the distance of any vertex from the two top corners, it will be clear that:

• Moving one step to the left in the lattice will decrease the distance from the top left corner by one and increase the distance from the top right corner by 1. The sum of distances doesn't change.

• Moving one step down increases both distances: the difference of distances doesn't change.

---

Old answer

I don't have time to implement this, unfortunately, but here's an idea for an algorithm:

We can categorize nodes in the graphs based on their degree. Corner vertices have degree 2, edge vertices have degree 3 and inner vertices have degree 4.

The algorithm:

1. Select a corner
2. Select a neighbour of the corner. This will be on the edge of the lattice, i.e. will have degree 3. Mark this as the "current node".
3. Take a yet unvisited degree 3 neighbour of the current node and make it the next current node. This will also be on the edge.
4. Repeat until we reach the next corner. Now remove the whole row of nodes in the lattice that we have visited.
5. Continue traversing rows like this until nothing is left.

Of course this requires special checks for handling the last row, etc. It may be practical to remove each node from the lattice as we visit it, to avoid having to keep track of visited nodes.

---

A more interesting case would be a periodic lattice, which has no corners or edges. This can probably be handled by selecting any starting node, then selecting two neighbours which have a different common neighbour than the starting node. This gives us an oriented unit cell of the lattice. Continue identifying unit cells and moving in the same direction until we arrive back to the original. Then take the next row of unit cells, and so on.

I hope this is clear. Anyone is welcome to post an implementation, as I won't have time to do it.

Answer 2

SeedRandom[11];
g = GridGraph[RandomInteger[{3, 7}, 2]];
origVertList = RandomSample@VertexList@g;
graph = Graph[origVertList, EdgeList@g, VertexLabels -> "Name"]

Assuming the graph is a GridGraph, but that we do not know the dimensions, we can find the dimensions. Then, most of the structure of the matrix is trivial, I am not sure if this is what you are after. If you really want the exact matrix, corresponding to the layout of the graph, that seems to be kind of tricky. Below we reproduce a matrix is the same as the matrix you want, up to some symmetry. There are 3 other versions of the matrix that can occur due how to the layout is done.

vertList = VertexList[graph];
edgeList = EdgeList[graph];
n = Length[vertList];
corners = 
  Select[Tally[Sequence @@@ EdgeList[graph]], #[[2]] == 2 &][[All, 1]];
gathered = 
  GatherBy[#, Length] &@
   Flatten[Outer[FindShortestPath[graph, #, #2] &, corners, corners], 
    1];
{width, height} = Length /@ gathered[[2 ;; 3, 1]];
normalMatr = Transpose@Partition[Range[n], width];
normalMatr // MatrixForm

It seems to me that the rest of the structure of matrix (which of the 4 orientations it is in), is not easily accessible. Where the points end up depends on the layout algorithm. We can get the locations of the points back from the graphics like so

points = Cases[ToBoxes[graph], DiskBox[x_, ___] :> x, Infinity];
orientation = {#1 >=   2, #2 <=  2} & @@ 
   First@Permute[points, origVertList];
funk = Composition @@ Pick[{ Reverse /@ # &, Reverse}, orientation];
funk@normalMatr // MatrixForm

This is kind of cheating though, because we use origVertList.

Answer 3

It's a modification of solution in How can I sequentially apply different graph embeddings?.

gridPosition[g_] := 
 Block[{coords, corners, tuples, shortpath, bound, m, n, paths, pairs,
    grids}, corners = VertexList[g, x_ /; VertexDegree[g, x] == 2];
  tuples = Subsets[corners, {2}];
  shortpath = FindShortestPath[g];
  bound = shortpath @@@ tuples;
  {m, n} = Most[Sort[Union[Length /@ bound]]];
  paths = Select[bound, Length[#] == m &];
  pairs = 
   If[Length[shortpath[paths[[1, 1]], paths[[2, 1]]]] == n, 
    Transpose[paths], paths[[1]] = Reverse[paths[[1]]];
    Transpose[paths]];
  shortpath @@@ pairs]

g = GridGraph[{5, 6}];
graph = Graph[RandomSample[VertexList@g], EdgeList@g, 
   VertexLabels -> "Name"];

gridPosition[graph]

{1, 6, 11, 16, 21, 26}, {2, 7, 12, 17, 22, 27}, {3, 8, 13, 18, 23, 28}, {4, 9, 14, 19, 24, 29}, {5, 10, 15, 20, 25, 30}

Answer 4

When the graph is:

SparseArray[Thread[Rule[Round[RotationTransform[-Pi/2][GraphEmbedding[g]]], 
    VertexList[g]]]] // MatrixForm

$\left( \begin{array}{cccccc} 26 & 21 & 16 & 11 & 6 & 1 \\ 27 & 22 & 17 & 12 & 7 & 2 \\ 28 & 23 & 18 & 13 & 8 & 3 \\ 29 & 24 & 19 & 14 & 9 & 4 \\ 30 & 25 & 20 & 15 & 10 & 5 \\ \end{array} \right)$

Actually,this is what I'm exactly go after.