agape.algos

Class MIS<V,E>

java.lang.Object

agape.algos.Algorithms<V,E>

agape.algos.MIS<V,E>

Type Parameters:

V - Vertices type

E - Edges type

public class MIS<V,E>
extends Algorithms<V,E>

This class computes the maximum independ set of a graph (directed or undirected). This problem consists in finding the maximum set of vertices such that two vertices of the computed set are not neighbors in the original graph. Several algorithms have been implemented.

Author:

V. Levorato, J.-F. Lalande, P. Berthome

Constructor Summary

Constructors

Constructor and Description
MIS(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> graphFactory, org.apache.commons.collections15.Factory<V> vertexFactory, org.apache.commons.collections15.Factory<E> edgeFactory)

Method Summary

Methods

Modifier and Type	Method and Description
static <V,E> boolean	isIndependentSet(edu.uci.ics.jung.graph.Graph<V,E> g, java.util.Set<V> S) This method tests if a set S of a Graph G is an independent set.
static <V,E> boolean	isMaximalIndependentSet(edu.uci.ics.jung.graph.Graph<V,E> g, java.util.Set<V> S) This method tests if a set S of a Graph G is a maximal independent set.
java.util.Set<V>	maximalIndependentSetGreedy(edu.uci.ics.jung.graph.Graph<V,E> g) This method finds a maximal independent set in a graph using a trivial greedy algorithm.
java.util.Set<V>	maximumIndependentSetBruteForce(edu.uci.ics.jung.graph.Graph<V,E> g) This method returns a maximum independent set of G using the naive brute force algorithm that examines every vertex subset and checks whether it is an independent set, which time complexity is O(n^2.2^n).
java.util.Set<V>	maximumIndependentSetMaximumDegree(edu.uci.ics.jung.graph.Graph<V,E> g) This method returns a maximum independent set of G by finding vertices with max degrees.
java.util.Set<V>	maximumIndependentSetMoonMoser(edu.uci.ics.jung.graph.Graph<V,E> g) This method returns a maximum independent set of G based on the Moon and Moser work ("On cliques in graphs" 1965).
java.util.Set<V>	maximumIndependentSetMoonMoserNonRecursive(edu.uci.ics.jung.graph.Graph<V,E> g) This method is the same as MaximumIndependentSetMM but in a non-recursive version (slower).
java.util.Set<V>	maximuRmIndependentSetFominGrandoniKratsch(edu.uci.ics.jung.graph.Graph<V,E> g) This method returns a maximum independent set of G based on the Fomin and al.

Methods inherited from class agape.algos.Algorithms

getEdgeFactory, getGraphFactory, getVertexFactory, setEdgeFactoy, setGraphFactoy, setVertexFactoy

Methods inherited from class java.lang.Object

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

Constructor Detail

MIS

public MIS(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> graphFactory,
   org.apache.commons.collections15.Factory<V> vertexFactory,
   org.apache.commons.collections15.Factory<E> edgeFactory)

Method Detail

maximalIndependentSetGreedy

public java.util.Set<V> maximalIndependentSetGreedy(edu.uci.ics.jung.graph.Graph<V,E> g)

This method finds a maximal independent set in a graph using a trivial greedy algorithm. The complexity of this algorithm is polynomial (O(n+m)).

Parameters:

g - Graph in which a maximal Independent set has to be found

Returns:

a maximal independent set of G

maximumIndependentSetBruteForce

public java.util.Set<V> maximumIndependentSetBruteForce(edu.uci.ics.jung.graph.Graph<V,E> g)

This method returns a maximum independent set of G using the naive brute force algorithm that examines every vertex subset and checks whether it is an independent set, which time complexity is O(n^2.2^n).

Parameters:

g - Graph in which Maximum Independent sets have to be found

Returns:

a maximum independent set of G

maximumIndependentSetMoonMoser

public java.util.Set<V> maximumIndependentSetMoonMoser(edu.uci.ics.jung.graph.Graph<V,E> g)

This method returns a maximum independent set of G based on the Moon and Moser work ("On cliques in graphs" 1965). The algorithm solves the problem in time O(1.4423^n).

Parameters:

g - Graph in which Maximum Independent sets have to be found

Returns:

A maximum independent set of G

maximumIndependentSetMoonMoserNonRecursive

public java.util.Set<V> maximumIndependentSetMoonMoserNonRecursive(edu.uci.ics.jung.graph.Graph<V,E> g)

This method is the same as MaximumIndependentSetMM but in a non-recursive version (slower).

Parameters:

g - Graph in which Maximum Independent sets have to be found

Returns:

A maximum independent set of G

maximumIndependentSetMaximumDegree

public java.util.Set<V> maximumIndependentSetMaximumDegree(edu.uci.ics.jung.graph.Graph<V,E> g)

This method returns a maximum independent set of G by finding vertices with max degrees.

Parameters:

g - Graph in which Maximum Independent sets have to be found

Returns:

A maximum independent set of G

maximuRmIndependentSetFominGrandoniKratsch

public java.util.Set<V> maximuRmIndependentSetFominGrandoniKratsch(edu.uci.ics.jung.graph.Graph<V,E> g)

This method returns a maximum independent set of G based on the Fomin and al. work ("A Measure & Conquer Approach for the Analysis of Exact Algorithms" 2009). The algorithm solves the problem in time O(1.2201^n).

Parameters:

g - graph

Returns:

a maximum independent set in G.

isIndependentSet

public static <V,E> boolean isIndependentSet(edu.uci.ics.jung.graph.Graph<V,E> g,
                             java.util.Set<V> S)

This method tests if a set S of a Graph G is an independent set.

Parameters:

g - graph

S - set to test

Returns:

true if S is an independent set, false if not.

isMaximalIndependentSet

public static <V,E> boolean isMaximalIndependentSet(edu.uci.ics.jung.graph.Graph<V,E> g,
                                    java.util.Set<V> S)

This method tests if a set S of a Graph G is a maximal independent set.

Parameters:

g - graph

S - set to test

Returns:

true if S is a maximal independent set, false if not.