Package com.jgalgo.alg.clique

Interface MaximalIndependentSetsEnumerator

All Known Implementing Classes:

MaximalIndependentSetsEnumeratorAbstract, MaximalIndependentSetsEnumeratorComplementCliques

public interface MaximalIndependentSetsEnumerator

Algorithm for enumerating over all maximal independent sets in a graph.

An independent set is a subset of vertices of a graph such that there are no edges between any pair of vertices in the set. Self edges are allowed within an independent set, namely they are ignored. A maximal independent set is an independent set that cannot be extended by including one more vertex.

There may be exponentially many maximal independent sets 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 independent sets, so that the caller can iterate over them without storing them all in memory. Avoid using this algorithm on very large graphs.

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

 
 Graph<String, Integer> g = ...;
 MaximalIndependentSetsEnumerator independentSetsAlgo = MaximalIndependentSetsEnumerator.newInstance();

 for (Iterator<Set<String>> it = independentSetsAlgo.maximalIndependentSetsIter(g); it.hasNext();) {
	Set<String> independentSet = it.next();
	System.out.println("Maximal independent set in the graph:");
	for (String v : independentSet)
		System.out.println("\t" + v);
 }
 

Author:

Barak Ugav

Method Summary

Modifier and Type	Method	Description
<V, E> Iterator<Set<V>>	maximalIndependentSetsIter(Graph<V,E> g)	Iterate over all maximal independent sets in a graph.
static MaximalIndependentSetsEnumerator	newInstance()	Create a new maximal independent sets algorithm object.

Method Details

maximalIndependentSetsIter

<V,
E> Iterator<Set<V>> maximalIndependentSetsIter(Graph<V,E> g)

Iterate over all maximal independent sets in a graph.

The input graph should not be changed during the iteration.

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

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

Returns:

an iterator that iterates over all maximal independent sets in the graph

newInstance

static MaximalIndependentSetsEnumerator newInstance()

Create a new maximal independent sets algorithm object.

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

Returns:

a default implementation of MaximalIndependentSetsEnumerator