Function Repository Resource:

MultiwayDeletionsGraph

Source Notebook

Explore graph traversals while deleting visited components

Contributed by: Bradley Klee

ResourceFunction["MultiwayDeletionsGraph"][g]

returns a directed acyclic graph which maps all possible traversals of graph g while deleting vertices along the way.

ResourceFunction["MultiwayDeletionsGraph"][g,v₁]

traverses graph g starting only from initial vertex v₁.

ResourceFunction["MultiwayDeletionsGraph"][g,{v₁,v₂,…,v_n}]

traverses graph g starting from n initial vertices v_i.

ResourceFunction["MultiwayDeletionsGraph"][g,{v₁,v₂,…,v_n},method]

allows deleting edges by setting method equals EdgeDelete.

ResourceFunction["MultiwayDeletionsGraph"][g,{v₁,v₂,…,v_n},method,max]

introduces a cutoff max for cases where the state space graph g is too large to explore efficiently.

Details

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

Vertex names of a ResourceFunction["MultiwayDeletionsGraph"] output depend on a method, either VertexDelete or EdgeDelete:

w₁={{},v₁}

an initial condition for either method, where v₁∈VertexList[g]

w_n={Sort[{v₁,v₂,…,v_n-1}],v_n}

with v_i∈VertexList[g] and w_n∈VertexList[ResourceFunction["MultiwayDeletionsGraph"][g,v₁]]

w_n={Sort[{e₁,e₂,…,e_n-1}],v_n]

withe_i∈EdgeList[g]andw_n∈VertexList[ResourceFunction["MultiwayDeletionsGraph"][g,v₁,EdgeDelete]]

Each vertex records an unordered list of vertices or edges visited as well as a current location.

Two vertices w_n and w_n-1 are adjacent in the output of ResourceFunction["MultiwayDeletionsGraph"] if and only if the following conditions are met, where edge can be either DirectedEdge or UndirectedEdge:

method=VertexDelete

First[w_n]==First[w_n-1]⋃{v_n}&&GraphDistance[g,Last[w_n-1],Last[w_n]]⩵1

method=EdgeDelete

First[w_n]==First[w_n-1]⋃{edge[v_n-1,v_n]}&& GraphDistance[g,Last[w_n-1],Last[w_n]]⩵1

In general, paths through a multiway deletions graph are said to be confluent whenever it is possible to find different valid orderings of the unordered First[w_n] which fix the endpoint Last[w_n]. Here, "valid" means that, per chosen ordering, each pair of successive vertices w_i and w_i-1 must satisfy the adjacency criteria.

Examples

Basic Examples (2)

Plot two pairs of confluent self-avoiding walks on a 2×2 GridGraph:

In[1]:=

Out[1]=

Add labels to see which vertices where visited when:

In[2]:=

$Row[{GridGraph[{2, 2}, ImageSize -> 50, VertexLabels -> (x_ :> Placed[x, Center]), VertexSize -> Large, EdgeStyle -> Darker[Gray, .8], VertexStyle -> Directive[White, EdgeForm[LightGray]]], Style[" \[LongRightArrow] ", Gray, Bold, 24], Grid[{WeaklyConnectedGraphComponents@ ResourceFunction["MultiwayDeletionsGraph"][GridGraph[{2, 2}], VertexLabels -> (x_ :> Placed[Last[x], Center]), VertexStyle -> Directive[White, EdgeForm[Gray]], EdgeStyle -> Gray, GraphLayout -> "LayeredDigraphEmbedding", VertexSize -> 1/2, ImageSize -> 200, AspectRatio -> 1/2]}, Frame -> All, FrameStyle -> LightGray, Spacings -> {1, 1}]}]$

Out[2]=

Graph self-avoiding walks on a 3×3 grid:

In[3]:=

Out[3]=

Only compute the subgraph starting from vertex 5:

In[4]:=

Out[4]=

Decorate the graph with publication-quality icons:

In[5]:=

With[{StyledDeletionsGraph = Function[{mdg, ing, ivs, vs},
Graph[mdg, VertexSize -> vs, EdgeStyle -> Gray,
VertexShapeFunction -> (Inset[HighlightGraph[Graph[ing, VertexStyle -> Directive[EdgeForm[GrayLevel[.4]], GrayLevel[.7]],
EdgeStyle -> Gray], {Style[First[#2], Hue[.55, 1, 0.9],
EdgeForm[GrayLevel[0, 0.25]]],
Style[Last[#2], Red, EdgeForm[GrayLevel[0, 0.25]]]},
VertexSize -> ivs, ImageSize -> 30], #1, Center, #3] &),
PerformanceGoal -> "Quality"]]},
StyledDeletionsGraph[
ResourceFunction["MultiwayDeletionsGraph"][GridGraph[{3, 3}], {5}],
GridGraph[{3, 3}], .75, 1.5]]

Out[5]=

Allow walks from vertex 5 to intersect on vertices, but not on edges:

In[6]:=

Out[6]=

Again, decorate the graph with publication-quality icons:

In[7]:=

$With[{StyledDeletionsGraph = Function[{mdg, ing, ivs, vs}, Graph[mdg, VertexSize -> vs, EdgeStyle -> Gray, VertexShapeFunction -> (Inset[HighlightGraph[Graph[ing, VertexStyle -> Directive[EdgeForm[GrayLevel[.4]], GrayLevel[.7]], EdgeStyle -> Directive[Darker@Gray, Thick]], {Style[ First[#2], Red, EdgeForm[GrayLevel[0, 0.25]]], Style[Last[#2], \!$\* TagBox[ StyleBox[ RowBox[{"Hue", "[", RowBox[{"0.08`", ",", "1", ",", "1"}], "]"}], ShowSpecialCharacters->False, ShowStringCharacters->True, NumberMarks->True, "NodeID" -> 26], FullForm]$, EdgeForm[GrayLevel[0, 0.25]]]}, VertexSize -> ivs, ImageSize -> 30], #1, Center, #3] &), PerformanceGoal -> "Quality"]]}, StyledDeletionsGraph[ ResourceFunction["MultiwayDeletionsGraph"][GridGraph[{3, 3}], 5, EdgeDelete], GridGraph[{3, 3}], .75, 3.5]]$