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