edge-coloring

Graph Edge colourer

Implementation 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.

Installation

npm install edge-colouring

Usage

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'));
 

import MisraGries, { createSampleRound } from 'edge-colouring';
const graph = new MisraGries(20);
graph.makeComplete();
graph.removeEdges(createSampleRound(20));
graph.colourEdges();
graph.print();