我正在寻找 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;
}
最佳答案
我制作了一个模块,它执行第一个版本的 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();
我没有尝试过,因为事实证明我不需要它,请告诉我它是否有效,或者我是否需要修复某些东西
关于Javascript - Bron-Kerbosch、Girvan-Newman 算法(图中的最大集团/社区),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16252680/