Package com.jgalgo.alg

Interface DominatingSetAlgo

public interface DominatingSetAlgo

An algorithm for computing a minimum dominating set.

Given a graph $G = (V, E)$, a dominating set is a subset $D \subseteq V$ such that for every $v \in V$, either $v \in D$ or there is an edge $(u, v) \in E$ such that $u \in D$. The minimum dominating set problem is to find a dominating set of minimum size or weight. The problem is NP-hard. Algorithms implementing this interfaces are heuristics or fixed ration approximation algorithms.

In a directed graph, the 'dominance' should be defined with respect to either the in-edges, out-edges or in-edges + out-edges of the vertices. This is specified as a EdgeDirection parameter to computeMinimumDominationSet(Graph, WeightFunction, EdgeDirection), which yields different types of dominating sets.

Use newInstance() to get a default implementation of this interface. A builder obtained via newBuilder() may support different options to obtain different implementations.

Author:

Barak Ugav

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	DominatingSetAlgo.Builder	A builder for DominatingSetAlgo algorithms.

Method Summary

Modifier and Type	Method	Description
default <V,E> Set<V>	computeMinimumDominationSet(Graph<V,E> g, WeightFunction<V> w)	Compute a minimum dominating set of the graph with respect to the in-degree + out-degree of the vertices.
<V,E> Set<V>	computeMinimumDominationSet(Graph<V,E> g, WeightFunction<V> w, EdgeDirection dominanceDirection)	Compute a minimum dominating set of the graph with respect to the given edges direction.
static <V,E> boolean	isDominatingSet(Graph<V,E> g, Collection<V> dominatingSet, EdgeDirection dominanceDirection)	Check whether a given set of vertices is a dominating set of a graph.
static DominatingSetAlgo.Builder	newBuilder()	Create a new dominating set algorithm builder.
static DominatingSetAlgo	newInstance()	Create a new dominating set algorithm object.

Method Detail

computeMinimumDominationSet

default <V,E> Set<V> computeMinimumDominationSet(Graph<V,E> g,
                                                       WeightFunction<V> w)

Compute a minimum dominating set of the graph with respect to the in-degree + out-degree of the vertices.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

w - a vertex weight function

Returns:

a minimum dominating set of the graph

computeMinimumDominationSet

<V,E> Set<V> computeMinimumDominationSet(Graph<V,E> g,
                                               WeightFunction<V> w,
                                               EdgeDirection dominanceDirection)

Compute a minimum dominating set of the graph with respect to the given edges direction.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

w - a vertex weight function

dominanceDirection - the direction of the edges to consider

Returns:

a minimum dominating set of the graph

isDominatingSet

static <V,E> boolean isDominatingSet(Graph<V,E> g,
                                           Collection<V> dominatingSet,
                                           EdgeDirection dominanceDirection)

Check whether a given set of vertices is a dominating set of a graph.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

dominatingSet - a set of vertices

dominanceDirection - the direction of the edges to consider, if null then EdgeDirection.All is used

Returns:

true if the given set is a dominating set of the graph

newInstance

static DominatingSetAlgo newInstance()

Create a new dominating set algorithm object.

This is the recommended way to instantiate a new DominatingSetAlgo object. The DominatingSetAlgo.Builder might support different options to obtain different implementations.

Returns:

a default implementation of DominatingSetAlgo

newBuilder

static DominatingSetAlgo.Builder newBuilder()

Create a new dominating set algorithm builder.

Use newInstance() for a default implementation.

Returns:

a new builder that can build DominatingSetAlgo objects