TransitivityAlgorithm

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

Inheritance Hierarchy

TransitivityAlgorithm

Remarks

Note: Methods of this class work with instances of Graph. To calculate the transitive closure or reduction of an IGraph use TransitiveClosure or TransitiveReduction instead.

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.

Type Details

yfiles module: algorithms
yfiles-umd modules: All layout modules, view-layout-bridge
Legacy UMD name: yfiles.algorithms.Transitivity

Static Methods

transitiveClosure

(graph: Graph, addedEdges?: EdgeList)

Calculates the transitive closure for a directed acyclic graph.

Remarks

Note: This method works with instances of Graph. To calculate the transitive closure for an IGraph use TransitiveClosure instead.

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.

Preconditions

The graph must be .

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the input graph to which this method will add transitive edges, if necessary
addedEdges - EdgeList: a list that will be filled during the execution and contains the edges that have been added to the graph by this method

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.

transitiveEdges

(graph: Graph, visibleNode: IDataProvider, directed: boolean) : EdgeList

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

Remarks

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

options - Object
A map of options to pass to the method.

graph - Graph

the original graph that contains both the visible and invisible nodes

visibleNode - IDataProvider

specifies which nodes should be considered as visible

Domain	YNode
Values	boolean	`true` it the node is visible, `false` otherwise

directed - boolean

whether or not the edges should be considered as directed

Returns

↪EdgeList: the EdgeList of created transitive edges

transitiveReduction

(graph: Graph, transitiveEdges?: EdgeList)

Calculates the transitive reduction for a directed acyclic graph.

Remarks

Note: This method works with instances of Graph. To calculate the transitive reduction for an IGraph use TransitiveReduction instead.

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.

Complexity

O(graph.N()^3)

Preconditions

The graph must be .

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the input graph
transitiveEdges - EdgeList: 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

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