时间戳

首页 > 解决方案 > AWK递归树结构

bash - AWK递归树结构

问题描述

我正在尝试解析包含分层结构中的行的文件。例如文件：

a b c
a b d
a B C
A B C

表示a包含bandB表示b包含candd表示B包含C. A包含一个不同B的包含它自己的C.

这很像文件列表。

我想以分层括号的方式格式化它，例如：

a {
    b {
        c
        d
    }
    B {
        C
    }
}
A {
    B {
        C
    }
}

我想不出一个体面的方法来做到这一点。我认为 AWK 将是我最好的选择，但想不出如何实际实施它。

语境

我的输入实际上是一个文件列表。如果需要，我当然可以用空格分隔字段，或者用/. 这些文件是无序的，并在编译时通过检查从代码库生成。我想要的输出将是一个 graphviz DOT 文件，其中每个文件都包含在它自己的子图中。

因此对于输入：

a/b/c
a/b/d
a/B/C
A/B/C

输出将是

digraph {
  subgraph cluster_a {
    label = a
    subgraph cluster_b {
        label = b
        node_1 [label=c]
        node_2 [label=d]
    }
    subgraph cluster_B {
        label = B
        node_3 [label=C]
    }
  }
  subgraph cluster_A {
      label = A
      subgraph cluster_B {
          label = B
          node_4 [label=C]
      }
  }
}

图形输出

有人知道我怎样才能完成这个处理吗？我也对其他工具持开放态度，而不仅仅是 AWK。

注意：深度不是固定的，但我可以在必要时预先计算最大深度。也不是所有的叶子都处于相同的深度。

标签： bashawkgraphvizdot

解决方案

如果深度固定在 3 个级别

gawk -F/ '
    {f[$1][$2][$3] = 1}
    END {
        n = 0
        print "digraph {"
        for (a in f) {
            print "  subgraph cluster_" a " {"
            print "    label = " a
            for (b in f[a]) {
                print "    subgraph cluster_" b " {"
                print "      label = " b
                for (c in f[a][b]) {
                    printf "      node_%d [label=%s]\n", ++n, c
                }
                print "    }"
            }
            print "  }"
        }
        print "}"
    }
' file

digraph {
  subgraph cluster_A {
    label = A
    subgraph cluster_B {
      label = B
      node_1 [label=C]
    }
  }
  subgraph cluster_a {
    label = a
    subgraph cluster_B {
      label = B
      node_2 [label=C]
    }
    subgraph cluster_b {
      label = b
      node_3 [label=c]
      node_4 [label=d]
    }
  }
}

如果深度是任意的，事情就会变得复杂。

推荐阅读