com.yworks.yfiles.algorithms

Class IndependentSets

java.lang.Object

com.yworks.yfiles.algorithms.IndependentSets

public final class IndependentSets
extends 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

Modifier and Type	Method and Description
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

getIndependentSet

public static final 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(Graph)

getIndependentSets

public static final NodeList[] getIndependentSets(Graph conflictGraph)

Partitions the set of nodes of the given graph into independent sets.

The method iteratively calls method getIndependentSet(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(Graph)