Package com.jgalgo.alg.shortestpath

Interface SimplePathsEnumerator

All Known Implementing Classes:
SimplePathsEnumeratorAbstract, SimplePathsEnumeratorSedgewick
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.

Use newInstance() to get a default implementation of this interface.

Author:
Barak Ugav

  • 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
    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 Details

    • 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.

      Returns:
      a default implementation of SimplePathsEnumerator