Package com.jgalgo.alg

Interface CyclesEnumerator

public interface CyclesEnumerator

An algorithm that enumerate all cycles in a graph.

Given a graph \(G = (V, E)\), a cycle is a path \(P = (v_1, v_2, \ldots, v_k), v_i \in V, (v_i,v_{i+1}) \in E\) such that \(v_1 = v_k\). There might be exponentially many cycles in a graph, and algorithms implementing this interface enumerate over all of them (use an Iterator avoiding storing all of them in memory).

Use newInstance() to get a default implementation of this interface. A builder obtained via newBuilder() may support different options to obtain different implementations.

Author:

Barak Ugav

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	CyclesEnumerator.Builder	A builder for CyclesEnumerator objects.

Method Summary

Modifier and Type	Method	Description
default <V,E> List<Path<V,E>>	allCycles(Graph<V,E> g)	Find all cycles in the given graph.
<V,E> Iterator<Path<V,E>>	cyclesIter(Graph<V,E> g)	Iterate over all cycles in the given graph.
static CyclesEnumerator.Builder	newBuilder()	Create a new cycles enumeration algorithm builder.
static CyclesEnumerator	newInstance()	Create a new algorithm for cycles enumerating.

Method Detail

cyclesIter

<V,E> Iterator<Path<V,E>> cyclesIter(Graph<V,E> g)

Iterate over all cycles in the given graph.

If g is IntGraph, the returned iterator will iterate over IPath objects.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

Returns:

an iterator that iteration over all cycles in the graph

allCycles

default <V,E> List<Path<V,E>> allCycles(Graph<V,E> g)

Find all cycles in the given graph.

The number of cycles may be large, and its recommend to use cyclesIter(Graph) to avoid storing all the cycles in memory at once.

If g is IntGraph, the returned list will contain IPath objects.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

Returns:

a list of all cycles in the graph

newInstance

static CyclesEnumerator newInstance()

Create a new algorithm for cycles enumerating.

This is the recommended way to instantiate a new CyclesEnumerator object. The CyclesEnumerator.Builder might support different options to obtain different implementations.

Returns:

a default implementation of CyclesEnumerator

newBuilder

static CyclesEnumerator.Builder newBuilder()

Create a new cycles enumeration algorithm builder.

Use newInstance() for a default implementation.

Returns:

a new builder that can build CyclesEnumerator objects