5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Do you mean that definition? $\endgroup$
    – user64494
    Commented Aug 31, 2021 at 15:10
  • $\begingroup$ 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. $\endgroup$ Commented Aug 31, 2021 at 15:18

3 Answers 3

6
$\begingroup$

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]] := 
 With[{m1 = AdjacencyMatrix[g1], m2 = AdjacencyMatrix[g2]},
  AdjacencyGraph[Mod[KroneckerProduct[m1, ConstantArray[1, Dimensions[m2]]] +
     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"]

disjunctive product

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.

$\endgroup$
2
$\begingroup$

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]];
$\endgroup$
2
  • $\begingroup$ +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. $\endgroup$
    – user64494
    Commented Aug 31, 2021 at 19:13
  • 1
    $\begingroup$ 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! $\endgroup$ Commented Aug 31, 2021 at 19:17
2
$\begingroup$

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]

enter image description here

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

enter image description here

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.