Search this API

y.algo
Class Transitivity

java.lang.Object
  extended by y.algo.Transitivity

public class Transitivity
extends java.lang.Object

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

Definitions

 

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:

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

© Copyright 2000-2022,
yWorks GmbH.
All rights reserved.