deploy

mac:/Users/yaroslav/Google Drive/src/gradient-checkpointing/treeDecomposition.nb

Mon 8 Jan 2018 12:55:49

## Init

Init

Copy of everything from treeDecomposition.m

Decomposition happens in runDecomposition which initializes the graph - based local variables (gg, V), decomposition variables (elimed, bags, tieBreaker) and runs decomposition to find good set of bags.

Decomposition proceeds by finding smallest fill vertex (minFillEliminate) and adding it to currently active bag.Vertices in the bag which are not connected to the new addition are removed from the active bag, this forms new bag in tree decomposition.

After set of bags is obtained, we obtain tree version by running maximum weight spanning tree on the set of bags, preferring to add bags with largest intersection as edges.

Directed tree decomposition modifies regular tree decomposition by adding directed versions of some symbols:

minFillEliminate2, treeDecomposition2, adjMat2

TODO: make this work with arbitrary vertex names, not sequential numbers

Decomposition proceeds by finding smallest fill vertex (minFillEliminate) and adding it to currently active bag.Vertices in the bag which are not connected to the new addition are removed from the active bag, this forms new bag in tree decomposition.

After set of bags is obtained, we obtain tree version by running maximum weight spanning tree on the set of bags, preferring to add bags with largest intersection as edges.

Directed tree decomposition modifies regular tree decomposition by adding directed versions of some symbols:

minFillEliminate2, treeDecomposition2, adjMat2

TODO: make this work with arbitrary vertex names, not sequential numbers

## Test

Test

g=GridGraph[{2,4},GraphStyle"DiagramBlue"];gtarget={{{1,2,3},{2,3,4},{3,4,5},{4,5,6},{5,6,7},{6,7,8}},{{{1,2,3},{2,3,4}},{{2,3,4},{3,4,5}},{{3,4,5},{4,5,6}},{{4,5,6},{5,6,7}},{{5,6,7},{6,7,8}}}};initAndRunDecomposition[g];(*Todo:renamebagstojbags*)jbagsFirst[target];jedges=Last[target];checkTreeDecomposition[jbags,jedges];getCost[n_]:=(g=GridGraph[{2,n},GraphStyle"DiagramBlue"];initAndRunDecomposition[g];getTreeCost[{jbags,jedges}])ListPlot[getCost/@Range[10]]g=GridGraph[{2,4}];initAndRunDecomposition[g];drawBagOnGraph/@jbags(*testdirecteddecomposition*)resnet=Graph[{12,13,23,34,35,45,56,57,67,78,79,89,910,911,1011}];initAndRunDecomposition[resnet,True];GraphicsGrid[{drawBagOnGraph/@jbags},ImageSize400]

## Thick chain decomposition

Thick chain decomposition

,,,,,

Contents cannot be rendered at this time; please try again later

Contents cannot be rendered at this time; please try again later

Contents cannot be rendered at this time; please try again later

Contents cannot be rendered at this time; please try again later

Contents cannot be rendered at this time; please try again later

Contents cannot be rendered at this time; please try again later

## Resnet decomposition

Resnet decomposition

Contents cannot be rendered at this time; please try again later

## Grid decomposition

Grid decomposition

initGraph[{"Grid",{3,3}}]Dynamic[drawBags[],TrackedSymbols{bags}]

visGraph[]

Contents cannot be rendered at this time; please try again later

## Polyiamond decomposition

Polyiamond decomposition

## Resnet 18 decomposition

Resnet 18 decomposition