com.yworks.yfiles.algorithms

Class Transitivity

java.lang.Object

com.yworks.yfiles.algorithms.Transitivity

public final class Transitivity
extends 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

Modifier and Type	Method and Description
static void	transitiveClosure(Graph graph) Calculates the transitive closure for a directed acyclic graph.
static void	transitiveClosure(Graph graph, EdgeList addedEdges) Calculates the transitive closure for a directed acyclic graph.
static void	transitiveReduction(Graph graph) Calculates the transitive reduction for a directed acyclic graph.
static void	transitiveReduction(Graph graph, EdgeList transitiveEdges) Calculates the transitive reduction for a directed acyclic graph.

Methods inherited from class java.lang.Object

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

Method Detail

transitiveClosure

public static final 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 final void transitiveClosure(Graph graph,
                                           EdgeList addedEdges)

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

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 final 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 final void transitiveReduction(Graph graph,
                                             EdgeList transitiveEdges)

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

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