Javascript - Bron-Kerbosch、Girvan-Newman 算法(图中的最大集团/社区)

Question

我正在寻找 Bron-Kerbosch algorithm 的 Javascript 实现或 Girvan-Newman algorithm .

基本上，我想在无向图中为最大集团/社区着色。

遗憾的是，我只找到了神秘的 Python 和臃肿的 Java 和 C++ 库代码。我需要纯 Javascript 代码(最好不要臃肿的 JS 库或 JQuery 等依赖项)。

// 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;
}

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

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