Lexicographic product of graphs

Question

I am seeking to use the undocumented Mathematica function

GraphComputation`GraphProduct[G1,G2,type]

to compute the lexicographic product of graphs G1 and G2. I can get this function to work for the Cartesian product but not for the Lexicographic product. Does anyone know how it works?

Answer 1

Playing around with Szabolcs' implementation, it appeared to me that the adjacency matrix of the lexicographic product can be easily described by KroneckerProduct. This led me to a second method, which seems to have better performance characteristics.

lexicographicProduct2[G_?UndirectedGraphQ, H_?UndirectedGraphQ, 
  opts : OptionsPattern[]] := AdjacencyGraph[
  Tuples[{VertexList[G], VertexList[H]}],
  With[{
    nG = VertexCount[G],
    nH = VertexCount[H]
    },
   Plus[
    KroneckerProduct[AdjacencyMatrix[G], ConstantArray[1, {nH, nH}]],
    KroneckerProduct[IdentityMatrix[nG, SparseArray], AdjacencyMatrix[H]]
    ]
   ],
  opts
  ]

Here is a short timing comparison:

G = CycleGraph[20];
H = CycleGraph[30];
K1 = lexicographicProduct[G, H]; // RepeatedTiming // First
K2 = lexicographicProduct2[G, H]; // RepeatedTiming // First
K1 == K2

1.40

0.0543

True

Edit

The product graphs have the tendency to be rather dense, so AdjacencyGraph might not be the best choice to construct it from the adjacency matrix: Doing so leads to a graph with GraphComputation`GraphRepresentation returning "Simple" which is in fact a sparse representation. The following leads to a result whose GraphComputation`GraphRepresentation equals "Incidence". This is also almost 10 times faster than lexicographicProduct2 and even faster than Mathe172's fix for GraphComputation`GraphProduct (at least on my machine).

lexicographicProduct3[G_?UndirectedGraphQ, H_?UndirectedGraphQ, opts : OptionsPattern[]] := Graph[
  Tuples[{VertexList[G], VertexList[H]}], 
  With[{nG = VertexCount[G], nH = VertexCount[H]},
    UpperTriangularize[Plus[
      KroneckerProduct[AdjacencyMatrix[G], ConstantArray[1, {nH, nH}]], 
      KroneckerProduct[IdentityMatrix[nG, SparseArray], AdjacencyMatrix[H]]
      ]
     ]]["NonzeroPositions"],
  opts
  ]

K3 = lexicographicProduct3[G, H]; // RepeatedTiming // First
VertexList[K2] == VertexList[K3]
EdgeList[K2] == EdgeList[K3]

0.0059

True

True

Answer 2

I did not know what lexicographic product was, so I looked it up.

If performance is not critical, you can implement the definition quite directly.

lexicographicProduct[g1_?UndirectedGraphQ, g2_?UndirectedGraphQ, opt : OptionsPattern[]] := 
 RelationGraph[
   (* two nodes are connected if their corresponding nodes in the first graph are connected *)
   EdgeQ[g1, First[#1] \[UndirectedEdge] First[#2]] || 
   (* or their corresponding nodes in the first graph are the same and their corresponding nodes in the second graph are connected *)
   (First[#1] === First[#2] && EdgeQ[g2, Last[#1] \[UndirectedEdge] Last[#2]]) &,

   (* the vertices are the cartesian product of the two vertex sets *)
   Tuples[{VertexList[g1], VertexList[g2]}],

   (* also allow setting graph options *)
   opt
 ]

lexicographicProduct[CycleGraph[5], CycleGraph[3]]

Answer 3

So I got GraphComputation`GraphProduct to work, and it appears to be even faster:

Unprotect[GraphComputation`GraphProduct];
DownValues[GraphComputation`GraphProduct] = 
  DownValues[GraphComputation`GraphProduct] /. "Lexicographic" -> "Lexicographical";
Protect[GraphComputation`GraphProduct];


K1 = lexicographicProduct[G, H, VertexLabels -> "Name"]; // 
  RepeatedTiming // First
K2 = lexicographicProduct2[G, H, VertexLabels -> "Name"]; // 
  RepeatedTiming // First
K3 = GraphComputation`GraphProduct[G, H, "Lexicographical"]; // 
  RepeatedTiming // First
IsomorphicGraphQ[K1, K2] && IsomorphicGraphQ[K2, K3]
(* 1.09 *)
(* 0.041 *)
(* 0.0086 *)
(* True *)

The issue is that there appears to be a typo in the definition of the function: The top-level GraphProduct function expects "Lexicographic", while the inner function expects "Lexicographical", leading to the unexpected error.

Note: Obviously, the function is undocumented, so be careful. Especially given that it's not even possible to call the function without fixing it up first.