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: BOOL ← FALSE;
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.