Function Repository Resource:

FixedPointGraph

Source Notebook

Obtain the graph of an iterative computation to a fixed point

Contributed by: Bradley Klee

ResourceFunction["FixedPointGraph"][f,expr]

gives the graph obtained by starting with expr and applying f until a fixed point is reached.

ResourceFunction["FixedPointGraph"][f,{expr₁,expr₂,…}]

gives the graph obtained by applying f to expr₁,expr₂,….

ResourceFunction["FixedPointGraph"][f,…,max]

applies f at most max times.

Details

ResourceFunction["FixedPointGraph"] takes all the options of Graph.

FixedPointGraph also takes a few options that enable canonicalization of states.

When setting "CanonicalSignature" → sig, two states expr₁and expr₂ are regarded as equivalent when sig[expr₁]==sig[expr₂]. The earliest-appearing expr is chosen as a representatitve of the class.

When more than one sig-equivalent expr is newly seen on the same time step, the first is chosen after sorting by ord, a function that is set through "SortFunction" → ord. The default value is Sort.

If signature based canonicalization is not necessary, "CanonicalTransform"→ form allows specification of a function which obtains a canonical form for any expr via direct calculation of form[expr].

State canonicalization is useful in ennumerative combinatorics, as is seen in the Neat Example from game theory below.

Examples

Basic Examples (4)

Generate a cycle graph:

In[1]:=

Out[1]=

Generate a torus graph:

In[2]:=

Out[2]=

Check graph isomorphism to TorusGraph:

In[3]:=

Out[3]=

The graph of a bifurcating integer calculation toward zero:

In[4]:=

Out[4]=

Set a limit for an unbounded calculation:

In[5]:=

Out[5]=

Scope (2)

Iterate through floating point approximations to Sqrt[2]:

In[6]:=

Out[6]=

Count the number of steps needed:

In[7]:=

Out[7]=

Graph different approaches to sorting characters in a string:

In[8]:=

abg = ResourceFunction["FixedPointGraph"][Function[word,
StringReplacePart[word, "AB", #] & /@ StringPosition[word, "BA"]
], "ABABABBA"]

Out[8]=

Verify the result is sorted:

In[9]:=

Out[9]=

Options (2)

Add styles to vertices and edges:

In[10]:=

$ResourceFunction["FixedPointGraph"][ Function[pt, MapAt[Mod[# + 1, 4] &, pt, #] & /@ {1, 2}], {{0, 0}}, VertexStyle -> Directive[EdgeForm[Opacity[.5]], Darker@Green], VertexSize -> 1/4, EdgeStyle -> (x_ :> Association[1 -> Red, 2 -> Blue][ Position[Subtract @@ x, 0][[1, 1]]]) ]$

Out[10]=

Compare to CayleyGraph:

In[11]:=

Out[11]=

Find the relation between integer Tuples when applying RotateRight:

In[12]:=

Out[12]=

Consider states equivalent by their Total:

In[13]:=

Out[13]=

Choose a different canonical form by adding "SortFunction":

In[14]:=

ResourceFunction["FixedPointGraph"][{RotateRight[#]} &, Tuples[Range[0, 1], 3],
"CanonicalSignature" -> Total, "SortFunction" -> ReverseSort,
VertexLabels -> Automatic]

Out[14]=

Another way to achieve the same result:

In[15]:=

ResourceFunction["FixedPointGraph"][{RotateRight[#]} &, Tuples[Range[0, 1], 3],
"CanonicalTransform" -> Function[First[ReverseSort[Permutations[#]]]],
VertexLabels -> Automatic]

Out[15]=

Applications (2)

Investigate different trajectories of a sorting algorithm:

In[16]:=

$With[{subValues = {HoldPattern[ iterateSort[0][ Pattern[sample, Blank[]]]] :> Hold[ Catenate[ Map[iterateSort[#][sample]& , 2^Range[0, Log[2, Length[sample]/2]]]]], HoldPattern[ iterateSort[ Pattern[len, Blank[]]][ Pattern[sample, Blank[]]]] :> Module[{parted, pos}, parted = Select[ Part[ Partition[ Partition[ Range[ Length[sample]], len, 1], 1 + len, 1], All, {1, 1 + len}], Order[ Part[sample, Part[#, 1]], Part[sample, Part[#, 2]]] == -1& ]; Map[ReplacePart[sample, Join[ Thread[Part[#, 1] -> Part[sample, Part[#, 2]]], Thread[Part[#, 2] -> Part[sample, Part[#, 1]]]]]& , parted]]}, init = {4, 3, 2, 1}}, sortg = ResourceFunction["FixedPointGraph"][ ReleaseHold[iterateSort[0][#] //. subValues] &, {init}, VertexLabels -> (x_ :> Row[x])]]$

Out[16]=