创建DAG表格表示的算法？

给定一个DAG，其中每个节点属于一个类别，该图表如何转换为每个类别都有列的表格？这种转换不一定是可逆的，但应该保留关于图的结构的有用信息;并且应该是一种“自然”转换，因为看着图表和表格的人不应该对任何行感到惊讶。它也应该是紧凑的，即具有几排。创建DAG表格表示的算法？

例如，给定具有边a1-> b1，a1-> b2，b1-> c1，b2-> c1（即菱形图）的节点a1，b1，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进行排序和过滤时，表格应该表现得很好。这意味着多个节点不能被打包到表格的单个单元中 - 每个单元只有一个节点。

来源

2009-11-20 rattigan

这里是我落得这样做：

查找一个节点发出的所有路径没有入边。（可能是一些图便宜，但适用于矿山）
遍历每个路径收集值行
紧凑的行

压实行是多内斯如下。

对于每对列×的，Y
- 构建地图x到它的每一个值的的Y
- 创建另一个地图有关条目仅具有Y的一个不同值的可能值，将x的值映射为y的单值。
使用这些贴图填充空白。填写数值时，请检查可填写的相关空白。

这给出了非常紧凑的输出，似乎满足我所有的要求。

来源

2009-11-24 16:12:40 rattigan

如何将一个节点上的所有可到达节点压缩在一个单元格中？例如，您的第一个DAG应该如下所示：

a b  c 
--------------- 
a1 [b1,b2] 
    b1  c1 
    b2  c1

来源

2009-11-20 20:24:23

这实际上并不是我在桌上所要找的。我想我认为重要的是表格应该以关系的方式表现良好，因为我希望能够在列上进行排序，并使用过滤器进行过滤。自动过滤器在Excel中。这种表示不符合该目标。还是）感谢你的建议！ – rattigan 2009-11-20 20:33:50

您需要的是变体topological sorting。这是一种“排序”图顶点的算法，就好像a---->b边缘意思是a > b。由于图形是一个DAG，因此它没有周期，并且这种关系是可传递的，所以至少存在一个排序顺序。

对于你的钻石形图中，两个拓扑订单存在：

a1 b1 b2 c1 
a1 b2 b1 c1

b1和b2项目不连接，即使是间接的，因此，它们可以被放置在任何顺序。

对图进行排序后，您知道订单的近似值。我的建议是直接填写表格（每行1个顶点），然后“紧凑”表格。执行排序并选择您获得的序列作为输出。填写该表从上到下，分配顶点到相关列：

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

现在，通过从顶部走到底部压实表（再作出类似的传球从底部到顶部）。每次迭代时，仔细看一下“当前”行（标记为=>）和“下一行”。

如果列在当前和下一个节点节点不同，什么也不做此列：

 from  ---->  to 
    X b c   X b c 
    --------   -------- 
=> X1 . .   X1 . . 
    X2 . .  => X2 . .

如果在接下来的行中的列X没有顶点（表单元格是空的），在当前行中有顶点X1，那么你有时应该填充这个空单元格当前行中的一个顶点。但并非总是如此：你想让你的桌子变得合乎逻辑，不是吗？因此，复制顶点当且仅当没有边缘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-20 20:38:25

这是一个有趣的方法。但是，我想知道它是否是确定性的 - 结果取决于您选择哪种拓扑排序，至少对于更复杂的DAG？我不在乎同一组行是否会导致不同的顺序，但我不会对可能导致不同行集的算法感到满意。我将更新问题以反映这一要求。 – rattigan 2009-11-20 20:51:29

我试图用边a1-> b1，b1-> c1，c1-> d1，a1-> b2，b2-> c2，c2-> d1做DAG。我不确定我是否理解规则二，所以我无法做到。但重点是这个图有拓扑排序，看起来好像他们可以产生不同的结果：a1，b1，c1，b2，c2，d1和a1，b1，b2，c1，c2，d1。你明白我的意思吗？ – rattigan 2009-11-20 21:19:02

@rattigan，是的，它可以产生不同的结果。您可以执行更具体的处理来对记录进行排序（例如，为图形添加更多边缘），但它超出了我的答案范围。至于规则二，我正在修改措辞让你再试一次。 – 2009-11-20 22:09:01

这听起来像是一个列车系统地图，车站在区域内（a，b，c）。

您可能会在一个方向上生成所有可能路线的表格。在这种情况下，“a1，b1，c1”似乎意味着a1-> b1，所以如果你只有a1-> c1，b1-> c1，则不要这样来格式化。你可以决定生成一个表格通过列出从区域a开始的最长路线，仅使用每个边缘一次，以短的剩余路线结束。或者只允许边连接未使用的边或扩展路线才能重复使用边。

换句话说，先进行深度优先搜索，尝试不重用边（拒绝任何不包含未使用边的路径，并可选地修剪使用的边在端点处）。

来源

2009-11-20 20:52:16

我喜欢这个想法。但是，生成的行集是否取决于表的遍历顺序？（请参阅编辑问题）也许这种变化也是一种选择：形成所有可能路线的集合 - 排除其他路线的子路线 - 并为每条路线发射一行。 – rattigan 2009-11-20 21:35:11

创建DAG表格表示的算法？

回答

相关问题