Implementation of Misra & Gries edge colouring algorithm that produces at most d+1 colours, where d is the maximum degree of the graph. Supports an arbitary number of nodes.
npm install edge-colouringImplementation of Misra & Gries edge colouring algorithm that produces at most d+1 colours, where d is the maximum degree of the graph.
Tends to produce d+1 colours. This is a limitation of the algorithm.
Supports an arbitary number of nodes and cases where edges are removed.
npm install edge-colouring
``js
const MisraGries = require('edge-colouring').default;
const { randBetween, createSampleRound } = require('edge-colouring');
const limit = 100;
const graph = new MisraGries(limit, {
isDev: false,
wSubsets: 'minimal'
});
graph.makeComplete();
let round1 = createSampleRound(limit);
let round2 = createSampleRound(limit, round1);
graph.removeEdges([...round1, ...round2]);
console.log('Fixed');
console.log([new Set(round1).size, round1.length, '|', ...round1].join(' '));
console.log([new Set(round2).size, round2.length, '|', ...round2].join(' '));
console.log('---');
graph.colourEdges();
let colours = graph.colours;
console.log(colours.length);
console.log(colours.map(c => c.length).join(' '));
console.log(colours.map(line => [new Set(line).size, line.length, '|', ...line].join(' ')).join('\n'));
`
`ts``
import MisraGries, { createSampleRound } from 'edge-colouring';
const graph = new MisraGries(20);
graph.makeComplete();
graph.removeEdges(createSampleRound(20));
graph.colourEdges();
graph.print();