Scratch Items


FoliationGraph algorithm

At each step, add a slice that contains allowed nodes, which are nodes “down graph” from the existing ones....
Assume that we always go at most one generation for each slices....
In[]:=
GraphSources[graph_]:=Pick[VertexList@graph,VertexInDegree@graph,0]
In[]:=
FoliationGraph[g_,t_:100000]:=With[{res=NestGraph[m@@@NextSlices[g,List@@#]&,m@@@Subsets[GraphSources[g]],t]},VertexReplace[res,#->List@@#&/@VertexList[res]]]
(*NextSlices[g_,current_]:=Rest[Union[Union/@(Tuples[Append[#,Null]&/@(VertexOutComponent[g,#,{1}]&/@current)]/.Null->Nothing)]]*)
In[]:=
GraphFoliationGraph
,VertexLabelsAutomatic
Out[]=
In[]:=
NextSlices[g_,current_]:=DeleteCases[Union[Union[Complement[#,current]]&/@Rest[Subsets[VertexOutComponent[g,current,{1}]]]],{}]
In[]:=
GraphFoliationGraph
,VertexLabelsAutomatic
Out[]=
In[]:=
MultiwayMatrix[{m1_,m2_},t_Integer]:=With[{g=NestGraph[(f/@{m1.First[#],m2.First[#]})&,{f[{1,1}]},t]},g]
In[]:=
MultiwayMatrix[{m1_,m2_},t_Integer,VertexLabelsAutomatic]:=With[{g=NestGraph[(f/@{m1.First[#],m2.First[#]})&,{f[{1,1}]},t]},Graph[g,VertexLabels((#InputForm[First[#]])&/@VertexList[g])]]
In[]:=
orig=SimpleGraph[MultiwayMatrix[{{{1,0},{1,1}},{{1,1},{0,0}}},4,VertexLabelsAutomatic]]
Out[]=
In[]:=
Graph[FoliationGraph[orig],VertexLabelsPlaced[Automatic,Tooltip],GraphLayout"LayeredDigraphEmbedding",AspectRatio1]
Out[]=
In[]:=
GraphSinks[%141]//Length
Out[]=
63
In[]:=
FindRandomPath[g_]:=First[FindPath[g,RandomChoice[GraphSources[g]],RandomChoice[GraphSinks[g]]]]
In[]:=
Framed/@FindRandomPath[%150]
Out[]=

{f[{1,1}]}
,
{f[{1,2}],f[{2,0}]}
,
{f[{1,3}],f[{2,2}]}
,
{f[{1,4}],f[{2,4}]}
,
{f[{1,5}],f[{2,6}],f[{5,0}]}

In[]:=
Flatten[MapIndexed[#->First[#2]&,FindRandomPath[%150],{2}]]
Out[]=
{f[{1,1}]1,f[{1,2}]2,f[{1,3}]3,f[{3,0}]3,f[{3,3}]4,f[{4,0}]4,f[{4,4}]5,f[{6,0}]5}
In[]:=
Graph[orig,VertexLabels->%]
Out[]=

Another Try