Skip to content

Main content

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.

References

  1. Tool.io on GitHub
  2. Tool.io TypeScript tools library

Similar or alternative tools