# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Convert any undirected graph to a cycle-free directed graph

Contributed by:
Bradley Klee

ResourceFunction["ToDirectedAcyclicGraph"][ updates undirected graph | |

ResourceFunction["ToDirectedAcyclicGraph"][ returns a directed acyclic conversion of graph |

ResourceFunction["ToDirectedAcyclicGraph"] takes at least the same options as Graph.

ResourceFunction["ToDirectedAcyclicGraph"] enables finding shortest paths and counting them.

This is accomplished as follows: First associate every vertex *v*_{i} with a graph distance *d*_{i}. Then when an edge goes between vertices *v*_{i} and *v*_{j}, so long as *d*_{i}<*d*_{j}, the assigned direction is from *v*_{i} to *v*_{j}.

Distance *d*_{i} is defined using GraphDistance as follows:

for one initial vertex v_{0} | d_{i}=GraphDistance[g,v_{0},v_{i}] |

for many initial vertices {v_{1},v_{2} , …} | d_{i}=Min[GraphDistance[g,#,v_{i}]&/@{v_{1},v_{2},…}] |

A difficulty arises with conflicted* *edges, which join two vertices *v*_{i} and *v*_{j} with *d*_{i}==*d*_{j}.

ResourceFunction["ToDirectedAcyclicGraph"] takes two additional options specifying how to handle conflicted edges.

An optional "CollisionFunction"→*cfun* specifies a SortBy condition for vertices on a conflicted edge so that is converted to DirectedEdge@@SortBy[{*v*_{1},*v*_{2}},*cfun*].

Default assignment "CollisionFunction"→None passes collision handling to a second conditional.

With "ConflictedEdges"→False, ResourceFunction["ToDirectedAcyclicGraph"] deletes conflicted edges.

With "ConflictedEdges"→True, ResourceFunction["ToDirectedAcyclicGraph"] returns conflicted edges as undirected edges.

Determine all shortest paths on a random graph:

In[1]:= |

Out[1]= |

Verify that the output above is indeed directed and acyclic:

In[2]:= |

Out[2]= |

Explore traversal maps of a Petersen graph:

In[3]:= |

Out[3]= |

Add another Graph-exploring reference point and compare possible pairwise dance moves:

In[4]:= |

Out[4]= |

Check to see that edges are lost only on odd cycles:

In[5]:= |

Out[5]= |

Compare what happens when different initial conditions are chosen:

In[6]:= |

Out[6]= |

Acyclic directed graphs can be plotted as causal graphs by setting VertexCoordinates to Automatic:

In[7]:= |

Out[7]= |

Plot a few more causal graphs:

In[8]:= |

Out[8]= |

Resolve conflicted edges by specifying a CollisionFunction:

In[9]:= |

Out[4]= |

Check non-uniqueness of path lengths:

In[10]:= |

Out[10]= |

The transformation acts as the identity on rows of the GraphDistanceMatrix:

In[11]:= |

Out[11]= |

Using Identity as the CollisionFunction returns the same output as DirectedGraph with "Acyclic" conversion:

In[12]:= |

Out[4]= |

Specifying multiple reference points can divide the graph into disconnected components:

In[13]:= |

Out[13]= |

Inputs with disconnected components may return only one component:

In[14]:= |

Out[14]= |

This can be fixed by specifying initial vertices on each component:

In[15]:= |

Out[15]= |

The function will balk at nonsense inputs:

In[16]:= |

Out[16]= |

In[17]:= |

Out[17]= |

In[18]:= |

Out[18]= |

Count possible walks on all Petersen graph outputs:

In[19]:= |

In[20]:= |

Out[20]= |

List a sequence that does not have an entry in the OEIS:

In[21]:= |

Out[21]= |

Plot the possibly new sequence:

In[22]:= |

Out[22]= |

Conjecture the form of a linear recurrence:

In[23]:= |

Out[23]= |

Compare with depictions to try and formulate a proof argument:

In[24]:= |

Out[24]= |

Resolve conflicted edges in a square grid:

In[25]:= |

Out[25]= |

Calculate part of a numerical triangle associated with the Schroeder numbers (cf. OEIS A033877):

In[26]:= |

In[27]:= |

Out[27]= |

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