Javascript - Bron-Kerbosch, Girvan-Newman 알고리즘 (그래프의 최대 파벌/커뮤니티)

Bron-Kerbosch algorithm 또는 Girvan-Newman algorithm의 자바 스크립트 구현을 찾고 있습니다.Javascript - Bron-Kerbosch, Girvan-Newman 알고리즘 (그래프의 최대 파벌/커뮤니티)

기본적으로 나는 방향없는 그래프에서 최대 파벌/커뮤니티를 색칠하고 싶습니다.

슬프게도, 나는 단지 비밀스런 파이썬과 비 대한 자바 & C++ 라이브러리 코드만을 발견했습니다. 나는 평범한 자바 스크립트 코드 (바람직하지 않은 비 대한 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

자바 스크립트에없는 언어 기본 최적화 기술이나 언어 기능을 사용했지만 다양한 소스 코드 구현을 다운로드했습니다. 1983 년의 C 코드는 많은 비트 이동을 사용했으며, Java 및 Python 소스는 벡터/사전 및 기타 기본 객체 유형에 크게 의존했으며 C++은 Boost/STL에 의존했습니다. 또한 나는 상당히 평행 한 버전이 필요하지 않습니다. 위키 피 디아 psydo 코드는 (첫 번째 시야에서만) 쉽게 보입니다. Javascript 또는 C 언어의 기본 구현을 최적화하지 않아도됩니다. – frik

사전의 벡터 및 객체에 배열을 사용할 수 있습니다. WP에서 의사 코드는 집합에 대한 배열을 사용하여 JS로 전송할 수 있어야합니다 (set 메서드의 일부 구현에 대해서는 [밑줄의 소스] (http://documentcloud.github.io/underscore/docs/underscore.html) 참조). 너 해봤 어? – Bergi

내가 브롱 - 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 알고리즘 (그래프의 최대 파벌/커뮤니티)

답변

관련 문제