Search this API

y.layout.planar
Class VertexOrder

java.lang.Object
  extended by y.layout.planar.VertexOrder

public class VertexOrder
extends java.lang.Object

Computes an ordering of the vertices of an graph. The ordering is a topological ordering for the subgraph induced by the directed edges.

 

Field Summary
protected  boolean allowRandomization
           
protected  java.util.ArrayList candidateList
           
protected  int[] degree
           
protected  Graph graph
           
protected  java.util.ArrayList graphNodes
           
protected  java.util.ArrayList neighbors
           
protected  YRandom random
           
protected  long seed
           
protected  boolean[] selected
           
 
Constructor Summary
VertexOrder()
           
 
Method Summary
 void computeVertexOrder(NodeList result)
          This method orders the vertices to place them on a line.
protected  void getMinDegreeNodes(java.util.ArrayList nodes, java.util.ArrayList result)
          Returns from a list of nodes the list of nodes with minimal degree and with indegree zero of directed edges.
protected  void initDegrees()
          This method calculates the potential of each node to cause a direction error.
protected  Node randomSelectNode(java.util.ArrayList _nl)
          selects a Node from a list of nodes.
 void selectNode(java.util.ArrayList graphNodes, java.util.ArrayList candidateList, java.util.ArrayList neighbors, NodeList result)
          Selects a node form the candidate list and updates the data structures accordingly.
 void setAllowRandomization(boolean allowRandomization)
          Sets if the randomized version of the algorithm is used.
 void setGraph(Graph graph)
          Sets the graph for which the vertex order is computed.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

graph

protected Graph graph

allowRandomization

protected boolean allowRandomization

degree

protected int[] degree

selected

protected boolean[] selected

graphNodes

protected java.util.ArrayList graphNodes

neighbors

protected java.util.ArrayList neighbors

candidateList

protected java.util.ArrayList candidateList

random

protected YRandom random

seed

protected long seed
Constructor Detail

VertexOrder

public VertexOrder()
Method Detail

setGraph

public void setGraph(Graph graph)
Sets the graph for which the vertex order is computed.

Parameters:
graph - an instance of graph.

setAllowRandomization

public void setAllowRandomization(boolean allowRandomization)
Sets if the randomized version of the algorithm is used.


computeVertexOrder

public void computeVertexOrder(NodeList result)
This method orders the vertices to place them on a line. It implements the first phase of the Goldschmidt-Takvorian heuristic


initDegrees

protected void initDegrees()
This method calculates the potential of each node to cause a direction error. When selected by vertex order, the potential must be zero or upward planarity cannot be reached. Undirected edges' potential is set to zero by default, because they never cause any trouble in that belongings.


getMinDegreeNodes

protected void getMinDegreeNodes(java.util.ArrayList nodes,
                                 java.util.ArrayList result)
Returns from a list of nodes the list of nodes with minimal degree and with indegree zero of directed edges.

Parameters:
nodes - the input list
result - result of the computation

selectNode

public void selectNode(java.util.ArrayList graphNodes,
                       java.util.ArrayList candidateList,
                       java.util.ArrayList neighbors,
                       NodeList result)
Selects a node form the candidate list and updates the data structures accordingly.

Parameters:
graphNodes - the list of unselected nodes.
candidateList - list of nodes from which the the node is selected. Sublist of graphNodes.
neighbors - the neighbors of the selected node, which are in graphNodes are stored here.
result - the list of selected nodes. The node selected by this method will be appended to this list.

randomSelectNode

protected Node randomSelectNode(java.util.ArrayList _nl)
selects a Node from a list of nodes.

Parameters:
_nl - a list of instance of Node.
Returns:
an arbitrary Node contained in _nl.

© Copyright 2000-2022,
yWorks GmbH.
All rights reserved.