com.tensegrity.graph.algorithm
Class TransitiveClosure

java.lang.Object
  com.tensegrity.graph.algorithm.TransitiveClosure

All Implemented Interfaces:

TransformAlgorithm

public class TransitiveClosure

extends java.lang.Object

implements TransformAlgorithm

Takes a graph and outputs a new (and probably more dense) graph which has direct edges for transitive connectivity information that was originally only reachable by traversing multiple nodes. This algorithm works in

O(|E|)

time and is likely the algorithm of choice. Nevertheless, the AllPairsShortestPath algorithm implicitly computes a transitive closure as well.

Version:

$Id: TransitiveClosure.java,v 1.17 2005/11/18 15:52:08 KevinCVS Exp $

Author:

Stepan Rutz

Constructor Summary

TransitiveClosure()
Constructs a new stateless instance of the TransitiveClosure algorithm.

Method Summary

Graph

apply(Graph input) Computes the transitive closure Graph for the given input Graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

TransitiveClosure

public TransitiveClosure()

Constructs a new stateless instance of the TransitiveClosure algorithm.

Method Detail

apply

public Graph apply(Graph input)
            throws GraphException

Computes the transitive closure Graph for the given input Graph.

Specified by:

apply in interface TransformAlgorithm

Parameters:

input - the input Graph.

Returns:

the transformed output Graph.

Throws:

GraphException - if creation of the output Graph failed.