diva.pod.lwgraph

Class Traversal

java.lang.Object

diva.pod.lwgraph.Traversal

public final class Traversal
extends Object

A primitive data structure that makes graph traversal and algorithms more efficient. Clients can instantiate and use this class directly if they don't mind dealing with integer indices to represent nodes and edges. A more friendly but less direct and efficient API is exposed by the LightweightGraph class.

An object of this class can be instantiated on an Topology, and then used to perform more efficient graph traversals. The contents of this class are valid only while the graph structure is maintained. As soon as the graph is modified, this object must be discarded and a new one created.

A traversal stores only the "forward" direction of a graph. If a client wants to be able to traverse a graph in both directions, then it will need to create a traversal on the graph, reverse the graph and create a traversal on the reversed graph, and then reverse the graph back again.

Although it seems like the approach like constructing a new Traversal object many times is inefficient, it is actually not. I also wrote a class the contained the data and functionality of both Topology and Traversal. As edges were added, the arrays of successor/predecessor nodes were updated each time. This class was consistently slower (by 10% - 25%) than constructing separate Traversal objects. Probably something to do with the way the java optimizer works. Also, the code was trickier when deleting things, so I left it like this. The performance is still about 50 times better than diva.graph.

If a graph becomes very sparse through a lot of node deletion, this class will get a little (time and space) inefficient. This can be avoided by compacting the graph first.

Version:

$Revision: 1.6 $

Author:

John Reekie

Constructor Summary

Constructors

Constructor and Description
Traversal(Topology top) Create a new traversal on the given topology

Method Summary

Modifier and Type	Method and Description
int	getEdgeCount(int node) Return the number of edges leaving the given node.
int[]	getEdges(int node) Return the array of edges leaving the given node.
int	getNodeCount() Return the number of nodes in the graph
int[]	getNodes() Return the array of nodes in the graph.
int	getRootCount() Return the number of roots of the graph
int[]	getRoots() Return the array of roots of the graph.
int	getSuccessorCount(int node) Return the number of successors of the given node.
int[]	getSuccessors(int node) Return the array of successors of the given node.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Traversal

public Traversal(Topology top)

Create a new traversal on the given topology

Method Detail

getEdgeCount

public int getEdgeCount(int node)

Return the number of edges leaving the given node.

getEdges

public int[] getEdges(int node)

Return the array of edges leaving the given node. The result must not be modified. Result is null if the node has no edges.

getRootCount

public int getRootCount()

Return the number of roots of the graph

getRoots

public int[] getRoots()

Return the array of roots of the graph. The result must not be modified. Result is null if the graph has no roots.

getNodeCount

public int getNodeCount()

Return the number of nodes in the graph

getNodes

public int[] getNodes()

Return the array of nodes in the graph. The result must not be modified.

getSuccessorCount

public int getSuccessorCount(int node)

Return the number of successors of the given node.

getSuccessors

public int[] getSuccessors(int node)

Return the array of successors of the given node. The result must not be modified. Result is null if the node has no successors. The successor array may contain the same node more than once (if there is more than one edge to that node).