1

ブロン-ケルボッシュ アルゴリズムまたはガーバン-ニューマン アルゴリズムの Javascript 実装を探しています。

基本的に、無向グラフで最大のクリーク/コミュニティに色を付けたいと考えています。

悲しいことに、わかりにくい 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;
}
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 に答える