通过整数 ID 引用图节点

Question

作为一个学习项目，我正在努力用 Chapel 实现替换一个速度较慢的 perl 程序。我已经掌握了算法，但我正在努力寻找引用 Chapel 中数据的最佳方法。我可以直接翻译，但似乎我错过了更好的方法。

现有计划的详细信息：

我有一个包含约 32000 个节点和约 210 万条边的图。状态保存在数据文件，但它运行作为将数据保存在内存中的守护进程。
每个节点都有一个数字ID（由另一个系统分配）并且有多种由字符串、整数和布尔值定义的其他属性。
边是有方向的并且有几个布尔值归于他们。
我有一个与我无法更改的守护程序交互的外部系统。它发出请求，例如 "Add node (int) with these attributes"、"find shortest path from node (int) to node (int)" 或 "add edges from node (int) to node(s) (int, int, int)"

在 Perl 中，该程序使用具有公共整数 ID 的散列来表示节点和边缘属性。我当然可以使用关联数组在 Chapel 中复制它。

有没有更好的方法将它们捆绑在一起？我一直在努力思考如何在每个项目中定义不透明的节点和边缘，但苦于如何以一种简单的方式使用整数 ID 来引用它们。

如果有人可以提供一种理想的方法来执行以下操作，它会让我获得所需的推动力。

创建两个具有由整数 ID 标识的 xx 属性的节点。
在具有 xx 属性的两者之间创建一条边
响应请求"show me the xx attribute of node (int)"

干杯，谢谢。

Answer 1

如您所料，在 Chapel 中有多种方法可以解决此问题，但我认为考虑到您的历史方法和外部系统的接口，关联域和数组绝对是一种合适的方法。具体来说，鉴于您希望通过整数 ID 引用节点，因此关联 domains/arrays 自然匹配。

对于 Chapel 新手：关联域本质上是任意值的集合，例如本例中的整数节点 ID 集合。关联数组是从关联域的索引到给定类型的元素（变量）的映射。本质上，域表示键，数组表示键值存储或散列中的值 table.

为了表示节点和边本身，我将采用使用 Chapel 记录的方法。这是我的节点记录：

record node {
  var id: int;

  var str: string,
      i: int,
      flag: bool;

  var edges: [1..0] edge;
}

可以看到，它把它的id存储为一个整数，各种类型的任意属性字段（一个字符串str，一个整数i，一个布尔值flag — 你可能可以为你的程序想出更好的名字），以及我将在一秒钟内 return 到的边数组。请注意，每个节点可能需要也可能不需要存储其 ID……也许在您拥有该节点的任何上下文中，您已经知道它的 ID，在这种情况下存储它可能是多余的。我把它存储在这里只是为了告诉你可以，而不是因为你必须这样做。

回到边缘：在你的问题中，听起来好像边缘可能有自己的整数 ID 并存储在与节点相同的池中，但在这里我采取了不同的方法：根据我的经验，给定一个节点，我通常想要从它引出的边集，所以我让每个节点存储一个其出边的数组。在这里，我使用了一个密集的一维边缘数组，它最初是空的（1..0 在 Chapel 中是一个空范围，因为 1 > 0）。如果你想给每个边缘一个唯一的 ID，你也可以使用边缘的关联数组。或者您可以从节点数据结构中完全删除边缘并将它们存储在全局范围内。如果您更喜欢不同的方法，请随时提出后续问题。

这是我代表边缘的记录：

record edge {
  var from, to: int,
      flag1, flag2: bool;
}

前两个字段（from和to）表示边缘连接的节点。与上面的节点 ID 一样，from 字段可能是多余的/不必要的，但为了完整起见，我将其包含在此处。这两个标志字段旨在表示您要与边关联的数据属性。

接下来，我将创建关联域和数组来表示节点 ID 集和节点本身：

var NodeIDs: domain(int),
    Nodes: [NodeIDs] node;

这里，NodeIDs是代表节点的整数ID的关联域（集合）。 Nodes 是一个关联数组，它将这些整数映射到 node 类型的值（我们上面定义的记录）。

现在，转到您的三个操作：

Create two nodes with xx attributes identified by integer ID.

以下声明使用 Chapel 为未定义自己的记录提供的默认记录 constructor/initializer 创建了一个名为 n1 的节点变量，其中包含一些任意属性：

var n1 = new node(id=1, "node 1", 42, flag=true);

然后我可以将它插入到节点数组中，如下所示：

Nodes[n1.id] = n1;

这个赋值有效地将 n1.id 添加到 NodeIDs 域并将 n1 复制到 Nodes 中相应的数组元素中。这是创建第二个匿名节点并将其添加到集合中的赋值：

Nodes[2] = new node(id=2, "node 2", i=133);

请注意，在上面的代码中，我假设您要明确地为每个节点选择 ID（例如，也许您的数据文件会建立节点 ID？）。另一种方法（此处未显示）可能是在使用全局计数器创建节点时自动确定它们（如果您并行创建它们，则可能是原子计数器）。

填充我们的节点后，我们可以串行或并行地迭代它们（这里我是并行进行的；将 forall 替换为 for 将使它们串行）：

writeln("Printing all node IDs (in an arbitrary order):");
forall nid in NodeIDs do
  writeln("I have a node with ID ", nid);

writeln("Printing all nodes (in an arbitrary order):");
forall n in Nodes do
  writeln(n);

这些循环打印 ID 和节点的顺序是任意的，原因有二：(1) 它们是并行循环； (2) 关联域和数组以任意顺序存储它们的元素。

Create an edge between the two with xx attribues

因为我将边与节点相关联，所以我采用了在 node 类型上创建一个方法来向其添加边的方法：

proc node.addEdge(to: int, flag1: bool, flag2: bool) {
  edges.push_back(new edge(id, to, flag1, flag2));
}

此过程将目标节点 ID 和属性作为其参数，使用该信息创建边（并提供原始节点的 ID 作为 from 字段），并使用 push_back() 矩形数组上的方法将其添加到边列表中。

然后我调用此例程三次为节点 2 创建一些边（包括冗余边和自边，因为到目前为止我只有两个节点）：

Nodes[2].addEdge(n1.id, true, false);
Nodes[2].addEdge(n1.id, false, true);
Nodes[2].addEdge(2, false, false);

此时，我可以按如下方式遍历给定节点的所有边：

writeln("Printing all edges for node 2: (in an arbitrary order):");
forall e in Nodes[2].edges do
  writeln(e);

这里，任意打印顺序只是由于使用了并行循环。如果我使用串行 for 循环，由于使用一维数组来表示它们，我将按照添加它们的顺序遍历边缘。

Respond to request "show me the xx attribute of node (int)"

你现在可能已经明白了，但我可以通过索引到 Nodes 数组来获取节点的任意属性。例如，表达式：

...Nodes[2].str...

会给我节点 2 的字符串属性。这是我编写的一个小帮助例程，用于获取（并打印）一些不同的属性：

proc showAttributes(id: int) {
  if (!NodeIDs.member(id)) {
    writeln("No such node ID: ", id);
    return;
  }

  writeln("Printing the complete attributes for node ", id);
  writeln(Nodes[id]);

  writeln("Printing its string field only:");
  writeln(Nodes[id].str);
}

下面是对它的一些调用：

showAttributes(n1.id);
showAttributes(2);
showAttributes(3);

I am working to replace a somewhat slow program in perl with a Chapel implementation

鉴于速度是您查看 Chapel 的原因之一，一旦您的程序正确，请使用 --fast 标志重新编译它以快速运行获得它。

通过整数 ID 引用图节点

Referencing graph nodes by integer ID

graph

chapel