Package com.jgalgo.alg.closure

Interface ClosuresEnumerator

All Known Implementing Classes:
ClosuresEnumeratorAbstract, ClosuresEnumeratorSchrageBaker
public interface ClosuresEnumerator
An algorithm that enumerate all the closure subsets in a directed graph.

Given a directed graph \(G = (V, E)\), a closure is a subset of vertices \(C \subseteq V\) such that there are no edges from \(C\) to \(V \setminus C\).

There may be exponentially many closures in a graph, therefore all implementations of this interface use some heuristic to speed up the process but run in exponential time in the worst case. The algorithm returns an iterator over the closures, so that the caller can iterate over them without storing them all in memory. Avoid using this algorithm on very large graphs.

For undirected graphs, the closure subsets are simply the weakly connected components, and algorithms implementing this interface will throw an exception if the graph is not directed.

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

Author:
Barak Ugav
See Also:

  • Method Summary

    Modifier and Type
    Method
    Description
    <V, E> Iterator<Set<V>>
    closuresIter(Graph<V,E> g)
    Iterate over all closures in the given graph.
    static <V, E> boolean
    isClosure(Graph<V,E> g, Collection<V> c)
    Check whether the given set of vertices is a closure in the given graph.
    static ClosuresEnumerator
    newInstance()
    Create a new closure enumeration algorithm.

  • Method Details

    • closuresIter

      <V, E> Iterator<Set<V>> closuresIter(Graph<V,E> g)
      Iterate over all closures in the given graph.

      Given a directed graph \(G = (V, E)\), a closure is a subset of vertices \(C \subseteq V\) such that there are no edges from \(C\) to \(V \setminus C\). Although the empty set of vertices is considered a colure, it is not returned by this method.

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

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a directed graph
      Returns:
      an iterator that iteration over all closures in the graph
      Throws:
      IllegalArgumentException - if the graph is not directed

    • newInstance

      static ClosuresEnumerator newInstance()
      Create a new closure enumeration algorithm.

      This is the recommended way to instantiate a new ClosuresEnumerator object.

      Returns:
      a default implementation of ClosuresEnumerator

    • isClosure

      static <V, E> boolean isClosure(Graph<V,E> g, Collection<V> c)
      Check whether the given set of vertices is a closure in the given graph.

      Given a directed graph \(G = (V, E)\), a closure is a subset of vertices \(C \subseteq V\) such that there are no edges from \(C\) to \(V \setminus C\). The empty set of vertices is considered a closure.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      c - a set of vertices. There should not be any duplicate vertices, otherwise the behavior is undefined
      Returns:
      true if the set is a closure, false otherwise