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:

Wikipedia

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 Detail

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