将有向图编码为数字

比方说，我有一个有向图，只有一个根，没有周期。我想每个节点上添加类型（举例来说，如一些自定义排序的整数）具有以下特性：将有向图编码为数字

if Node1.type <= Node2.type then there exists a path from Node1 to Node2

注意拓扑排序实际上满足逆转属性：

if there exists a path from Node1 to Node2 then Node1.type <= Node2.type

所以它不能在这里使用。

现在请注意，具有自然排序的整数在这里不能使用，因为每2个整数都可以进行比较，即整数排序是线性的，而树不一定是。

所以这里有一个例子。假设有图有4个节点A, B, C, D和4个箭头：

A->B, A->C, B->D, C->D

所以这是一个菱形。现在我们可以把

A.type = 00 
B.type = 01 
C.type = 10 
D.type = 11

其中在右侧我们有二进制格式的整数。比较是按位定义的：

(X <= Y) if and only if (n-th bit of X <= n-th bit of Y for all n)

所以我猜这样的排序可以使用，问题是如何构造给定图的值？我甚至不确定解决方案是否一直存在。任何提示？

UPDATE：既然有关于我使用的是让我更explicite术语一些误解：我感兴趣的是向无环图，使得在没有前辈在一个节点（又名根），并有一个在任何两个节点之间的最多一个箭头。钻石就是一个例子。它不是不是必须有一个叶子（即没有后继的节点）。每个节点可能有多个前辈和多个后继者。您可能会说这是一个具有最小元素的部分有序集合（即唯一的全局最小元素）。

来源

2016-06-14 freakish

如果'Node1.type <= Node2.type'永远不会满足要求，。 –

@ n.m。我不确定我是否理解，谨慎地阐述？ – freakish

如果'a

对于任何DAG，您可以将定义为x <= y为“存在从x到y的路径”。这种关系是部分秩序。我认为，问题是如何有效地表达这种关系。

对于每个顶点X，定义X是从X（包括X本身）可到达的顶点集合。这两种说法

¡X是¡Ÿ
X的一个子集可达Y的

是等价的。

将这些集合编码为位集（N位二进制数），然后进行设置。

来源

2016-06-14 12:31:04

我真的很惊讶这是多么简单。这两个等价的陈述是我没有看到的。谢谢！ – freakish

您调用关系<=，但它一定是不完全的（即：它可能是，对于给定对a和b，既不a <= b也不b <= a）。

下面是如何定义它的一个想法。

如果你的节点编号为0，1 ...，N-1，那么您可以定义type这样的：

type(i) = (1 << i) + sum(1 << (N + j), for j such that Path(i, j))

，并定义<=这样的：

type1 <= type2 if (type1 >> N) & type2 != 0

也就是说，type(i)在最低N位中编码i的值，并且在最高位N位中编码所有可达节点的集合。 <=关系查找编码的可达节点集合中的目标节点。

该定义适用于图中是否存在循环，实际上只是在您的节点集上编码任意关系。

通过使用ceil(log2(N))位对节点号进行编码（总共N + ceil(log2(N))位/ type），可以使定义更有效一些。

来源

2016-06-14 08:48:19

”：它不一定是传递性的“为什么？如果从A到B有一条路径，从B到C有一条路径，那么从A到C有一条路径。 –

@ n.m。这意味着“存在路径”关系是可传递的。不是'<='关系。从理论上讲，即使它映射成传递关系，'<='也可能不是传递的。请注意，如果路径存在，我不需要'<='必须保持。要求'<='传递将是很好，但我认为这不是我的目的所必需的。 – freakish

呃，是的，它是传递性的。但它不完整。我会编辑答案。 –

这个问题说（并继续说）输入是一棵树，但稍后的编辑与钻石图的例子相矛盾。在这种非树情况下，下面的算法将不适用。

现有的答案适用于普通有向图上的一般关系，它将它们的表示大小膨胀为n个顶点的O（n）位。由于您拥有一棵树，因此可以使用较短的O（log n）位表示。对于任何两个顶点u和v，从u和v到达的叶子集合L（u）和L（v）必须是不相交的，或者必须是一个必须的成为另一个的子集。如果它们不相交，那么u不能从v到达（反之亦然）;如果一个是另一个的合适子集，那么具有较小集合的子集可以从另一个子集中获得（在这种情况下，具有较小集合的子集将必然具有严格更大的深度）。如果L（u）= L（v），那么u可以从v到达当且仅当深度（u），其中深度（u）是从根到u的路径上的边的数量。（特别是，如果L（u）= L（v）和深度（u）=深度（v），那么u = v。）

我们可以简洁地编码这个关系，注意到所有的叶子都可以从给定的顶点v通过树的中间遍历占据叶子输出的连续段。对于任何给定的顶点v，这组树叶因此可以用一对整数(first, last)来表示，其中first标识第一叶（以中序遍历顺序）和last最后一个。对于是否从i到j存在路径的测试则很简单 - 在伪C++：

bool doesPathExist(int i, int j) { 
    return x[i].first <= x[j].first && x[i].last >= x[j].last && depth[i] <= depth[j]; 
}

注意，如果在树中的每个非叶顶点至少有2个孩子，那么你不”因为在这种情况下L（u）= L（v）意味着u = v，所以需要打扰深度。（我的原始版本的帖子做了这个假设;我现在已经修复它的工作，即使不是这种情况）。

来源

2016-06-14 14:44:07

“_必须是不相交的，或者必须是other_的子集”：在DAG中这不是真的。特别是，一个节点可能有两个来自不同“子树”的进入边缘。 OP提供的钻石示例就是这种情况的一个实例。 –

@PatriceGahide：OP问题的第一行：“假设我有一个有向图，**实际上是一棵树**” –

查看OP的注释。我们正在处理DAG。 –

将有向图编码为数字

回答

相关问题