y.layout.planar
Class VertexOrder

java.lang.Object
  |
  +--y.layout.planar.VertexOrder

public class VertexOrder
extends 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  ArrayList candidateList
           
protected  int[] degree
           
protected  Graph graph
           
protected  ArrayList graphNodes
           
protected  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(ArrayList nodes, 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(ArrayList _nl)
          selects a Node from a list of nodes.
 void selectNode(ArrayList graphNodes, ArrayList candidateList, ArrayList neighbors, NodeList result)
          Selects a node form the candidate list and updates the datastructures 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 ArrayList graphNodes

neighbors

protected ArrayList neighbors

candidateList

protected 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(ArrayList nodes,
                                 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(ArrayList graphNodes,
                       ArrayList candidateList,
                       ArrayList neighbors,
                       NodeList result)
Selects a node form the candidate list and updates the datastructures accordingly.

Parameters:
graphNodes - the list of nonselected 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(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-2003,
yWorks GmbH.
All rights reserved.

2003