Package com.jgalgo.alg

Interface ClosuresEnumerator

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 no edges leave \(C\) to \(V \setminus C\). There might be exponentially many closures in a graph, and algorithms implementing this interface enumerate over all of them (use an Iterator avoiding storing all of them in memory).

For undirected graphs, the closure subsets are simply the weakly connected components.

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

Author:

Barak Ugav

See Also:

Wikipedia

Method Summary

Modifier and Type	Method	Description
default <V,E> List<Set<V>>	allClosures(Graph<V,E> g)	Find all closures in the given graph.
<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, Set<V> c)	Check whether the given set 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 no edges leave \(C\) to \(V \setminus C\). Although the empty set of vertices is consider 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

allClosures

default <V,E> List<Set<V>> allClosures(Graph<V,E> g)

Find 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 no edges leave \(C\) to \(V \setminus C\). Although the empty set of vertices is consider a colure, it is not returned by this method.

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

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a directed graph

Returns:

a list of 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,
                                     Set<V> c)

Check whether the given set 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 no edges leave \(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

Returns:

true if the set is a closure, false otherwise