y.algo
Class Transitivity

java.lang.Object
  y.algo.Transitivity

public class Transitivity
extends java.lang.Object

This class provides algorithms to compute reachability information for directed, acyclic graphs.

Definitions

• Reflexive, transitive closure:

  Let G = (V,E) be a directed acyclic graph. The reflexive, transitive closure of G is a graph which contains edge (v,w) only if there exists a path from v to w in G.

• Transitive reduction:

  Let G = (V,E) be a directed acyclic graph. The transitive reduction of G is a graph which contains edge (v,w) only if there exists no path from v to w in G of length 2 or more.

Method Summary

static void	transitiveClosure(Graph graph) Calculates the transitive closure for a directed acyclic graph.
static void	transitiveClosure(Graph graph, EdgeList addedEdges) Like transitiveClosure(Graph), but additionally this method returns the edges that have been added to the graph.
static EdgeList	transitiveEdges(Graph graph, DataProvider visibleNode, boolean directed) Creates the transitive edges that connect the visible nodes in the specified graph.
static void	transitiveReduction(Graph graph) Calculates the transitive reduction for a directed acyclic graph.
static void	transitiveReduction(Graph graph, EdgeList transitiveEdges) Like transitiveReduction(Graph), but the transitive edges will not be removed from the graph.

Methods inherited from class java.lang.Object

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

Method Detail

transitiveClosure

public static void transitiveClosure(Graph graph)

Calculates the transitive closure for a directed acyclic graph.

Given a G = (V,E) be a directed acyclic graph. The reflexive, transitive closure of G is a graph which contains edge (v,w) only if there exists a path from v to w in G.

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:

The graph must be acyclic.

Parameters:

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

transitiveClosure

public static void transitiveClosure(Graph graph,
                                     EdgeList addedEdges)

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

Precondition:

The graph must be acyclic.

Parameters:

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

addedEdges - a list that will be filled during the execution and contains the 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.

Given G = (V,E) be a directed acyclic graph. The transitive reduction of G is a graph which contains edge (v,w) only if there exists no path from v to w in G of length 2 or more.

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

Precondition:

The graph must be acyclic.

Complexity:

O(graph.N()^3)

Parameters:

graph - the input graph

transitiveReduction

public static void transitiveReduction(Graph graph,
                                       EdgeList transitiveEdges)

Like transitiveReduction(Graph), but the transitive edges will not be removed from the graph.

Instead, they will be returned in an EdgeList.

Precondition:

The graph must be acyclic.

Complexity:

O(graph.N()^3)

Parameters:

graph - the input graph

transitiveEdges - a list that will be filled during the execution and contains all transitive edges of the given graph; removal of these edges will yield the transitive reduction of the graph

transitiveEdges

public static EdgeList transitiveEdges(Graph graph,
                                       DataProvider visibleNode,
                                       boolean directed)

Creates the transitive edges that connect the visible nodes in the specified graph.

The algorithm creates a transitive edge between two visible nodes if:

• there is a (directed/undirected) path between the nodes using only invisible nodes as intermediate nodes
• and there is not already an edge between the two nodes

Parameters:

graph - the original graph that contains both the visible and invisible nodes

visibleNode - specifies which nodes should be considered as visible

directed - whether or not the edges should be considered as directed

Returns:

the EdgeList of created transitive edges