Class MinimumVertexCoverApproximationAlgorithm<TVertex, TEdge>

A minimum vertices cover approximation algorithm for undirected graphs.

Inheritance
System.Object
AlgorithmBase<IUndirectedGraph<TVertex, TEdge>>
MinimumVertexCoverApproximationAlgorithm<TVertex, TEdge>
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: QuikGraph.Algorithms.VertexCover
Assembly: QuikGraph.dll
Syntax
public sealed class MinimumVertexCoverApproximationAlgorithm<TVertex, TEdge> : AlgorithmBase<IUndirectedGraph<TVertex, TEdge>>, IAlgorithm<IUndirectedGraph<TVertex, TEdge>>, IComputation, IAlgorithmComponent where TEdge : IEdge<TVertex>
Type Parameters
Name Description
TVertex
TEdge
Remarks

This is a modified version (by Batov Nikita) of the original Mihalis Yannakakis and Fanica Gavril algorithm.

Constructors

| Improve this Doc View Source

MinimumVertexCoverApproximationAlgorithm(IUndirectedGraph<TVertex, TEdge>)

Initializes a new instance of the MinimumVertexCoverApproximationAlgorithm<TVertex, TEdge> class.

Declaration
public MinimumVertexCoverApproximationAlgorithm(IUndirectedGraph<TVertex, TEdge> graph)
Parameters
Type Name Description
IUndirectedGraph<TVertex, TEdge> graph

Graph to compute the cover.
Remarks

This constructor will use CryptoRandom ad random number generator.

Exceptions
Type Condition
System.ArgumentNullException

graph is null.
| Improve this Doc View Source

MinimumVertexCoverApproximationAlgorithm(IUndirectedGraph<TVertex, TEdge>, Random)

Initializes a new instance of the MinimumVertexCoverApproximationAlgorithm<TVertex, TEdge> class.

Declaration
public MinimumVertexCoverApproximationAlgorithm(IUndirectedGraph<TVertex, TEdge> graph, Random rng)
Parameters
Type Name Description
IUndirectedGraph<TVertex, TEdge> graph

Graph to compute the cover.
System.Random rng

Random number generator.
Exceptions
Type Condition
System.ArgumentNullException

graph is null.
System.ArgumentNullException

rng is null.

Properties

| Improve this Doc View Source

CoverSet

Set of covering vertices.

Declaration
public VertexList<TVertex> CoverSet { get; }
Property Value
Type Description
VertexList<TVertex>

Methods

| Improve this Doc View Source

InternalCompute()

Algorithm compute step.

Declaration
protected override void InternalCompute()
Overrides
QuikGraph.Algorithms.AlgorithmBase<QuikGraph.IUndirectedGraph<TVertex, TEdge>>.InternalCompute()

Implements

Extension Methods