修剪大图的杂散节点

Question

我有一个由大约 35,000 个以纯文本表示的节点组成的图表：

node1 -> node35000
node29420 -> node35000
node2334 -> node4116
...

我想通过删除不属于至少三个长的链的节点来修剪它。因此，如果我只有

1 -> 2;
2 -> 3;
3 -> 4;
0 -> 4;

1、2、3 和 4（因为 1 -> 2 -> 3 -> 4 是四个节点长）但丢弃 0，即删除 0 -> 4..

有什么好方法可以做到这一点吗？我尝试了 Perl 和 shell 函数的组合，但我认为我需要更好的方法。除非已经有工具可以做到这一点？数据采用 graphviz 格式，但我没有在该套件中看到任何与手头任务相关的工具。

哦，如果有一种简单的方法来做这样的事情，我愿意接受建议——它不需要完全是我建议的任务。我只是在寻找一种方法来消除大团块周围的大部分噪音（这种团块很少见，而且大多只是一些相交的链）。

Answer 1

该工具 gvpr 是 graphviz 工具 允许将规则应用于图形并输出修改后的图形。

从描述来看：

它将输入图复制到其输出，可能会改变它们的
结构和属性，创建新图，...

看起来您想要删除所有入度为 0 的节点，并且仅具有出度为 0 的链接节点（后继节点）。

这是我的 gvpr script nostraynodes.gv ：

BEGIN {node_t n; int candidates[]; int keepers[];}
E{
  if (tail.indegree == 0 && head.outdegree == 0)
  {
    candidates[tail] = 1;
    candidates[head] = 1;
  }
  else if (tail.indegree == 0)
  {
    keepers[tail] = 1;
  }
  else if (head.outdegree == 0)
  {
    keepers[head] = 1;
  }
}

END_G {
  for (candidates[n]){
    if (n in keepers == 0)
    {
       delete(NULL, n);
    }
  }
}

脚本的作用如下：

1. 循环所有边一次并填充两个列表：

   • 候选 - 可能需要删除的节点列表，以及
   • keepers - 可能最终成为候选者但不应被删除的节点列表。

   那么什么会添加到哪个列表中？

   • 任意两个相互连接的节点，其中尾节点没有任何传入边并且头节点没有任何传出边，形成仅包含 2 个节点的链，因此是候选节点被删除；也就是说，除非相同的节点是长度超过 2 个节点的其他链的一部分：
   • 没有任何传入边但连接到本身具有传出边的头节点的尾节点是一个守护者；和
   • 没有任何传出边但连接到本身具有传入边的尾节点的头节点也是一个守护者。
2. 删除所有不在keepers中的候选人

此解决方案不是通用，仅适用于问题中所述的问题，即至少仅保留链3 个节点长。它也不会删除短循环（两个节点相互连接）。

您可以使用以下行调用它：

gvpr -c -f .\nostraynodes.gv .\graph.dot

使用示例图的输出是：

digraph g {
    1 -> 2;
    2 -> 3;
    3 -> 4;
}

请注意，这是我的第一个 gvpr 脚本 - 可能有更好的方法来编写此脚本，但我不确定如何编写这可以处理 35000 个节点，尽管我相信这不是什么大问题。

---

另请参阅Graphviz/Dot - 如何用独特的颜色标记树中的所有叶子？ 一个更简单的图形转换示例。

Answer 2

Gephi 是一个优秀的开源 GUI 工具，用于可视化和操作图形，您可能会找到某种在那里过滤这类事情......也许度数过滤器可以做到：它会删除只有一条边的节点。您还可以过滤入度、出度，可以计算 PageRank 等。它还有一些非常好的尺寸/标签/颜色选项，并且很容易放大/缩小。

Answer 3

假设任何给定节点可以有任意多个前驱或后继，则节点的入度和出度与解决问题无关。

以下是在路径长度 3 准则下针对 N 个节点和 E 个边的所有图的简单 O(N+E) 算法。该算法可以很容易地用 Perl 或 C 实现。该方法基于定义和断言：将“生成节点”定义为具有父节点和子节点（前驱节点和后继节点）的任何节点。将保留的每个节点都是已创建节点，或者是已创建节点的父节点或子节点。

1. 将状态数组 S[Nmax] 初始化为全零。 Nmax 是最大节点数。如果一开始不知道Nmax，则读取所有数据并找出它。

2. 读入给定的边列表。每个输入项指定从节点 p 到节点 q 的有向边 (p, q)。对于读入的每个 (p, q) 项：将 S[p] 设置为 S[p] | 1 表示 p 有一个孩子，并将 S[q] 设置为 S[q] | 2 表示 q 有一个父对象。 （在此步骤之后，每个生成的节点 n 都有 S[n] == 3。）

3. 再次读取边列表。对于读入的每个 (p, q) 项： If (S[p]==3) or (S[q] == 3) 输出边 (p,q)。

要将此方法扩展到除 3 之外的路径长度 K，请将边列表保留在内存中，使用父链和子链的长度维护 Sp[] 和 Sc[]，并执行 K/2 次额外传递。也许可以在 O(N+K*E) 时间内完成。
该问题没有指定图是否是 DAG（有向无环图），但给出的示例是 DAG。对于K＞3，这可能会产生影响。

更新 1 这是 K>3 算法的更精确的表述，其中 H[i].p 和 H[i].q 是边 #i 的端点，pc[j], cc[ j] 是关于节点 j 的前驱链和后继链的长度。另外，令 E = 边数； N = 节点数； K = 保持边缘所需的最小链条长度。

1. 将 E 边沿数据条目读入 H[ ] 数组。将所有 pc[j]、cc[j] 条目设置为 0。

2. 对于 i = 1 到 E，设置 cc[H[i].p]=1 和 pc[H[i].q]=1。

3. 对于 j = 1 到 K+1，{ 对于 i = 1 到 E，{ 令 p=H[i].p 且 q=H[i].q。设置 cc[p] = max(cc[p], 1+cc[q]) 和 pc[q] = max(pc[q], 1+pc[p])。 } }

4. 对于 i = 1 到 E，{ 令 p=H[i].p 且 q=H[i].q。如果 pc[p]+cc[p]+1 >= K 且 pc[q]+cc[q]+1 >= K，则输出边缘 (p,q)。}

如果图不是，则此方法可能会出错一个 DAG 并包含短循环路径。例如，如果图边包括 (1,2) 和 (2,1)，并且没有其他节点链接到节点 1 或 2，则不应输出这些边；但我们最终得到这些节点的 cc[] 和 pc[] 的 K+2，因此它们无论如何都会得到输出。