JML

org.multijava.util
Class DirectedAcyclicGraph

java.lang.Object
  extended byorg.multijava.util.DirectedAcyclicGraph

public class DirectedAcyclicGraph
extends 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  Object[] result
          Working space for the depth-first search algorithm
private  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(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
 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 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 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.

Constructor Detail

DirectedAcyclicGraph

public DirectedAcyclicGraph(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);
 

Method Detail

initEdges

private void initEdges(DirectedAcyclicGraph.EdgeCalculator calc)
Initializes the edges of the DAG representation using the given calculator.


inDFSOrder

public 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()

JML

JML is Copyright (C) 1998-2002 by Iowa State University and is distributed under the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This release depends on code from the MultiJava project and is based in part on the Kopi project Copyright (C) 1990-99 DMS Decision Management Systems Ges.m.b.H.