Function Repository Resource:

# DirectedAcyclicEvaluate (1.0.0)current version: 2.0.0 »

Evaluate functions locally over any directed acyclic graph

Contributed by: Bradley Klee  |  Brad Klee
 ResourceFunction["DirectedAcyclicEvaluate"][graph,rules] assigns values to the vertices of a directed acyclic graph by recursively summing over preceding values, starting from initial values listed in rules. ResourceFunction["DirectedAcyclicEvaluate"][graph,rules,vfun] allows for a wide range of calculations via specified function vfun, which evaluates locally on each vertex (see details). ResourceFunction["DirectedAcyclicEvaluate"][expr] allows specification of expr as an Association with the keys "Graph", "VertexWeights", "VertexFunction", and optionally "EdgeWeights".

## Details

Graph vertices can be thought of as named memory locations for both inputs and outputs.
Evaluation distinguishes inputs as the set of root vertices not pointed to by any directed edge (sources).
All other vertices reached by following directed edges are considered outputs.
A vertex vi and its edge vivj are both said to precede another vertex vj, if the graph indeed contains edge vivj.
Values (or weights) wi are assigned to vertices vi using rules of the form viwi.
Input rules should list viwi for all input vertices vi.
If input values are missing from rules, vertex names vi are assumed as values.
If rules includes a rule for an output vertex vi, the associated value is ignored and overwritten upon evaluation.
Function vfun accepts three arguments parallel over index i:
 #1 a list of values wi on all vertices vi preceeding vj #2 a list of edge weights wij for each preceeding edge vivj #3 a list of all preceeding edges vivj
If vfun is specified as a symbol sym (such as Times or Plus), then vfun=sym@@#1&.
Unless the option EdgeWeights is specified, #2=#3.
Optional specification of EdgeWeights → {(vivj)wij,(vkvl)wkl,} may simplify some calculations.
Setting EdgeWeights as above then causes #2=#3/.{(vivj)wij,(vkvl)wkl,}.
ResourceFunction["DirectedAcyclicEvaluate"] also acts as Evaluate on an Unevaluated expr, which is formatted as an Association.
Association expr has a primary key "Graph", which should point to a directed acyclic graph.
Optional Keys of the Association and their default values are:
 "VertexWeights" {} a list of function values "VertexFunction" Plus determines how to fold over incoming values "EdgeWeights" {} weights or phases per graph edge
The Association expr is then effectively its own type of expression, which should have a definite evaluation.
Any expr that conforms to the schema outlined above should ultimately be easy to compile for optimized evaluation.
Ultimately, MultiwayEvaluate returns a complete Association listing all function values under key "VertexWeights".
The output Association is certified in the sense that it is locally checkable on every graph vertex.

## Examples

### Basic Examples (3)

Enumerate the first few terms of the Fibonacci sequence:

 In[1]:=
 Out[1]=

Compare with pre-compiled function Fibonacci:

 In[2]:=
 Out[2]=

Depict the Fibonacci calculation on its directed graph:

 In[3]:=
 Out[3]=

### Scope (5)

Count walks on a directed grid:

 In[4]:=
 Out[4]=

Count the leaves on a random tree:

 In[5]:=
 Out[5]=

Evaluate a Factorial number using binary splitting:

 In[6]:=
 Out[6]=

Use symbolic functions to create an encoding of 24 branching and merging traversals of a hypercube:

 In[7]:=
 Out[7]=

Split path symbols based on parity of the outgoing and incoming vertices:

 In[8]:=
 Out[8]=

### Properties and Relations (2)

Valid output Associations should cause the following check function to list zeroes:

 In[9]:=

Double check a p-recurrence important to the theory of algebraic sphere curves (cf. OEIS A318495):

 In[10]:=
 Out[10]=

### Possible Issues (3)

Invalid inputs result in a failure message:

 In[11]:=
 Out[11]=
 In[12]:=
 Out[12]=

MultiwayEvaluate ignores double edges:

 In[13]:=
 Out[13]=

If necessary, a corrected input could assign factor of 2 via EdgeWeights:

 In[14]:=
 Out[14]=

### Neat Examples (4)

Calculate a Fourier transform with only n Log2 n complexity (n=32):

 In[15]:=
 Out[15]=

Calculate the first few Fubini numbers (OEIS A000670):

 In[16]:=
 Out[16]=

Count corner-to-corner walks on three-dimensional grids:

 In[17]:=
 Out[17]=

Compare with series expansion of Ramanujan's elliptic integrals:

 In[18]:=
 Out[18]=

Count corner-to-corner walks on the cells of MengerMesh when n=2:

 In[19]:=
 Out[19]=

Repeat this calculation for sequential inputs, then output maximum path counts:

 In[20]:=
 Out[20]=

Try a similar calculation for the Menger sponge (a.k.a. MengerMesh with d=3):

 In[21]:=
 Out[21]=

## Version History

• 2.0.0 – 08 November 2022
• 1.1.0 – 03 May 2022
• 1.0.0 – 11 April 2022

## Author Notes

Significant revisions to improve Vertex Function + Rename + more better examples (also fixed typo).