y.algo
Class Cycles

java.lang.Object
  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

• 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

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