2

给定一个 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 等进行排序和过滤时,该表应该表现良好。这意味着不能将多个节点打包到表的单个单元格中 - 每个单元格只有一个节点。

4

4 回答 4

2

您需要的是拓扑排序的变体。这是一种算法,可以“排序”图顶点,就好像a---->b边的意思一样a > b。由于图是一个有向无环图,其中没有环,而且这种>关系是传递的,所以至少存在一个排序顺序。

对于您的菱形图,存在两个拓扑顺序:

a1 b1 b2 c1
a1 b2 b1 c1

b1b2项目没有联系,即使是间接的,因此,它们可以按任何顺序放置。

对图形进行排序后,您就知道了顺序的近似值。我的建议是以简单的方式填充表格(每行 1 个顶点),然后“压缩”表格。执行排序并选择你得到的序列作为输出。从上到下填充表格,为相关列分配一个顶点:

a  b  c
--------
a1 
   b2 
   b1
      c1

现在通过从上到下走动来压实桌子(然后从下到上进行类似的传递)。在每次迭代中,您都会仔细查看“当前”行(标记为=>)和“下一个”行。

  1. 如果当前节点和下一个节点中的列节点不同,则对此列不执行任何操作:

         from     ---->      to
       X  b  c            X  b  c
       --------           --------
    => X1 .  .           X1 .  .
       X2 .  .        => X2 .  .
    
  2. 如果X在下一行的列中没有顶点(表格单元格为空)并且在当前行中有 vertex X1,那么您有时应该用当前行中的顶点填充这个空单元格。但并非总是如此:您希望您的表格符合逻辑,不是吗?因此,当且仅当当前行中的所有顶点都没有 edge b--->X1、等时,才复制顶点。c--->X1

         from     --->      to
       X  b  c           X  b  c
       --------          --------
    => X1 b  c           X1 b  c
          b1 c1       => X1 b1 c1
    

(编辑:)在第一次(向前)和第二次(向后)传球之后,您将拥有这样的表格:

 first       second
a  b  c     a  b  c 
--------    --------
a1          a1 b2 c1     
a1 b2       a1 b2 c1  
a1 b1       a1 b1 c1  
a1 b1 c1    a1 b1 c1

然后,只需删除相等的行,您就完成了:

a  b  c 
--------
a1 b2 c1  
a1 b1 c1  

你应该得到一张漂亮的桌子。O(n^2)。

于 2009-11-20T20:38:25.493 回答
0

将一个节点的所有可达节点压缩到一个单元格中怎么样?例如,您的第一个 DAG 应如下所示:

a   b        c
---------------
a1  [b1,b2]  
    b1       c1
    b2       c1
于 2009-11-20T20:24:23.217 回答
0

这听起来像是在区域(a、b、c)内有车站的火车系统地图。

您可以生成一个方向上所有可能路线的表格。在这种情况下,“a1,b1,c1”似乎意味着 a1->b1,所以如果你只有 a1->c1,b1->c1,请不要这样格式化

您可以通过列出从区域 a 开始的最长路线来决定生成一个表格,每条边只使用一次,以剩余的短路线结束。或者仅在连接未使用的边或扩展路线时才允许重用边。

换句话说,进行深度优先搜索,尽量不重复使用边缘(拒绝任何不包括未使用边缘的路径,并可选择修剪端点处使用的边缘)。

于 2009-11-20T20:52:16.557 回答
0

这就是我最终做的事情:

  • 查找从没有入边的节点发出的所有路径。(对于某些图表来说可能很昂贵,但对我来说有效)
  • 遍历每条路径收集一行值
  • 压缩行

按如下方式压缩行。

  • 对于每对列 x,y
    • 构造一个 x 的每个值到它的可能值 y 的映射
    • 创建另一个映射 对于只有一个不同的 y 值的条目,将 x 的值映射到它的单个 y 值。
  • 使用这些地图填空。填写值时,请检查可以填写的相关空白。

这提供了非常紧凑的输出,似乎满足了我的所有要求。

于 2009-11-24T16:12:40.603 回答