Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
    
Please show your use case (how do you want to build the weighted graph) –  belisarius Jan 27 at 4:48
    
    
Thanks @DavidCarraher, the linked thread seems very useful. –  Eckhard Jan 28 at 0:35

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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