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

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

对图形进行排序后，您就知道了顺序的近似值。我的建议是以简单的方式填充表格（每行 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 回答