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:

  • 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 Details

    • 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