--File: IPFloorMinCutImpl.mesa
Last Edited by: CSChow, January 28, 1985 6:40:28 am PST
Preas, August 2, 1986 6:16:48 pm PDT
DIRECTORY
Set USING [Handle, Put, New, Remove, In, Enumerate, Cardinality, Nth, Difference, Element],
Rope,
IP,
IPCoTab,
IPTopOps,
IPTop,
IPNetTab,
IPSimpleTree,
IPFloorMinCut;
IPFloorMinCutImpl: CEDAR PROGRAM
IMPORTS Set, Rope, IP, IPCoTab, IPTopOps, IPNetTab, IPSimpleTree, IPTop
EXPORTS IPFloorMinCut = BEGIN OPEN IPFloorMinCut;
DoMinCut: PUBLIC PROC [top: IPTop.Ref] RETURNS [IPSimpleTree.Ref] ={
cutSet0: Set.Handle ← Set.New[];
minCutTree: IPSimpleTree.Ref ← IPSimpleTree.Create[];
activateAll: IPCoTab.EachComponentAction ={
[] ← Set.Put[cutSet0, co];
IF ~ IPCoTab.CoActive[co]
THEN [] ← IPTopOps.SetComponent[top, co, TRUE, [0, 0], FALSE];
}; --activateAll
deactivateAll: IPCoTab.EachComponentAction ={
IF IPCoTab.CoActive[co]
THEN [] ← IPTopOps.SetComponent[top, co, FALSE, [0, 0], FALSE]
}; --deactivateAll
cutRecursively: PROC[set: Set.Handle, name, parent: Rope.ROPE] ={
nPart, pPart: Set.Handle;
nPartName, pPartName: Rope.ROPE;
cutCount: INT;
[nPart, pPart, cutCount] ← Cut[top, set];
IF Atomic[nPart]
THEN {
nComp: IPCoTab.Component ← GetComponents[nPart].first;
nPartName ← Rope.Cat[IPCoTab.GetName[nComp], "*"];
IPSimpleTree.AddNode[minCutTree, nPartName, name, NIL, CompArea[nComp], nComp]}
ELSE {
nPartName ← Rope.Cat[name, "n"];
cutRecursively[nPart, nPartName, name]};
IF Atomic[pPart]
THEN {
pComp: IPCoTab.Component ← GetComponents[pPart].first;
pPartName ← Rope.Cat[IPCoTab.GetName[pComp], "*"];
IPSimpleTree.AddNode[minCutTree, pPartName, name, NIL, CompArea[pComp], pComp]}
ELSE {
pPartName ← Rope.Cat[name, "p"];
cutRecursively[pPart, pPartName, name]};
IPSimpleTree.AddNode[minCutTree, name, parent, LIST[nPartName, pPartName], 0, NEW[INT ← cutCount]]
}; --cutRecursively
IF ~ IPTop.NoTopology[top]
THEN ERROR IP.Error[callingError, "Can't do min-cut if there are channels"];
IPCoTab.AllComponents[top.coTab, activateAll];
--Do the above so that nets knows about components
cutRecursively[cutSet0, "IPTopRoot", NIL];
IPCoTab.AllComponents[top.coTab, deactivateAll];
RETURN [minCutTree]
}; --DoMinCut
Cut: PROC[top: IPTop.Ref, s: Set.Handle] RETURNS [nPart, pPart: Set.Handle, count: INT] ={
setSize: NAT ← Set.Cardinality[s];
cutCount, newCount: INT;
ImproveCut: PROC[nCut, pCut: Set.Handle, bestCnt: INT] RETURNS [INT]={
SwapRec: TYPE = RECORD[negComp, posComp: REF];
bestSwap: REF SwapRec ← NIL;
swapTrials: LIST OF REF SwapRec ← NIL;
DoSwap: PROC[swap: REF SwapRec, sense: {doIt, undo}] ={
SELECT sense FROM
doIt => {
IF ~Set.Remove[nCut, swap.negComp] THEN ERROR IP.Error[programmingError];
IF Set.Put[pCut, swap.negComp] THEN ERROR IP.Error[programmingError];
IF ~Set.Remove[pCut, swap.posComp] THEN ERROR IP.Error[programmingError];
IF Set.Put[nCut, swap.posComp] THEN ERROR IP.Error[programmingError]};
undo => {
IF ~Set.Remove[nCut, swap.posComp] THEN ERROR IP.Error[programmingError];
IF Set.Put[pCut, swap.posComp] THEN ERROR IP.Error[programmingError];
IF ~Set.Remove[pCut, swap.negComp] THEN ERROR IP.Error[programmingError];
IF Set.Put[nCut, swap.negComp] THEN ERROR IP.Error[programmingError]};
ENDCASE => ERROR;
}; --DoSwap
FOR nl: LIST OF IPCoTab.Component ← GetComponents[nCut], nl.rest UNTIL nl = NIL DO
FOR pl: LIST OF IPCoTab.Component ← GetComponents[pCut], pl.rest UNTIL pl = NIL DO
swapTrials ← CONS[NEW[SwapRec ← [nl.first, pl.first]], swapTrials]
ENDLOOP;
ENDLOOP;
FOR l: LIST OF REF SwapRec ← swapTrials, l.rest UNTIL l = NIL DO
tempCnt: INT;
DoSwap[l.first, doIt];
tempCnt ← CutCount[top, nCut, pCut];
IF tempCnt < bestCnt THEN {
bestCnt ← tempCnt;
bestSwap ← l.first};
DoSwap[l.first, undo];
ENDLOOP;
IF bestSwap # NIL THEN DoSwap[bestSwap, doIt];
RETURN [bestCnt]
}; --ImproveCut
IF setSize = 1 THEN ERROR IP.Error[callingError, "Can't split atomic set"];
nPart ← Set.New[];
FOR x: NAT IN [1..setSize/2] DO
[] ← Set.Put[nPart, Set.Nth[s, x]]
ENDLOOP;
pPart ← Set.Difference[s, nPart];
cutCount ← CutCount[top, nPart, pPart];
DO
newCount ← ImproveCut[nPart, pPart, cutCount];
IF newCount >= cutCount
THEN EXIT
ELSE cutCount ← newCount;
ENDLOOP;
RETURN [nPart, pPart, cutCount]
};--Cut
CutCount: PROC[top: IPTop.Ref, nPart, pPart: Set.Handle] RETURNS [count: INT ← 0] ={
EachNet: IPNetTab.EachNetAction ={
connNPart, connPPart: BOOLFALSE;
FOR l: LIST OF REF IP.PinNetRep ← net.pinNets, l.rest UNTIL l = NIL DO
comp: REF ← l.first.owner;
IF Set.In[nPart, comp] THEN connNPart ← TRUE;
IF Set.In[pPart, comp] THEN connPPart ← TRUE;
IF connNPart AND connPPart THEN {
count ← count.SUCC;
EXIT}
ENDLOOP;
};
IPNetTab.Nets[top.nets, EachNet]
};--CutCount
GetComponents: PROC[s: Set.Handle] RETURNS [l: LIST OF IPCoTab.Component ← NIL] ={
eachElement: PROC[e: Set.Element] RETURNS [BOOL] ={
l ← CONS[NARROW[e], l];
RETURN[FALSE]}; --eachElement
[] ← Set.Enumerate[s, eachElement]
};--GetComponents
Atomic: PROC[s: Set.Handle] RETURNS [BOOL] ={
RETURN[Set.Cardinality[s] = 1]
}; --Atomic
CompArea: PROC [comp: IPCoTab.Component] RETURNS [INT] = {
xDim, yDim: INT;
[xDim, yDim] ← IPCoTab.GetDim[comp];
RETURN [xDim * yDim]
}; --CompArea
END.