Route

Overview

Package

Class

Use

Deprecated

Index

Home >> All >> com >> port80 >> graph >> dot >> [ impl overview ]

PREV CLASS NEXT CLASS

SUMMARY:

JAVADOC |

Sourc code of com.port80.graph.dot.impl.Route

SOURCE |

Download com.port80.graph.dot.impl.Route

DOWNLOAD | NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

com.port80.graph.dot.impl
Class Route

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

public class Route
extends java.lang.Object

Draw splines for VirtualGraph.

Nested Class Summary

static class Route.TextLabel


static class Route.TextLine


Field Summary

private static int ANYW


private static int ARR_DOT


private static int ARR_INV


private static int ARR_INVDOT


private static int ARR_INVODOT


private static int ARR_NONE


private static int ARR_NORM


private static int ARR_ODOT


private static int[] arr_type


private static double ARROW_GAP_MAX


private static double ARROW_GAP_MIN


private static java.lang.String[] arrowDirNames


private static java.lang.String[] arrowHeadNames


private static int AUXGRAPH


private static int BINC


static int BOTTOM
          Sides of boxes for SHAPE path.

static int BOXBOTTOM


static int BOXLEFT


static int BOXRIGHT


static int BOXTOP


private static int BWDEDGE


private static int CCW


private static boolean CHECK


private static int CHUNK


private static int CW


private static boolean DEBUG


private static int DELTA_STRAIGHT


private static int[] dir_eflag


private static int[] dir_sflag


private static int EDGEDIRMASK


private static int EDGETYPEMASK


private static double EPSILON


private int fBottomBound


private int fBOX_MINOVERLAP


private int fBoxCount


private int fESpacing


private int fFlatHeight


private VirtualGraph fGraph


private DotBox[] fInterRankBoxes
          Inter-rank spacing.

private static int FLATEDGE


private static int[][] flatSideMap


private int fLeftBound


private int fMERGE_OFFSET


private DotPath fPath


private DotPolyline fPolyBound
          Bounding polygon for routing.

private VirtualGraph.Rank[] fRanks


private int fRightBound


private RouteSpline fRouter


private DotPolyline fSegment


private DotSpline fSpline


private int fSplineCount
          Statistics

private java.util.Map fSplineMap
          VirtualEdge->Spline mapping for saving generated splines.

private int fTopBound


private static int FWDEDGE


private int fXDIV_EDGES


private int fXDIV_XEDGE


private int fXESpacing


private int fXSpacing


private static int GRAPHTYPEMASK


static int LEFT


static int LL


static int LR


private static int MAINGRAPH


private static int MAXSUB


private static java.lang.String NAME


private static int PINC


private static int REGULAREDGE


static int RIGHT


private static int SELFEDGE


private static int SELFNPEDGE


private static int[][] selfSideMap


private static int SELFWPEDGE


private static int STRAIGHT_LONG


private static int STRAIGHT_SHORT


static int TOP


static int UL


static int UR


private static boolean VERBOSE


private static int YSUB


Constructor Summary

Route()


Method Summary

private void adjustChain(VirtualGraph graph, VirtualEdge chaintail, DotSpline spline, DotPath path)
          Move virtual vertices to routed locations so that other routing can take advantage of the spare spaces.

private void adjustRegularPath(DotPath path, int firstbox, int lastbox)
          Adjust boxes to meet MINWIDTH and ensure overlapped.

private void adjustVertexWithoutReorder(int newx, VirtualVertex head, VirtualGraph.Rank rank)
          Adjust x coordinate of given vertex to as close as possible to newx while maintaining vertex orders.

private void adjustVertexWithReorder(int neworder, int newx, VirtualVertex head, VirtualGraph.Rank rank)
          Move given vertex to location before the vertex vts[neworder] and adjust x coordinate to as close as possible to 'newx'.

private VirtualEdge bottomBound(VirtualEdge e, int side)


private VirtualEdge bottomLeftBound(VirtualEdge e)


private VirtualEdge bottomRightBound(VirtualEdge e)


private int boundHeadBoxes(VirtualEdge e, int nboxes, DotBoxList ret)
          Bound and replace the last 'nboxes' boxes in the given DotBoxList with bounding splines at head of 'e'.

private int boundTailBoxes(VirtualEdge e, DotBox box, DotBoxList ret)
          Bound the inter-rank spacing below the tail.

private int clipEndArrow(DotSpline s, int start, int end, com.port80.graph.IEdge e)
          Clip arrow at end of spline (head arrow if ve is not reversed).

private void clipInstall(VirtualEdge chaintail, com.port80.graph.IEdge e, DotSpline s, int offset)
          Clip spline to the shape boundary.

private void clipShape(VirtualVertex v, java.awt.Shape shape, DotSpline spline, int index, boolean istail)
          Clip spline by vertex shape, given 'index' is the tail (left) end of the Bezier that intersect the shape.

private int clipStartArrow(DotSpline s, int start, int end, com.port80.graph.IEdge e)
          Clip arrow at start of spline (tail arrow if not reversed).

private double dist(DotPoint p1, DotPoint p2)


private double dist2(DotPoint p1, DotPoint p2)


static void dot(VirtualGraph g)


private void ensureBoxWidth(DotBox box)


private void ensureContact(DotBox above, DotBox box)
          Ensure given box 'box' contact with box above.

private int findOrder(int x, VirtualGraph.Rank rank)
          Find the new order for a vertex at the given x-coordinate 'x' such that vts[neworder-1].x <= x and vts[neworder].x > x

private java.util.SortedSet init(VirtualGraph g)


private java.util.SortedSet initChain()


private void initInterRankBoxes()


private void installBus(com.port80.graph.IVertex v, java.lang.String name, VirtualGraph.Rank rank)


private boolean isSplineMidPoint(VirtualVertex v)


private DotBox makeRegularBox(DotBox box, int side, int y)
          Make a box at bottom or top of an existing box.

private int maximalBoxes(int side, VirtualVertex v, VirtualEdge ie, VirtualEdge oe, DotBoxList ret)
          Determine the maximal bounding box around 'v' available for routing edges 'ie' and 'oe'.

private VirtualVertex neighbour(VirtualVertex v, VirtualEdge ie, VirtualEdge oe, int lly, int ury, int dir)
          Get neighbour on left (dir=-1) or right (dir=1).

private boolean pathsCrossed(VirtualVertex v0, VirtualVertex v1, VirtualEdge ie1, VirtualEdge oe1)
          Check if edge chain 'ie1->v1->oe1' any cross edge chain through 'v0'.

void route(VirtualGraph g)


private int routePath(DotPath path, DotPolyline ret)
          Route a spline segment inside the bounding boxes of 'path'.

private DotSpline routeRegular(VirtualEdge chaintail)
          Compute the spline points for edge chain starting at edge 'e'.

static void setVerbose(boolean yes)


private int straightLength(VirtualEdge start, int chainlen)
          Count number of ranks that are vertically aligned.

private VirtualEdge straightPath(VirtualEdge e, int len, DotSpline spline)
          Construct a straight spline segment that represent 'len' edges starting at 'e'.

private VirtualEdge topBound(VirtualEdge e, int side)


private VirtualEdge topLeftBound(VirtualEdge e)
          Bound given boxes by the neighbour routed edges.

private VirtualEdge topRightBound(VirtualEdge e)


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

CHECK

private static boolean CHECK

VERBOSE

private static boolean VERBOSE

EPSILON

private static final double EPSILON

See Also:: Constant Field Values

DELTA_STRAIGHT

private static final int DELTA_STRAIGHT

See Also:: Constant Field Values

ARROW_GAP_MIN

private static final double ARROW_GAP_MIN

See Also:: Constant Field Values

ARROW_GAP_MAX

private static final double ARROW_GAP_MAX

See Also:: Constant Field Values

BOTTOM

public static final int BOTTOM

Sides of boxes for SHAPE path.

See Also:: Constant Field Values

RIGHT

public static final int RIGHT

See Also:: Constant Field Values

TOP

public static final int TOP

See Also:: Constant Field Values

LEFT

public static final int LEFT

See Also:: Constant Field Values

BOXBOTTOM

public static final int BOXBOTTOM

See Also:: Constant Field Values

BOXRIGHT

public static final int BOXRIGHT

See Also:: Constant Field Values

BOXTOP

public static final int BOXTOP

See Also:: Constant Field Values

BOXLEFT

public static final int BOXLEFT

See Also:: Constant Field Values

UL

public static final int UL

See Also:: Constant Field Values

LL

public static final int LL

See Also:: Constant Field Values

LR

public static final int LR

See Also:: Constant Field Values

UR

public static final int UR

See Also:: Constant Field Values

MAXSUB

private static final int MAXSUB

See Also:: Constant Field Values

YSUB

private static final int YSUB

See Also:: Constant Field Values

STRAIGHT_SHORT

private static final int STRAIGHT_SHORT

See Also:: Constant Field Values

STRAIGHT_LONG

private static final int STRAIGHT_LONG

See Also:: Constant Field Values

CHUNK

private static final int CHUNK

See Also:: Constant Field Values

REGULAREDGE

private static final int REGULAREDGE

See Also:: Constant Field Values

FLATEDGE

private static final int FLATEDGE

See Also:: Constant Field Values

SELFWPEDGE

private static final int SELFWPEDGE

See Also:: Constant Field Values

SELFNPEDGE

private static final int SELFNPEDGE

See Also:: Constant Field Values

SELFEDGE

private static final int SELFEDGE

See Also:: Constant Field Values

EDGETYPEMASK

private static final int EDGETYPEMASK

See Also:: Constant Field Values

FWDEDGE

private static final int FWDEDGE

See Also:: Constant Field Values

BWDEDGE

private static final int BWDEDGE

See Also:: Constant Field Values

EDGEDIRMASK

private static final int EDGEDIRMASK

See Also:: Constant Field Values

MAINGRAPH

private static final int MAINGRAPH

See Also:: Constant Field Values

AUXGRAPH

private static final int AUXGRAPH

See Also:: Constant Field Values

GRAPHTYPEMASK

private static final int GRAPHTYPEMASK

See Also:: Constant Field Values

CCW

private static final int CCW

See Also:: Constant Field Values

CW

private static final int CW

See Also:: Constant Field Values

ANYW

private static final int ANYW

See Also:: Constant Field Values

BINC

private static final int BINC

See Also:: Constant Field Values

PINC

private static final int PINC

See Also:: Constant Field Values

ARR_NONE

private static final int ARR_NONE

See Also:: Constant Field Values

ARR_NORM

private static final int ARR_NORM

See Also:: Constant Field Values

ARR_INV

private static final int ARR_INV

See Also:: Constant Field Values

ARR_DOT

private static final int ARR_DOT

See Also:: Constant Field Values

ARR_ODOT

private static final int ARR_ODOT

See Also:: Constant Field Values

ARR_INVDOT

private static final int ARR_INVDOT

See Also:: Constant Field Values

ARR_INVODOT

private static final int ARR_INVODOT

See Also:: Constant Field Values

arrowDirNames

private static final java.lang.String[] arrowDirNames

arrowHeadNames

private static final java.lang.String[] arrowHeadNames

dir_sflag

private static final int[] dir_sflag

dir_eflag

private static final int[] dir_eflag

arr_type

private static final int[] arr_type

selfSideMap

private static final int[][] selfSideMap

flatSideMap

private static final int[][] flatSideMap

fGraph

private VirtualGraph fGraph

fRanks

private VirtualGraph.Rank[] fRanks

fFlatHeight

private int fFlatHeight

fESpacing

private int fESpacing

fXSpacing

private int fXSpacing

fXESpacing

private int fXESpacing

fSplineMap

private java.util.Map fSplineMap

VirtualEdge->Spline mapping for saving generated splines. The key is the chain head of the edge chain that the spline represent.

fLeftBound

private int fLeftBound

fRightBound

private int fRightBound

fTopBound

private int fTopBound

fBottomBound

private int fBottomBound

fInterRankBoxes

private DotBox[] fInterRankBoxes

Inter-rank spacing. interRankBoxes[0] is the space between rank[0] and rank[1].

fRouter

private RouteSpline fRouter

fPolyBound

private DotPolyline fPolyBound

Bounding polygon for routing. An initialized array of DotPoint which can be reused without allocating DotPoint each time. (replace 'polypoints' in original 'routespl.c' code)

fSegment

private DotPolyline fSegment

fPath

private DotPath fPath

fSpline

private DotSpline fSpline

fSplineCount

private int fSplineCount

Statistics

fBoxCount

private int fBoxCount

fXDIV_EDGES

private int fXDIV_EDGES

fXDIV_XEDGE

private int fXDIV_XEDGE

fMERGE_OFFSET

private int fMERGE_OFFSET

fBOX_MINOVERLAP

private int fBOX_MINOVERLAP

Constructor Detail

Route

public Route()

Method Detail

dot

public static void dot(VirtualGraph g)

setVerbose

public static void setVerbose(boolean yes)

route

public void route(VirtualGraph g)

init

private java.util.SortedSet init(VirtualGraph g)

initChain

private java.util.SortedSet initChain()

initInterRankBoxes

private void initInterRankBoxes()

routeRegular

private DotSpline routeRegular(VirtualEdge chaintail)

Compute the spline points for edge chain starting at edge 'e'.

adjustChain

private void adjustChain(VirtualGraph graph,
                         VirtualEdge chaintail,
                         DotSpline spline,
                         DotPath path)

Move virtual vertices to routed locations so that other routing can take advantage of the spare spaces.

findOrder

private int findOrder(int x,
                      VirtualGraph.Rank rank)

Find the new order for a vertex at the given x-coordinate 'x' such that vts[neworder-1].x <= x and vts[neworder].x > x

adjustVertexWithReorder

private void adjustVertexWithReorder(int neworder,
                                     int newx,
                                     VirtualVertex head,
                                     VirtualGraph.Rank rank)

Move given vertex to location before the vertex vts[neworder] and adjust x coordinate to as close as possible to 'newx'.

adjustVertexWithoutReorder

private void adjustVertexWithoutReorder(int newx,
                                        VirtualVertex head,
                                        VirtualGraph.Rank rank)

Adjust x coordinate of given vertex to as close as possible to newx while maintaining vertex orders.

boundTailBoxes

private int boundTailBoxes(VirtualEdge e,
                           DotBox box,
                           DotBoxList ret)

Bound the inter-rank spacing below the tail.

boundHeadBoxes

private int boundHeadBoxes(VirtualEdge e,
                           int nboxes,
                           DotBoxList ret)

Bound and replace the last 'nboxes' boxes in the given DotBoxList with bounding splines at head of 'e'.

ensureContact

private void ensureContact(DotBox above,
                           DotBox box)

Ensure given box 'box' contact with box above.

ensureBoxWidth

private void ensureBoxWidth(DotBox box)

maximalBoxes

private int maximalBoxes(int side,
                         VirtualVertex v,
                         VirtualEdge ie,
                         VirtualEdge oe,
                         DotBoxList ret)

Determine the maximal bounding box around 'v' available for routing edges 'ie' and 'oe'.

neighbour

private VirtualVertex neighbour(VirtualVertex v,
                                VirtualEdge ie,
                                VirtualEdge oe,
                                int lly,
                                int ury,
                                int dir)

Get neighbour on left (dir=-1) or right (dir=1).

pathsCrossed

private boolean pathsCrossed(VirtualVertex v0,
                             VirtualVertex v1,
                             VirtualEdge ie1,
                             VirtualEdge oe1)

Check if edge chain 'ie1->v1->oe1' any cross edge chain through 'v0'.

topLeftBound

private VirtualEdge topLeftBound(VirtualEdge e)

Bound given boxes by the neighbour routed edges.

topRightBound

private VirtualEdge topRightBound(VirtualEdge e)

bottomLeftBound

private VirtualEdge bottomLeftBound(VirtualEdge e)

bottomRightBound

private VirtualEdge bottomRightBound(VirtualEdge e)

topBound

private VirtualEdge topBound(VirtualEdge e,
                             int side)

bottomBound

private VirtualEdge bottomBound(VirtualEdge e,
                                int side)

makeRegularBox

private DotBox makeRegularBox(DotBox box,
                              int side,
                              int y)

Make a box at bottom or top of an existing box. . For now, regular edges always go from top to bottom

adjustRegularPath

private void adjustRegularPath(DotPath path,
                               int firstbox,
                               int lastbox)

Adjust boxes to meet MINWIDTH and ensure overlapped.

straightLength

private int straightLength(VirtualEdge start,
                           int chainlen)

Count number of ranks that are vertically aligned. To prevent the closed packed bus-bus ranks to cause a short segment being considered as a long straight section, the actual length as ratio to rankspacing is also calculated. A BUS-BUS separation is smallest and counted as 1 unit.

straightPath

private VirtualEdge straightPath(VirtualEdge e,
                                 int len,
                                 DotSpline spline)

Construct a straight spline segment that represent 'len' edges starting at 'e'.

routePath

private int routePath(DotPath path,
                      DotPolyline ret)

Route a spline segment inside the bounding boxes of 'path'.

isSplineMidPoint

private boolean isSplineMidPoint(VirtualVertex v)

clipInstall

private void clipInstall(VirtualEdge chaintail,
                         com.port80.graph.IEdge e,
                         DotSpline s,
                         int offset)

Clip spline to the shape boundary. Update graph bounding box using the spline control points.

installBus

private void installBus(com.port80.graph.IVertex v,
                        java.lang.String name,
                        VirtualGraph.Rank rank)

clipShape

private void clipShape(VirtualVertex v,
                       java.awt.Shape shape,
                       DotSpline spline,
                       int index,
                       boolean istail)

Clip spline by vertex shape, given 'index' is the tail (left) end of the Bezier that intersect the shape. -------tail----- ----head----- | index-c-|-c--index--c-|-c--e |

clipStartArrow

private int clipStartArrow(DotSpline s,
                           int start,
                           int end,
                           com.port80.graph.IEdge e)

Clip arrow at start of spline (tail arrow if not reversed).

clipEndArrow

private int clipEndArrow(DotSpline s,
                         int start,
                         int end,
                         com.port80.graph.IEdge e)

Clip arrow at end of spline (head arrow if ve is not reversed).

dist

private double dist(DotPoint p1,
                    DotPoint p2)

dist2

private double dist2(DotPoint p1,
                     DotPoint p2)