Message Boards Message Boards

Strong Graph product between two C_5 graphs?

Posted 8 years ago

Dear Community, I am trying to compute a Strong Graph product between two C_5 graphs. Looking around I did not find anything in the documentation. Only on Internet I found this Mathematica function

GraphComputation`GraphProduct[G, H, type]

at this link:

http://mathworld.wolfram.com/GraphProduct.html

But I was not able to find any documentation about. Moreover I tried to do something but it seem that only the Cartesian product works:

GraphComputation`GraphProduct[G, H, "Cartesian"]

The other products gives error even if contained in this link:

http://mathworld.wolfram.com/GraphLexicographicProduct.html

for example. Thus does someone know how to make Graph Products with Mathematica? Thanks for the attention.

POSTED BY: Alessio Lapolla
4 Replies

Thanks for the answer Chip! Of course I created my own function for calculate the Strong Product, even if my code is a bit different from yours. But they are equivalent I guess. I was just surprised that exist a sort of reference about a build-in function that does not exist really. Thank you again! Anyway that is my function to get the Strong Product

GraphStrongProduct[G_, H_] :=

 Module[{ajmG, ajmH, ajm1G, ajm1H, P, ajmGH} ,
         (* give the adjacency matrix of the graphs*)

  ajmG = Normal[ArrayFlatten[AdjacencyMatrix[G]]];
              ajmH = Normal[ArrayFlatten[AdjacencyMatrix[H ]]];
         (* give the modified adjacency matrix of the graphs, 
  1 on the diagonal*)
         ajm1G = ReplacePart[ajmG, {i_, i_} -> 1];
         ajm1H = ReplacePart[ajmH, {i_, i_} -> 1];
         (*the adjacent matrix of the strong product between G and H*)
    \
       P = ArrayFlatten[TensorProduct[ajm1G, ajm1H]];
         ajmGH = ReplacePart[P, {i_, i_} -> 0];
         AdjacencyGraph[ajmGH]
  ]

It seems work too.

POSTED BY: Alessio Lapolla
Posted 8 years ago

This is a nice solution!

POSTED BY: Greg Hurst
Posted 8 years ago

You can get around 1.5 times faster if you avoid the pattern matcher by replacing the lines containing ReplacePart with the following:

Change

ajm1G = ReplacePart[ajmG, {i_, i_} -> 1];
ajm1H = ReplacePart[ajmH, {i_, i_} -> 1];

to

ajm1G = Unitize[ajmG + IdentityMatrix[Length[ajmG]]];
ajm1H = Unitize[ajmH + IdentityMatrix[Length[ajmH]]];

and

ajmGH = ReplacePart[P, {i_, i_} -> 0];

to

ajmGH = P (1 - IdentityMatrix[Length[P]]);
POSTED BY: Greg Hurst
Posted 8 years ago

You could always implement your own, based on the definition of a strong graph product.

strongGraphProduct[g_, h_] :=
    Block[{mg, mh, vj, n, mj},
       mg = AdjacencyMatrix[g];
       mh = AdjacencyMatrix[h];

       vj = Tuples[{Range[VertexCount[g]], Range[VertexCount[h]]}];
       n = Length[vj];

       mj = SparseArray[{{i_, j_} /; strongCondition[vj, mg, mh, i, j] -> 1}, {n, n}];

       AdjacencyGraph[mj]
    ]

strongCondition[vj_, mg_, mh_, i_, j_] :=
    Block[{u1, u2, v1, v2},
       {u1, u2} = vj[[i]];
       {v1, v2} = vj[[j]];

       Or[
         u1 === v1 && (mh[[u2, v2]] != 0 || mh[[v2, u2]] != 0),
         u2 === v2 && (mg[[u1, v1]] != 0 || mg[[v1, u1]] != 0),
         (mg[[u1, v1]] != 0 || mg[[v1, u1]] != 0) && (mh[[u2, v2]] != 0 || mh[[v2, u2]] != 0)
       ]
    ]

Then test it:

g = h = CycleGraph[5];
j = strongGraphProduct[g, h]

enter image description here

Some properties:

{VertexCount[j], EdgeCount[j]}
(* {25, 100} *)
POSTED BY: Greg Hurst
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract