y.algo
Class Cycles

java.lang.Object
  y.algo.Cycles

public class Cycles
extends Object

Responsible for finding cycles within a graph that have certain properties.

Constructor Summary

Cycles()

Method Summary

static EdgeList	findAllCycleEdges(Graph graph, boolean directed) Returns all edges that are part of at least one directed or undirected simple cycle.
static EdgeList	findCycle(Graph graph, boolean directed) Returns an edge list that contains the edges of a cycle found in the given graph.
static void	findCycleEdges(Graph graph, EdgeMap cycleEdges) This method marks edges of a given graph whose removal or reversal would make that graph acyclic.
static void	findCycleEdges(Graph graph, EdgeMap cycleEdges, DataProvider costDP) This method is similar to findCycleEdges(Graph, EdgeMap), but instead of minimizing the number of marked edges it tries to find a set of marked edges, for which the associated cost is minimal.
static void	findCycleEdgesDFS(Graph graph, EdgeMap cycleEdges) Like findCycleEdges(Graph, EdgeMap) this method marks edges of a given graph whose removal or reversal would make that graph acyclic.

Methods inherited from class java.lang.Object

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

Constructor Detail

Cycles

public Cycles()

Method Detail

findCycleEdges

public static void findCycleEdges(Graph graph,
                                  EdgeMap cycleEdges)

This method marks edges of a given graph whose removal or reversal would make that graph acyclic. This method tries to minimize the number of marked edges for that task heuristically, since it is a well known hard problem to come up with an optimal solution.

Parameters:

graph - the input graph

cycleEdges - return value. cycleEdge.getBool(e) == true iff e is a detected cycle edge.

Complexity:

O(graph.E()+graph.N()*log(graph.E()))

findCycleEdges

public static void findCycleEdges(Graph graph,
                                  EdgeMap cycleEdges,
                                  DataProvider costDP)

This method is similar to findCycleEdges(Graph, EdgeMap), but instead of minimizing the number of marked edges it tries to find a set of marked edges, for which the associated cost is minimal. In case each edge has cost 1.0 the result will be the same as the one returned by findCycleEdges(Graph, EdgeMap).

Parameters:

costDP - data provider that yields the reversal cost for each edge. The reversal cost for each edge must be a non-negative value of type double.

Complexity:

O(graph.E()+graph.N()*log(graph.E()))

findCycleEdgesDFS

public static void findCycleEdgesDFS(Graph graph,
                                     EdgeMap cycleEdges)

Like findCycleEdges(Graph, EdgeMap) this method marks edges of a given graph whose removal or reversal would make that graph acyclic. The implementation of this method is based on a Depth First Search. The number of marked cycle edges is expected to be slightly larger than when using findCycleEdges(Graph, EdgeMap). The advantage of this method is that the result set is more stable when edges get added or removed over the time.

Parameters:

graph - the input graph

cycleEdges - return value. cycleEdge.getBool(e) == true iff e is a detected cycle edge.

Complexity:

O(graph.E()+graph.N())

findCycle

public static EdgeList findCycle(Graph graph,
                                 boolean directed)

Returns an edge list that contains the edges of a cycle found in the given graph. The edges are returned in the order they appear in the found cycle.

If the returned cycle is empty then no cycle has been found in the given graph.

Complexity:

O(graph.N()+graph.E())

findAllCycleEdges

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

Returns all edges that are part of at least one directed or undirected simple cycle. A simple cycle is a closed edge path without repeating edges. Moreover, selfloops are always considered to be cycle edges.

Parameters:

graph - the input graph

directed - whether or not to look for edges on directed cycles

Returns:

all edges that belong to a cycle