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]; 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. ¶--File: IPFloorMinCutImpl.mesa Last Edited by: CSChow, January 28, 1985 6:40:28 am PST Preas, August 2, 1986 6:16:48 pm PDT --Do the above so that nets knows about components ÊÒ˜J™™7Icode™$—J˜šÏk ˜ KšœœR˜[K˜Kšœ˜Kšœ˜K˜ Kšœ˜Kšœ ˜ K˜Kšœ˜—K˜šœœœ˜!Kšœ œ4˜IKšœœœ˜1K˜šÏnœœœœ˜DK˜!Kšœ5˜5šœ+˜+Kšœ˜šœ˜Kšœ%œ œ˜>—KšœÏc ˜—šœ-˜-šœ˜Kšœ%œ œ˜>—KšœŸ˜—šœœ%œ˜AKšœ˜Kšœœ˜ Kšœ œ˜Kšœ)˜)šœ˜šœ˜Kšœ6˜6Kšœ2˜2Kšœ2œ˜O—šœ˜Kšœ ˜ Kšœ(˜(——šœ˜šœ˜Kšœ6˜6Kšœ2˜2Kšœ2œ˜O—šœ˜Kšœ ˜ Kšœ(˜(——Kšœ/œœœ ˜bKšœŸ˜—šœ˜Kšœœœ?˜L—K˜šœ/˜/Kšœ2™2—Kšœ%œ˜*Kšœ0˜0Kšœ ˜KšœŸ ˜ —K˜šžœœ œ#œ˜ZKšœ œ˜"Kšœœ˜š ž œœ"œœœ˜FKšœ œœœ˜.Kšœ œ œ˜Kš œ œœœ œ˜&šžœœœ!˜7šœ˜šœ ˜ Kšœ!œœœ˜IKšœœœœ˜EKšœ!œœœ˜IKšœœœœ˜F—šœ ˜ Kšœ!œœœ˜IKšœœœœ˜EKšœ!œœœ˜IKšœœœœ˜F—Kšœœ˜—KšœŸ˜ —š œœœ2œœ˜Rš œœœ2œœ˜RKšœ œœ-˜BKšœ˜—Kšœ˜—š œœœœœœ˜@Kšœ œ˜ Kšœ˜Kšœ$˜$šœœ˜Kšœ˜Kšœ˜—Kšœ˜Kšœ˜—Kšœ œœ˜.Kšœ ˜KšœŸ ˜—Kšœ œœœ/˜KKšœ˜šœœœ˜Kšœ"˜"Kšœ˜—Kšœ!˜!Kšœ'˜'š˜Kšœ.˜.šœ˜Kšœ˜ Kšœ˜—Kšœ˜—Kšœ˜KšœŸ˜—K˜šžœœ+œ œ˜Tšœ"˜"Kšœœœ˜#šœœœœœ!œœ˜FKšœœ˜Kšœœ œ˜-Kšœœ œ˜-šœ œ œ˜!Kšœœ˜Kšœ˜—Kšœ˜—Kšœ˜—Kšœ ˜ KšœŸ ˜ —K˜š ž œœœœœœ˜Ršœ œœœ˜3Kšœœœ˜KšœœŸ ˜—Kšœ"˜"KšœŸ˜—K˜šžœœœœ˜-Kšœ˜KšœŸ˜ —K˜šžœœœœ˜:Kšœ œ˜K˜$Kšœ˜KšœŸ ˜ —K˜Kš˜—K˜K˜—…—hð