Javascript - Bron-Kerbosch，Girvan-Newman算法（图中的最大派系/社区）

我在寻找一个关于Bron-Kerbosch algorithm或Girvan-Newman algorithm的Javascript实现。Javascript - Bron-Kerbosch，Girvan-Newman算法（图中的最大派系/社区）

基本上我想为无向图中的最大派系/社区着色。

不幸的是，我发现只有神秘的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; 
}

来源

2013-04-27 frik

你有什么试图实现它们？算法并不复杂，是吗？ – Bergi 2013-04-27 14:09:00

我下载了各种源代码实现，尽管它们都使用了一些语言原生优化技术或JavaScript中不存在的语言特性。 1983年的C代码使用了大量的位移，Java和Python源代码严重依赖于vector/dictionary和其他本地对象类型，C++依赖于Boost/STL。我也不需要很平行的版本。维基百科psydo-code看起来很简单（尽管只是一见钟情）。我希望在没有任何优化的情况下以Javascript或C语言的基本实现。 – frik 2013-04-27 18:35:21

您可以将矢量和对象用于词典。来自WP的伪代码应该可以转移到JS，使用数组进行设置（查看[Underscore的源代码]（http://documentcloud.github.io/underscore/docs/underscore.html）了解set方法的一些实现）。你试过了吗？ – Bergi 2013-04-27 18:39:44

我做了一个模块，做勒布朗 - 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-17 10:01:57 user1918845

Javascript - Bron-Kerbosch，Girvan-Newman算法（图中的最大派系/社区）

回答

相关问题