graph-theory - 了解 PBBS 邻接图格式。

Question

我正在尝试找出一种方法来转换边缘列表表示，即Edge(start, end)图形的，以及此处和此处描述的。

我试过自己弄清楚，但文档非常简洁。我主要不明白数值是从什么开始计算的：偏移量是从哪里写入偏移量的行数？它只是邻接表开头的行号吗？如果我减去相邻的偏移量，我会得到连续块的大小吗？差一个吗？

太多的问题本可以用一个例子来解决，但不幸的是，使用这个套件的所有东西都没有真正解释它应该如何解释。

例如，如果我有一个看起来像这样的有向图

Edge(1,2), Edge (2,4), Edge(3,4), Edge(1,3), ..., Edge(i,j)

它将如何以 PBBS 的邻接图格式表示。

我知道这是非常具体的，而且它可能真的很容易理解，但我个人遇到了麻烦。我无法理解。如果有人可以提供帮助，我将不胜感激。

标签： graph-theory

Answer 1

这种格式我没用过，不过举个例子不难理解。

这是上图所有出边的有序列表：

0-6  line 0
1-5  line 1
2-4  line 2
2-6  line 3
3-0  line 4
3-6  line 5
3-7  line 6
5-4  line 7

顶点的出边列表

0 starts at line 0, mark it as [0, 1)
1 starts at line 1, mark it as [1, 2)
2 starts at line 2, mark it as [2, 4)
3 starts at line 4, mark it as [4, 7)
4 starts at line 7, mark it as [7, 7)
5 starts at line 7, mark it as [7, 8)
6 starts at line 8, mark it as [8, 8)
7 starts at line 8, mark it as [8, 8)

根据格式说明，

顶点 i 的偏移量是指边序列中顶点 i 的连续出边块的开始位置。该块继续直到下一个顶点的偏移量，或者如果 i 是最后一个顶点，则结束。

应该写成，

0
1
2
4
7
7
8
8

0-6
1-5
2-4
2-6
3-0
3-7
5-4

至于如何将边缘列表图转换为邻接列表图，您可以通过比较边缘节点来对图进行排序。假设e1 = (source1, target1), e2 = (source2, target2)，e1 < e2如果

source1 < souce2
or
source1 == source2 and target1 < target2