C

Cycle

Show Usages
Finds a directed or undirected cycle of edges in a graph.
Inheritance Hierarchy

Remarks

The graph can be directed or undirected.

Other Path-Related Algorithms

yFiles for HTML supports a number of other algorithms related to paths in a graph:

  • Paths – finds all paths between a set of source and a set of target nodes
  • Chains – finds all chains, that is, sequences of nodes that are each connected with just an edge without branches
  • LongestPath – finds the longest path in the graph

Complexity

O(|V| + |E|)

Examples

Highlighting the edge of a cycle in a graph
// prepare the cycle detection algorithm
const algorithm = new Cycle({
  // We are only interested in finding directed cycles
  directed: true,
})
// run the algorithm
const result = algorithm.run(graph)

// highlight the cycle
for (const edge of result.edges) {
  graph.setStyle(edge, highlightCycleStyle)
}

See Also

Developer's Guide

API

findCycle

Members

No filters for this type

Constructors

Cycle

()

Parameters

Properties

directed

: boolean
Gets or sets a value indicating whether edge direction should be considered.
Default is true.
final

Property Value

true if the graph should be considered as directed, false otherwise.

subgraphEdges

: ItemCollection<IEdge>
Gets or sets the collection of edges which define a subset of the graph for the algorithms to work on.

If nothing is set, all edges of the graph will be processed.

If only the ItemCollection<TItem>.excludes are set, all edges in the graph except those provided in the ItemCollection<TItem>.excludes are processed.

Note that edges which start or end at nodes which are not in the subgraphNodes are automatically not considered by the algorithm.

ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithm.

The edges provided here must be part of the graph which is passed to the run method.
conversionfinal

Examples

Finding a cycle on a subset of the graph
// prepare the cycle detection algorithm
const algorithm = new Cycle({
  // We are only interested in finding directed cycles
  directed: true,
  // Ignore edges without target arrow heads
  subgraphEdges: {
    excludes: (edge: IEdge): boolean =>
      edge.style instanceof PolylineEdgeStyle &&
      edge.style.targetArrow instanceof Arrow &&
      edge.style.targetArrow.type === ArrowType.NONE,
  },
})
// run the algorithm
const result = algorithm.run(graph)

// highlight the cycle
for (const edge of result.edges) {
  graph.setStyle(edge, highlightCycleStyle)
}

subgraphNodes

: ItemCollection<INode>
Gets or sets the collection of nodes which define a subset of the graph for the algorithms to work on.

If nothing is set, all nodes of the graph will be processed.

If only the ItemCollection<TItem>.excludes are set, all nodes in the graph except those provided in the ItemCollection<TItem>.excludes are processed.

ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithm.

The nodes provided here must be part of the graph which is passed to the run method.
conversionfinal

Examples

Finding a cycle on a subset of the graph
// prepare the cycle detection algorithm
const algorithm = new Cycle({
  // We are only interested in finding directed cycles
  directed: true,
  subgraphNodes: {
    // only consider elliptical nodes in the graph
    includes: (node: INode): boolean =>
      node.style instanceof ShapeNodeStyle &&
      node.style.shape === ShapeNodeShape.ELLIPSE,
    // but ignore the first node, regardless of its shape
    excludes: graph.nodes.first()!,
  },
})
// run the algorithm
const result = algorithm.run(graph)

// highlight the cycle
for (const edge of result.edges) {
  graph.setStyle(edge, highlightCycleStyle)
}

Methods

run

(graph: IGraph): CycleResult
Finds a cycle in the given graph.
The result obtained from this algorithm is a snapshot which is no longer valid once the graph has changed, e.g. by adding or removing nodes or edges.
final

Parameters

graph: IGraph
The input graph to run the algorithm on.

Return Value

CycleResult
A CycleResult with a cycle (if one exists in the graph).

Throws

Exception ({ name: 'InvalidOperationError' })
If the algorithm can't create a valid result due to an invalid graph structure or wrongly configured properties.

Complexity

O(|V| + |E|)