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算法（圖中的最大派系/社區）

回答

相關問題