Package com.jgalgo.alg

Interface SimplePathsEnumerator

public interface SimplePathsEnumerator

An algorithm that enumerate over simple paths between a source and a target.

Given a graph \(G=(V,E)\), a path is a sequence of edges \(e_1,e_2,\ldots,e_k\) such that \(e_i=(v_{i-1},v_i)\) and \(v_i\neq v_j\) for \(i\neq j\). A simple path is a path that does not contain a cycle, namely the vertices visited by the path are distinct. Algorithms implementing this interface find all simple paths between a source and a target vertices in a given graph. Note that there may be exponentially many simple paths between two vertices in a graph.

Author:

Barak Ugav

Nested Class Summary

Nested Classes

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

Method Summary

Modifier and Type	Method	Description
default <V,E> List<Path<V,E>>	allSimplePaths(Graph<V,E> g, V source, V target)	Find all the simple paths between a source and a target vertices in the given graph.
static SimplePathsEnumerator.Builder	newBuilder()	Create a new simple paths enumerator algorithm builder.
static SimplePathsEnumerator	newInstance()	Create a new algorithm for simple paths enumeration.
<V,E> Iterator<Path<V,E>>	simplePathsIter(Graph<V,E> g, V source, V target)	Iterate over all the simple paths between a source and a target vertices in the given graph.

Method Detail

simplePathsIter

<V,E> Iterator<Path<V,E>> simplePathsIter(Graph<V,E> g,
                                                      V source,
                                                      V target)

Iterate over all the simple paths between a source and a target vertices in the given graph.

If g is an IntGraph, an iterator of IPath objects will be returned.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

source - the source vertex

target - the target vertex

Returns:

an iterator that iteration over all simple paths between the two vertices in the graph

allSimplePaths

default <V,E> List<Path<V,E>> allSimplePaths(Graph<V,E> g,
                                                         V source,
                                                         V target)

Find all the simple paths between a source and a target vertices in the given graph.

If g is an IntGraph, a list of IPath objects will be returned.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

source - the source vertex

target - the target vertex

Returns:

a list of all simple paths between the two vertices in the graph

newInstance

static SimplePathsEnumerator newInstance()

Create a new algorithm for simple paths enumeration.

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

Returns:

a default implementation of SimplePathsEnumerator

newBuilder

static SimplePathsEnumerator.Builder newBuilder()

Create a new simple paths enumerator algorithm builder.

Use newInstance() for a default implementation.

Returns:

a new builder that can build SimplePathsEnumerator objects