
Search this API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object y.algo.Transitivity
public class Transitivity
This class provides algorithms to compute reachability information for directed, acyclic graphs.
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
.
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 

public static void transitiveClosure(Graph 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
.
acyclic
.graph
 the input graph to which this method will add transitive edges, if necessarypublic static void transitiveClosure(Graph graph, EdgeList addedEdges)
transitiveClosure(Graph)
, but additionally this method returns the edges
that have been added to the graph.
acyclic
.graph
 the input graph to which this method will add transitive edges, if necessaryaddedEdges
 a list
that will be filled during the execution and contains the edges that have
been added to the graph by this methodpublic static void transitiveReduction(Graph 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.
n
x n
)matrix is
allocated to store reach data.acyclic
.O(graph.N()^3)
graph
 the input graphpublic static void transitiveReduction(Graph graph, EdgeList transitiveEdges)
transitiveReduction(Graph)
, but the transitive edges will not be removed from the graph.
Instead, they will be returned in an EdgeList
.
acyclic
.O(graph.N()^3)
graph
 the input graphtransitiveEdges
 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 graphpublic static EdgeList transitiveEdges(Graph graph, DataProvider visibleNode, boolean directed)
visible
nodes in the specified graph.
The algorithm creates a transitive edge
between two visible nodes if:
graph
 the original graph that contains both the visible and invisible nodesvisibleNode
 specifies which nodes should be considered as visible
directed
 whether or not the edges should be considered as directed
EdgeList
of created transitive edges

© Copyright 20002022, yWorks GmbH. All rights reserved. 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 