chinese-whispers/bundles/chinese-whispers.es6.umd.js

/* chinese-whisper version 0.3.9 */
(function (global, factory) {
    typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports, require('events')) :
    typeof define === 'function' && define.amd ? define(['exports', 'events'], factory) :
    (global = global || self, factory(global.window = {}, global.events));
}(this, function (exports, events) { 'use strict';

    /**
     * This file was auto generated from scripts/generate-version.sh
     */
    const VERSION = '0.3.9';

    /**
     * Chinese Whispers Algorithm for Node.js
     *
     * https://github.com/huan/chinese-whispers
     * License: Apache-2.0
     * Author: Huan LI <zixia@zixia.net>
     *
     * Inspired by:
     *  - http://blog.csdn.net/liyuan123zhouhui/article/details/70312716
     *  - http://alexloveless.co.uk/data/chinese-whispers-graph-clustering-in-python/
     *  - https://github.com/uhh-lt/chinese-whispers
     *  - https://github.com/anvaka/ngraph.cw
     *
     */
    const jsnx = require('jsnetworkx');
    const { knuthShuffle } = require('knuth-shuffle');
    class ChineseWhispers extends events.EventEmitter {
        constructor(options) {
            super();
            this.weightFunc = options.weightFunc;
            this.epochs = options.epochs || 15;
            this.threshold = options.threshold;
            this.on('change', () => this.changeCounter++);
        }
        on(event, listener) {
            super.on(event, listener);
            return this;
        }
        emit(event, ...args) {
            return super.emit(event, ...args);
        }
        cluster(dataList) {
            // this.dataList = dataList
            this.graph = this.buildNetwork(dataList, this.weightFunc, this.threshold);
            // initial epoch
            this.emit('epoch', this.graph, -1);
            // run Chinese Whispers
            // I default to 10 iterations. This number is usually low.
            // After a certain number (individual to the data set) no further clustering occurs
            let epochs = this.epochs;
            while (epochs--) {
                this.changeCounter = 0;
                this.iterate();
                this.emit('epoch', this.graph, this.changeCounter);
            }
            const clusterList = this.buildClusterList(this.graph);
            return clusterList;
        }
        iterate() {
            const nodeList = this.graph.nodes();
            // I randomize the nodes to give me an arbitrary start point
            knuthShuffle(nodeList); // orignal array modified
            for (const node of nodeList) {
                this.relabelNode(node);
            }
        }
        relabelNode(node) {
            const newLabel = this.recalcLabel(node);
            const nodeAttr = this.graph.node.get(node);
            if (nodeAttr.label !== newLabel) {
                // set the label of target node to the winning local label
                this.emit('change', node, nodeAttr.label, newLabel);
                nodeAttr.label = newLabel;
                // console.log('set node ' + this.data[node] + ' label to ' + this.data[parseInt(newLabel)])
            }
        }
        recalcLabel(node) {
            const nxNode = this.graph.get(node);
            const neighborList = this.graph.neighbors(node);
            if (neighborList.length === 0) {
                const attr = this.graph.node.get(node);
                return attr.label; // return self label if no neighbors
            }
            // console.log('neighbors of node ' + this.data[node]
            //     + ' is: ', neighborList.map((i: number) => this.data[i]))
            const labelWeightMap = {};
            // do an inventory of the given nodes neighbours and edge weights
            for (const neighbor of neighborList) {
                const neighborAttr = this.graph.node.get(neighbor);
                const label = neighborAttr.label;
                if (!(label in labelWeightMap)) {
                    labelWeightMap[label] = 0;
                }
                const edgeAttr = nxNode.get(neighbor);
                const weight = edgeAttr.weight;
                // console.log('### ', weight, ' ###')
                labelWeightMap[label] += weight;
            }
            // find the label with the highest edge weight sum
            let max = 0;
            // In javascript the keys of object can only be strings
            //  - https://stackoverflow.com/a/41870625/1123955
            let maxLabel = '-1';
            // for (const label in labelWeightMap) {
            //   console.log('labelWeight node: ' + this.data[node] + ' - '
            //       + this.data[parseInt(label)] + ' is: ', labelWeightMap[label])
            // }
            for (const label in labelWeightMap) {
                if (labelWeightMap[label] > max) {
                    max = labelWeightMap[label];
                    maxLabel = label;
                }
            }
            return maxLabel;
        }
        buildClusterList(G) {
            const clusterList = [];
            const labelIndexMap = {};
            let index = 0;
            for (const node of G.nodes()) {
                const label = G.node.get(node).label;
                if (!(label in labelIndexMap)) {
                    labelIndexMap[label] = index++;
                }
                const labelIndex = labelIndexMap[label];
                if (!(labelIndex in clusterList)) {
                    clusterList[labelIndex] = [];
                }
                clusterList[labelIndex].push(node);
            }
            return clusterList;
        }
        buildNetwork(dataList, weightFunc, threshold) {
            const nodeList = Object.keys(dataList).map(k => parseInt(k, 10)); // [0, 1, 2, ..., data.length - 1]
            // const nodeList: CWNode[] = [...data.keys()] // [0, 1, 2, ..., data.length - 1]
            const edgeList = [];
            for (let i = 0; i < dataList.length; i++) {
                for (let j = i + 1; j < dataList.length; j++) {
                    const weight = weightFunc(dataList[i], dataList[j]);
                    if (threshold && threshold > weight) {
                        // console.log('threshold: ', threshold, ' weight: ', weight)
                        // skip this edge because it's weight is below threshold
                        this.emit('edge');
                    }
                    else {
                        const edge = [i, j, { weight }];
                        edgeList.push(edge);
                        this.emit('edge', edge);
                    }
                }
            }
            // initialize the graph
            const G = new jsnx.Graph();
            // Add nodes
            G.addNodesFrom(nodeList);
            // CW needs an arbitrary, unique label for each node before initialisation
            // Here I use the ID of the node since I know it's unique
            // You could use a random number or a counter or anything really
            for (const n of G.nodes()) {
                const nodeAttr = G.node.get(n);
                nodeAttr.label = n;
            }
            // add edges
            G.addEdgesFrom(edgeList);
            // console.log(edgeList)
            return G;
        }
    }

    exports.ChineseWhispers = ChineseWhispers;
    exports.VERSION = VERSION;
    exports.default = ChineseWhispers;

    Object.defineProperty(exports, '__esModule', { value: true });

}));
/* https://git.io/zixia/ */
//# sourceMappingURL=chinese-whispers.es6.umd.js.map