20514590651

Committed 26 Dec 2025 02:37AM UTC coverage: 70.559% (-0.3%) from 70.836%

Build # 20514590651

Build Type

push

github

Committed by

apowers313

Commit Message

ci: fix npm ci

Run Details

9591 of 13363 branches covered (71.77%)

Branch coverage included in aggregate %.

25136 of 35854 relevant lines covered (70.11%)

6233.71 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

90.18

/src/algorithms/BipartiteMatchingAlgorithm.ts

/**
 * @file Bipartite Matching Algorithm wrapper
 *
 * This algorithm finds the maximum matching in a bipartite graph.
 * A matching is a set of edges without common vertices.
 * Maximum matching has the largest possible number of edges.
 */

import {bipartitePartition, maximumBipartiteMatching} from "@graphty/algorithms";

import {SuggestedStylesConfig} from "../config";
import {Algorithm} from "./Algorithm";
import {toAlgorithmGraph} from "./utils/graphConverter";

/**
 * Bipartite Matching algorithm for finding maximum matchings
 *
 * Finds the maximum matching in a bipartite graph where nodes can be divided
 * into two disjoint sets with edges only between sets.
 */
export class BipartiteMatchingAlgorithm extends Algorithm {
    static namespace = "graphty";
    static type = "bipartite-matching";

    static suggestedStyles = (): SuggestedStylesConfig => ({
        layers: [
            {
                edge: {
                    selector: "",
                    style: {enabled: true},
                    calculatedStyle: {
                        inputs: ["algorithmResults.graphty.bipartite-matching.inMatching"],
                        output: "style.line.color",
                        expr: "{ return StyleHelpers.color.binary.blueHighlight(arguments[0]) }",
                    },
                },
                metadata: {
                    name: "Matching - Matched Edges",
                    description: "Highlights edges in maximum matching (blue) - colorblind-safe",
                },
            },
            {
                edge: {
                    selector: "algorithmResults.graphty.\"bipartite-matching\".inMatching == `false`",
                    style: {
                        enabled: true,
                        line: {
                            opacity: 0.3,
                        },
                    },
                },
                metadata: {
                    name: "Matching - Non-Matched Edges",
                    description: "Dims edges not in maximum matching",
                },
            },
            {
                node: {
                    selector: "",
                    style: {enabled: true},
                    calculatedStyle: {
                        inputs: ["algorithmResults.graphty.bipartite-matching.partition"],
                        output: "style.texture.color",
                        expr: "{ return arguments[0] === 'left' ? StyleHelpers.color.categorical.okabeIto(0) : StyleHelpers.color.categorical.okabeIto(1) }",
                    },
                },
                metadata: {
                    name: "Matching - Partition Colors",
                    description: "Colors nodes by partition (left/right) - colorblind-safe",
                },
            },
        ],
        description: "Visualizes maximum bipartite matching with partition coloring",
        category: "path",
    });

    /**
     * Executes the bipartite matching algorithm on the graph
     *
     * Computes the maximum matching and partitions nodes into left and right sets.
     */
    async run(): Promise<void> {
        const g = this.graph;
        const edges = Array.from(g.getDataManager().edges.values());

        if (edges.length === 0) {
            return;
        }

        // Convert to @graphty/algorithms format
        // Use undirected graph without reverse edges for bipartite matching
        const graphData = toAlgorithmGraph(g, {directed: false, addReverseEdges: false});

        // First check if the graph is bipartite
        const partition = bipartitePartition(graphData);
        if (!partition) {
            // Graph is not bipartite - store error and mark all edges as not in matching
            this.addGraphResult("error", "Graph is not bipartite");
            this.addGraphResult("matchingSize", 0);

            for (const edge of edges) {
                this.addEdgeResult(edge, "inMatching", false);
            }

            return;
        }

        // Run maximum bipartite matching
        const result = maximumBipartiteMatching(graphData, {
            leftNodes: partition.left,
            rightNodes: partition.right,
        });

        // Create set of matched edge keys for fast lookup
        const matchedEdgeKeys = new Set<string>();
        for (const [leftNode, rightNode] of result.matching) {
            matchedEdgeKeys.add(`${String(leftNode)}:${String(rightNode)}`);
            matchedEdgeKeys.add(`${String(rightNode)}:${String(leftNode)}`);
        }

        // Mark each edge as in matching or not
        for (const edge of edges) {
            const edgeKey = `${edge.srcId}:${edge.dstId}`;
            const inMatching = matchedEdgeKeys.has(edgeKey);
            this.addEdgeResult(edge, "inMatching", inMatching);
        }

        // Store node partition information
        for (const nodeId of partition.left) {
            this.addNodeResult(nodeId, "partition", "left");
            this.addNodeResult(nodeId, "isMatched", result.matching.has(nodeId));
        }

        for (const nodeId of partition.right) {
            this.addNodeResult(nodeId, "partition", "right");
            // Check if this node is matched (appears in values of matching map)
            const isMatched = Array.from(result.matching.values()).includes(nodeId);
            this.addNodeResult(nodeId, "isMatched", isMatched);
        }

        // Store graph-level results
        this.addGraphResult("matchingSize", result.size);
        this.addGraphResult("leftPartitionSize", partition.left.size);
        this.addGraphResult("rightPartitionSize", partition.right.size);
    }
}

// Auto-register this algorithm when the module is imported
Algorithm.register(BipartiteMatchingAlgorithm);

1	/**
2	* @file Bipartite Matching Algorithm wrapper
3	*
4	* This algorithm finds the maximum matching in a bipartite graph.
5	* A matching is a set of edges without common vertices.
6	* Maximum matching has the largest possible number of edges.
7	*/
8
9	import {bipartitePartition, maximumBipartiteMatching} from "@graphty/algorithms";	15✔
10
11	import {SuggestedStylesConfig} from "../config";
12	import {Algorithm} from "./Algorithm";	15✔
13	import {toAlgorithmGraph} from "./utils/graphConverter";	15✔
14
15	/**
16	* Bipartite Matching algorithm for finding maximum matchings
17	*
18	* Finds the maximum matching in a bipartite graph where nodes can be divided
19	* into two disjoint sets with edges only between sets.
20	*/
21	export class BipartiteMatchingAlgorithm extends Algorithm {	15✔
22	static namespace = "graphty";	18✔
23	static type = "bipartite-matching";	119✔
24
25	static suggestedStyles = (): SuggestedStylesConfig => ({	119✔
26	layers: [	12✔
27	{	12✔
28	edge: {	12✔
29	selector: "",	12✔
30	style: {enabled: true},	12✔
31	calculatedStyle: {	12✔
32	inputs: ["algorithmResults.graphty.bipartite-matching.inMatching"],	12✔
33	output: "style.line.color",	12✔
34	expr: "{ return StyleHelpers.color.binary.blueHighlight(arguments[0]) }",	12✔
35	},	12✔
36	},	12✔
37	metadata: {	12✔
38	name: "Matching - Matched Edges",	12✔
39	description: "Highlights edges in maximum matching (blue) - colorblind-safe",	12✔
40	},	12✔
41	},	12✔
42	{	12✔
43	edge: {	12✔
44	selector: "algorithmResults.graphty.\"bipartite-matching\".inMatching == `false`",	12✔
45	style: {	12✔
46	enabled: true,	12✔
47	line: {	12✔
48	opacity: 0.3,	12✔
49	},	12✔
50	},	12✔
51	},	12✔
52	metadata: {	12✔
53	name: "Matching - Non-Matched Edges",	12✔
54	description: "Dims edges not in maximum matching",	12✔
55	},	12✔
56	},	12✔
57	{	12✔
58	node: {	12✔
59	selector: "",	12✔
60	style: {enabled: true},	12✔
61	calculatedStyle: {	12✔
62	inputs: ["algorithmResults.graphty.bipartite-matching.partition"],	12✔
63	output: "style.texture.color",	12✔
64	expr: "{ return arguments[0] === 'left' ? StyleHelpers.color.categorical.okabeIto(0) : StyleHelpers.color.categorical.okabeIto(1) }",	12✔
65	},	12✔
66	},	12✔
67	metadata: {	12✔
68	name: "Matching - Partition Colors",	12✔
69	description: "Colors nodes by partition (left/right) - colorblind-safe",	12✔
70	},	12✔
71	},	12✔
72	],	12✔
73	description: "Visualizes maximum bipartite matching with partition coloring",	12✔
74	category: "path",	12✔
75	});	12✔
76
77	/**
78	* Executes the bipartite matching algorithm on the graph
79	*
80	* Computes the maximum matching and partitions nodes into left and right sets.
81	*/
82	async run(): Promise<void> {	18✔
83	const g = this.graph;	3✔
84	const edges = Array.from(g.getDataManager().edges.values());	3✔
85
86	if (edges.length === 0) {	3!
87	return;	×
88	}	×
89
90	// Convert to @graphty/algorithms format
91	// Use undirected graph without reverse edges for bipartite matching
92	const graphData = toAlgorithmGraph(g, {directed: false, addReverseEdges: false});	3✔
93
94	// First check if the graph is bipartite
95	const partition = bipartitePartition(graphData);	3✔
96	if (!partition) {	3!
97	// Graph is not bipartite - store error and mark all edges as not in matching
98	this.addGraphResult("error", "Graph is not bipartite");	×
99	this.addGraphResult("matchingSize", 0);	×
100
101	for (const edge of edges) {	×
102	this.addEdgeResult(edge, "inMatching", false);	×
103	}	×
104
105	return;	×
106	}	×
107
108	// Run maximum bipartite matching
109	const result = maximumBipartiteMatching(graphData, {	3✔
110	leftNodes: partition.left,	3✔
111	rightNodes: partition.right,	3✔
112	});	3✔
113
114	// Create set of matched edge keys for fast lookup
115	const matchedEdgeKeys = new Set<string>();	3✔
116	for (const [leftNode, rightNode] of result.matching) {	3✔
117	matchedEdgeKeys.add(`${String(leftNode)}:${String(rightNode)}`);	21✔
118	matchedEdgeKeys.add(`${String(rightNode)}:${String(leftNode)}`);	21✔
119	}	21✔
120
121	// Mark each edge as in matching or not
122	for (const edge of edges) {	3✔
123	const edgeKey = `${edge.srcId}:${edge.dstId}`;	36✔
124	const inMatching = matchedEdgeKeys.has(edgeKey);	36✔
125	this.addEdgeResult(edge, "inMatching", inMatching);	36✔
126	}	36✔
127
128	// Store node partition information
129	for (const nodeId of partition.left) {	3✔
130	this.addNodeResult(nodeId, "partition", "left");	21✔
131	this.addNodeResult(nodeId, "isMatched", result.matching.has(nodeId));	21✔
132	}	21✔
133
134	for (const nodeId of partition.right) {	3✔
135	this.addNodeResult(nodeId, "partition", "right");	21✔
136	// Check if this node is matched (appears in values of matching map)
137	const isMatched = Array.from(result.matching.values()).includes(nodeId);	21✔
138	this.addNodeResult(nodeId, "isMatched", isMatched);	21✔
139	}	21✔
140
141	// Store graph-level results
142	this.addGraphResult("matchingSize", result.size);	3✔
143	this.addGraphResult("leftPartitionSize", partition.left.size);	3✔
144	this.addGraphResult("rightPartitionSize", partition.right.size);	3✔
145	}	3✔
146	}	18✔
147
148	// Auto-register this algorithm when the module is imported
149	Algorithm.register(BipartiteMatchingAlgorithm);	15✔

graphty-org / graphty-element / 20514590651

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous