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