Search this API

## y.algo Class Transitivity

```java.lang.Object
y.algo.Transitivity
```

`public class Transitivityextends 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,
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