org.multijava.util
Class DirectedAcyclicGraph

java.lang.Object
  org.multijava.util.DirectedAcyclicGraph

public class DirectedAcyclicGraph

extends java.lang.Object

This utility class represents a directed acyclic graph. It is useful for sorting collections that contain some incomparable members.

Version:

$Revision: 1.8 $

Author:

Curtis Clifton

Nested Class Summary
static interface	DirectedAcyclicGraph.EdgeCalculator

 

Field Summary
private  boolean[][]	edgeExists           The edges of the DAG.
private  int	nextResultSlot           Index to the next entry to be filled in result.
private  java.lang.Object[]	result           Working space for the depth-first search algorithm
private  java.lang.Object[]	vertex           The vertices of the DAG.
private  boolean[]	visited           Tracks whether the depth-first search algorithm has visited a given vertex.

 

Constructor Summary

DirectedAcyclicGraph(java.lang.Object[] vertices, DirectedAcyclicGraph.EdgeCalculator calc)           Constructs a directed acyclic graph with the given objects as the vertices and the given calculator specifying the edges.

 

Method Summary
java.lang.Object[]	inDFSOrder()           Returns the vertices in depth-first search order.
private  void	initEdges(DirectedAcyclicGraph.EdgeCalculator calc)           Initializes the edges of the DAG representation using the given calculator.
private  void	showDAG()
private  void	visit(int pos)           Helper method for depthFirstOrder.

 

Methods inherited from class java.lang.Object

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

 

Field Detail

vertex

private final java.lang.Object[] vertex

The vertices of the DAG.

edgeExists

private final boolean[][] edgeExists

The edges of the DAG. edgeExists[i][j] ==> there is an edge from vertex[i] to vertex[j]

result

private java.lang.Object[] result

Working space for the depth-first search algorithm

nextResultSlot

private int nextResultSlot

Index to the next entry to be filled in result.

visited

private boolean[] visited

Tracks whether the depth-first search algorithm has visited a given vertex.

DirectedAcyclicGraph

public DirectedAcyclicGraph(java.lang.Object[] vertices,
                            DirectedAcyclicGraph.EdgeCalculator calc)

Constructs a directed acyclic graph with the given objects as the vertices and the given calculator specifying the edges.

 requires vertices != null && calc != null &&
          acyclic(vertices, calc);
 

initEdges

private void initEdges(DirectedAcyclicGraph.EdgeCalculator calc)

Initializes the edges of the DAG representation using the given calculator.

inDFSOrder

public java.lang.Object[] inDFSOrder()

Returns the vertices in depth-first search order. Using algorithm from Cormen, Leiserson, & Rivest, 1990, p. 478.

visit

private void visit(int pos)

Helper method for depthFirstOrder.

showDAG

private void showDAG()