algorithm - 修剪杂散节点的大图

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 格式，但我没有在该套件中看到任何与手头任务相关的工具。

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

Answer 1

工具gvpr这是 graphviz tools 的一部分允许将规则应用于图形并输出修改后的图形。

来自描述:

It copies input graphs to its output, possibly transforming their structure and attributes, creating new graphs, ...

看起来您想删除所有入度为 0 且仅具有出度为 0 的链接节点(后继节点)的节点。

这是我的 gvpr 脚本 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. 遍历所有边一次并填充两个列表:

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

   那么什么被添加到哪个列表？

   • 任意两个相互连接的节点，其中尾节点没有任何入边，头节点没有任何出边，形成一个只有 2 个节点的链，因此是候选被删除；也就是说，除非相同的节点是长度超过 2 个节点的其他链的一部分:
   • 尾节点没有任何入边，但连接到本身有出边的头节点，是一个keeper；和
   • 没有任何出边的头节点，但连接到本身有入边的尾节点，也是一个keeper。
2. 删除所有candidates 不在keepers

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

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

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

使用示例图的输出是:

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

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

---

另见 Graphviz/Dot - how to mark all leaves in a tree with a distinctive color?一个更简单的图形转换示例。