| Package | com.yworks.yfiles.algo |
| Class | public class Transitivity |
| Inheritance | Transitivity  YObject Object |
| Method | Defined By | ||
|---|---|---|---|
Transitivity(init:Boolean = true) | Transitivity | ||
 | equals(o:Object):Boolean | YObject | |
getClass():Class [override] | Transitivity | ||
| hashCode():int | YObject | |
[static] | Transitivity | ||
transitiveClosure(graph:Graph):void [static]
Calculates the transitive closure for a directed acyclic graph. The reflexive, transitive closure is defined as follows: Let G = (V,E) be an directed acyclic graph. The directed acyclic graph G* = (V,E*) is the reflexive, transitive closure of G, if (v,w) in E* iff there is a path from v to w in G. REMARK: Note, that 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. | Transitivity | ||
[static]
Like transitiveClosure(), additionally this method returns the edges that have been added to the graph. | Transitivity | ||
transitiveReduction(graph:Graph):void [static]
Calculates the transitive reduction for a directed acyclic graph. | Transitivity | ||
[static]
Like transitiveReduction() this method calculates the transitive reduction of a graph. | Transitivity | ||
| Method | Defined By | ||
|---|---|---|---|
initTransitivity():void | Transitivity | ||
| Transitivity | () | Constructor |
Hide Inherited Public Methods
Show Inherited Public Methodspublic function Transitivity(init:Boolean = true)init:Boolean (default = true) |
| getClass | () | method |
override public function getClass():ClassReturnsClass |
| initTransitivity | () | method |
protected final function initTransitivity():void| newTransitivity | () | method |
| transitiveClosure | () | method |
public static function transitiveClosure(graph:Graph):void
Calculates the transitive closure for a directed acyclic graph. The reflexive, transitive closure is defined as follows: Let G = (V,E) be an directed acyclic graph. The directed acyclic graph G* = (V,E*) is the reflexive, transitive closure of G, if (v,w) in E* iff there is a path from v to w in G. REMARK: Note, that 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 GraphChecker.isAcyclic(graph)
Parameters
graph:Graph — input graph to which this method will add transitive edges if necessary.
|
| transitiveClosureGetAddedEdges | () | method |
public static function transitiveClosureGetAddedEdges(graph:Graph, addedEdges:EdgeList):voidLike transitiveClosure(), additionally this method returns the edges that have been added to the graph.
Precondition GraphChecker.isAcyclic(graph)
Parameters
graph:Graph — input graph to which this method will add transitive edges if necessary.
| |
addedEdges:EdgeList — contains edges that have been added to the graph by this method.
|
See also
| transitiveReduction | () | method |
public static function transitiveReduction(graph:Graph):void
Calculates the transitive reduction for a directed acyclic graph.
The transitive edges in the graph will be removed by this method. The transitive reduction is defined as follows: Let G = (V,E) be an directed acyclic graph. The directed acyclic graph G* = (V,E*) is the transitive reduction of G, if (v,w) in E* iff there is no path from v to w in G of length 2 or more. WARNING: This implementation is costly in terms of memory, since a (n x n)-Matrix is allocated to store reach data.
Complexity O(n^3), where n is the node count of the specified graph
Precondition GraphChecker.isAcyclic(graph)
Parameters
graph:Graph |
| transitiveReductionGetEdgesToRemove | () | method |
public static function transitiveReductionGetEdgesToRemove(graph:Graph, transitiveEdges:EdgeList):voidLike transitiveReduction() 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.
Complexity O(n^3), where n is the node count of the specified graph
Precondition GraphChecker.isAcyclic(graph)
Parameters
graph:Graph — the input graph
| |
transitiveEdges:EdgeList — 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.
|
See also