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 need to draw graphs that are Cartesian products of 2 graphs. I need them to look like this: enter image description here.

So each copy of the factors can have LinearEmbedding, but the whole drawing should be based on grid-like skeleton. Clearly, vertices should be on nodes of the grid, and edges can be arbitrary. Are there any solutions?

In particular, for Grid Graphs the SpringEmbedding gives similar result, but even for Torus Graphs result is very different. I need to draw Cartesian products of complete graphs, cycles, paths, complete bipartite graphs, and add labels to edges of the products.

share|improve this question
add comment

1 Answer

up vote 11 down vote accepted

I do feel that the question could be a bit more clear. When you write "each copy of the factors can have LinearEmbedding", do mean that each factor is, in fact, a path graph? Assuming so, perhaps something like the following could work. (Seems to complicated, I admit.)

m = 3;
n = 2;
g1 = Graph[
   Table[UndirectedEdge[Subscript[u, i], Subscript[u, i + 1]], {i, 1, m - 1}],
   VertexLabels -> "Name",
   VertexCoordinates -> Table[{0, i}, {i, 1, m}]
   ];
g2 = Graph[
   Table[UndirectedEdge[Subscript[u, i], Subscript[u, i + 1]], {i, 1, n - 1}],
   VertexLabels -> "Name",
   VertexCoordinates -> Table[{i, 0}, {i, 1, n}]
   ];
g1g2 = Graph[
   Flatten@Join[
     Table[
      UndirectedEdge[{Subscript[u, i], Subscript[u, j]}, 
        {Subscript[u, i], Subscript[u, j + 1]}], {i, 1, m}, {j, 1, n - 1}],
     Table[
      UndirectedEdge[{Subscript[u, i], Subscript[u, j]}, 
         {Subscript[u, i + 1], Subscript[u, j]}], {i, 1, m - 1}, {j, 1, n}]
     ],
   VertexLabels -> "Name",
   VertexCoordinates -> Flatten[Table[{i, j}, {i, 1, m}, {j, 1, n}], 1]
   ];
size[1] = {100, 200};
size[2] = {200, 100};
size[3] = {300, 200};
Row[MapIndexed[Show[GraphComputation`GraphConvertToGraphics[#],
    ImageMargins -> 5, ImageSize -> size[#2[[1]]]] &, 
  {g1, g2, g1g2}],
 ImageSize -> 700, Alignment -> Center]

enter image description here

The bulk of this code involves the layout of the graph. If you simply want a generalized Cartesian product of graphs without regard to the layout, then that's a bit easier.

SeedRandom[1];
g1 = RandomGraph[{5, 5},VertexLabels -> "Name"];
g2 = RandomGraph[{5, 8},VertexLabels -> "Name"];
makeCartesianProductEdge[u_, UndirectedEdge[u2_, v2_]] := UndirectedEdge[{u, u2}, {u, v2}];
makeCartesianProductEdge[UndirectedEdge[u1_, v1_], v_] := UndirectedEdge[{u1, v}, {v1, v}];
g1g2 = Graph[Flatten[{
     Table[makeCartesianProductEdge[u, e],{u, VertexList[g1]}, {e, EdgeList[g2]}],
     Table[makeCartesianProductEdge[e, u],{u, VertexList[g2]}, {e, EdgeList[g1]}]}], 
     VertexLabels -> "Name"];
graphToGraphics[g_Graph] := GraphComputation`GraphConvertToGraphics[g];
graphToGraphics[else_] := else;
GraphicsGrid[Partition[graphToGraphics /@ {g1, g2, g1g2, SpanFromLeft}, 2]]

enter image description here

If you want a linear embedding of non-path graphs, then you'll need to do something to keep the edges from lying on top of one another.

g1 = Graph[EdgeList[g1], VertexCoordinates -> Table[{i, 0}, {i, 1, Length[VertexList[g1]]}]];
g2 = Graph[EdgeList[g2], VertexCoordinates -> Table[{i, 0}, {i, 1, Length[VertexList[g2]]}]];
g1g2 = Graph[EdgeList[g1g2], VertexCoordinates -> VertexList[g1g2]]

enter image description here

Perhaps the following EdgeShapeFunction will help, but I doubt it.

esf[{u_, v_}, ___] := {Opacity[0.3], Arrow[BSplineCurve[Table[
  (u + v)/2 + Norm[v - u] {Cos[t], Sin[t]}/2,
  {t, ArcTan @@ (v - u), ArcTan @@ (v - u) + Pi, Pi/5}]]]};
GraphicsRow[SetProperty[#, EdgeShapeFunction -> esf] & /@ {g1, g2, g1g2}]

enter image description here

share|improve this answer
    
@R.M I got the impression he was looking for the Cartesian product of arbitrary path graphs (note the parameters m and n). Hence, my question about linear embeddings. –  Mark McClure Apr 30 '12 at 4:09
    
I stand corrected. While my interpretation was the same as yours, I didn't pay closer attention to your code. Very nice! :) –  rm -rf Apr 30 '12 at 6:03
    
Thank you very much for the answer. I've noted that I need to draw Cartesian products of complete graphs, paths, cycles etc. If each factor is a path graph, then the product is GridGraph for which SpringEmbedding is nice. I wrote I needed LinearEmbedding because for GraphPlot that option produced a drawing with curved, non-overlapping edges, same result that you got using EdgeShapeFunction –  Hrant Khachatrian Apr 30 '12 at 8:07
    
So the last part of the answer is what I needed :) Two important things I learned: 1. how to effectively construct Cartesian product for Graph objects; 2. how to use EdgeShapeFunction. Hope this will be enough to achieve all my goals. Thanks again. –  Hrant Khachatrian Apr 30 '12 at 8:08
    
hmm.. I couldn't recreate the last drawings you've attached. Output for your code is SetProperty[ (* image here *), EdgeShapeFunction->esf], so it doesn't work. I tried to use your EdgeShapeFunction for g1 only: Graph[EdgeList[g1], EdgeShapeFunction -> esf, VertexCoordinates -> Table[{i, 0}, {i, 1, Length[VertexList[g1]]}]] and I get ArcTan::indet: "Indeterminate expression ArcTan[0.,0.] encountered.". –  Hrant Khachatrian Apr 30 '12 at 8:32
show 3 more comments

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.