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

这也表明这种形式的索引具有O(n)复杂度而不是O(1)

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

• 只要igraph函数或方法需要顶点ID,就使用顶点名称而不是顶点ID
• 用于g.vs.find("foo")查找name等于的任意顶点"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的开发到目前为止已经是这种情况,我认为没有理由在未来的任何时候改变它.我也经常在我自己的代码中依赖它.这同样适用于边缘.