|
|||||||||
| 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 Anneal
java.lang.Objectcom.port80.graph.dot.impl.Anneal
- public class Anneal
- extends java.lang.Object
Anneal a placement of a VirtualGraph with dynamic created grid points and meeting spacing requirements. For bus->bus and vertex->bus routes, grid start from the vertex x-coordinates and edge-edge (ESPACING) spacing apart on both sides. For vertex->vertex routes, grid start from the src x-coordinates and with (dest.x-src.x)/ESPACING divisions such that grid points are aligned with both src.x and dest.x. Each grid point is checked against existing vertices to make sure there are proper spacings. . Since Grid are now created dynamically, static data (eg. crossCost) are now moved to VirtualVertex and Grid.vertex points to the static data in the VirtualVertex. If Grid do not corresponds to a vertex Grid.vertex==null. These are the only two types of Grid: ERASED and SPACE. VirtualVertex.erased indicates that the vertex is erased for routing. . Four main data structures are used. The fGraph.ranks, fSpaceTable, fGridTable and the GridHeap. Grid points are identified using the x-coordinate and rank. fGridTable contains the coordinates->Grid object mapping. If a Grid point do not exists, check of the fSpaceTable to see if a Grid point should be allocated at the coordinate. fSpaceTable contains the vertex positions and dimensions for lookup of available space for a Grid. A binary search with an x-coordinate as key return an index such that index/2==vertex.order, index%2==0 indicates it hit the space before the vertex index%2==1 indicates it hit the vertex (or the reserved spacing around the vertex). If the coordinate hit a vertex, further check of vertex.isErased is needed to see if the space is available. If a Grid point do not exists and the coordinate is located in a space region, a Grid point can be allocated on the GridHeap by GridHeap.enqueue(). GridHeap keeps a pool of allocated Grid objects. enqueue() take a spare object from the spare pool and populate it with the provided values. Once enqueued, the Grid object should never be dequeued. A peek() at the top returns the lowest cost Grid which can be used for expansion. When new Grids are enqueued, the top Grid would be rearranged to a new priority according to its cost and a new top Grid object would automatically stay at the top of the heap for next expansion. If the cost of an existing Grid object on the heap is changed, the object should be requeue() to move it to the proper location on the heap. When the AStar algorithm is completed, the Grid list of the best path is retreived and the ERASED vertices are moved the the x-coordinates indicated by Grid.x. VirtualVertex.order are adjusted if neccessary. . 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 (Athlon 700MHz). . 09/13/2002 Switch from cell based to dynamic grid. TODO: . Anneal route of the longest top 10% routes. . Regression test on rank cost calculations.
| Nested Class Summary | |
(package private) class |
Anneal.Stat
|
| Field Summary | |
private static boolean |
CHECK
Enable checkings. |
private static boolean |
DEBUG
Debug info. |
private int[] |
fCrossCounts
Counters for rankCost(). |
private VirtualEdge[] |
fCurChain
Edge chain being routed indexed by rown instead of rank. |
(package private) ErasedPath |
fErasedPath
|
(package private) VirtualGraph |
fGraph
|
(package private) GridFactory |
fGridFactory
|
(package private) java.util.Set |
fIgnoreSet
Set of VirtualEdge (chaintail) to be ignored (eg. |
(package private) int |
fImprovedCount
|
private int |
fMaxCol
|
(package private) int |
fMaxIter
|
(package private) int |
fMaxRank
|
private static float |
fMINPTPCOST
|
(package private) int |
fMinRank
|
(package private) java.util.List |
fNewPath
|
(package private) GridHeap |
fOpenQueue
|
private int |
fPTP_PERCENT
|
(package private) VirtualGraph.Rank[] |
fRanks
|
(package private) int |
fRoutedCount
|
(package private) Anneal.Stat |
fStat
|
(package private) int |
fStraightCount
|
private int |
fXSpacing
Sorted open cells. |
private int |
fYSpacing
|
private static java.lang.String |
NAME
|
private static int[] |
OFFSETS
Offsets that routeStraightLine() would search. |
private static boolean |
TERSE
Verbose+terse intermediate results. |
private static boolean |
VERBOSE
Show time, statistics and final result. |
| Constructor Summary | |
Anneal(VirtualGraph g,
int griddiv)
|
|
| Method Summary | |
private Grid |
aStar(VirtualChain chain,
ErasedPath erased,
float oldcost)
|
void |
clear()
|
(package private) int |
crossAfter(Grid parent,
Grid child,
VirtualVertex beforeParent,
VirtualVertex beforeChild,
VirtualEdge segment)
Calculate crossing cost for edge from parent to child below. |
private int |
crossAfterBefore(Grid parent,
Grid child,
VirtualVertex beforeParent,
VirtualEdge segment)
Calculate crossing cost for edge from parent to space before the first vertex below. |
private int |
crossBeforeAfter(Grid parent,
Grid child,
VirtualVertex beforeChild,
VirtualEdge segment)
parent vts[0](afterParent) |-------------------v beforechild child |
static int |
dot(VirtualGraph g,
int griddiv,
int maxiter)
|
private void |
expandDown(Grid best,
VirtualVertex dest,
float oldcost,
ErasedPath erased)
Expand from best to its children below. |
private void |
expandUp(Grid best,
VirtualVertex dest,
float oldcost,
ErasedPath erased)
Expand from best to its children above. |
(package private) GridFactory |
getGridFactory()
|
private void |
getPath(Grid end,
boolean isdown,
java.util.List ret)
|
private void |
installPath(java.util.List newpath)
Install the new path. |
private java.lang.String |
mapToGeneralPath(Grid[][] map)
|
int |
reRoute(int maxiter)
|
(package private) boolean |
rerouteBusChain(VirtualChain chain)
|
(package private) int |
rerouteBuses(java.util.List chainlist,
int maxiter)
|
(package private) int |
reroutePTP(java.util.List chainlist,
int maxiter)
|
boolean |
route(VirtualChain chain,
boolean isdown,
java.lang.String message)
Route the given edge chain. |
private boolean |
routePath(Grid end)
Route path according to the newpath if cost improved, else restore old erased path. |
(package private) boolean |
sanityCheck()
|
| 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+terse intermediate results.
- See Also:
- Constant Field Values
DEBUG
private static final boolean DEBUG
- Debug info.
- See Also:
- Constant Field Values
VERBOSE
private static boolean VERBOSE
- Show time, statistics and final result.
CHECK
private static final boolean CHECK
- Enable checkings.
OFFSETS
private static final int[] OFFSETS
- Offsets that routeStraightLine() would search.
fMINPTPCOST
private static final float fMINPTPCOST
- See Also:
- Constant Field Values
fPTP_PERCENT
private int fPTP_PERCENT
fGraph
VirtualGraph fGraph
fMaxIter
int fMaxIter
fRanks
VirtualGraph.Rank[] fRanks
fMinRank
int fMinRank
fMaxRank
int fMaxRank
fIgnoreSet
java.util.Set fIgnoreSet
- Set of VirtualEdge (chaintail) to be ignored (eg. alway have min. cost).
fGridFactory
GridFactory fGridFactory
fOpenQueue
GridHeap fOpenQueue
fErasedPath
ErasedPath fErasedPath
fNewPath
java.util.List fNewPath
fStat
Anneal.Stat fStat
fRoutedCount
int fRoutedCount
fImprovedCount
int fImprovedCount
fStraightCount
int fStraightCount
fXSpacing
private int fXSpacing
- Sorted open cells.
fYSpacing
private int fYSpacing
fMaxCol
private int fMaxCol
fCrossCounts
private int[] fCrossCounts
- Counters for rankCost().
fCurChain
private VirtualEdge[] fCurChain
- Edge chain being routed indexed by rown instead of rank.
| Constructor Detail |
Anneal
public Anneal(VirtualGraph g, int griddiv)
| Method Detail |
dot
public static final int dot(VirtualGraph g, int griddiv, int maxiter)
reRoute
public final int reRoute(int maxiter)
route
public boolean route(VirtualChain chain, boolean isdown, java.lang.String message)
- Route the given edge chain.
clear
public void clear()
rerouteBuses
int rerouteBuses(java.util.List chainlist, int maxiter)
reroutePTP
int reroutePTP(java.util.List chainlist, int maxiter)
getGridFactory
GridFactory getGridFactory()
rerouteBusChain
boolean rerouteBusChain(VirtualChain chain)
sanityCheck
boolean sanityCheck()
crossAfter
int crossAfter(Grid parent, Grid child, VirtualVertex beforeParent, VirtualVertex beforeChild, VirtualEdge segment)
- Calculate crossing cost for edge from parent to child below.
child.
crossAfterBefore
private int crossAfterBefore(Grid parent, Grid child, VirtualVertex 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(Grid parent, Grid child, VirtualVertex beforeChild, VirtualEdge segment)
- parent vts[0](afterParent)
|-------------------v
beforechild child
routePath
private boolean routePath(Grid end)
- Route path according to the newpath if cost improved,
else restore old erased path.
installPath
private void installPath(java.util.List newpath)
- Install the new path.
Since the new route may have changed the vertex ordering in
the ranks, VirtualVertex.order need to be reassigned.
getPath
private void getPath(Grid end, boolean isdown, java.util.List ret)
aStar
private Grid aStar(VirtualChain chain, ErasedPath erased, float oldcost)
expandDown
private void expandDown(Grid best, VirtualVertex dest, float oldcost, ErasedPath erased)
- Expand from best to its children below.
expandUp
private void expandUp(Grid best, VirtualVertex dest, float oldcost, ErasedPath erased)
- Expand from best to its children above.
mapToGeneralPath
private java.lang.String mapToGeneralPath(Grid[][] map)
|
|||||||||
| Home >> All >> com >> port80 >> graph >> dot >> [ impl overview ] | PREV CLASS NEXT CLASS | ||||||||
|
SUMMARY: JAVADOC | SOURCE | DOWNLOAD | NESTED | FIELD | CONSTR | METHOD |
DETAIL: FIELD | CONSTR | METHOD | ||||||||