我在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？ (即我是否可以始终使用vs数组中顶点的位置来引用add_edge()等函数中的顶点？)
>我总是保证当我向图表添加一个新的顶点时,它的索引将是len(g.vs)-1？

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

解决方法:

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

这不是真的; igraph维护名称顶点属性的名称与顶点ID的内部映射(就像您建议的那样),无论何时添加或删除顶点,都会自动更新.如果有多个具有相同名称的顶点,则映射会选择一个任意顶点,然后返回该一个顶点(一致地)以进行名称查找.在幕后,这一切都是用标准的Python字典完成的.因此,您可以安全地执行以下所有操作：

>只要igraph函数或方法需要顶点ID,就使用顶点名称而不是顶点ID
>使用g.vs.find(“foo”)查找名称等于“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

原因是顶点和边缘对象非常“笨”,因为它们只存储对它们来源的图形的引用以及它们在图形中的索引 – 但是当图形本身更新时它们不会更新.经验法则是,一旦您改变底层图形,您持有引用的任何顶点或边缘对象都将变为“无效”.

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不能保证这一点(作为正式的“合同”),但从igraph的开发到目前为止,情况就是如此,我认为没有理由在未来的任何时候改变它.我也经常在我自己的代码中依赖它.这同样适用于边缘.