com.lf.commons.graph

Class AdjacencyListGraph

java.lang.Object

com.lf.commons.graph.AdjacencyListGraph

public class AdjacencyListGraph
extends java.lang.Object

Represents a graph represented by adjacency lists.

This is based on the C algorithm data structures introduced by the book "Algorithms in C" written by Robert Sedgewick. Adjacency lists are more suitable for graphs that are not dense than adjacency matrices. For instance you can easily convert a list of database schemas with foreign key relations into a graph representation. Then you are able to determine the optimal export order for table data so that it can be imported easily without constraint violations. This is called the reverse topological order.

This nodes used by this class are of type Object so that you can build up your graphs with any object type.

Since:

1.6

Version:

$Revision: 1.4 $, $Date: 2012/12/28 11:44:25 $

Author:

Axel Schwolow

Field Summary

Fields

Modifier and Type	Field and Description
protected java.util.Vector<java.lang.Object>	adjLists The adjacency lists in the order as the nodes wre added.
protected java.util.Hashtable<java.lang.Object,java.lang.Object[]>	cacheListByNode The unique identifier of the node (e.g. database table name).

Constructor Summary

Constructors

Constructor and Description
AdjacencyListGraph() Constructor for this class.

Method Summary

Methods

Modifier and Type	Method and Description
void	addAdjacencyList(java.lang.Object node, java.lang.Object[] list) Adds an adjacency list for a graph node.
void	debugPrint() Prints the adjacency lists currently managed by this object.
protected void	finalize() Helps the garbage collector.
java.util.Vector<java.lang.Object>	findCycles() Checks whether this adjacency list graph has cycles.
java.lang.Object[]	getAdjacencyList(java.lang.Object node) Provides the adjacency list for the given node.
java.lang.Object[]	getAdjacencyNodes() Provides the list of nodes for which adjacency lists do exist.
java.util.Vector<java.lang.Object>	sortTopologically(boolean reverse) Performs topological sorting of the nodes of this adjacency list graph.

Methods inherited from class java.lang.Object

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

Field Detail

cacheListByNode

protected java.util.Hashtable<java.lang.Object,java.lang.Object[]> cacheListByNode

The unique identifier of the node (e.g. database table name).

adjLists

protected java.util.Vector<java.lang.Object> adjLists

The adjacency lists in the order as the nodes wre added.

Constructor Detail

AdjacencyListGraph

public AdjacencyListGraph()

Constructor for this class.

Since:

1.6

Method Detail

finalize

protected void finalize()
                 throws java.lang.Throwable

Helps the garbage collector.

Overrides:

finalize in class java.lang.Object

Throws:

java.lang.Throwable

addAdjacencyList

public void addAdjacencyList(java.lang.Object node,
                    java.lang.Object[] list)

Adds an adjacency list for a graph node.

Parameters:

node - The node object

list - The list for the node

Throws:

java.lang.NullPointerException - If parameters are null

Since:

1.6

getAdjacencyList

public java.lang.Object[] getAdjacencyList(java.lang.Object node)

Provides the adjacency list for the given node.

Parameters:

node - The node object

Returns:

The adjacency list, may be null

Throws:

java.lang.NullPointerException - If parameters are null

Since:

1.6

getAdjacencyNodes

public java.lang.Object[] getAdjacencyNodes()

Provides the list of nodes for which adjacency lists do exist.

A MissingValue object indicates that a foreign key relation could be be resolved due to a missing table definition.

Returns:

The adjacency list nodes

Since:

1.6

findCycles

public java.util.Vector<java.lang.Object> findCycles()

Checks whether this adjacency list graph has cycles.

A cycle is found if a node has a connection to itself following the directed edges (paths).

Returns:

The cycle nodes, zero-length indicates acyclic graph

Since:

1.6

sortTopologically

public java.util.Vector<java.lang.Object> sortTopologically(boolean reverse)

Performs topological sorting of the nodes of this adjacency list graph.

A fundamental operation on directed acyclic graphs is processing the vertices of the graph in such an order that no vertex is processed before any vertex that points to it.

Parameters:

reverse - Reverse sorting?

Returns:

The sorted nodes

Since:

1.6

debugPrint

public void debugPrint()

Prints the adjacency lists currently managed by this object.

Since:

1.6