给定一个 DAG,其中每个节点都属于一个类别,如何将这个图转换为一个表,每个类别都有一个列?转换不必是可逆的,但应该保留有关图结构的有用信息;并且应该是一种“自然”的转换,从某种意义上说,查看图表和表格的人不应该对任何行感到惊讶。它也应该是紧凑的,即只有几行。
例如,给定一个节点 a1,b1,b2,c1 与边 a1->b1, a1->b2, b1->c1, b2->c1 的图(即菱形图),我希望看到以下内容桌子:
a b c
--------
a1 b1 c1
a1 b2 c1
我已经对这个问题想了很多,但是我很难想出一种算法来在某些图表上给出直观的结果。考虑具有边 a1->c1, b1->c1 的图 a1,b1,c1。我想要生成这张表的算法:
a b c
--------
a1 b1 c1
但也许它应该产生这个:
a b c
--------
a1 c1
a1 b1
我正在寻找对这个问题的创造性想法和见解。如果您认为这会有所帮助,请随意改变以简化或限制问题。
头脑风暴!
编辑:
尽管行的顺序无关紧要,但转换应始终生成相同的行集。
在使用 Excel 等进行排序和过滤时,该表应该表现良好。这意味着不能将多个节点打包到表的单个单元格中 - 每个单元格只有一个节点。