org.processmining.humbertogarciacaballero.models.util.circuits

Class ElementaryCyclesSearch

java.lang.Object

org.processmining.humbertogarciacaballero.models.util.circuits.ElementaryCyclesSearch

public class ElementaryCyclesSearch
extends java.lang.Object

Searchs all elementary cycles in a given directed graph. The implementation is independent from the concrete objects that represent the graphnodes, it just needs an array of the objects representing the nodes the graph and an adjacency-matrix of type boolean, representing the edges of the graph. It then calculates based on the adjacency-matrix the elementary cycles and returns a list, which contains lists itself with the objects of the concrete graphnodes-implementation. Each of these lists represents an elementary cycle.

The implementation uses the algorithm of Donald B. Johnson for the search of the elementary cycles. For a description of the algorithm see:
Donald B. Johnson: Finding All the Elementary Circuits of a Directed Graph. SIAM Journal on Computing. Volumne 4, Nr. 1 (1975), pp. 77-84.

The algorithm of Johnson is based on the search for strong connected components in a graph. For a description of this part see:
Robert Tarjan: Depth-first search and linear graph algorithms. In: SIAM Journal on Computing. Volume 1, Nr. 2 (1972), pp. 146-160.

Version:

1.2, 22.03.2009

Author:

Frank Meyer, web_at_normalisiert_dot_de

Constructor Summary

Constructors

Constructor and Description
ElementaryCyclesSearch(boolean[][] matrix, java.lang.Object[] graphNodes) Constructor.

Method Summary

Modifier and Type	Method and Description
java.util.List	getElementaryCycles() Returns List::List::Object with the Lists of nodes of all elementary cycles in the graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

ElementaryCyclesSearch

public ElementaryCyclesSearch(boolean[][] matrix,
                              java.lang.Object[] graphNodes)

Constructor.

Parameters:

matrix - adjacency-matrix of the graph

graphNodes - array of the graphnodes of the graph; this is used to build sets of the elementary cycles containing the objects of the original graph-representation

Method Detail

getElementaryCycles

public java.util.List getElementaryCycles()

Returns List::List::Object with the Lists of nodes of all elementary cycles in the graph.

Returns:

List::List::Object with the Lists of the elementary cycles.