java.lang.Object
com.port80.graph.dot.impl.MinCross
- public class MinCross
- extends java.lang.Object
Find an ordering with minimum edge crossing for a ranked graph with
clusters are expanded.
. The rank structure is global (not allocated per cluster)
because mincross may compare nodes in different clusters.
|
Method Summary |
static int |
dot(VirtualGraph g,
int startpass,
int endpass,
int seed)
|
private boolean |
flatMedian(VirtualVertex v)
When given vertex 'v' do not have vertically connections, try
determine its median value from one of its peer 'w' that do. |
static MinCross |
getInstance()
|
private int |
inCost(VirtualVertex v,
VirtualVertex w,
boolean swap,
boolean reverse)
For each input to v crossed input to w, cost+=product of
xpenalty of the crossed edges. |
private boolean |
medians(VirtualGraph g,
int r0,
int r1)
|
private int |
minCross(VirtualGraph g,
int startpass,
int endpass,
int seed)
Run minCross algorithm on given graph 'g'. |
private int |
minCrossStep(VirtualGraph g,
int iter)
|
private int |
outCost(VirtualVertex v,
VirtualVertex w,
boolean swap,
boolean reverse)
Crossing cost between v and w if v is on left of w. |
private void |
permutate(VirtualGraph g,
int seed)
Cost of route distance approximated by absolute order distance
of tails to 'v'. |
private boolean |
reorder(VirtualGraph g,
int r,
boolean reverse,
boolean hasnoswap)
A special (bubble) sort function on the given rank that
reorder vertices in ascending median value but preserve order
of flat connected (keepOrder) vertices. |
void |
transpose(VirtualGraph g,
boolean reverse)
|
private int |
transposeStep(VirtualGraph g,
int r,
int step,
boolean reverse)
|
| Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
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 final boolean CHECK
- See Also:
- Constant Field Values
VERBOSE
private static boolean VERBOSE
MCSCALE
private static final int MCSCALE
- See Also:
- Constant Field Values
convergence
private static final double convergence
- See Also:
- Constant Field Values
instance
private static MinCross instance
niter
int niter
fDISTCOST
double fDISTCOST
MinCross
public MinCross()
getInstance
public static MinCross getInstance()
dot
public static int dot(VirtualGraph g,
int startpass,
int endpass,
int seed)
minCross
private int minCross(VirtualGraph g,
int startpass,
int endpass,
int seed)
- Run minCross algorithm on given graph 'g'.
. Even passes use out edges from minRank to maxRank.
. Odd passes use in edges from maxRank to minRank.
. Run MaxIter iterations for each pass.
minCrossStep
private int minCrossStep(VirtualGraph g,
int iter)
medians
private boolean medians(VirtualGraph g,
int r0,
int r1)
flatMedian
private boolean flatMedian(VirtualVertex v)
- When given vertex 'v' do not have vertically connections, try
determine its median value from one of its peer 'w' that do.
Such that 'v'->'w' or 'w'->'v' from left to right.
NOTE:
. The original code tried to find the rightmost tail and put
'v' on right of it or the leftmost head and put 'v' on left
of it. Flat connected nodes are not swapped, the flat
order are always preserved. Since we are iterating from left
to right, there is no problem with the using the median
value from the rightmost tail. But there is no guarantee
that the leftmost head have valid median value.
reorder
private boolean reorder(VirtualGraph g,
int r,
boolean reverse,
boolean hasnoswap)
- A special (bubble) sort function on the given rank that
reorder vertices in ascending median value but preserve order
of flat connected (keepOrder) vertices.
NOTE:
. Since for now, the virtual graph only have the rank leaders
from the clusters, we don't need the sawclust stuff from the
original code that filter out vertices after the leader.
transpose
public void transpose(VirtualGraph g,
boolean reverse)
transposeStep
private int transposeStep(VirtualGraph g,
int r,
int step,
boolean reverse)
inCost
private int inCost(VirtualVertex v,
VirtualVertex w,
boolean swap,
boolean reverse)
- For each input to v crossed input to w, cost+=product of
xpenalty of the crossed edges.
For each input to a vertex, cost+=Math.abs(tail.order-v.order).
outCost
private int outCost(VirtualVertex v,
VirtualVertex w,
boolean swap,
boolean reverse)
- Crossing cost between v and w if v is on left of w.
permutate
private void permutate(VirtualGraph g,
int seed)
- Cost of route distance approximated by absolute order distance
of tails to 'v'.
JAVADOC | 
SOURCE | 
DOWNLOAD | NESTED | FIELD | CONSTR | METHOD