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

Quick Search    Search Deep
Overview  Package   Class  Use  Deprecated  Index 
Home >> All >> com >> port80 >> graph >> dot >> [ impl overview ]  PREV CLASS  NEXT CLASS
SUMMARY: JavaDoc of com.port80.graph.dot.impl.VirtualGraph JAVADOC | Sourc code of com.port80.graph.dot.impl.VirtualGraph SOURCE | Download com.port80.graph.dot.impl.VirtualGraph DOWNLOAD | NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD

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

java.lang.Object
  extended bycom.port80.graph.dot.impl.VirtualGraph
public class VirtualGraph
extends java.lang.Object

Virtual graph constructed for routing from a IGraph. . VirtualGraph is created by extracting the topology information from an input IGraph for routing. . Routing information are patched back to the original graph attribute table ('pos') and the VirtualGraph can be released after each layout.

Nested Class Summary
(package private) static class VirtualGraph.AdjacencyMatrix
           
(package private)  class VirtualGraph.MinimiumSpacingIterator
          Minimium spacing (not include vertex widths) required between two vertices in the given rank.
(package private) static class VirtualGraph.Rank
           
 
Field Summary
(package private)  java.awt.Rectangle bounds
           
private static boolean CHECK
           
private static java.lang.String CLASSNAME
           
private static boolean DEBUG
           
(package private)  int defaultHalfHeight
          Default half width in pixels.
(package private)  int defaultHalfWidth
          Scaling factor (*vertexspacing) for graph margin.
(package private)  boolean fBidirectionalUseBus
           
(package private)  int fBOX_MINOVERLAP
           
(package private)  int fCELL_BASICFACTOR
           
(package private)  int fCELL_DISTFACTOR
           
(package private)  int fCELL_TURNFACTOR
           
(package private)  int fCELL_XDIV
           
(package private)  boolean fCriticalUseInBus
           
(package private)  boolean fCriticalUseOutBus
           
(package private)  int[] fCrossCounts
          Scratch path for rankCost().
(package private)  double fDISTCOST
           
(package private)  int fESpacing
          Min.
(package private)  int fHALFHEIGHT_VIRTUALVERTEX
           
(package private)  int fMERGE_OFFSET
           
(package private)  int fPTP_PERCENT
           
private  java.util.List fVertexList
          IVertex->VirtualVertex map.
private  java.util.Map fVertexMap
          List of all VirtualVertex.
(package private)  int fWEIGHT_BUS
           
(package private)  int fWEIGHT_CRITICAL
           
(package private)  int fWEIGHT_DEFAULT
           
(package private)  int fWEIGHT_STUB
           
(package private)  int fWEIGHT_VIRTUALFACTOR
           
(package private)  int fXDIV_EDGES
           
(package private)  int fXDIV_XEDGE
           
(package private)  int fXESpacing
           
(package private)  int fXPENALTY_AUX
           
(package private)  int fXPENALTY_BUS
           
(package private)  int fXPENALTY_CRITICAL
           
(package private)  int fXPENALTY_DEFAULT
           
(package private)  int fXPENALTY_STUB
           
(package private)  int fYSPACING_BUSBUS
           
(package private)  int fYSPACING_XBUS
          Default half height in pixels.
(package private)  boolean hasFlatEdges
          Layout graph in left->right orientation.
(package private)  boolean hasHeadTailLabel
          Graph has edge labels.
(package private)  boolean hasLabel
          Graph has flat edges.
private  java.util.Map iedgeMap
           
(package private)  boolean isLeftToRight
           
private  java.util.Map ivertexMap
          IEdge->VirtualEdge map.
(package private)  int margin
          Scaling factor for vertex (sideway) dimensions.
(package private)  int maxIter
           
(package private)  int maxRank
           
(package private)  int minQuit
          Graph has edge head label or edge tail label.
(package private)  int minRank
           
private  java.lang.String name
          Working vertex list, fast graph nlist in dot.
private static java.lang.String NAME
           
private  com.port80.graph.IGraph original
           
private static java.lang.String PACKAGENAME
           
(package private)  VirtualGraph.Rank[] ranks
           
(package private)  double rankSep
           
(package private)  int rankSpacing
          Graph bounds in pixel.
(package private)  int selfEdgeSize
           
private static boolean TERSE
           
private static boolean USE_MERGE
           
private static boolean VERBOSE
           
private static int VERSION
           
private static java.lang.String VERSIONNAME
           
(package private)  double vertexSep
          Scaling factor for rank dimensions.
(package private)  int vertexSpacing
          Min.
private  VirtualVertex[] vertices
           
 
Constructor Summary
VirtualGraph(com.port80.graph.IGraph g)
          Construct virtual graph for 'dot' mincross, using given ranked IGraph.
 
Method Summary
private  void addGraph(com.port80.graph.IGraph g)
          Add vertices, cluster rank leaders.
private  void adjustRanks(java.util.SortedSet sorted)
          Adjust VirtualVertex ranks to account for new created buses.
 void breakFlatCycles()
           
private  void breakFlatCycles(VirtualVertex v, java.util.Set visited, java.util.Set ancestors, VirtualGraph.AdjacencyMatrix matrix)
          Look for cycles starting from given vertex 'v'.
 void buildRanks(int pass)
          Install nodes in ranks (init_rank()).
private  void buildVertex(VirtualVertex v)
          Install a node at the current right end of its rank
(package private)  boolean checkCrossCosts()
           
 void checkOrder(java.lang.String m)
          Check all vertex orders are inside bound.
 void clear()
           
private  void createAuxChain(VirtualVertex tail, VirtualVertex head, java.lang.String name)
          Create an edge chain for connections between a vertex and its inBus and outBus duplicates.
private  void createEdgeChain(VirtualVertex tail, com.port80.graph.IEdge e)
          Create an VirtualEdge chain for the given IEdge.
private  void createStubChain(VirtualVertex tail, VirtualVertex head)
          Create an edge chain for connections between a vertex and its inBus and outBus.
 void debugPrintRanks()
           
private  void expandMergedChainWidth(VirtualEdge e)
           
 java.awt.Rectangle getBounds()
           
 java.util.List getChainList()
           
 int getDefaultHalfHeight()
           
 int getDefaultHalfWidth()
           
 int getESpacing()
           
 int getHeight()
           
 int getMargin()
           
 java.lang.String getName()
           
 com.port80.graph.IGraph getOriginal()
           
 double getRankSep()
           
 int getRankSpacing()
           
 int getSelfEdgeSize()
           
 VirtualVertex getVertex(java.lang.String name)
           
 double getVertexSep()
           
 int getVertexSpacing()
           
 VirtualVertex[] getVertices()
           
 int getWidth()
           
 int getXESpacing()
           
 boolean hasHeadTailLabel()
           
 boolean hasLabel()
           
private  void incrRank(int rank)
          Increment rank of all VirtualVertex whose rank>=v.rank except v itself.
private  void initCluster()
          For now, we ignore all the cluster stuff first.
 void initFlatOrder()
          Init.
private  void initFlatOrder(VirtualVertex v, java.util.Set visited, java.util.List ret)
          Construct reachable vertex from 'v' in post-order.
private  int localCost(VirtualVertex v, boolean tobottom)
          Determine crossing cost if vertex has port.
 void plotMinCross()
           
private  void print(int[] counts)
           
private  void printMinCross()
           
private  void queueNeighbours(VirtualVertex v, java.util.Set visited, java.util.List queue, int pass)
          Queue decendents/ancestors from v.
private  int rankCost(int r)
          Determine total real crossing cost between the specified rank (r) and the one below (r+1).
 void rankCostRemoveEdge(VirtualEdge segment)
          Adjust rankCost on removal of a segemnt.
 void removeAux()
           
 void resetCost()
           
 void restoreOrder()
          Restore saved ordering.
 void sanityCheck()
          Sanity check on vertex.order and vertex.x.
 void saveOrder()
          Save current ordering.
 void setHeight(int h)
           
 void setMaxRank(int max)
           
 void setMinRank(int min)
           
 void setWidth(int w)
           
 int staticCost()
          Pre-calculate static costs for each possible path segments.
 int staticRankCost(int r)
          Cross cost for imaginary edge from every vertices on top to every vertices at bottom.
 java.lang.String toString()
          Convert this Object to a human-readable String.
 int totalCost()
          Determine the crossing cost for current ordering.
 void updateBoundBox(int x, int y, int w, int h)
           
 void updateBoundBox(java.awt.Rectangle r)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

NAME

private static final java.lang.String NAME
See Also:
Constant Field Values

PACKAGENAME

private static final java.lang.String PACKAGENAME
See Also:
Constant Field Values

CLASSNAME

private static final java.lang.String CLASSNAME
See Also:
Constant Field Values

VERSION

private static final int VERSION
See Also:
Constant Field Values

VERSIONNAME

private static final java.lang.String VERSIONNAME
See Also:
Constant Field Values

DEBUG

private static final boolean DEBUG
See Also:
Constant Field Values

TERSE

private static final boolean TERSE
See Also:
Constant Field Values

VERBOSE

private static boolean VERBOSE

CHECK

private static boolean CHECK

USE_MERGE

private static final boolean USE_MERGE
See Also:
Constant Field Values

vertices

private VirtualVertex[] vertices

name

private java.lang.String name
Working vertex list, fast graph nlist in dot.

original

private com.port80.graph.IGraph original

iedgeMap

private java.util.Map iedgeMap

ivertexMap

private java.util.Map ivertexMap
IEdge->VirtualEdge map.

fVertexList

private java.util.List fVertexList
IVertex->VirtualVertex map.

fVertexMap

private java.util.Map fVertexMap
List of all VirtualVertex.

minRank

int minRank

maxRank

int maxRank

isLeftToRight

boolean isLeftToRight

hasFlatEdges

boolean hasFlatEdges
Layout graph in left->right orientation.

hasLabel

boolean hasLabel
Graph has flat edges.

hasHeadTailLabel

boolean hasHeadTailLabel
Graph has edge labels.

minQuit

int minQuit
Graph has edge head label or edge tail label.

maxIter

int maxIter

bounds

java.awt.Rectangle bounds

rankSpacing

int rankSpacing
Graph bounds in pixel.

vertexSpacing

int vertexSpacing
Min. spacing between ranks.

fESpacing

int fESpacing
Min. spacing between vertices.

fXESpacing

int fXESpacing

selfEdgeSize

int selfEdgeSize

ranks

VirtualGraph.Rank[] ranks

rankSep

double rankSep

vertexSep

double vertexSep
Scaling factor for rank dimensions.

margin

int margin
Scaling factor for vertex (sideway) dimensions.

defaultHalfWidth

int defaultHalfWidth
Scaling factor (*vertexspacing) for graph margin.

defaultHalfHeight

int defaultHalfHeight
Default half width in pixels.

fYSPACING_XBUS

int fYSPACING_XBUS
Default half height in pixels.

fYSPACING_BUSBUS

int fYSPACING_BUSBUS

fHALFHEIGHT_VIRTUALVERTEX

int fHALFHEIGHT_VIRTUALVERTEX

fXDIV_EDGES

int fXDIV_EDGES

fXDIV_XEDGE

int fXDIV_XEDGE

fXPENALTY_DEFAULT

int fXPENALTY_DEFAULT

fXPENALTY_BUS

int fXPENALTY_BUS

fXPENALTY_CRITICAL

int fXPENALTY_CRITICAL

fXPENALTY_STUB

int fXPENALTY_STUB

fXPENALTY_AUX

int fXPENALTY_AUX

fDISTCOST

double fDISTCOST

fWEIGHT_DEFAULT

int fWEIGHT_DEFAULT

fWEIGHT_BUS

int fWEIGHT_BUS

fWEIGHT_CRITICAL

int fWEIGHT_CRITICAL

fWEIGHT_STUB

int fWEIGHT_STUB

fWEIGHT_VIRTUALFACTOR

int fWEIGHT_VIRTUALFACTOR

fCELL_XDIV

int fCELL_XDIV

fCELL_BASICFACTOR

int fCELL_BASICFACTOR

fCELL_DISTFACTOR

int fCELL_DISTFACTOR

fCELL_TURNFACTOR

int fCELL_TURNFACTOR

fPTP_PERCENT

int fPTP_PERCENT

fBOX_MINOVERLAP

int fBOX_MINOVERLAP

fMERGE_OFFSET

int fMERGE_OFFSET

fCriticalUseInBus

boolean fCriticalUseInBus

fCriticalUseOutBus

boolean fCriticalUseOutBus

fBidirectionalUseBus

boolean fBidirectionalUseBus

fCrossCounts

int[] fCrossCounts
Scratch path for rankCost().

Constructor Detail

VirtualGraph

public VirtualGraph(com.port80.graph.IGraph g)
Construct virtual graph for 'dot' mincross, using given ranked IGraph. . The VirtualGraph contains VirtualVertex created to represent the top level vertices and clusters of the input graph. Clusters are represented by VirtualVertex called 'rank leaders', one for each rank in the cluster. . Also for each edges that connects two vertices in different rank, a VirtualVertex is created as place holder along the route in each rank between the two vertices. The original edges are replaced by a VirtualEdge chain and the placeholder VirtualVertex along the route. If the edge has label, it would be represented by the VirtualVertex in the middle of the chain. . Flat edges (edge between vertex on the same rank), intra-cluster edges are ignored. Parallel edges between same pair of vertices and have same label (or no labels) are merged into one to make sure they would route together. . Bus vertices are added for each real vertex (say 'v') that have lots of input or output edges and new ranks for the bus vertices are inserted before and after 'v'. Ranks for vertices below 'v' are incremented accordingly. r-1 r-1 . r --- new input bus rank --- r v -> r+1 v . r+2 --- new output bus rank --- r+1 r+3 A VirtualVertex is created for each edge 'e' to 'v' in addition to a VirtualVertex for the connection from the bus to 'v'. Each edge 'e' is then terminated at the bus vertex instead of at 'v' and thus allow them to be rearranged independently. | | v v --'iv0'--'iv1'--'iv2'-- | v 'v' | v --'ov0'--'ov1'--'ov2'-- | | v v

Method Detail

buildRanks

public void buildRanks(int pass)
Install nodes in ranks (init_rank()). The initial ordering ensure that series-parallel graphs such as trees are drawn with no crossings. It tries searching in- and out-edges and takes the better of the two initial orderings.

buildVertex

private void buildVertex(VirtualVertex v)
Install a node at the current right end of its rank

queueNeighbours

private void queueNeighbours(VirtualVertex v,
                             java.util.Set visited,
                             java.util.List queue,
                             int pass)
Queue decendents/ancestors from v.

addGraph

private void addGraph(com.port80.graph.IGraph g)
Add vertices, cluster rank leaders. Only top level clusters (g.parent.parent==null) would be added. All vertices in the top level cluster and its sub-clusters should be collapsed into its rank leaders.

initCluster

private void initCluster()
For now, we ignore all the cluster stuff first.

createEdgeChain

private void createEdgeChain(VirtualVertex tail,
                             com.port80.graph.IEdge e)
Create an VirtualEdge chain for the given IEdge.

expandMergedChainWidth

private void expandMergedChainWidth(VirtualEdge e)

createStubChain

private void createStubChain(VirtualVertex tail,
                             VirtualVertex head)
Create an edge chain for connections between a vertex and its inBus and outBus.

createAuxChain

private void createAuxChain(VirtualVertex tail,
                            VirtualVertex head,
                            java.lang.String name)
Create an edge chain for connections between a vertex and its inBus and outBus duplicates.

removeAux

public void removeAux()

getChainList

public java.util.List getChainList()

adjustRanks

private void adjustRanks(java.util.SortedSet sorted)
Adjust VirtualVertex ranks to account for new created buses.

incrRank

private void incrRank(int rank)
Increment rank of all VirtualVertex whose rank>=v.rank except v itself.

getName

public java.lang.String getName()

getOriginal

public com.port80.graph.IGraph getOriginal()

getVertex

public VirtualVertex getVertex(java.lang.String name)

getVertices

public VirtualVertex[] getVertices()

setMinRank

public void setMinRank(int min)

setMaxRank

public void setMaxRank(int max)

getHeight

public int getHeight()

getWidth

public int getWidth()

getBounds

public java.awt.Rectangle getBounds()

getRankSep

public double getRankSep()

getVertexSep

public double getVertexSep()

getMargin

public int getMargin()

getDefaultHalfWidth

public int getDefaultHalfWidth()

getDefaultHalfHeight

public int getDefaultHalfHeight()

getRankSpacing

public int getRankSpacing()

getVertexSpacing

public int getVertexSpacing()

getESpacing

public int getESpacing()

getXESpacing

public int getXESpacing()

getSelfEdgeSize

public int getSelfEdgeSize()

hasLabel

public boolean hasLabel()

hasHeadTailLabel

public boolean hasHeadTailLabel()

setWidth

public void setWidth(int w)

setHeight

public void setHeight(int h)

clear

public void clear()

toString

public java.lang.String toString()
Description copied from class: java.lang.Object
Convert this Object to a human-readable String. There are no limits placed on how long this String should be or what it should contain. We suggest you make it as intuitive as possible to be able to place it into System.out.println() 55 and such.

It is typical, but not required, to ensure that this method never completes abruptly with a java.lang.RuntimeException.

This method will be called when performing string concatenation with this object. If the result is null, string concatenation will instead use "null".

The default implementation returns getClass().getName() + "@" + Integer.toHexString(hashCode()).

updateBoundBox

public void updateBoundBox(int x,
                           int y,
                           int w,
                           int h)

updateBoundBox

public void updateBoundBox(java.awt.Rectangle r)

saveOrder

public void saveOrder()
Save current ordering.

restoreOrder

public void restoreOrder()
Restore saved ordering.

resetCost

public void resetCost()

localCost

private int localCost(VirtualVertex v,
                      boolean tobottom)
Determine crossing cost if vertex has port.

rankCost

private int rankCost(int r)
Determine total real crossing cost between the specified rank (r) and the one below (r+1). cost=sum(e.xPenalty*f.xPenalty) for every edges e & f that crossed. Used by Mincross.

print

private void print(int[] counts)

totalCost

public int totalCost()
Determine the crossing cost for current ordering.

breakFlatCycles

public void breakFlatCycles()

breakFlatCycles

private void breakFlatCycles(VirtualVertex v,
                             java.util.Set visited,
                             java.util.Set ancestors,
                             VirtualGraph.AdjacencyMatrix matrix)
Look for cycles starting from given vertex 'v'.

initFlatOrder

public void initFlatOrder()
Init. order of the nodes in each rank. This may be done by a depth-first or breadth-first search starting with vertices of minimum rank. Vertices are assigned positions in their ranks in left-to-right order as the search progresses. This strategy ensures that the initial ordering of a tree has no crossings.

initFlatOrder

private void initFlatOrder(VirtualVertex v,
                           java.util.Set visited,
                           java.util.List ret)
Construct reachable vertex from 'v' in post-order. This is the same as doing a topological sort in reverse order. NOTE: In original code, order is left-to-right from tail->head if rankdir=top-to-bottom and reversed otherwise. Probably because 'dot' coordinate system have origin at the lower left corner instead of upper-left corner as in Java. In Java coordinate system, we don't have to reverse.

debugPrintRanks

public void debugPrintRanks()

plotMinCross

public void plotMinCross()

staticCost

public int staticCost()
Pre-calculate static costs for each possible path segments.

staticRankCost

public int staticRankCost(int r)
Cross cost for imaginary edge from every vertices on top to every vertices at bottom. v.crossCost[i] is the sum of all xPenalty that the edge v->rank1.vts[i] would crossed.

rankCostRemoveEdge

public 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.

checkCrossCosts

boolean checkCrossCosts()

sanityCheck

public void sanityCheck()
Sanity check on vertex.order and vertex.x.

printMinCross

private void printMinCross()

checkOrder

public void checkOrder(java.lang.String m)
Check all vertex orders are inside bound.

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