Python igraph 顶点索引

Question

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

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 使得 v['name'] == 'hello' 找到了)。

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

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 的内部映射(就像您提出的那样) vertex 属性，当你添加或删除顶点时，它会自动更新。如果有多个具有相同名称的顶点，则映射会选择任意一个顶点，然后(一致地)返回该顶点以进行名称查找。在幕后，这一切都是通过标准的 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

原因是顶点和边对象非常“愚蠢”，因为它们只存储对它们所源自的图的引用以及它们在图中的索引——但它们不会在图本身更新时更新。经验法则是，只要您改 rebase 础图，您持有引用的任何顶点或边对象就会变得“无效”。

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 开发之初就一直如此，我认为将来没有理由改变它。我在自己的代码中也经常依赖它。这同样适用于边缘。