Vertex-Cover 2-Approximation Demonstrator Source Code
Browse the implementation files for Vertex-Cover 2-Approximation Demonstrator.tool.ts typescript
// Tool: Vertex-Cover 2-Approximation Demonstrator
type Vertex = number | string;
const MAX_EDGES = 10_000;
const vertexKey = (vertex: Vertex): string =>
`${typeof vertex}:${String(vertex)}`;
const parseEdges = (
input: unknown
): [Vertex, Vertex][] | null => {
if (typeof input !== 'string' || input.trim() === '')
return null;
try {
const edges: unknown = JSON.parse(input);
if (
!Array.isArray(edges) ||
edges.length === 0 ||
edges.length > MAX_EDGES
) {
return null;
}
const validVertex = (vertex: unknown): vertex is Vertex =>
(typeof vertex === 'string' && vertex.trim() !== '') ||
(typeof vertex === 'number' && Number.isFinite(vertex));
return edges.every(
(edge) =>
Array.isArray(edge) &&
edge.length === 2 &&
validVertex(edge[0]) &&
validVertex(edge[1]) &&
vertexKey(edge[0]) !== vertexKey(edge[1])
)
? (edges as [Vertex, Vertex][])
: null;
} catch {
return null;
}
};
export const approximateVertexCover = (
edgesInput: unknown
): string => {
const edges = parseEdges(edgesInput);
if (edges === null) return '';
const selectedKeys = new Set<string>();
const selectedVertices: Vertex[] = [];
const matching: [Vertex, Vertex][] = [];
for (const [first, second] of edges) {
const firstKey = vertexKey(first);
const secondKey = vertexKey(second);
if (
selectedKeys.has(firstKey) ||
selectedKeys.has(secondKey)
) {
continue;
}
matching.push([first, second]);
for (const vertex of [first, second]) {
const key = vertexKey(vertex);
selectedKeys.add(key);
selectedVertices.push(vertex);
}
}
const coversEveryEdge = edges.every(
([first, second]) =>
selectedKeys.has(vertexKey(first)) ||
selectedKeys.has(vertexKey(second))
);
if (!coversEveryEdge) return '';
return JSON.stringify(
{
approximationRatio: 2,
cover: selectedVertices,
coverSize: selectedVertices.length,
maximalMatching: matching
},
null,
2
);
};
export const Tool: TypeTool = {
name: 'Vertex-Cover 2-Approximation Demonstrator',
slug: 'approximation/vertex-cover-2-approximation',
intro:
'Build a maximal matching and select both endpoints to obtain an unweighted vertex cover with a factor-2 guarantee.',
tool: approximateVertexCover,
i: [
{
example: '[["A","B"],["B","C"],["C","D"],["D","A"]]',
label: 'Edges',
placeholder:
'JSON array of two-vertex edges using strings or numbers',
render: 'textarea',
type: 'text',
value: '[["A","B"],["B","C"],["C","D"],["D","A"]]'
}
],
o: [
{
example:
'{ "cover": ["A", "B", "C", "D"], "approximationRatio": 2 }',
label: 'Approximate Vertex Cover',
placeholder: 'Approximate cover will appear here...',
render: 'textarea',
type: 'text'
}
],
cite: [
{
title: 'Approximation algorithm — Wikipedia',
url: 'https://en.wikipedia.org/wiki/Approximation_algorithm'
},
{
title: 'Vertex cover — Wikipedia',
url: 'https://en.wikipedia.org/wiki/Vertex_cover'
}
]
};
export default Tool;
Description
Browse the implementation files for Vertex-Cover 2-Approximation Demonstrator.