# How can one calculate the co-normal (disjunctive/or) product of two graphs in Wolfram Language?

I'm trying to verify a result in Wolfram Cloud. The standard cartesian graph product is implemented. Graph join is implemented. But it seems that the co-normal product does not seem to be, and honestly as easy as it should be to code the function myself, I have no idea where to begin.

I'm really new with the language, so I don't even know how I would code a function that would create a new graph, where there's an edge between (a, b) and (c, d) iff there's an edge between a and c or between b and d.

• Do you mean that definition? Commented Aug 31, 2021 at 15:10
• Yes, the co-normal product as defined there, or in other words, what I stated above as (a, b) ~ (c, d) iff a ~ c or b ~ d. Commented Aug 31, 2021 at 15:18

As noted in this Community post, the conormal/disjunctive product can be implemented like so for unweighted graphs:

conormalProduct[g1_?GraphQ, g2_?GraphQ, opts : OptionsPattern[GraphProduct]] :=
KroneckerProduct[ConstantArray[1, Dimensions[m1]], m2] +
KroneckerProduct[m1, m2], 2], opts]]

Using kglr's example,

g1 = Graph[{1 <-> 2, 2 <-> 3, 3 <-> 1}];
g2 = Graph[{a <-> b, c <-> a}];
conormalProduct[g1, g2, EdgeShapeFunction -> "CurvedArc"]

In fact, the disjunctive product is actually built-in as GraphProduct[g1, g2, "Conormal"], but the internal implementation seems to be quite a bit slower.

Here's what I came up with. It's messy, but it seems to work. I'm sure someone would be able to do a better implementation. I don't even know how to store a result so I don't have to type out cpF[cpF[VertexList[g1], VertexList[g2]],cpF[VertexList[g1], VertexList[g2]]], nor can I figure out why Cartesian Product of a list isn't working normally, thus why I used the cpF function that I found somewhere else.

cpF = Distribute[{##}, List] &;

edgeQS[g_, e : {_, _}] := Or @@ (EdgeQ[g, #] & /@ {DirectedEdge @@ e,
DirectedEdge @@ Reverse[e], UndirectedEdge @@ e});

edgeBetweenQ[g1_, g2_, e1_, e2_]:= {e1<-> e2, edgeQS[g1, {e1[[1]], e2[[1]]}] || edgeQS[g2, {e1[[2]], e2[[2]]}]};

samePairQ[e1_, e2_] := e1 === e2 || e1 === Reverse[e2];

coedges[g1_, g2_] := Map[edgeBetweenQ[g1, g2, #[[1]] , #[[2]]]&, cpF[cpF[VertexList[g1], VertexList[g2]],cpF[VertexList[g1], VertexList[g2]]]];

conorm[g1_, g2_] :=  Graph[DeleteDuplicates[Map[#[[1]] &, Select[coedges[g1, g2],#[[2]] &]], samePairQ]];
• +1. I test it at conorm[Graph[{1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3, 3 \[UndirectedEdge] 1}], Graph[{a \[UndirectedEdge] b, c \[UndirectedEdge] a}]]. A good code is a commented code. You wrote "can I figure out why Cartesian Product of a list isn't working normally". I think there is a conflikt between the Combinatorica package and WL. Commented Aug 31, 2021 at 19:13
• No idea how to even use comments in Wolfram Language. I selected Wolfram simply because it had useful graph operations, and I assumed co-normal product would be in there already. But apparently not! Commented Aug 31, 2021 at 19:17

Perhaps something like:

ClearAll[coNormalProduct]
coNormalProduct[g__?UndirectedGraphQ, opts : OptionsPattern[Graph]] :=
RelationGraph[Or @@ MapThread[EdgeQ, {{g}, UndirectedEdge @@@ Transpose[{##}]}] &,
Tuples[VertexList /@ {g}], opts, EdgeShapeFunction -> "CurvedArc"]

Example:

g1 = Graph[{1 <-> 2, 2 <-> 3, 3 <-> 1}];
g2 = Graph[{a <-> b, c <-> a}];

coNormalProduct[g1, g2]

coNormalProduct[g1, g2, g1, ImageSize -> Large, VertexLabels -> "Name"]

• I'm not familiar with Wolfram Language enough to be sure, but does seem like it. Much more concise than what I provided. Commented Aug 31, 2021 at 23:15