com.yworks.yfiles.algorithms

Class Cycles

java.lang.Object

com.yworks.yfiles.algorithms.Cycles

public final class Cycles
extends Object

This class is responsible for finding cycles within a graph that have certain properties.

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.

Example of an acyclic directed graph (edge directions are considered) Example of a graph containing a cycle. Marked edges form a directed cycle.

Method Summary

Modifier and Type	Method and Description
static EdgeList	findAllCycleEdges(Graph graph, boolean directed) Returns an EdgeList that contains all the edges that are part of at least one directed or undirected simple cycle.
static EdgeList	findCycle(Graph graph, boolean directed) Returns an EdgeList that contains the edges of a cycle found in the given graph.
static void	findCycleEdges(Graph graph, IEdgeMap cycleEdges) 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.
static void	findCycleEdges(Graph graph, IEdgeMap cycleEdges, IDataProvider costDP) 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.
static void	findCycleEdgesDFS(Graph graph, IEdgeMap cycleEdges) Marks the edges of a given graph whose removal or reversal would make the graph acyclic based on a depth first search.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

findAllCycleEdges

public static final EdgeList findAllCycleEdges(Graph graph,
                                               boolean directed)

Returns an EdgeList that contains all the edges that are part of at least one directed or undirected simple cycle.

Self-loops are always considered to be cycle edges.

Parameters:

graph - the input graph

directed - true if the graph should be considered directed, false otherwise

Returns:

an EdgeList that contains all the edges that are part of at least one directed or undirected simple cycle

findCycle

public static final EdgeList findCycle(Graph graph,
                                       boolean directed)

Returns an EdgeList that contains the edges of a cycle found in the given graph.

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:

graph - the given graph

directed - true if the graph should be considered directed, false otherwise

Returns:

an EdgeList containing the edges of a cycle or an empty EdgeList if the graph is acyclic

findCycleEdges

public static final void findCycleEdges(Graph graph,
                                        IEdgeMap cycleEdges)

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.

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:

graph - the given graph

cycleEdges - the IEdgeMap that will be filled during the execution and returns whether an edge is a detected cycle edge

findCycleEdges

public static final void findCycleEdges(Graph graph,
                                        IEdgeMap cycleEdges,
                                        IDataProvider costDP)

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.

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:

graph - the given graph

cycleEdges - the IEdgeMap that will be filled during the execution and returns whether an edge is a detected cycle edge

costDP - the IDataProvider that holds the non-negative Double reversal cost for each edge

findCycleEdgesDFS

public static final void findCycleEdgesDFS(Graph graph,
                                           IEdgeMap cycleEdges)

Marks the edges of a given graph whose removal or reversal would make the graph acyclic based on a depth first search.

The number of marked cycle edges is expected to be slightly greater than when using findCycleEdges(Graph, IEdgeMap, IDataProvider). 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:

graph - the given graph

cycleEdges - the IEdgeMap that will be filled during the execution and returns a boolean value indicating whether or not an edge is a detected cycle edge