‚̧Nighttime Possum Meandering
    Have ideas to improve npm?Join in the discussion! ¬Ľ

    edge-colouring
    TypeScript icon, indicating that this package has built-in type declarations

    1.0.0¬†‚Äʬ†Public¬†‚Äʬ†Published

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

    Install

    npm i edge-colouring

    DownloadsWeekly Downloads

    0

    Version

    1.0.0

    License

    MIT

    Unpacked Size

    138 kB

    Total Files

    53

    Last publish

    Collaborators

    • avatar