Function Resource
DEFINITION NOTEBOOK
Function Repository »
Open Sample
Style Guidelines
Tools
Check
Preview
▼
Deploy
▼
Submit to Repository
Template Input
Literal Input
Insert Delimiter
Subscripted Variable
Tables▼
Cells▼
​

GraphFoliations

Enumerate all possible foliations of a graph

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//ClearAll​​GraphFoliations[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

Usage

GraphFoliations[g]
returns foliations of a graph
g
.

Details & Options

▪
GraphFoliations
recursively generates foliations by poping top vertices off the given graph and reattaching them back in all possible ways.

Examples

Basic Examples

Enumerate and highlight foliations of a graph:
In[]:=
GraphFoliationsg=

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,#,VertexLabelsNone]&/@%
Out[]=

,
,
,

In[]:=
GraphFoliationsg=

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,#,VertexLabelsNone]&/@%
Out[]=

,
,
,
,

In[]:=
GraphFoliations

Out[]=
{{{1},{2,3},{4,5,10},{6,7,11,14},{8,9,12,13,15,16}},{{1},{2,3},{4,5,10},{6,7,11,14},{8},{9,12,13,15,16}},{{1},{2,3},{4,5,10},{6,7,11},{8,14},{9,12,13,15,16}},{{1},{2,3},{4,10},{6,7,11,5},{8,14},{9,12,13,15,16}},{{1},{2,3},{4,5,10},{6,7,14},{8,11},{9,12,13,15,16}},
⋯7196⋯
,{{1},{2,3},{4},{6,10},{8},{9,11,5},{12,14},{13},{15,7},{16}},{{1},{2},{4,3},{6,10},{8},{9,11,5},{12,14},{13},{15,7},{16}},{{1},{2,3},{4},{6},{8,10},{9,11,5},{12,14},{13},{15,7},{16}},{{1},{2},{4,3},{6},{8,10},{9,11,5},{12,14},{13},{15,7},{16}},{{1},{2},{4},{6,3},{8,10},{9,11,5},{12,14},{13},{15,7},{16}}}
large output
show less
show more
show all
set size limit...

Scope

Options

Applications

Properties and Relations

Possible Issues

Neat Examples

Source & Additional Information

Contributed By

Nikolay Murzin

Keywords

◼
  • keyword 1

    • Categories

    Cloud & Deployment
    Core Language & Structure
    Data Manipulation & Analysis
    Engineering Data & Computation
    External Interfaces & Connections
    Financial Data & Computation
    Geographic Data & Computation
    Geometry
    Graphs & Networks
    Higher Mathematical Computation
    Images
    Just For Fun
    Knowledge Representation & Natural Language
    Machine Learning
    Notebook Documents & Presentation
    Programming Utilities
    Repository Tools
    Scientific and Medical Data & Computation
    Social, Cultural & Linguistic Data
    Sound
    Strings & Text
    Symbolic & Numeric Computation
    System Operation & Setup
    Time-Related Computation
    User Interface Construction
    Visualization & Graphics
    Wolfram Physics Project
    ◼
  • 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.