|
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
Provides algorithms to compute reachability information for directed, acyclic graphs. The following algorithms are available:
Constructor Summary | |
---|---|
Transitivity()
|
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) , additionally this method returns the edges
that have been added to the 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) this method calculates the transitive reduction
of a graph. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public Transitivity()
Method Detail |
---|
public static void transitiveClosure(Graph graph)
G = (V,E)
be an directed acyclic graph.G* = (V,E*)
is the reflexive,
transitive closure of G
,(v,w) in E*
iff there is a path from v
to
w
in G
.
graph
- input graph to which this method will add transitive edges if necessary.GraphChecker.isAcyclic(graph)
public static void transitiveClosure(Graph graph, EdgeList addedEdges)
transitiveClosure(Graph)
, additionally this method returns the edges
that have been added to the graph.
graph
- input graph to which this method will add transitive edges if necessary.addedEdges
- contains edges that have been added to the graph by this method.GraphChecker.isAcyclic(graph)
public static void transitiveReduction(Graph graph)
G = (V,E)
be an directed acyclic graph.G* = (V,E*)
is the transitive
reduction of G
,(v,w) in E*
iff there is no path from v
to
w
in G
of length 2 or more.n
x n
)-Matrix is allocated to store reach
data.
O(n^3)
, where n
is
the node count of the specified graphGraphChecker.isAcyclic(graph)
public static void transitiveReduction(Graph graph, EdgeList transitiveEdges)
transitiveReduction(Graph)
this method calculates the transitive reduction
of a graph. The transitive edges will not be removed from the graph. Instead they will be returned
in an EdgeList.
graph
- the input graphtransitiveEdges
- returns the result. It will contain all transitive
edges of the given graph. Removal of these edges will yield the transitive
reduction of the graph.O(n^3)
, where n
is
the node count of the specified graphGraphChecker.isAcyclic(graph)
|
© Copyright 2000-2013, yWorks GmbH. All rights reserved. |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |