Package com.jgalgo.alg.cover

Interface EdgeCover

All Known Implementing Classes:

EdgeCoverAbstract, EdgeCoverCardinality, EdgeCoverWeighted

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.

Author:

Barak Ugav

See Also:

VertexCover

Method Summary

Modifier and Type	Method	Description
<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.

Returns:

a default implementation of EdgeCover