3
$\begingroup$

I noticed that the nice symmetric layout of a grid graph gets distorted when additional edges are added to the graph. Is there way to prevent that from happening and to keep the rectangular, grid-like layout?

A minimal example would be

g = GridGraph[{3, 3}]
Graph[Range[9], Join[EdgeList[g], {1 \[UndirectedEdge] 5}]]

giving the following two outputs.

enter image description here

I would like the additional edge(s) added to the original graph, keeping its layout unchanged.

Thanks.

Edit: I realize that

EdgeAdd[g, 1 \[UndirectedEdge] 5]

does what I want. I'd still be interested to learn how I can force a grid-like layout when constructing the graph explicitly from vertex and edge lists, in particular since EdgeAdd does not seem to work well with edge weights.

Edit 2: A concrete example of how I would go about constructing the weighted edge would be

n=5;
ind = RandomVariate[BernoulliDistribution[1/2],{n-1,n-1}]+1;
crossedges = Table[{(j-1)n+i \[UndirectedEdge] (j-1)n+i+n+1,(j-1)n+i+1 \[UndirectedEdge] (j-1)n+i+n}[[ind[[j, i]]]],{j,1,n-1},{i,1,n-1}] // Flatten;

g = Graph[Range[n^2],Join[EdgeList[GridGraph[{n,n}]],crossedges],EdgeWeight -> Join[ConstantArray[1,2n(n-1)],ConstantArray[Sqrt[2],(n-1)^2]]];

This construction is motivated by this question on MO.

$\endgroup$
4
$\begingroup$

One way is to take advantage of WeightedAdjacencyGraph with GraphLayout option.

Take the code in your edit 2 for example.

n = 20;
ind = RandomVariate[BernoulliDistribution[1/2], {n - 1, n - 1}] + 1;
crossedges = Table[{
                    (j - 1) n + i \[UndirectedEdge] (j - 1) n + i + n + 1,
                    (j - 1) n + i + 1 \[UndirectedEdge] (j - 1) n + i + n
                   }[[ind[[j, i]]]],
                   {j, 1, n - 1}, {i, 1, n - 1}] // Flatten;

Save the adjacency matrix for the base GridGraph first:

gridG = GridGraph[{n, n}];
adjMgg = Normal[AdjacencyMatrix[gridG]];

Then add the crossedges to gridG:

adjMdg = Normal[AdjacencyMatrix[EdgeAdd[gridG, crossedges]]];

Construct the weighted adjacency matrix:

adjWeight = adjMgg + Sqrt[2] (adjMdg - adjMgg) /. {0 -> ∞};

Use GraphLayout -> {"GridEmbedding", "Dimension" -> {n, n}} to shape the graph:

dg = WeightedAdjacencyGraph[adjWeight,
                            GraphLayout  -> {"GridEmbedding", "Dimension" -> {n, n}},
                            EdgeStyle    -> Directive[GrayLevel[.7]],
                            VertexStyle  -> GrayLevel[.9], VertexSize -> 0.05,
                            ImagePadding -> 10]

Now we are ready for computing the shortest path:

Module[{i = 1, j = n^2, path},
       path = FindShortestPath[dg, i, j];
       HighlightGraph[dg,
                      PathGraph @ path,
                      GraphHighlightStyle -> "Thick"]
      ]

shortest path on grid graph

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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