借助ArangoDB，带你玩转Google图算法引擎Pregel

1顶
0踩

2014-11-25 14:37 by 正式编辑 cao345657340 评论(0) 有5782人浏览

算法 javascript google

声明：ITeye资讯文章的版权属于ITeye网站所有，严禁任何网站转载本文，否则必将追究法律责任！

【编者按】ArangoDB团队研究出一种算法，能够在一个图中识别出已连接的子图，文中以国家为例；在ArangoDB中引入Pregel框架，通过Worker算法、合成算法、pregelRunner模块来执行不同的实现方式。开发者也可以自行编写算法，编程世界魅力无穷！

译文如下：

Pregel作为Google推出的一种面向图算法的分布式编程框架，主要用于处理大规模的图算法计算。比如，图遍历（BFS）、最短路径（SSSP）、PageRank计算等。

检测“已连接节点”的算法

为了解决已连接节点的问题，ArangoDB团队研究出一种算法，能够在一个图中识别出已连接的子图。这里以国家为例子，下图包含10个国家，互相之间的关系定义为边界接壤(hasBorderWith)，其形成的4种已连接节点组分别为：

引用

要导入该图，请点击这里进行下载，然后打开ArangoShell并执行如下语句：

arangosh [_system]> require("internal").load(PATH_TO_THE_FILE);

Worker算法

Worker算法执行于图中每个顶点之上，每个顶点有一个相关的消息游标和一个global对象，里面含有步长信息和用户定义的Global数据。该算法定义如下：

var connectedSetsAlgorithm = function (vertex, message, global) {

为了检测所有的节点组，这里使用了一种非常直接的方法：

每个节点组有一个字母标识符，存有其顶点最后的_key属性信息。所以，第0步的时候，每个顶点存储的是其自身的key信息以及初始邻近接壤节点信息。要访问源顶点需要使用_get(“someAttribute”)方法：

switch(global.step) {  
 case 0:  
   result = {  
     value: vertex._get("_key"),  
     backwards: []  
   }  
   sendSender = true;  
   break;  
}

一个顶点只能访问其外部边界，因此在第1步的时候要记得把它所有接收到的消息放入数组中，以便进行向后通信，同时要根据传入的消息来更新节点组。

case 1:  
  result = vertex._getResult();  
  while (message.hasNext()) {  
    next = message.next();  
    if (result.value < next.data) {  
      result.value = next.data;  
    }  
    result.backwards.push(next.sender);  
  }  
  break;

所以前两步的操作开启了向前和向后通信，接着执行算法直到每个顶贴都接收到其顶点组标识信息。因此，当接收到邻近标识符信息后，每个顶点需要更新顶点组标识信息：

default:  
  result = vertex._getResult();  
  while (message.hasNext()) {  
    next = message.next();  
    if (result.value < next.data) {  
      result.value = next.data;  
      changed = true;  
    }  
  }

当一个顶点不再接收到新的消息或新的组标识时，要使它暂时失效。仅当再从邻近顶点接收新消息的时候进行激活：

if (global.step > 1 && ! changed) {  
 vertex._deactivate();  
 return;  
}

如果接收到新的组标识时要把结果进行存储：

vertex._setResult(result);

接着要通知邻近顶点，包括向前与向后：

while (vertex._outEdges.hasNext()) {  
  edge = vertex._outEdges.next();  
  message.sendTo(edge._getTarget(), result.value, sendSender);  
}

for (var i = 0; i < result.backwards.length; ++i) {  
  message.sendTo(result.backwards[i], result.value, sendSender);  
}

然后失效该顶点直到接收到新的消息：

vertex._deactivate();

合成算法

为了减少冗余的消息使得工作者算法更加高效，ArangoDB团队引入了消息合成算法。比方说在该示例中，德国节点可能会收到来自奥地利和瑞士的消息；由于按字母排序，奥地利的消息可以忽略，从而减少不必要的消息接收。在Pregel中的消息合成器可定义为：

function(next, old) {}

合成器会筛选冗余消息，然后发送有效的标识信息：

<p>varcombiner=function(next,old){</p><p>if(old==null||next<old){</p><p>returnnext;</p><p>}</p><p>returnold;</p><p>}</p>

引入该算法后，德国节点虽然有两个接壤点，但是只会收到一个消息。

pregelRunner模块

首先创建Runner实例：

arangosh [_system]> var pregelRunner = require("org/arangodb/pregelRunner");  
arangosh [_system]> var runner = new pregelRunner.Runner();

Pregel算法的具体实现请点击这里进行下载。在Shell中载入该文件，使Runner可以实现相关函数：

arangosh [_system]> require("internal").load(PATH_TO_THE_FILE);  
arangosh [_system]> runner.setWorker(worker);  
{   
  "worker" : function (vertex, message, global) { ... }   
}  
arangosh [_system]> runner.setCombiner(combiner);  
{   
  "worker" : function (vertex, message, global) { ... },   
  "combiner" : function (next, old) { ... }   
}

然后在图中启动Pregel：

arangosh [_system]> runner.start("CountryGraph");  
16752523162

启动后会接收到唯一的执行码，可以使用runner来查阅当前运行状态：

arangosh [_system]> runner.getStatus();  
{   
 "step" : 5,   
 "state" : "finished"   
}

执行完毕后可以得到图的结果名：

arangosh [_system]> runner.getResult();  
{   
  "graphName" : "P_16752523162_RESULT_CountryGraph",   
  "state" : "finished"   
}

要检查该结果是否符合要求，可以载入全部顶点进行校对：

arangosh [_system]> var graph_module = require("org/arangodb/general-graph");  
var resultGraph = graph_module._graph("P_16752523162_RESULT_CountryGraph");  
arangosh [_system]> resultGraph._vertices().toArray().forEach(function(vertex) {require("internal").print(vertex._key + " is in component " + vertex.result.value); });  
Switzerland is in component Switzerland  
Germany is in component Switzerland  
Austria is in component Switzerland  
Algeria is in component Tunisia  
Tunisia is in component Tunisia  
Morocco is in component Tunisia  
Brazil is in component Uruguay  
Argentina is in component Uruguay  
Uruguay is in component Uruguay  
Australia is in component Australia

结果是正确的，算法能正确识别出4个子图(瑞士，突尼斯，乌拉圭，澳大利亚)。最后要做好收尾工作：

arangosh [_system]> runner.dropResult();  
{   
  "error" : false,   
  "code" : 200   
}

arangosh [_system]> var resultGraph = graph_module._graph("P_16752523162_RESULT_CountryGraph");  
JavaScript exception in file './js/common/modules/org/arangodb/general-graph.js' at 2349,11: [ArangoError 1924: graph not found]  
!    throw err;  
!          ^<br>

写在最后：

ArangoDB仍在进一步完善pregelRunner以满足更大规模图处理的需求。很多受时间和内存限制的大型图问题在Pregel系统中都可逐步解决，例如：最短路径，图着色，最小生成树等。

原文来自：Arangodb