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 NetworkSimplex  

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

---

public class NetworkSimplex

extends java.lang.Object

Network Simplex Algorithm for ranking an acyclic directed graph. . Clusters and same/min/max ranked subgraphs should have been collapsed into a single vertex for ranking.

---

Field Summary
private  DotEdge	bestEnter
private  DotVertex	cutChild
private static boolean	DEBUG
private  java.util.List	fRoots
private  DotVertex[]	grVertices
private static NetworkSimplex	instance
private  int	minSlack
private static java.lang.String	NAME
private  int	nTreeEdges
private  int	nTreeVts
private  int	searchIndex
private  int	searchSize
private static int	SEARCHSIZE
private  DotEdge[]	treeEdges
private  DotVertex[]	treeVts           All input graph vertices.
private static java.lang.String	USAGE
private static boolean	VERBOSE

 

Constructor Summary

NetworkSimplex()

 

Method Summary
private  void	addTreeEdge(DotEdge e)
private  void	checkCutValues()           Check that cut values are correct by recalculating all the cut vaules.
private  int	checkRanks()           Check that ranks do not violate minLength of edges.
private  void	checkTight()           Check that vertices have a valid tight tree.
private  void	checkTree()           Check number of tree edges match treeEdges size.
private  void	cleanup()
private  void	dfCutValue(DotVertex v, DotEdge parent)           Calculate cut value of edges in a tree from bottom up.
private  void	dfEnterInEdge(DotVertex v)           Find an non-tree edge with minimum slack going from head component to the tail component.
private  void	dfEnterOutEdge(DotVertex v)           Find an non-tree edge with minimum slack going from head component to the tail component.
static int	dotRank(DotGraph g, double nslimit, boolean tbmode)
private  DotEdge	enterEdge(DotEdge e)           Find an non-tree edge with minimum slack going from head component to the tail component.
private  void	exchangeTreeEdges(DotEdge leave, DotEdge enter)           Swap non-tree edge 'leave' with tree edge 'enter'.
private  void	feasibleTree()
static NetworkSimplex	getInstance()
private  DotVertex	incident(DotEdge e)
private  void	initCutValues()
private  void	initRank()           Assign ranks by breadth first search and init vertices.
private  DotEdge	leaveEdge()           Find edge with minimum cutValue starting from the last leave edge in round-robin.
private  void	lrBalance()
int	rank(DotGraph g, double nslimit, boolean tbmode)
private  void	rerank(DotVertex v, int delta)           Adjust ranks of subtree at v by -delta.
private  int	sanityChecks()
private  java.lang.String	sprintTreeVts()
private  void	tbBalance()           Move vertex that don't care (with same inweight and outweight) to less populated rank.
private  int	tightTree()           Find all edges with slack==0 into treeVts and treeEdges.
private  boolean	treeSearch(DotVertex v)           Find tree edges started from v outward that have slack==0.
private  DotVertex	treeUpdate(DotVertex v, DotVertex w, int cutvalue, boolean fromtail)           Walk up from v to LCA(v,w), setting new cut values.
private  void	update(DotEdge leave, DotEdge enter)           Compute new cut values, ranks, and exchange leave and enter.

 

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

---

USAGE

private static final java.lang.String USAGE

See Also:

Constant Field Values

---

DEBUG

private static final boolean DEBUG

See Also:

Constant Field Values

---

VERBOSE

private static boolean VERBOSE

---

SEARCHSIZE

private static final int SEARCHSIZE

See Also:

Constant Field Values

---

instance

private static NetworkSimplex instance

---

grVertices

private DotVertex[] grVertices

---

treeVts

private DotVertex[] treeVts

All input graph vertices.

---

treeEdges

private DotEdge[] treeEdges

---

nTreeVts

private int nTreeVts

---

nTreeEdges

private int nTreeEdges

---

searchSize

private int searchSize

---

fRoots

private java.util.List fRoots

---

cutChild

private DotVertex cutChild

---

bestEnter

private DotEdge bestEnter

---

minSlack

private int minSlack

---

searchIndex

private int searchIndex

Constructor Detail

NetworkSimplex

public NetworkSimplex()

Method Detail

getInstance

public static NetworkSimplex getInstance()

---

dotRank

public static int dotRank(DotGraph g,
                          double nslimit,
                          boolean tbmode)

---

rank

public int rank(DotGraph g,
                double nslimit,
                boolean tbmode)

---

initRank

private void initRank()

Assign ranks by breadth first search and init vertices.

---

feasibleTree

private void feasibleTree()

---

tightTree

private int tightTree()

Find all edges with slack==0 into treeVts and treeEdges.

---

treeSearch

private boolean treeSearch(DotVertex v)

Find tree edges started from v outward that have slack==0.

---

incident

private DotVertex incident(DotEdge e)

---

addTreeEdge

private void addTreeEdge(DotEdge e)

---

initCutValues

private void initCutValues()

---

dfCutValue

private void dfCutValue(DotVertex v,
                        DotEdge parent)

Calculate cut value of edges in a tree from bottom up.

---

leaveEdge

private DotEdge leaveEdge()

Find edge with minimum cutValue starting from the last leave edge in round-robin.

---

dfEnterOutEdge

private void dfEnterOutEdge(DotVertex v)

Find an non-tree edge with minimum slack going from head component to the tail component.

---

dfEnterInEdge

private void dfEnterInEdge(DotVertex v)

Find an non-tree edge with minimum slack going from head component to the tail component.

---

enterEdge

private DotEdge enterEdge(DotEdge e)

Find an non-tree edge with minimum slack going from head component to the tail component.

---

exchangeTreeEdges

private void exchangeTreeEdges(DotEdge leave,
                               DotEdge enter)

Swap non-tree edge 'leave' with tree edge 'enter'.

---

treeUpdate

private DotVertex treeUpdate(DotVertex v,
                             DotVertex w,
                             int cutvalue,
                             boolean fromtail)

Walk up from v to LCA(v,w), setting new cut values.

---

update

private void update(DotEdge leave,
                    DotEdge enter)

Compute new cut values, ranks, and exchange leave and enter.

---

rerank

private void rerank(DotVertex v,
                    int delta)

Adjust ranks of subtree at v by -delta.

---

lrBalance

private void lrBalance()

---

tbBalance

private void tbBalance()

Move vertex that don't care (with same inweight and outweight) to less populated rank.

---

cleanup

private void cleanup()

---

checkTight

private void checkTight()

Check that vertices have a valid tight tree.

---

checkCutValues

private void checkCutValues()

Check that cut values are correct by recalculating all the cut vaules.

---

checkRanks

private int checkRanks()

Check that ranks do not violate minLength of edges.

---

checkTree

private void checkTree()

Check number of tree edges match treeEdges size.

---

sanityChecks

private int sanityChecks()

---

sprintTreeVts

private java.lang.String sprintTreeVts()

---

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

---