Wolfram Research

Function Repository Resource:

BranchialHypergraph

Source Notebook

Compute the branchial hypergraph of a graph

Contributed by: Nikolay Murzin

ResourceFunction["BranchialHypergraph"][g]

computes the branchial hypergraph of a graph g.

Details

A branchial hypergraph consists of ordered hyperedges encoding the ancestry degree of separation between an initial vertex and other vertices. For example, hyperedge {a,b,c,d} means that vertices a and b have an immediate common ancestor, a and c have a common ancestor of degree 2 (an ancestor at maximum distance of 2 from both a and c), and vertices a and d have a common ancestor of degree 3.
Vertices without any branchpairs will result in an unary hyperedge.

Examples

Basic Examples (3) 

Compute branchial hyperedges of a simple graph:

In[1]:=
ResourceFunction["BranchialHypergraph"][\!\(\*
GraphicsBox[
NamespaceBox["NetworkGraphics",
DynamicModuleBox[{Typeset`graph = HoldComplete[
Graph[{$CellContext`i, $CellContext`a, $CellContext`e, \
$CellContext`b, $CellContext`c, $CellContext`d}, {{{1, 2}, {2, 3}, {1,
          4}, {4, 5}, {5, 6}}, Null}, {
        VertexLabels -> {Automatic}}]]}, 
TagBox[GraphicsGroupBox[{
{Hue[0.6, 0.7, 0.5], Opacity[0.7], Arrowheads[Medium], ArrowBox[{{{0.4767312946227961, 2.8603877677367766`}, {0., 1.9069251784911843`}}, {{0.4767312946227961, 2.8603877677367766`}, {0.9534625892455922, 1.9069251784911843`}}, {{0., 1.9069251784911843`}, {0., 0.9534625892455921}}, {{0.9534625892455922, 1.9069251784911843`}, {0.9534625892455922, 0.9534625892455921}}, {{0.9534625892455922, 0.9534625892455921}, {0.9534625892455922, 0.}}}, 0.029229881084280332`]}, 
{Hue[0.6, 0.2, 0.8], EdgeForm[{GrayLevel[0], Opacity[
          0.7]}], {
           DiskBox[{0.4767312946227961, 2.8603877677367766}, 0.029229881084280332], InsetBox["i", Offset[{2, 2}, {0.5059611757070764, 2.8896176488210568}], ImageScaled[{0, 0}],
BaseStyle->"Graphics"]}, {
           DiskBox[{0., 1.9069251784911843}, 0.029229881084280332], InsetBox["a", Offset[{2, 2}, \
{0.029229881084280332, 1.9361550595754646}], ImageScaled[{0, 0}],
BaseStyle->"Graphics"]}, {
           DiskBox[{0., 0.9534625892455921}, 0.029229881084280332], InsetBox["e", Offset[{2, 2}, \
{0.029229881084280332, 0.9826924703298725}], ImageScaled[{0, 0}],
BaseStyle->"Graphics"]}, {
           DiskBox[{0.9534625892455922, 1.9069251784911843}, 0.029229881084280332], InsetBox["b", Offset[{2, 2}, {0.9826924703298726, 1.9361550595754646}], ImageScaled[{0, 0}],
BaseStyle->"Graphics"]}, {
           DiskBox[{0.9534625892455922, 0.9534625892455921}, 0.029229881084280332], InsetBox["c", Offset[{2, 2}, {0.9826924703298726, 0.9826924703298725}], ImageScaled[{0, 0}],
BaseStyle->"Graphics"]}, {
           DiskBox[{0.9534625892455922, 0.}, 0.029229881084280332], InsetBox["d", Offset[{2, 2}, \
{0.9826924703298726, 0.029229881084280332}], ImageScaled[{0, 0}],
BaseStyle->"Graphics"]}}}],
MouseAppearanceTag["NetworkGraphics"]],
AllowKernelInitialization->False]],
DefaultBaseStyle->{
     "NetworkGraphics", FrontEnd`GraphicsHighlightColor -> Hue[0.8, 1., 0.6]},
FormatType->TraditionalForm,
FrameTicks->None,
ImageSize->{56.137833437344256`, Automatic}]\)]
Out[1]=

Branchial hypergraph of a mixed graph:

In[2]:=
ResourceFunction["BranchialHypergraph"][\!\(\*
GraphicsBox[
NamespaceBox["NetworkGraphics",
DynamicModuleBox[{Typeset`graph = HoldComplete[
Graph[{1, 2, 3, 4, 5}, {{{1, 2}, {1, 4}, {3, 5}}, {{1, 3}, {3, 4}}}, {
        VertexLabels -> {Automatic}}]]}, 
TagBox[GraphicsGroupBox[{
{Hue[0.6, 0.7, 0.5], Opacity[0.7], Arrowheads[Medium], 
{Arrowheads[0.], ArrowBox[{{2.123724619186534, 0.2848465012502784}, {
            1.0246020231662252`, 0.28468259702878873`}}, 0.031290867382760074`]}, ArrowBox[{{2.123724619186534, 0.2848465012502784}, {
           3.147903408145563, 0.}}, 0.031290867382760074`], ArrowBox[{{2.123724619186534, 0.2848465012502784}, {
           1.5742315378161784`, 0.9655937588020892}}, 0.031290867382760074`], 
{Arrowheads[0.], ArrowBox[{{1.0246020231662252`, 0.28468259702878873`}, {
            1.5742315378161784`, 0.9655937588020892}}, 0.031290867382760074`]}, ArrowBox[{{1.0246020231662252`, 0.28468259702878873`}, {0., 0.00016831547416262804`}}, 0.031290867382760074`]}, 
{Hue[0.6, 0.2, 0.8], EdgeForm[{GrayLevel[0], Opacity[
          0.7]}], {
           DiskBox[{2.123724619186534, 0.2848465012502784}, 0.031290867382760074], InsetBox["1", Offset[{2, 2}, {2.1550154865692943, 0.31613736863303843}],
             ImageScaled[{0, 0}],
BaseStyle->"Graphics"]}, {
           DiskBox[{3.147903408145563, 0.}, 0.031290867382760074], InsetBox["2", Offset[{2, 2}, {3.179194275528323, 0.031290867382760074}],
             ImageScaled[{0, 0}],
BaseStyle->"Graphics"]}, {
           DiskBox[{1.0246020231662252, 0.28468259702878873}, 0.031290867382760074], InsetBox["3", Offset[{2, 2}, {1.0558928905489853, 0.31597346441154883}],
             ImageScaled[{0, 0}],
BaseStyle->"Graphics"]}, {
           DiskBox[{1.5742315378161784, 0.9655937588020892}, 0.031290867382760074], InsetBox["4", Offset[{2, 2}, {1.6055224051989385, 0.9968846261848493}], ImageScaled[{0, 0}],
BaseStyle->"Graphics"]}, {
           DiskBox[{0., 0.00016831547416262804}, 0.031290867382760074], InsetBox["5", Offset[{2, 2}, \
{0.031290867382760074, 0.0314591828569227}], ImageScaled[{0, 0}],
BaseStyle->"Graphics"]}}}],
MouseAppearanceTag["NetworkGraphics"]],
AllowKernelInitialization->False]],
DefaultBaseStyle->{
     "NetworkGraphics", FrontEnd`GraphicsHighlightColor -> Hue[0.8, 1., 0.6]},
FormatType->TraditionalForm,
FrameTicks->None,
ImageSize->{147., Automatic}]\)]
Out[2]=

The branchial hypergraph of any undirected graph is trivial:

In[3]:=
ResourceFunction["BranchialHypergraph"][RandomGraph[{10, 25}]]
Out[3]=

Scope (2) 

Make a branchial hypergraph for a simple string substitution multiway system:

In[4]:=
ResourceFunction[
 "MultiwaySystem"][{"A" -> "AB", "A" -> "BA"}, "A", 2, "StatesGraph"]
Out[4]=

Display the branchial hypergraph using an Echo while plotting the graph:

In[5]:=
ResourceFunction["WolframModelPlot"][
 Echo@ResourceFunction["BranchialHypergraph"]@%, Sequence @@ ResourceFunction["WolframPhysicsProjectStyleData"][
    "BranchialGraph"]["Options"], VertexLabels -> Automatic]
Out[5]=

Properties and Relations (1) 

Usually the branchial graph can be recovered from the hypergraph by taking the first two vertices from each hyperedge:

In[6]:=
GraphicsRow[{
  ResourceFunction[
   "MultiwaySystem"][{"A" -> "AB", "A" -> "BA", "A" -> "BB"}, "A", 4, "AllStatesBranchialGraphStructure"], SimpleGraph[
   If[Length@# > 1, UndirectedEdge @@ Take[#, 2], Nothing] & /@ ResourceFunction["BranchialHypergraph"][
     ResourceFunction[
      "MultiwaySystem"][{"A" -> "AB", "A" -> "BA", "A" -> "BB"}, "A", 4, "StatesGraph"]],
   Sequence @@ ResourceFunction["WolframPhysicsProjectStyleData"][
      "BranchialGraph"]["Options"]]
  }, Frame -> All]
Out[6]=

Resource History

Related Resources

License Information