# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Evaluate functions locally over any directed acyclic graph

Contributed by:
Bradley Klee

ResourceFunction["DirectedAcyclicEvaluate"][ assigns values to the vertices of a directed acyclic | |

ResourceFunction["DirectedAcyclicEvaluate"][ allows for a wide range of calculations via specified function | |

ResourceFunction["DirectedAcyclicEvaluate"][ allows specification of |

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 *v*_{i} and its edge are both said to precede another vertex *v*_{j}, if the *graph* indeed contains edge .

Values (or weights) *w*_{i} are assigned to vertices *v*_{i} using rules of the form *v*_{i}→*w*_{i}.

Input *rules* should list *v*_{i}→*w*_{i} for all input vertices *v*_{i}.

If input values are missing from *rules*, vertex names *v*_{i} are assumed as values.

If *rules* includes a rule for an output vertex *v*_{i}, the associated value is ignored and overwritten upon evaluation.

Function *vfun* accepts three arguments parallel over index *i*:

#1 | a list of values w_{i} on all vertices v_{i} preceeding v_{j} |

#2 | a list of edge weights w_{ij} for each preceeding edge |

#3 | a list of all preceeding edges |

Optional specification of may simplify some calculations.

Values in #2 are obtained most efficiently using an Association, so it is possible to get a Missing["KeyAbsent",_] error if the list of EdgeWeights is incomplete.

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, ResourceFunction["DirectedAcyclicEvaluate"] 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.

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]= |

Count walks on a directed grid:

In[4]:= |

Out[4]= |

Convert to partial probabilities by adding edge weights:

In[5]:= |

Out[5]= |

Count the leaves on a random tree:

In[6]:= |

Out[6]= |

Evaluate a Factorial number using binary splitting:

In[7]:= |

Out[7]= |

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

In[8]:= |

Out[8]= |

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

In[9]:= |

Out[9]= |

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

In[10]:= |

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

In[11]:= |

Out[11]= |

Invalid inputs result in a Failure message:

In[12]:= |

Out[12]= |

In[13]:= |

Out[13]= |

DirectedAcyclicEvaluate ignores double edges:

In[14]:= |

Out[14]= |

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

In[15]:= |

Out[15]= |

Calculate a Fourier transform with only *n** *log_{2}(*n*) complexity (*n*=32):

In[16]:= |

Out[16]= |

Calculate the first few Fubini numbers (OEIS A000670):

In[17]:= |

Out[17]= |

Count corner-to-corner walks on 3D grids:

In[18]:= |

Out[18]= |

Compare with series expansion of Ramanujan's elliptic integrals:

In[19]:= |

Out[19]= |

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

In[20]:= |

Out[20]= |

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

In[21]:= |

Out[21]= |

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

In[22]:= |

Out[22]= |

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