Docjar: A Java Source and Docuemnt Enginecom.*    java.*    javax.*    org.*    all    new    plug-in

Quick Search    Search Deep

com.port80.graph.dot.impl
Class Anneal  view Anneal download Anneal.java

java.lang.Object
  extended bycom.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)