y.algo
Class IndependentSets

java.lang.Object
  y.algo.IndependentSets

public class IndependentSets
extends java.lang.Object

This class provides methods for calculating independent sets.

An independent set is a set of nodes in a graph, in which no two nodes are adjacent.

Circular nodes represent one of the independent sets of the given graph

Method Summary

static NodeList	getIndependentSet(Graph conflictGraph) Calculates an independent set for a given graph.
static NodeList[]	getIndependentSets(Graph conflictGraph) Partitions the set of nodes of the given graph into independent sets.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

getIndependentSets

public static NodeList[] getIndependentSets(Graph conflictGraph)

Partitions the set of nodes of the given graph into independent sets. The method iteratively calls method getIndependentSet(y.base.Graph).

Precondition:

The input graph is simple i.e., it contains neither parallel edges nor self-loops.

Parameters:

conflictGraph - the input graph

Returns:

an array of NodeLists each of which contains an independent set of nodes

See Also:

getIndependentSet(y.base.Graph)

getIndependentSet

public static NodeList getIndependentSet(Graph conflictGraph)

Calculates an independent set for a given graph.

A greedy heuristic is applied which tries to find a large independent set.

Precondition:

The input graph is simple i.e., it contains neither parallel edges nor self-loops.

Parameters:

conflictGraph - the input graph

Returns:

a NodeList containing an independent set of nodes

See Also:

getIndependentSet(y.base.Graph)