/*
* (C) Copyright 2016-2017, by Joris Kinable and Contributors.
*
* JGraphT : a free Java graph-theory library
*
* This program and the accompanying materials are dual-licensed under
* either
*
* (a) the terms of the GNU Lesser General Public License version 2.1
* as published by the Free Software Foundation, or (at your option) any
* later version.
*
* or (per the licensee's choosing)
*
* (b) the terms of the Eclipse Public License v1.0 as published by
* the Eclipse Foundation.
*/
package org.jgrapht.alg.interfaces;
import java.util.*;
import java.util.function.*;
import java.util.stream.*;
import org.jgrapht.*;
/**
* Computes a weighted vertex cover in an undirected graph. A vertex cover of a graph is a set of
* vertices such that each edge of the graph is incident to at least one vertex in the set. A
* minimum vertex cover is a vertex cover having the smallest possible number of vertices for a
* given graph. The size of a minimum vertex cover of a graph G is known as the vertex cover number.
* A vertex cover of minimum weight is a vertex cover where the sum of weights assigned to the
* individual vertices in the cover has been minimized. The minimum vertex cover problem is a
* special case of the minimum weighted vertex cover problem where all vertices have equal weight.
* Consequently, any algorithm designed for the weighted version of the problem can also solve
* instances of the unweighted version.
*
* @param the graph vertex type
* @param the graph edge type
*
*/
public interface MinimumWeightedVertexCoverAlgorithm
extends MinimumVertexCoverAlgorithm
{
/**
* {@inheritDoc}
*/
@Override
default VertexCover getVertexCover(UndirectedGraph graph)
{
Map vertexWeightMap = graph
.vertexSet().stream().collect(Collectors.toMap(Function.identity(), vertex -> 1.0));
return getVertexCover(graph, vertexWeightMap);
}
/**
* Computes a vertex cover; the weight of each vertex is provided in the in the
* {@code vertexWeightMap}.
*
* @param graph the input graph
* @param vertexWeightMap map containing non-negative weights for each vertex
* @return a vertex cover
*/
VertexCover getVertexCover(UndirectedGraph graph, Map vertexWeightMap);
}
Ads help maintain this website.