Function Repository Resource:

# ToDirectedAcyclicGraph

Convert any undirected graph to a cycle-free directed graph

 ResourceFunction["ToDirectedAcyclicGraph"][g,v0] updates undirected graph g by assigning directions to edges, such that directions point along shortest paths from any one initial vertex v0 to all others. ResourceFunction["ToDirectedAcyclicGraph"][g,{v1,v2,…}] returns a directed acyclic conversion of graph g with directions indicating shortest paths from the nearest initial vertex vi.

## Details

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 vi with a graph distance di. Then when an edge goes between vertices vi and vj, so long as di<dj, the assigned direction is from vi to vj.
Distance di is defined using GraphDistance as follows:
 for one initial vertex v0 di=GraphDistance[g,v0,vi] for many initial vertices {v1,v2 , …} di=Min[GraphDistance[g,#,vi]&/@{v1,v2,…}]
A difficulty arises with conflicted edges, which join two vertices vi and vj with di==dj.
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[{v1,v2},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.

## Examples

### Basic Examples (2)

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

### Scope (3)

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

### Options (3)

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

### Properties and Relations (2)

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

### Possible Issues (3)

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

### Neat Examples (2)

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