|
|||||||||
| Home >> All >> com >> port80 >> graph >> dot >> [ impl overview ] | PREV CLASS NEXT CLASS | ||||||||
SUMMARY:  JAVADOC |  SOURCE |  DOWNLOAD | NESTED | FIELD | CONSTR | METHOD |
DETAIL: FIELD | CONSTR | METHOD | ||||||||
com.port80.graph.dot.impl
Class AnnealWithCell
java.lang.Objectcom.port80.graph.dot.impl.AnnealWithCell
- public class AnnealWithCell
- extends java.lang.Object
Anneal a placement of a VirtualGraph. . Output from MinCross and Position often contains some very obvious layout problem mainly due to MinCross having no distance information consider those cases as equivalent. Especially for bus routing, there are lots of opportunities to improve the layout by taking advantage the fact that anywhere on the bus is equivalent. . shortestPath() try to find a point to line or point to point path with minimum distance in the VirtualGraph with placement. Another pass of Position may be required to compact the layout afterwards. For bus-bus connections, shortestPath() is run on both end points. For point to point connections, shortest path from either end point should be the same. However, since layout may have changed after shortestPath() is run from the first end point, it may be useful to run again on the other end point for maximum optimization. shortestPath() use A* algorithm. The layout is converted to a grid. Instead of a uniform grid, each rank is divided into segments of vertices and inter-vertex spacings. Vertex have a point coordinate and occupy the grid interval from floor(v.x-v.leftWidth-vertexSpacing/4) to ceil(v.x+v.rightWidth+vertexSpacing/4). The inter-vertex spacing is the interval between two vertices with both sides aligned to the grid and width=vertexSpacing/4. Transversal are directional, up or down. In down transversal, only cells in the lower row are neighbours. Cost of transversing from one cell to the other is consists of two costs, a static cost is pre-calculated for the current map (cross and distance cost) from one cell to the other. Another portion of the cost are determined on each visit (eg. cost for turns). The list of neighbours are determined on each visit depends on up/down transversal. Vertices occupied by old path are marked so they are candidate as neighbours. All other vertices are excluded as neighbour. Static costs: . Cross cost and distance cost for each pair of cells are pre-calculated before start. Cross cost are updated after each route changes. To reduce slope of paths, distance cost is proportional to square of grid count, so long horizontal path would be distributed as short segments in each rank. Dynamic costs: . To avoid path from zigzagging, a cost is associated with each turn. NOTE: . After an edge chain is erased before routing, the vertex cells still keep the .vertex and .crossCost fields valid and used for cross cost calculations. HISTORY: . 05/13/2002 Speed improvement by incrementally adjust crossCost information instead of recalc. on each eraseTrail (without installPath() optimization. This speed up Anneal() on 'testdot00' from ~60sec. to ~35sec. . Expand routeStraightLine() to allow offset!=0. Improves Anneal() on 'testdot00' from 35sec. to 30sec. TODO: . Anneal route of the longest top 10% routes. . Regression test on rank cost calculations.
| Nested Class Summary | |
(package private) class |
AnnealWithCell.Stat
|
| Field Summary | |
private static boolean |
CHECK
|
private static boolean |
DEBUG
Terse+debug info. |
private int |
fCELL_BASICCOST
|
private int |
fCELL_XDIV
|
(package private) java.util.Map |
fCellTable
VirtualVertex->cell mapping. |
private int[] |
fCrossCounts
Counters for rankCost(). |
private VirtualEdge[] |
fCurChain
Edge chain being routed indexed by rown instead of rank. |
(package private) VirtualGraph |
fGraph
|
(package private) java.util.Set |
fIgnoreSet
Set of VirtualEdge (chaintail) to be ignored (eg. |
(package private) int |
fImprovedCount
|
(package private) Cell[][] |
fMap
|
(package private) int |
fMapHeight
|
(package private) int |
fMapWidth
|
private int |
fMaxCol
|
(package private) int |
fMaxRank
|
private float |
fMINPTPCOST
|
(package private) int |
fMinRank
|
private CellHeap |
fOpenQueue
|
private int |
fPTP_PERCENT
|
(package private) com.port80.util.struct.IHeap |
fPTPHeap
|
(package private) int |
fRoutedCount
|
private AnnealWithCell.Stat |
fStat
|
(package private) int |
fStraightCount
|
private int |
fXOffset
|
private int |
fXSpacing
Sorted open cells. |
private int |
fYSpacing
|
private int |
MAXSLACK
Max slack allowed for route to be considered done. |
private int |
N_OFFSET
Number of tries straight vertical route search. |
private static java.lang.String |
NAME
|
private int[] |
OFFSETS
These are tunable instance parameters, put here for convenient. |
private static boolean |
TERSE
Verbose+intermediate results. |
private static boolean |
VERBOSE
Show time, status. |
private int |
YDIST
|
| Constructor Summary | |
AnnealWithCell()
|
|
| Method Summary | |
private Cell |
aStar(Cell src,
Cell dest,
int oldcost,
VirtualEdge[] chain)
|
private boolean |
checkCrossCosts()
|
private void |
clear()
|
private void |
createMap(VirtualGraph graph)
Create the map from given VirtualGraph. |
private int |
crossAfter(Cell parent,
Cell child,
Cell beforeParent,
Cell beforeChild,
VirtualEdge segment)
Calculate crossing cost for edge from parent to child below. |
private int |
crossAfterBefore(Cell parent,
Cell child,
Cell beforeParent,
VirtualEdge segment)
Calculate crossing cost for edge from parent to space before the first vertex below. |
private int |
crossBeforeAfter(Cell parent,
Cell child,
Cell beforeChild,
VirtualEdge segment)
parent vts[0](afterParent) | -------------------v beforechild child |
static int |
dot(VirtualGraph g,
int maxiter)
|
private Cell |
enqueue(Cell cell,
int nextbest,
Cell next)
Enqueue the cell not good for next expansion ('next' or 'cell') and return the next candidate for expansion. |
private int |
eraseTrail(VirtualEdge chaintail,
Cell src,
Cell dest,
VirtualEdge[] retchain,
CellList erased)
Erase route for edge chain started at 'chaintail' to prepare for reroute. |
private Cell |
expandDown(Cell best,
Cell next,
int nextbest,
Cell dest,
int oldcost,
VirtualEdge[] chain)
Expand from best to its children below. |
private Cell |
expandUp(Cell best,
Cell next,
int nextbest,
Cell dest,
int oldcost,
VirtualEdge[] chain)
Expand from best to its children above. |
private void |
getPath(Cell end,
boolean isdown,
CellList ret)
|
private void |
installPath(CellList newpath,
VirtualEdge chaintail,
boolean isdown)
Install the new path. |
private java.lang.String |
mapToGeneralPath(Cell[][] map)
|
private void |
newSpaceCells(Cell[] row,
int rn,
int start,
int end)
|
private Cell |
newVertexCells(Cell[] row,
int rn,
int left,
int right,
VirtualVertex v)
Populate cells [left..right) occupied by v. |
private int |
pathCost(VirtualEdge chaintail,
CellList path)
Determine cost of the given path. |
private int |
rankCost(int r,
VirtualEdge segment)
|
private void |
rankCostRemoveEdge(VirtualEdge segment)
Adjust rankCost on removal of a segemnt. |
int |
reRoute(VirtualGraph g,
int maxiter)
|
private int |
rerouteBus(java.util.List chainlist,
int maxiter)
|
private boolean |
rerouteBusFor(VirtualChain chain)
|
private void |
rerouteBusFrom(Cell src)
|
private boolean |
reRouteDown(Cell src,
Cell dest,
VirtualEdge chaintail)
|
private int |
reroutePTP(java.util.List chainlist,
int maxiter)
|
private boolean |
reRouteUp(Cell src,
Cell dest,
VirtualEdge chaintail)
ReRoute a bus from bottom (src) to top (dest). |
private void |
restorePath(CellList erased,
VirtualEdge chaintail)
|
private void |
restoreRankCost(int r)
Restore crossCost of cell in the given rank 'r'. |
CellList |
route(Cell src,
Cell dest,
int oldcost,
VirtualEdge[] chain,
boolean isdown)
|
private boolean |
routePath(CellList newpath,
int oldcost,
VirtualEdge chaintail,
CellList erased,
boolean isdown,
java.lang.String message)
Route path according to the newpath if cost improved, else restore old erased path. |
private Cell |
routeStraightLine(Cell src,
Cell dest,
int oldcost,
VirtualEdge[] chain,
boolean isdown)
|
private void |
saveRankCost(int r)
Take a snapshot of rank cost in the given rank 'r'. |
private void |
staticCost()
Pre-calculate static costs for each possible path segments. |
| Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
| Field Detail |
NAME
private static final java.lang.String NAME
- See Also:
- Constant Field Values
TERSE
private static final boolean TERSE
- Verbose+intermediate results.
- See Also:
- Constant Field Values
DEBUG
private static final boolean DEBUG
- Terse+debug info.
- See Also:
- Constant Field Values
VERBOSE
private static boolean VERBOSE
- Show time, status.
CHECK
private static boolean CHECK
OFFSETS
private final int[] OFFSETS
- These are tunable instance parameters, put here for convenient.
N_OFFSET
private final int N_OFFSET
- Number of tries straight vertical route search.
- See Also:
- Constant Field Values
MAXSLACK
private final int MAXSLACK
- Max slack allowed for route to be considered done.
- See Also:
- Constant Field Values
fGraph
VirtualGraph fGraph
fMinRank
int fMinRank
fMaxRank
int fMaxRank
fMap
Cell[][] fMap
fMapWidth
int fMapWidth
fMapHeight
int fMapHeight
fCellTable
java.util.Map fCellTable
- VirtualVertex->cell mapping.
fOpenQueue
private CellHeap fOpenQueue
fRoutedCount
int fRoutedCount
fImprovedCount
int fImprovedCount
fStraightCount
int fStraightCount
fIgnoreSet
java.util.Set fIgnoreSet
- Set of VirtualEdge (chaintail) to be ignored (eg. alway have min. cost).
fXSpacing
private int fXSpacing
- Sorted open cells.
fYSpacing
private int fYSpacing
fXOffset
private int fXOffset
fMaxCol
private int fMaxCol
fStat
private AnnealWithCell.Stat fStat
fCrossCounts
private int[] fCrossCounts
- Counters for rankCost().
fCurChain
private VirtualEdge[] fCurChain
- Edge chain being routed indexed by rown instead of rank.
fPTPHeap
com.port80.util.struct.IHeap fPTPHeap
YDIST
private int YDIST
fMINPTPCOST
private float fMINPTPCOST
fCELL_XDIV
private int fCELL_XDIV
fCELL_BASICCOST
private int fCELL_BASICCOST
fPTP_PERCENT
private int fPTP_PERCENT
| Constructor Detail |
AnnealWithCell
public AnnealWithCell()
| Method Detail |
dot
public static final int dot(VirtualGraph g, int maxiter)
reRoute
public final int reRoute(VirtualGraph g, int maxiter)
rerouteBus
private int rerouteBus(java.util.List chainlist, int maxiter)
rerouteBusFrom
private void rerouteBusFrom(Cell src)
rerouteBusFor
private boolean rerouteBusFor(VirtualChain chain)
reroutePTP
private int reroutePTP(java.util.List chainlist, int maxiter)
reRouteDown
private boolean reRouteDown(Cell src, Cell dest, VirtualEdge chaintail)
reRouteUp
private boolean reRouteUp(Cell src, Cell dest, VirtualEdge chaintail)
- ReRoute a bus from bottom (src) to top (dest).
createMap
private void createMap(VirtualGraph graph)
- Create the map from given VirtualGraph.
newSpaceCells
private void newSpaceCells(Cell[] row, int rn, int start, int end)
newVertexCells
private Cell newVertexCells(Cell[] row, int rn, int left, int right, VirtualVertex v)
- Populate cells [left..right) occupied by v.
staticCost
private void staticCost()
- Pre-calculate static costs for each possible path segments.
Vertex/spacing to vertex/spacing.
Crossing cost are calculated in two passes, from left to right
and then right to left as follow.
NOTE: Since we have to recalculate the rank cost after
eraseTrail() each time, there is no need to pre-calculate any
rank cost.
rankCost
private int rankCost(int r,
VirtualEdge segment)
rankCostRemoveEdge
private void rankCostRemoveEdge(VirtualEdge segment)
- Adjust rankCost on removal of a segemnt.
Deduct the xPenalty of the removed segment from all imaginary
edges that crossed the segment.
saveRankCost
private void saveRankCost(int r)
- Take a snapshot of rank cost in the given rank 'r'.
restoreRankCost
private void restoreRankCost(int r)
- Restore crossCost of cell in the given rank 'r'.
checkCrossCosts
private boolean checkCrossCosts()
crossAfterBefore
private int crossAfterBefore(Cell parent, Cell child, Cell beforeParent, VirtualEdge segment)
- Calculate crossing cost for edge from parent to space before
the first vertex below. The cost=crossCost(parent,child)
+e.xPenalty*(xPenalty of all edges from vertex on left of
parent to child).
beforeParent parent
|
v-------------------
child vts[0](afterChild)
crossBeforeAfter
private int crossBeforeAfter(Cell parent, Cell child, Cell beforeChild, VirtualEdge segment)
- parent vts[0](afterParent)
|
-------------------v
beforechild child
crossAfter
private int crossAfter(Cell parent, Cell child, Cell beforeParent, Cell beforeChild, VirtualEdge segment)
- Calculate crossing cost for edge from parent to child below.
child.
routePath
private boolean routePath(CellList newpath, int oldcost, VirtualEdge chaintail, CellList erased, boolean isdown, java.lang.String message)
- Route path according to the newpath if cost improved,
else restore old erased path.
restorePath
private void restorePath(CellList erased, VirtualEdge chaintail)
installPath
private void installPath(CellList newpath, VirtualEdge chaintail, boolean isdown)
- Install the new path.
Since the new route may have changed the vertex ordering in
the ranks, VirtualVertex.order need to be reassigned.
mapToGeneralPath
private java.lang.String mapToGeneralPath(Cell[][] map)
route
public CellList route(Cell src, Cell dest, int oldcost, VirtualEdge[] chain, boolean isdown)
routeStraightLine
private Cell routeStraightLine(Cell src, Cell dest, int oldcost, VirtualEdge[] chain, boolean isdown)
eraseTrail
private int eraseTrail(VirtualEdge chaintail, Cell src, Cell dest, VirtualEdge[] retchain, CellList erased)
- Erase route for edge chain started at 'chaintail' to prepare for reroute.
All cells on the route are marked as SPACE except the src cell.
. Update cross cost in all ranks affected.
. Mark vertices on the path as SPACE.
Note that removing an edge currently have no cross cost still
affect cross cost of imaginary edges which have counted this
edge.
pathCost
private int pathCost(VirtualEdge chaintail, CellList path)
- Determine cost of the given path.
clear
private void clear()
aStar
private Cell aStar(Cell src, Cell dest, int oldcost, VirtualEdge[] chain)
expandDown
private Cell expandDown(Cell best, Cell next, int nextbest, Cell dest, int oldcost, VirtualEdge[] chain)
- Expand from best to its children below.
expandUp
private Cell expandUp(Cell best, Cell next, int nextbest, Cell dest, int oldcost, VirtualEdge[] chain)
- Expand from best to its children above.
enqueue
private Cell enqueue(Cell cell, int nextbest, Cell next)
- Enqueue the cell not good for next expansion ('next' or 'cell')
and return the next candidate for expansion.
getPath
private void getPath(Cell end, boolean isdown, CellList ret)
|
|||||||||
| Home >> All >> com >> port80 >> graph >> dot >> [ impl overview ] | PREV CLASS NEXT CLASS | ||||||||
|
SUMMARY: JAVADOC | SOURCE | DOWNLOAD | NESTED | FIELD | CONSTR | METHOD |
DETAIL: FIELD | CONSTR | METHOD | ||||||||