/*
* (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 org.jgrapht.*;
/**
* Computes a 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.
*
* @param the graph vertex type
* @param the graph edge type
*
*/
public interface MinimumVertexCoverAlgorithm
{
/**
* Computes a vertex cover; all vertices are considered to have equal weight.
*
* @param graph the graph
* @return a vertex cover
*/
VertexCover getVertexCover(UndirectedGraph graph);
/**
* A vertex cover
*
* @param the vertex type
*/
interface VertexCover
{
/**
* Returns the weight of the vertex cover. When solving the minimum weighted vertex cover
* problem, the weight returned is the sum of the weights of the vertices in the cover. When
* solving the unweighted variant, the cardinality of the vertex cover is returned instead.
*
* @return weight of the vertex cover
*/
double getWeight();
/**
* Set of vertices constituting the vertex cover
*
* @return vertices in the vertex cover
*/
Set getVertices();
}
/**
* Default implementation of a vertex cover
*
* @param the vertex type
*/
class VertexCoverImpl
implements VertexCover
{
protected Set cover;
protected double weight;
public VertexCoverImpl(Set cover, double weight)
{
this.cover = cover;
this.weight = weight;
}
@Override
public double getWeight()
{
return weight;
}
@Override
public Set getVertices()
{
return cover;
}
@Override
public String toString()
{
StringBuilder builder = new StringBuilder("Cover(");
builder.append(this.getWeight());
builder.append("): ");
builder.append(this.getVertices().toString());
return builder.toString();
}
}
}
Ads help maintain this website.