MaxCompute用户指南：图模型：图模型概述

MaxCompute Graph 是一套面向迭代的图计算处理框架。图计算作业使用图进行建模，图由点（Vertex）和边（Edge）组成，点和边包含权值（Value）。
MaxCompute Graph 支持以下图编辑操作：

• 
  修改点或边的权值。
• 
  增加/删除点。
• 
  增加/删除边。

注意：
编辑点和边时，点与边的关系需要您来维护。

通过迭代对图进行编辑、演化，最终求解出结果，典型应用有： PageRank， 单源最短距离算法 ， K-均值聚类算法 等。您可以使用 MaxCompute Graph 提供的接口 Java SDK 编写图计算程序。

Graph 数据结构


MaxCompute Graph 能够处理的图必须是是一个由点（Vertex）和边（Edge）组成的有向图。由于 MaxCompute 仅提供二维表的存储结构，因此需要您自行将图数据分解为二维表格式存储在 MaxCompute 中。
在进行图计算分析时，使用自定义的 GraphLoader 将二维表数据转换为 MaxCompute Graph 引擎中的点和边。至于如何将图数据分解为二维表格式，您可以根据自身的业务场景做决定。
点的结构可以简单表示为 < ID, Value, Halted, Edges>，分别表示点标识符（ID），权值（Value），状态（Halted,表示是否要停止迭代），出边集合（Edges，以该点为起始点的所有边列表）。边的结构可以简单表示为 <DestVertexID，Value>，分别表示目标点（DestVertexID）和权值（Value）。

例如，上图由下面的点组成：

Vertex	<ID, Value, Halted, Edges>
v0	<0, 0, false, [ <1, 5 >, <2, 10 > ] >
v1	<1, 5, false, [ <2, 3>, <3, 2>, <5, 9>]>
v2	<2, 8, false, [<1, 2>, <5, 1 >]>
v3	<3, Long.MAX_VALUE, false, [<0, 7>, <5, 6>]>
v5	<5, Long.MAX_VALUE, false, [<3, 4 > ]>

Graph 程序逻辑



图加载


图加载：框架调用您自定义的 GraphLoader，将输入表的记录解析为点或边。
分布式化：框架调用您自定义的 Partitioner 对点进行分片（默认分片逻辑：点 ID 哈希值，然后对 Worker 数取模），分配到相应的Worker。

例如，上图假设 Worker 数是 2，那么 v0，v2 会被分配到 Worker0，因为 ID 对 2 取模结果为 0，而 v1，v3，v5 将被分配到 Worker1，ID 对 2 取模结果为 1。

迭代计算：

• 
  一次迭代为一个 超步（SuperStep），遍历所有非结束状态（Halted 值为 false）的点或者收到消息的点（处于结束状态的点收到信息会被自动唤醒），并调用其 compute(ComputeContext context, Iterable messages) 方法。
• 
  在您实现的 compute(ComputeContext context, Iterable messages) 方法中：
  处理上一个超步发给当前点的消息（Messages）。
• 
  根据需要对图进行编辑：
  修改点/边的取值。
• 
  发送消息给某些点。
• 
  增加/删除点或边。

通过 Aggregator 汇总信息到全局信息。
设置当前点状态，结束或非结束状态。
迭代进行过程中，框架会将消息以异步的方式发送到对应 Worker，并在下一个超步进行处理，您无需关心。

迭代终止


满足以下任意一条，迭代即终止。

• 
  所有点处于结束状态（Halted 值为 true）且没有新消息产生。
• 
  达到最大迭代次数。
• 
  某个 Aggregator 的 terminate 方法返回 true。

伪代码描述如下所示：

1. // 1. load
2. for each record in input_table {
3.   GraphLoader.load();
4. }
6. // 2. setup
7. WorkerComputer.setup();
8. for each aggr in aggregators {
9.   aggr.createStartupValue();
10. }
11. for each v in vertices {
12.   v.setup();
13. }
15. // 3. superstep
16. for (step = 0; step < max; step ++) {
17.   for each aggr in aggregators {
18.     aggr.createInitialValue();
19.   }
20.   for each v in vertices {
21.      v.compute();
22.    }
23. }
25. // 4. cleanup
26. for each v in vertices {
27.   v.cleanup();
28. }
29. WorkerComputer.cleanup();