10
$\begingroup$

According to MathWorld >> GraphJoin, Mathematica could compute the join of two graphs with the GraphJoin command, part of Combinatorica. This command no longer works as of v10, and I cannot find a replacement. I want something like:

GraphJoin[PathGraph[{a, b}], PathGraph[{c, d, e}]]

To produce $G_1+G_2$ below.

Join of two path graphs

Improve this question
$\endgroup$

2 Answers 2

Reset to default
9
$\begingroup$

GraphComputation`GraphJoin

GraphComputation`GraphJoin[PathGraph[{a, b}], PathGraph[{c, d, e}], 
 VertexLabels -> "Name", ImagePadding -> 10, 
 GraphLayout -> "MultipartiteEmbedding"]

enter image description here

This undocumented function works in both version 9.0 and version 11.3.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks! Knew it had to be somewhere, but it sure isn't documented anywhere that I could find. $\endgroup$
    – Bryan Clair
    Commented Jan 2, 2018 at 6:30
  • $\begingroup$ @Bryan, my pleasure. Thank you for the accept. $\endgroup$
    – kglr
    Commented Jan 2, 2018 at 6:32
  • $\begingroup$ Unrelated question: Do you know if there's a fast way to retrieve EdgeCapacity, comparable to how GraphComputation`WeightValues retrieves EdgeWeight much faster than PropertyValue or Options can? $\endgroup$
    – Szabolcs
    Commented Jan 2, 2018 at 9:14
  • $\begingroup$ @Szabolcs, i don't remember seeing any function that does it; and I think I learned about GraphComputation`WeightValues from a post of yours. $\endgroup$
    – kglr
    Commented Jan 2, 2018 at 9:34
7
$\begingroup$

The function you reference still works fine, but it is part of the Combinatorica package. You need to load the package first, and work with Combinatorica's own graph datatype. Combinatorica precedes Mathematica's built-in graph datatype by many years, and is not interoperable with it.

That said, it is relatively easy to implement an equivalent function for built-in Graph objects as well:

graphJoin1[g1_?GraphQ, g2_?GraphQ, opt : OptionsPattern[]] :=
  GraphUnion[
    GraphDisjointUnion[g1, g2], 
    CompleteGraph[{VertexCount[g1], VertexCount[g2]}], 
    opt
  ]

graphJoin1[PathGraph[{a, b}], PathGraph[{c, d, e}],
 VertexLabels -> "Name", GraphLayout -> "MultipartiteEmbedding"]

enter image description here

If you want to preserve vertex names (when the original vertex sets are disjoint), you can write a slightly more complicated function:

graphJoin2[g1_?GraphQ, g2_?GraphQ, opt : OptionsPattern[]] := 
 With[{g = graphJoin1[g1, g2, opt], vl1 = VertexList[g1], vl2 = VertexList[g2]},
   If[DisjointQ[vl1, vl2],
     VertexReplace[g, Thread[VertexList[g] -> Join[vl1, vl2]]],
     g
   ]
 ]

This solution uses only supported and documented functionality.

The original version of this answer used the implementation

graphJoin[g1_?UndirectedGraphQ, g2_?UndirectedGraphQ, opt : OptionsPattern[Graph]] :=
 Graph[
   Join[
     EdgeList@IndexGraph[g1],
     EdgeList@IndexGraph[g2, VertexCount[g1] + 1],
     EdgeList@CompleteGraph[{VertexCount[g1], VertexCount[g2]}]
   ],
   opt
 ]
Improve this answer
$\endgroup$

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.