GridGraph layout with added edges

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.

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.

-
Please show your use case (how do you want to build the weighted graph) – Dr. belisarius Jan 27 '14 at 4:48
– DavidC Jan 28 '14 at 0:27
Thanks @DavidCarraher, the linked thread seems very useful. – Eckhard Jan 28 '14 at 0:35

1 Answer

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"]
]


-