<<--File: IPFloorMinCutImpl.mesa>> <> <> 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.