Search this API

y.algo
Class Cycles

java.lang.Object
  extended by y.algo.Cycles

public class Cycles
extends java.lang.Object

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

Definitions


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

findCycleEdges

public 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.

This minimization is performed 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 - the input graph
cycleEdges - the EdgeMap that will be filled during the execution and returns whether an edge is a detected cycle edge

findCycleEdges

public 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.

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 non-negative double value for each edge.

Complexity:
O(graph.E() + graph.N() * log(graph.E()))
Parameters:
graph - the given graph
cycleEdges - the EdgeMap that will be filled during the execution and returns whether an edge is a detected cycle edge
costDP - the DataProvider that holds the non-negative Double reversal cost for each edge

findCycleEdgesDFS

public 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.

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.

Complexity:
O(graph.E() + graph.N())
Parameters:
graph - the given graph
cycleEdges - the EdgeMap that will be filled during the execution and returns a boolean value indicating whether or not an edge is a detected cycle edge

findCycle

public static 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

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

© Copyright 2000-2022,
yWorks GmbH.
All rights reserved.