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