图形生成器

译者：flink.sojb.cn

Gelly提供了一系列可扩展的图形生成器。每台发电机都是

  • 可并行化，以创建大型数据集
  • 无标度，无论并行性如何都生成相同的图形
  • 节俭，使用尽可能少的算子

使用构建器模式配置图生成器。可以通过调用显式设置生成器 算子的并行性setParallelism(parallelism)。降低并行度将Reduce内存和网络缓冲区的分配。

必须首先调用特定于图形的配置，然后调用所有生成器通用的配置，最后调用generate()。以下示例配置具有两个维度的网格图，配置并行度并生成图形。

  1. ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();
  3. boolean wrapEndpoints = false;
  5. int parallelism = 4;
  7. Graph<LongValue, NullValue, NullValue> graph = new GridGraph(env)
  8.     .addDimension(2, wrapEndpoints)
  9.     .addDimension(4, wrapEndpoints)
  10.     .setParallelism(parallelism)
  11.     .generate();
  1. import org.apache.flink.api.scala._
  2. import org.apache.flink.graph.generator.GridGraph
  4. val env: ExecutionEnvironment = ExecutionEnvironment.getExecutionEnvironment
  6. wrapEndpoints = false
  8. val parallelism = 4
  10. val graph = new GridGraph(env.getJavaEnv).addDimension(2, wrapEndpoints).addDimension(4, wrapEndpoints).setParallelism(parallelism).generate()

循环图

一个循环图是一个 有向图具有偏移的一个或多个连续的范围进行配置。边连接整数顶点ID，其差值等于配置的偏移量。没有偏移的循环图是空图，具有最大范围的图是 完整图。

  1. ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();
  3. long vertexCount = 5;
  5. Graph<LongValue, NullValue, NullValue> graph = new CirculantGraph(env, vertexCount)
  6.     .addRange(1, 2)
  7.     .generate();
  1. import org.apache.flink.api.scala._
  2. import org.apache.flink.graph.generator.CirculantGraph
  4. val env: ExecutionEnvironment = ExecutionEnvironment.getExecutionEnvironment
  6. val vertexCount = 5
  8. val graph = new CirculantGraph(env.getJavaEnv, vertexCount).addRange(1, 2).generate()

完整的图表

连接每个不同顶点对的无向图。

  1. ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();
  3. long vertexCount = 5;
  5. Graph<LongValue, NullValue, NullValue> graph = new CompleteGraph(env, vertexCount)
  6.     .generate();
  1. import org.apache.flink.api.scala._
  2. import org.apache.flink.graph.generator.CompleteGraph
  4. val env: ExecutionEnvironment = ExecutionEnvironment.getExecutionEnvironment
  6. val vertexCount = 5
  8. val graph = new CompleteGraph(env.getJavaEnv, vertexCount).generate()
0 1 2 3 4

循环图

一个无向图，其中边集通过将每个顶点连接到链式循环中的两个相邻顶点而形成单个循环。

  1. ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();
  3. long vertexCount = 5;
  5. Graph<LongValue, NullValue, NullValue> graph = new CycleGraph(env, vertexCount)
  6.     .generate();
  1. import org.apache.flink.api.scala._
  2. import org.apache.flink.graph.generator.CycleGraph
  4. val env: ExecutionEnvironment = ExecutionEnvironment.getExecutionEnvironment
  6. val vertexCount = 5
  8. val graph = new CycleGraph(env.getJavaEnv, vertexCount).generate()
0 1 2 3 4

回声图

一个回波图形是一个 循环图与n由在中心的偏移量的单一范围的宽度所定义的顶点n/2。顶点连接到’far’顶点，顶点连接到’near’顶点，连接到’far’顶点，….

  1. ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();
  3. long vertexCount = 5;
  4. long vertexDegree = 2;
  6. Graph<LongValue, NullValue, NullValue> graph = new EchoGraph(env, vertexCount, vertexDegree)
  7.     .generate();
  1. import org.apache.flink.api.scala._
  2. import org.apache.flink.graph.generator.EchoGraph
  4. val env: ExecutionEnvironment = ExecutionEnvironment.getExecutionEnvironment
  6. val vertexCount = 5
  7. val vertexDegree = 2
  9. val graph = new EchoGraph(env.getJavaEnv, vertexCount, vertexDegree).generate()

空图

不包含边的图。

  1. ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();
  3. long vertexCount = 5;
  5. Graph<LongValue, NullValue, NullValue> graph = new EmptyGraph(env, vertexCount)
  6.     .generate();
  1. import org.apache.flink.api.scala._
  2. import org.apache.flink.graph.generator.EmptyGraph
  4. val env: ExecutionEnvironment = ExecutionEnvironment.getExecutionEnvironment
  6. val vertexCount = 5
  8. val graph = new EmptyGraph(env.getJavaEnv, vertexCount).generate()
0 1 2 3 4

网格图

一个无向图，用于连接一个或多个维度中常规平铺中的顶点。每个维度都单独配置。当尺寸大小至少为3时，可选择通过设置连接端点wrapEndpoints。更改下面的示例addDimension(4, true)将连接0到3和4到7。

  1. ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();
  3. boolean wrapEndpoints = false;
  5. Graph<LongValue, NullValue, NullValue> graph = new GridGraph(env)
  6.     .addDimension(2, wrapEndpoints)
  7.     .addDimension(4, wrapEndpoints)
  8.     .generate();
  1. import org.apache.flink.api.scala._
  2. import org.apache.flink.graph.generator.GridGraph
  4. val env: ExecutionEnvironment = ExecutionEnvironment.getExecutionEnvironment
  6. val wrapEndpoints = false
  8. val graph = new GridGraph(env.getJavaEnv).addDimension(2, wrapEndpoints).addDimension(4, wrapEndpoints).generate()
0 1 2 3 4 5 6 7

超立方体图

一个无向图，其中边形成一个n三维超立方体。超立方体中的每个顶点连接到每个维度中的另一个顶点。

  1. ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();
  3. long dimensions = 3;
  5. Graph<LongValue, NullValue, NullValue> graph = new HypercubeGraph(env, dimensions)
  6.     .generate();
  1. import org.apache.flink.api.scala._
  2. import org.apache.flink.graph.generator.HypercubeGraph
  4. val env: ExecutionEnvironment = ExecutionEnvironment.getExecutionEnvironment
  6. val dimensions = 3
  8. val graph = new HypercubeGraph(env.getJavaEnv, dimensions).generate()
0 1 2 3 4 5 6 7

路径图

一个无向图，其中边集形成一个单独的路径，通过连接两个endpoint顶点与度1和所有中点顶点与度 2。可以通过从循环图中移除单个边来形成路径图。

  1. ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();
  3. long vertexCount = 5
  5. Graph<LongValue, NullValue, NullValue> graph = new PathGraph(env, vertexCount)
  6.     .generate();
  1. import org.apache.flink.api.scala._
  2. import org.apache.flink.graph.generator.PathGraph
  4. val env: ExecutionEnvironment = ExecutionEnvironment.getExecutionEnvironment
  6. val vertexCount = 5
  8. val graph = new PathGraph(env.getJavaEnv, vertexCount).generate()
0 1 2 3 4

RMat图

使用递归矩阵（R-Mat）模型生成的有向幂律多图 。

RMat是一个随机生成器，配置有实现RandomGenerableFactory接口的随机源 。提供的实现是JDKRandomGeneratorFactory 和MersenneTwisterFactory。这些生成随机值的初始序列，然后将其用作生成边缘的种子。

  1. ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();
  3. RandomGenerableFactory<JDKRandomGenerator> rnd = new JDKRandomGeneratorFactory();
  5. int vertexCount = 1 << scale;
  6. int edgeCount = edgeFactor * vertexCount;
  8. Graph<LongValue, NullValue, NullValue> graph = new RMatGraph<>(env, rnd, vertexCount, edgeCount)
  9.     .generate();
  1. import org.apache.flink.api.scala._
  2. import org.apache.flink.graph.generator.RMatGraph
  4. val env = ExecutionEnvironment.getExecutionEnvironment
  6. val vertexCount = 1 << scale
  7. val edgeCount = edgeFactor * vertexCount
  9. val graph = new RMatGraph(env.getJavaEnv, rnd, vertexCount, edgeCount).generate()

可以覆盖默认的RMat常量，如以下示例所示。常量定义了每个生成的边的源标记和目标标签的位的相互依赖性。可以启用RMat噪声，并在生成每个边缘时逐渐扰乱常量。

RMat生成器可以配置为通过删除自循环和重复边来生成简单的图。对称化是通过“剪切和翻转”抛弃对角线上方的半矩阵或完全“翻转”保存并镜像所有边缘来进行的。

  1. ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();
  3. RandomGenerableFactory<JDKRandomGenerator> rnd = new JDKRandomGeneratorFactory();
  5. int vertexCount = 1 << scale;
  6. int edgeCount = edgeFactor * vertexCount;
  8. boolean clipAndFlip = false;
  10. Graph<LongValue, NullValue, NullValue> graph = new RMatGraph<>(env, rnd, vertexCount, edgeCount)
  11.     .setConstants(0.57f, 0.19f, 0.19f)
  12.     .setNoise(true, 0.10f)
  13.     .generate();
  1. import org.apache.flink.api.scala._
  2. import org.apache.flink.graph.generator.RMatGraph
  4. val env = ExecutionEnvironment.getExecutionEnvironment
  6. val vertexCount = 1 << scale
  7. val edgeCount = edgeFactor * vertexCount
  9. clipAndFlip = false
  11. val graph = new RMatGraph(env.getJavaEnv, rnd, vertexCount, edgeCount).setConstants(0.57f, 0.19f, 0.19f).setNoise(true, 0.10f).generate()

Singleton边缘图

包含孤立的双路径的无向图，其中每个顶点都具有度 1。

  1. ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();
  3. long vertexPairCount = 4
  5. // note: configured with the number of vertex pairs
  6. Graph<LongValue, NullValue, NullValue> graph = new SingletonEdgeGraph(env, vertexPairCount)
  7.     .generate();
  1. import org.apache.flink.api.scala._
  2. import org.apache.flink.graph.generator.SingletonEdgeGraph
  4. val env: ExecutionEnvironment = ExecutionEnvironment.getExecutionEnvironment
  6. val vertexPairCount = 4
  8. // note: configured with the number of vertex pairs val graph = new SingletonEdgeGraph(env.getJavaEnv, vertexPairCount).generate()
0 1 2 3 4 5 6 7

星图

一个无向图，包含连接到所有其他叶顶点的单个中心顶点。

  1. ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();
  3. long vertexCount = 6;
  5. Graph<LongValue, NullValue, NullValue> graph = new StarGraph(env, vertexCount)
  6.     .generate();
  1. import org.apache.flink.api.scala._
  2. import org.apache.flink.graph.generator.StarGraph
  4. val env: ExecutionEnvironment = ExecutionEnvironment.getExecutionEnvironment
  6. val vertexCount = 6
  8. val graph = new StarGraph(env.getJavaEnv, vertexCount).generate()
0 1 2 3 4 5