
Search this API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object y.algo.Cycles
public class Cycles
This class is responsible for finding cycles within a graph that have certain properties.
v0, v1, v2, ... , vk
(with k > 0 and
(vi1,vi), 0 < i <= k is edge of the given graph) is called simple if no vertex appears
more than once.v0 = vk
.
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  

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,
EdgeMap cycleEdges)
Marks the edges of a given graph whose removal or reversal would make the graph acyclic while heuristically minimizing the number of marked edges. 
static void 
findCycleEdges(Graph graph,
EdgeMap cycleEdges,
DataProvider 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,
EdgeMap 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 

public static void findCycleEdges(Graph graph, EdgeMap cycleEdges)
This minimization is performed heuristically, since it is a well known hard problem to come up with an optimal solution.
O(graph.E() + graph.N() * log(graph.E()))
graph
 the input graphcycleEdges
 the EdgeMap
that will be filled during the execution and returns whether an edge is a
detected cycle edgepublic static void findCycleEdges(Graph graph, EdgeMap cycleEdges, DataProvider costDP)
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 DataProvider
that holds a nonnegative double value for each edge.
O(graph.E() + graph.N() * log(graph.E()))
graph
 the given graphcycleEdges
 the EdgeMap
that will be filled during the execution and returns whether an edge is a
detected cycle edgecostDP
 the DataProvider
that holds the nonnegative Double
reversal cost for each edgepublic static void findCycleEdgesDFS(Graph graph, EdgeMap cycleEdges)
The number of marked cycle edges is expected to be slightly greater than when using
findCycleEdges(Graph, EdgeMap)
. The advantage of this method is that the result set is more stable
when edges are added or removed over time.
O(graph.E() + graph.N())
graph
 the given graphcycleEdges
 the EdgeMap
that will be filled during the execution and returns a boolean value
indicating whether or not an edge is a detected cycle edgepublic static EdgeList findCycle(Graph graph, boolean directed)
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.
O(graph.E() + graph.N())
graph
 the given graphdirected
 true
if the graph should be considered directed, false
otherwise
EdgeList
containing the edges of a cycle or an empty EdgeList
if the graph is acyclicpublic static final EdgeList findAllCycleEdges(Graph graph, boolean directed)
EdgeList
that contains all the edges that are part of at least one directed or undirected
simple cycle.
graph
 the input graphdirected
 true
if the graph should be considered directed, false
otherwise
EdgeList
that contains all the edges that are part of at least one directed or undirected
simple cycle

© Copyright 20002022, yWorks GmbH. All rights reserved. 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 