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