Overview  Package   Class  Use  Deprecated  Index
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 Untangle  

java.lang.Object
  com.port80.graph.dot.impl.Untangle

---

public class Untangle

extends java.lang.Object

Untangle a placement of a VirtualGraph. Global cross reduction using shortest path algoirthm on output of MinCross. . This is adapted from Anneal except that without actual coordinates, the distance and turn cost are not used. Instead of find the actual shortest path, the goal is just to go around crossings. Instead of using a grid, the map opens a channel between each pair of vertices for routing. 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.

---

Nested Class Summary
private  class	Untangle.Cell           Min.
private  class	Untangle.CellHeap           Heap/priority queue of Cell.
private  class	Untangle.CellList           A simple ArrayList never deallocate on clear and have direct access to array.
private  class	Untangle.Stat

 

Field Summary
private static int	BASICFACTOR
private  int[]	crossCounts           Counters for rankCost().
private  VirtualEdge[]	curChain           Edge chain being routed indexed by rown instead of rank.
private static boolean	DEBUG
(package private)  VirtualGraph	graph
(package private)  java.util.Set	ignoreSet           Set of VirtualEdge (chainhead) to be ignored (eg.
(package private)  int	markCounter
private  int	maxCol
private  int	maxRank
private  int	minRank
private static java.lang.String	NAME
(package private)  int	nImproved
private  Untangle.CellHeap	openQueue           Sorted open cells.
private  Untangle.Stat	stat
(package private)  Untangle.Cell[][]	theMap
private static int	VERBOSE           1=time only, 2=1+stat, 3=2+result, 4=3+intermediate results.

 

Constructor Summary

Untangle()

 

Method Summary
private  Untangle.Cell	aStar(Untangle.Cell src, Untangle.Cell dest, int oldcost, VirtualEdge[] chain)
void	clear()
private  void	createMap()           Create the map from 'g'.
private  int	crossAfter(Untangle.Cell parent, Untangle.Cell child, Untangle.Cell beforeParent, Untangle.Cell beforeChild, VirtualEdge segment)           Calculate crossing cost for edge from parent to child below.
private  int	crossAfterBefore(Untangle.Cell parent, Untangle.Cell child, Untangle.Cell beforeParent, VirtualEdge segment)           Calculate crossing cost for edge from parent to space before the first vertex below.
private  int	crossBeforeAfter(Untangle.Cell parent, Untangle.Cell child, Untangle.Cell beforeChild, VirtualEdge segment)           parent vts[0](afterParent) |-------------------v beforechild child
static int	dot(VirtualGraph g, int maxiter)
private  Untangle.Cell	enqueue(Untangle.Cell cell, int nextbest, Untangle.Cell next)           Enqueue cell if cell is not the next candidate for expansion.
int	eraseTrail(VirtualEdge chainhead, VirtualVertex src, VirtualEdge[] retchain, Untangle.CellList erased)           Erase route for edge chain started at 'e'.
private  Untangle.Cell	expandDown(Untangle.Cell best, Untangle.Cell next, int nextbest, Untangle.Cell dest, int oldcost, VirtualEdge[] chain)           Expand from best to its children below.
private  Untangle.Cell	expandUp(Untangle.Cell best, Untangle.Cell next, int nextbest, Untangle.Cell dest, int oldcost, VirtualEdge[] chain)           Expand from best to its children above.
private  void	getPath(Untangle.Cell end, boolean isdown, Untangle.CellList ret)
private  void	installPath(Untangle.CellList newpath, VirtualEdge chainhead)           Install the new path.
private  java.lang.String	mapToGeneralPath(Untangle.Cell[][] map)
int	pathCost(VirtualEdge chainhead, Untangle.CellList path)           Determine cost of the given path.
private  int	rankCost(int r, VirtualEdge ignore)
int	reRoute(VirtualGraph g, int maxiter)
private  Untangle.Cell	reRouteDown(Untangle.Cell src, Untangle.Cell dest, VirtualEdge chainhead)
private  Untangle.Cell	reRouteUp(Untangle.Cell src, Untangle.Cell dest, VirtualEdge chainhead)
private  void	restorePath(Untangle.CellList erased, VirtualEdge chainhead)
private  Untangle.Cell	routePath(Untangle.CellList newpath, int oldcost, VirtualEdge chainhead, Untangle.CellList erased, boolean isdown)           If newpath is better than oldpath, install path according to newpath and clean up, else restore oldpath.
Untangle.CellList	routePointToLine(Untangle.Cell src, Untangle.Cell dest, int oldcost, VirtualEdge[] chain, boolean isdown)
private  void	staticCost()           Pre-calculate static costs for each possible path segments.
private  void	updateRankCost(VirtualEdge chainhead, boolean isdown)

 

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

---

DEBUG

private static final boolean DEBUG

See Also:

Constant Field Values

---

VERBOSE

private static final int VERBOSE

1=time only, 2=1+stat, 3=2+result, 4=3+intermediate results.

See Also:

Constant Field Values

---

BASICFACTOR

private static final int BASICFACTOR

See Also:

Constant Field Values

---

graph

VirtualGraph graph

---

theMap

Untangle.Cell[][] theMap

---

markCounter

int markCounter

---

nImproved

int nImproved

---

ignoreSet

java.util.Set ignoreSet

Set of VirtualEdge (chainhead) to be ignored (eg. alway have min. cost).

---

openQueue

private Untangle.CellHeap openQueue

Sorted open cells.

---

minRank

private int minRank

---

maxRank

private int maxRank

---

maxCol

private int maxCol

---

stat

private Untangle.Stat stat

---

crossCounts

private int[] crossCounts

Counters for rankCost().

---

curChain

private VirtualEdge[] curChain

Edge chain being routed indexed by rown instead of rank.

Constructor Detail

Untangle

public Untangle()

Method Detail

dot

public static final int dot(VirtualGraph g,
                            int maxiter)

---

reRoute

public final int reRoute(VirtualGraph g,
                         int maxiter)

---

reRouteDown

private Untangle.Cell reRouteDown(Untangle.Cell src,
                                  Untangle.Cell dest,
                                  VirtualEdge chainhead)

---

reRouteUp

private Untangle.Cell reRouteUp(Untangle.Cell src,
                                Untangle.Cell dest,
                                VirtualEdge chainhead)

---

createMap

private void createMap()

Create the map from 'g'.

---

rankCost

private int rankCost(int r,
                     VirtualEdge ignore)

---

crossAfterBefore

private int crossAfterBefore(Untangle.Cell parent,
                             Untangle.Cell child,
                             Untangle.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(Untangle.Cell parent,
                             Untangle.Cell child,
                             Untangle.Cell beforeChild,
                             VirtualEdge segment)

parent vts[0](afterParent) |-------------------v beforechild child

---

crossAfter

private int crossAfter(Untangle.Cell parent,
                       Untangle.Cell child,
                       Untangle.Cell beforeParent,
                       Untangle.Cell beforeChild,
                       VirtualEdge segment)

Calculate crossing cost for edge from parent to child below. child.

---

routePath

private Untangle.Cell routePath(Untangle.CellList newpath,
                                int oldcost,
                                VirtualEdge chainhead,
                                Untangle.CellList erased,
                                boolean isdown)

If newpath is better than oldpath, install path according to newpath and clean up, else restore oldpath.

---

restorePath

private void restorePath(Untangle.CellList erased,
                         VirtualEdge chainhead)

---

installPath

private void installPath(Untangle.CellList newpath,
                         VirtualEdge chainhead)

Install the new path. Since the new route may have changed the vertex ordering in the ranks, VirtualVertex.order need to be reassigned. Also need to reorder cells to put SPACE cells on both side of the new vertex.

---

mapToGeneralPath

private java.lang.String mapToGeneralPath(Untangle.Cell[][] map)

---

routePointToLine

public Untangle.CellList routePointToLine(Untangle.Cell src,
                                          Untangle.Cell dest,
                                          int oldcost,
                                          VirtualEdge[] chain,
                                          boolean isdown)

---

eraseTrail

public int eraseTrail(VirtualEdge chainhead,
                      VirtualVertex src,
                      VirtualEdge[] retchain,
                      Untangle.CellList erased)

Erase route for edge chain started at 'e'. . 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

public int pathCost(VirtualEdge chainhead,
                    Untangle.CellList path)

Determine cost of the given path.

---

clear

public void clear()

---

aStar

private Untangle.Cell aStar(Untangle.Cell src,
                            Untangle.Cell dest,
                            int oldcost,
                            VirtualEdge[] chain)

---

expandDown

private Untangle.Cell expandDown(Untangle.Cell best,
                                 Untangle.Cell next,
                                 int nextbest,
                                 Untangle.Cell dest,
                                 int oldcost,
                                 VirtualEdge[] chain)

Expand from best to its children below.

---

expandUp

private Untangle.Cell expandUp(Untangle.Cell best,
                               Untangle.Cell next,
                               int nextbest,
                               Untangle.Cell dest,
                               int oldcost,
                               VirtualEdge[] chain)

Expand from best to its children above.

---

enqueue

private Untangle.Cell enqueue(Untangle.Cell cell,
                              int nextbest,
                              Untangle.Cell next)

Enqueue cell if cell is not the next candidate for expansion.

---

getPath

private void getPath(Untangle.Cell end,
                     boolean isdown,
                     Untangle.CellList ret)

---

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.

---

updateRankCost

private void updateRankCost(VirtualEdge chainhead,
                            boolean isdown)

---

Overview  Package   Class  Use  Deprecated  Index
Home >> All >> com >> port80 >> graph >> dot >> [ impl overview ]	PREV CLASS  NEXT CLASS
SUMMARY:  JAVADOC |  SOURCE |  DOWNLOAD | NESTED | FIELD | CONSTR | METHOD	DETAIL: FIELD | CONSTR | METHOD

---