Wolfram Research

Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

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

  • Date Created: 19 January 2021

Related Resources

License Information