Python igraph 顶点索引

Question

我正在使用 python 中的 igraph 库。我想知道是否有使用字符串作为顶点索引的方法。我知道 'name' 属性并且我可以写

g = igraph.Graph(directed=True)
g.add_vertex('hello')
g.add_vertex('world')
g.add_edge('hello','world')

一切正常。除了如果我两次添加相同的顶点，例如：

g = igraph.Graph(directed=True)
g.add_vertex('world')
g.add_vertex('hello')
g.add_vertex('hello')

创建了两个不同的顶点，如果我现在添加一条边：

g.add_edge('hello','world')

这条边被添加到第一个匹配 'hello' 的顶点作为名称。这也表明这种形式的索引具有 O(n) 复杂度而不是 O(1) （即扫描整个顶点列表直到找到满足 v['name'] == 'hello' 的顶点 v）。

所以我在考虑保持顶点名称和索引之间的映射，例如：

mapping = {}
g = igraph.Graph(directed=True)
g.add_vertex('hello')
mapping['hello'] = len(g.vs)-1
g.add_vertex('world')
mapping['world'] = len(g.vs)-1
g.add_edge(mapping['hello'],mapping['world'])

我认为这应该有效，因为我从不删除顶点所以我想索引应该保持不变。它还具有查找的平均速度 O(1)，这应该比以前的解决方案更好。但是我想知道：

我总是保证g.vs[i].index == i吗？（即我可以总是使用 vs 数组中顶点的位置来引用像 add_edge() 这样的函数中的那个顶点吗？）
当我向图中添加一个新顶点时，我是否始终保证它的索引将是 len(g.vs)-1？

编辑：关于边的相同问题：我能保证我会在 g.es[len(g.es)-1] 中找到最后添加的边吗？

Answer 1

This also suggests that such form of indexing has O(n) complexity instead of O(1)

这不是真的； igraph 为 name 顶点属性维护从名称到顶点 ID（就像您建议的那样）的内部映射，每当您添加或删除顶点时，它都会自动更新。如果有多个具有相同名称的顶点，则映射选择任意一个顶点，然后 returns 那个（一致地）用于名称查找。在幕后，这一切都是通过标准 Python 字典完成的。因此，您可以安全地执行以下所有操作：

只要 igraph 函数或方法需要顶点 ID，就使用顶点名称而不是顶点 ID
使用g.vs.find("foo")找到name等于"foo"的任意顶点。

请注意，我们不能阻止用户创建多个具有相同名称的顶点，因为这在 igraph 可以读取的许多图形格式（例如 GraphML）中都是有效的，我们不想阻止用户读取它们.

am I always guaranteed that g.vs[i].index == i?

是的，这保证是真的。但是，以下不是：

>>> v = g.vs[12]
>>> g.delete_vertices(...)
>>> g.vs[v.index] == v

原因是顶点和边对象非常漂亮 "dumb" 因为它们只存储对它们所源自的图的引用以及它们在图中的索引 - 但它们不会在图本身时更新已更新。经验法则是，只要您改变基础图形，您持有引用的任何顶点或边对象就会变成 "invalid"。

am I always guaranteed that when I add a new vertex to the graph its index is going to be len(g.vs)-1?

严格来说，API（作为正式的 "contract"）并不能保证这一点，但从 igraph 开发之初就一直如此，我认为没有理由这样做将来随时更改。我在自己的代码中也经常依赖它。这同样适用于边缘。

Python igraph 顶点索引

Python igraph vertex indices

python

indexing

igraph