y.algo
Class Transitivity

java.lang.Object
  |
  +--y.algo.Transitivity

public class Transitivity

extends Object

Provides algorithms to compute reachability information for directed, acyclic graphs:

• transitive closure
• transitive reduction

Constructor Summary

Transitivity()

Method Summary

static void	transitiveClosure(Graph graph) Calculates the transitive closure for a directed acyclic graph.
static void	transitiveClosure(Graph graph, EdgeList addedEdges) Like Transitivity.transitiveClosure(Graph), additionally this method returns the edges that have been added to the graph.
static void	transitiveReduction(Graph graph) Calculates the transitive reduction for a directed acyclic graph.
static void	transitiveReduction(Graph graph, EdgeList transitiveEdges) Like Transitivity.transitiveReduction(Graph) this method calculates the transitive reduction of a graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

Transitivity

public Transitivity()

Method Detail

transitiveClosure

public static void transitiveClosure(Graph graph)

Calculates the transitive closure for a directed acyclic graph.

The reflexive, transitive closure is defined as follows:
Let G = (V,E) be an directed acyclic graph.
The directed acyclic graph G* = (V,E*) is the reflexive, transitive closure of G,
if (v,w) in E* iff there is a path from v to w in G.

REMARK:
Note, that this implementation produces the transitive closure and not the reflexive, transitive closure of the specified graph, since no self-loops are added to the specified graph.

Precondition:

GraphChecker.isAcyclic(graph)

Parameters:

graph - input graph to which this method will add transitive edges if necessary.

transitiveClosure

public static void transitiveClosure(Graph graph,
                                     EdgeList addedEdges)

Like Transitivity.transitiveClosure(Graph), additionally this method returns the edges that have been added to the graph.

Precondition:

GraphChecker.isAcyclic(graph)

Parameters:

graph - input graph to which this method will add transitive edges if necessary.

addedEdges - contains edges that have been added to the graph by this method.

transitiveReduction

public static void transitiveReduction(Graph graph)

Calculates the transitive reduction for a directed acyclic graph. The transitive edges in the graph will be removed by this method.

The transitive reduction is defined as follows:
Let G = (V,E) be an directed acyclic graph.
The directed acyclic graph G* = (V,E*) is the transitive reduction of G,
if (v,w) in E* iff there is no path from v to w in G of length 2 or more.

WARNING:
This implementation is costly in terms of memory, since a (n x n)-Matrix is allocated to store reach data.

Precondition:

GraphChecker.isAcyclic(graph)

Complexity:

O(n^3), where n is the node count of the specified graph

Parameters:

graph -

transitiveReduction

public static void transitiveReduction(Graph graph,
                                       EdgeList transitiveEdges)

Like Transitivity.transitiveReduction(Graph) this method calculates the transitive reduction of a graph. The transitive edges will not be removed from the graph. Instead they will be returned in an EdgeList.

Precondition:

GraphChecker.isAcyclic(graph)

Complexity:

O(n^3), where n is the node count of the specified graph

Parameters:

graph - the input graph

transitiveEdges - returns the result. It will contain all transitive edges of the given graph. Removal of these edges will yield the transitive reduction of the graph.