Search this API

## y.algo Class IndependentSets

```java.lang.Object
y.algo.IndependentSets
```

`public class IndependentSetsextends 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 `NodeList`s 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)`

© Copyright 2000-2022,
yWorks GmbH.
All rights reserved.