Python igraph顶点索引

Question

Python igraph顶点索引

5

我正在使用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，使得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？（例如，我是否可以始终在诸如 add_edge() 这样的函数中使用 vs 数组中顶点的位置来引用该顶点？）
我是否始终保证当我向图中添加新顶点时，它的索引将会是 len(g.vs)-1？

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

- Simone Bronzini

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tamás · Accepted Answer

这也意味着这种索引形式的复杂度为O(n)，而不是O(1)。

这是不正确的。Igraph维护了一个从名称到顶点ID的内部映射（就像您提出的那个）用于name顶点属性，其在添加或删除顶点时会自动更新。如果有多个名称相同的顶点，则映射选择任意一个顶点并为名称查找返回该顶点（一致性）。在幕后，所有这些都是通过标准Python字典完成的。因此，您可以安全地执行以下所有操作：

- 每当igraph函数或方法需要顶点ID时，请使用顶点名称而不是顶点ID - 使用g.vs.find("foo")查找名称等于"foo"的任意顶点

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

“我总是保证g.vs[i].index == i吗？”是的，这是保证为真的。但是下面的内容不是：

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

原因在于顶点和边对象比较“愚蠢”，它们仅存储对图的引用以及它们在图中的索引，但当更改图本身时，它们并不会更新。经验法则是，任何你持有引用的顶点或边对象，在底层图发生变化时都将变得“无效”。

“当我向图添加新顶点时，是否总可以保证其索引为 len(g.vs)-1？” 严格来说，API不能保证这一点（作为正式的“合同”），但从igraph开发初期以来就一直如此，并且我认为没有理由在未来更改这种情况。我在自己的代码中也经常依赖它。边也是如此。