Package | com.yworks.yfiles.algo |
Class | public class Cycles |
Inheritance | Cycles YObject Object |
Method | Defined By | ||
---|---|---|---|
Cycles(init:Boolean = true) | Cycles | ||
equals(o:Object):Boolean | YObject | ||
[static]
Returns all edges that are part of at least one directed or undirected simple cycle. | Cycles | ||
[static]
Returns an edge list that contains the edges of a cycle found in the given graph. | Cycles | ||
[static]
This method marks edges of a given graph whose removal or reversal would make that graph acyclic. | Cycles | ||
[static]
Like findCycleEdges() this method marks edges of a given graph whose removal or reversal would make that graph acyclic. | Cycles | ||
[static]
This method is similar to findCycleEdges(), but instead of minimizing the number of marked edges it tries to find a set of marked edges, for which the associated cost is minimal. | Cycles | ||
getClass():Class [override] | Cycles | ||
hashCode():int | YObject | ||
[static] | Cycles |
Method | Defined By | ||
---|---|---|---|
initCycles():void | Cycles |
Cycles | () | Constructor |
public function Cycles(init:Boolean = true)
init:Boolean (default = true )
|
findAllCycleEdges | () | method |
public static function findAllCycleEdges(graph:Graph, directed:Boolean):EdgeList
Returns all edges that are part of at least one directed or undirected simple cycle. A simple cycle is a closed edge path without repeating edges. Moreover, selfloops are always considered to be cycle edges.
Parameters
graph:Graph — the input graph
| |
directed:Boolean — whether or not to look for edges on directed cycles
|
EdgeList — all edges that belong to a cycle
|
findCycle | () | method |
public static function findCycle(graph:Graph, directed:Boolean):EdgeList
Returns an edge list that contains the edges of a cycle found in the given graph. The edges are returned in the order they appear in the found cycle.
If the returned cycle is empty then no cycle has been found in the given graph.Complexity O(graph.N()+graph.E())
Parameters
graph:Graph | |
directed:Boolean |
EdgeList |
findCycleEdges | () | method |
public static function findCycleEdges(graph:Graph, cycleEdges:EdgeMap):void
This method marks edges of a given graph whose removal or reversal would make that graph acyclic. This method tries to minimize the number of marked edges for that task heuristically, since it is a well known hard problem to come up with an optimal solution.
Complexity O(graph.E()+graph.N()*log(graph.E()))
Parameters
graph:Graph — the input graph
| |
cycleEdges:EdgeMap — return value. cycleEdge.getBool(e) == true iff e is a detected cycle edge.
|
findCycleEdgesDFS | () | method |
public static function findCycleEdgesDFS(graph:Graph, cycleEdges:EdgeMap):void
Like findCycleEdges() this method marks edges of a given graph whose removal or reversal would make that graph acyclic. The implementation of this method is based on a Depth First Search. The number of marked cycle edges is expected to be slightly larger than when using findCycleEdges() . The advantage of this method is that the result set is more stable when edges get added or removed over the time.
Complexity O(graph.E()+graph.N())
Parameters
graph:Graph — the input graph
| |
cycleEdges:EdgeMap — return value. cycleEdge.getBool(e) == true iff e is a detected cycle edge.
|
See also
findCycleEdgesWithMinimalCost | () | method |
public static function findCycleEdgesWithMinimalCost(graph:Graph, cycleEdges:EdgeMap, costDP:DataProvider):void
This method is similar to findCycleEdges(), but instead of minimizing the number of marked edges it tries to find a set of marked edges, for which the associated cost is minimal.
In case each edge has cost 1.0
the result will be the same as the one returned by findCycleEdges().
Complexity O(graph.E()+graph.N()*log(graph.E()))
Parameters
graph:Graph | |
cycleEdges:EdgeMap | |
costDP:DataProvider — data provider that yields the reversal cost for each edge. The reversal cost for each edge must be a non-negative value of type double .
|
See also
getClass | () | method |
override public function getClass():Class
ReturnsClass |
initCycles | () | method |
protected final function initCycles():void
newCycles | () | method |