This class is responsible for finding cycles within a graph that have certain properties.
Remarks
Note: Methods of this class work with instances of Graph. To determine cycles in an IGraph instance use one of the following classes instead:
Definitions
- An edge path with vertices
v0, v1, v2, ... , vk(with k > 0 and (vi-1,vi), 0 < i <= k is edge of the given graph) is called simple if no vertex appears more than once. - An edge path forms a cycle if
v0 = vk. - A cycle is called simple if no vertex appears more than once.
- A graph that contains no cycles is called acyclic.
Type Details
- yfiles module
- algorithms
- yfiles-umd modules
- All layout modules, view-layout-bridge
- Legacy UMD name
- yfiles.algorithms.Cycles
Static Methods
Returns an EdgeList that contains all the edges that are part of at least one directed or undirected simple cycle.
Remarks
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- directed - boolean
trueif the graph should be considered directed,falseotherwise
Returns
- ↪EdgeList
- an EdgeList that contains all the edges that are part of at least one directed or undirected simple cycle
Returns an EdgeList that contains the edges of a cycle found in the given graph.
Remarks
Note: This method works with instances of Graph. To find a cycle in an IGraph use Cycle instead.
The edges are returned in the order they appear in the detected cycle.
If the returned cycle is empty, no cycle has been found in the given graph.
Complexity
O(graph.E() + graph.N())
Parameters
A map of options to pass to the method.
- graph - Graph
- the given graph
- directed - boolean
trueif the graph should be considered directed,falseotherwise
Returns
Marks the edges of a given graph whose removal or reversal would make the graph acyclic while trying to minimize the cost associated with the marked edges.
Remarks
Note: This method works with instances of Graph. To determine feedback edges in an IGraph use FeedbackEdgeSet instead.
This minimization is performed heuristically, since it is a well known hard problem to come up with an optimal solution.
The costs are assigned using a IDataProvider that holds a non-negative double value for each edge.
Complexity
O(graph.E() + graph.N() * log(graph.E()))
Parameters
A map of options to pass to the method.
- graph - Graph
- the given graph
- cycleEdges - IEdgeMap
- the IEdgeMap that will be filled during the execution and returns whether an edge is a detected cycle edge
Domain Edge Values boolean trueif the edge is a detected cycle edge,falseotherwise - costDP - IDataProvider
- the IDataProvider that holds the non-negative number reversal cost for each edge
Domain Edge Values number a non-negative value representing the reversal cost for each edge
Marks the edges of a given graph whose removal or reversal would make the graph acyclic based on a depth first search.
Remarks
Note: This method works with instances of Graph. To determine feedback edges in an IGraph use FeedbackEdgeSet instead.
The number of marked cycle edges is expected to be slightly greater than when using findCycleEdges. The advantage of this method is that the result set is more stable when edges are added or removed over time.
Complexity
O(graph.E() + graph.N())
Parameters
A map of options to pass to the method.