1

I am searching for an Javascript implementation of the Bron-Kerbosch algorithm or Girvan-Newman algorithm.

Basically I want to color maximal cliques/communities in an undirected graph.

Sadly, I found only cryptic Python and bloated Java & C++ library code. I need it in plain Javascript code (preferable no bloated JS library or JQuery et al dependencies).

// I am using the following data structure
fg_p = []; // Points (Users)
fg_e = []; // Edges

function fgAddUser(uid, name) {
  var t_obj = {};
  t_obj.id = id;
  t_obj.name = name;            
  fg_g[fg_g.length] = t_obj;
}

function fgAddEdge(a, b) {
  var t_obj = {};
  t_obj.a = a; // user A
  t_obj.b = b; // user B
  fg_e[fg_e.length] = t_obj;
}
4

1 回答 1

1

我制作了一个执行第一个版本的Bron–Kerbosch算法的模块

'use strict';

function graphUtils(){
var methods = {};



methods.allCliques = function(g){
    var cliques=[];
    var p=[];
    g.forEachNode(function(node){
        p.push(node.id);
    });
    var r =[];
    var x=[];

    bronKerbosch(g, r, p, x, cliques);
    return cliques;
};

function bronKerbosch(g, r, p, x, cliques) {
    if (p.length===0 && x.length===0){
        cliques.push(r);
    }

    p.forEach(function(v){
        var tempR= r.splice(0);
        tempR.push(v);
        bronKerbosch(g, tempR, p.filter(function(temp){
            return methods.neighbors(g, v).indexOf(temp)!=-1;
        }), x.filter(function(temp){
            return methods.neighbors(g, v).indexOf(temp)!=-1;
        }), cliques);

        p.splice(p.indexOf(v),1);
        x.push(v);
    });
}

methods.neighbors = function(g, v){
    var neighbors=[];
    g.forEachLinkedNode(v, function(linkedNode){
        neighbors.push(linkedNode.id);
    });
    return neighbors;
};
return methods;
}
module.exports = graphUtils();

我没有尝试，因为事实证明我不需要它，告诉我它是否有效或者我是否需要修复某些东西

于 2015-02-17T10:01:57.357 回答