y.algo
Class Cycles

java.lang.Object
  |
  +--y.algo.Cycles

public class Cycles

extends Object

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

Constructor Summary

Cycles()

Method Summary

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	findCycleEdgesDFS(Graph graph, EdgeMap cycleEdges) Like Cycles.findCycleEdges(Graph, EdgeMap) this method 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 know hard problem to come up with an optimal solution.

Complexity:

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

Parameters:

graph - the input graph

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

findCycleEdgesDFS

public static void findCycleEdgesDFS(Graph graph,
                                     EdgeMap cycleEdges)

Like Cycles.findCycleEdges(Graph, EdgeMap) this method 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 Cycles.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.

Complexity:

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

Parameters:

graph - the input graph

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

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())