Package com.jgalgo.alg

Interface EdgeCover

public interface EdgeCover

Minimum edge vertex cover algorithm.

Given a graph \(G=(V,E)\) an edge cover is a set \(S \subseteq E\) for which for any vertex \(v \in V\) at least one of the edges adjacent to \(v\) is in \(S\). Given an edge weight function \(w:E \rightarrow R\), the weight of an edge cover is the weight sum of the edges in the cover. The minimum edge cover is the edge cover with the minimum weight. In contrast to the VertexCover problem which is NP-hard, the edge cover problem can be solved in polynomial time.

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

Author:

Barak Ugav

See Also:

VertexCover

Nested Class Summary

Nested Classes

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

Method Summary

Modifier and Type	Method	Description
static EdgeCover.Builder	builder()	Create a new edge cover algorithm builder.
<V,E> Set<E>	computeMinimumEdgeCover(Graph<V,E> g, WeightFunction<E> w)	Compute a minimum edge cover of a graph with respect to an edge weight function.
static <V,E> boolean	isCover(Graph<V,E> g, Collection<E> edges)	Check whether a set of edges is a edge cover of a graph.
static EdgeCover	newInstance()	Create a new edge cover algorithm object.

Method Detail

computeMinimumEdgeCover

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

Compute a minimum edge cover of a graph with respect to an edge weight function.

If g is IntGraph, the returned object is IntSet. If g is IntGraph, prefer to pass IWeightFunction for best performance.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

w - an edge weight function

Returns:

a minimum edge cover

isCover

static <V,E> boolean isCover(Graph<V,E> g,
                                   Collection<E> edges)

Check whether a set of edges is a edge cover of a graph.

A set of edges is an edge cover of a graph if for every vertex has at least one adjacent edge which is in the set. In addition, the collection of the edges must not contain duplicates.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

edges - a collection of edges that should cover all the vertices in the graph

Returns:

true if edges is an edge cover of g

newInstance

static EdgeCover newInstance()

Create a new edge cover algorithm object.

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

Returns:

a default implementation of EdgeCover

builder

static EdgeCover.Builder builder()

Create a new edge cover algorithm builder.

Use newInstance() for a default implementation.

Returns:

a new builder that can build EdgeCover objects