GraphFoliations
GraphFoliations
Enumerate all possible foliations of a graph
Definition
Definition
In[]:=
topVertices[g_Graph]:=Extract[VertexList[g],Position[VertexInDegree[g],0]]expandAntichains[foliations_,elem_,descendants_]:=Catenate@Map[foliation|->With[{pos=FirstPosition[foliation,_?(ContainsAny[descendants]),{Length[foliation]+1},1]},MapAt[Append[elem],foliation,#]&/@Range[pos[[1]]-1]],foliations]GraphFoliations//ClearAllGraphFoliations[g_Graph]/;DirectedGraphQ[g]&&AcyclicGraphQ[g]:=Module[{vs,newGraph},vs=topVertices[g];newGraph=VertexDelete[g,vs];If[VertexCount[newGraph]==0,ResourceFunction["SetPartitions"][vs],DeleteCases[Catenate[(foliation|->Fold[expandAntichains[#1,#2,VertexOutComponent[g,#2,1]]&,{Prepend[foliation,{}]},vs])/@GraphFoliations[newGraph]],{},{2}]]]
Documentation
Documentation
Usage
Usage
GraphFoliations[g]
returns foliations of a graph .
g
Details & Options
Details & Options
▪
GraphFoliations
Examples
Examples
Basic Examples
Basic Examples
Enumerate and highlight foliations of a graph:
In[]:=
GraphFoliationsg=
Out[]=
{{{5,1},{3},{2,6},{4}},{{5},{3,1},{2,6},{4}},{{5,1},{3},{2},{4,6}},{{5},{3,1},{2},{4,6}}}
In[]:=
HighlightGraph[g,#,VertexLabelsNone]&/@%
Out[]=
,
,
,
In[]:=
GraphFoliationsg=
Out[]=
{{{1},{2,3},{4,5,6},{7,8}},{{1},{2,3},{4,5},{7,8,6}},{{1},{2,3},{4,5,6},{7},{8}},{{1},{2,3},{4,5},{7,6},{8}},{{1},{2,3},{4,5},{7},{8,6}}}
In[]:=
HighlightGraph[g,#,VertexLabelsNone]&/@%
Out[]=
,
,
,
,
In[]:=
GraphFoliations
Out[]=
Scope
Scope
Options
Options
Applications
Applications
Properties and Relations
Properties and Relations
Possible Issues
Possible Issues
Neat Examples
Neat Examples
Source & Additional Information
Source & Additional Information
Contributed By
Contributed By
Nikolay Murzin
Keywords
Keywords
◼
keyword 1
Categories
Categories
◼
SymbolName (documented Wolfram Language symbol)
◼
Resource Name (resources from any Wolfram repository)
Source, reference or citation information
◼
Link to other related material
Additional information about limitations, issues, etc.
Additional information for the reviewer.