# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Depict branch-like connections between components of a directed acyclic graph

Contributed by:
Bradley Klee

ResourceFunction["BranchialGraphs"][ returns an Association of time-indexed graphs, whose edges indicate which simultaneous vertices of | |

ResourceFunction["BranchialGraphs"][ only computes components at times |

ResourceFunction["BranchialGraphs"] takes the same options as Graph.

Two vertices *v*_{j} and *v*_{k} are have branch-like separation if *g* contains a vertex *v*_{i} and a pair of edges *v*_{i}→*v*_{j} and *v*_{i}→*v*_{k}.

Branch-like separation is necessary, but not sufficient, for an edge between *v*_{j} and *v*_{k} to appear in a branchial graph of *g*.

A foliation of the vertices of *g* is a partitioning of *g*-vertices into time-ordered subsets (preferably also an exact cover).

Vertices *v*_{j} and *v*_{k} must also satisfy a simultaneity condition, which depends on choice of a foliation.

ResourceFunction["BranchialGraphs"] takes an additional option of the form: "Foliation" → {{*v*_{1},*v*_{2},…,*v*_{n}}, {*v*_{n+1},*v*_{n+2},…,*v*_{n+m}}, …, {*v*_{x},*v*_{x+1},…,*v*_{x+y}}}.

The default "Foliation" lists a vertex in a subset as soon as its entire VertexInComponent is covered by preceding subsets.

If a specified "Foliation" lists a vertex before its entire VertexInComponent is covered by preceding subsets, the algorithm will not give a valid result.

The positions of subsets in the foliation determine their Keys in the output of ResourceFunction["BranchialGraphs"].

Provided the foliation subset at time *t*_{i} includes vertices *v*_{j} and *v*_{k} from *g*, then the branchial graph at time *t*_{i} will have an edge between *v*_{j} and *v*_{k} if and only if *v*_{j} and *v*_{k} have branch-like separation.

Obtain the branchial graphs of a complete binary tree with four levels:

In[1]:= |

Out[1]= |

Branchial graphs of a complete tertiary tree with four levels:

In[2]:= |

Out[2]= |

Plot a disc graph alongside its branchial graphs:

In[3]:= |

Out[3]= |

And changing definition slightly, plot another:

In[4]:= |

Out[4]= |

Obtain the branchial graphs for a RandomGraph with almost 100 vertices:

In[5]:= |

Out[5]= |

Only compute the sixth branchial graph:

In[6]:= |

Out[6]= |

Specify foliations directly using the "Foliation" option:

In[7]:= |

Out[7]= |

Compare to the default foliations in a grid:

In[8]:= |

Out[8]= |

BranchialGraphs accepts the same style options as Graph:

In[9]:= |

Out[9]= |

BranchialGraphs expects the input graph to be directed and acyclic:

In[10]:= |

Out[10]= |

Input foliations can not include a vertex in a subset before all earlier vertices are listed in preceding subsets:

In[11]:= |

Out[11]= |

Calculate the "mergial graphs" of the nine-layer RandomGraph above:

In[12]:= |

Out[12]= |

The mergial graphs are not simply the branchial graphs of a ReverseGraph:

In[13]:= |

Out[13]= |

Compare where forward and reverse foliations agree:

In[14]:= |

Out[14]= |

- 1.0.0 – 27 June 2022

This work is licensed under a Creative Commons Attribution 4.0 International License