已杀死：9 从节点列表和链接列表创建图形

Question

我正在使用 iGraph 从 nodes 列表和 links 列表构建网络。有 200,000 个节点和 450,000 links。对于每个 node 都有一些关联的元数据，对于每个 link 也是如此。

节点列表如下所示：

[{u'toid': u'osgb4000000031043205', u'index': 1, u'point': [508180.748, 195333.973]}, {u'toid': u'osgb4000000031043206', u'index': 2, u'point': [508163.122, 195316.627]}, {u'toid': u'osgb4000000031043207', u'index': 3, u'point': [508172.075, 195325.719]}, {u'toid': u'osgb4000000031043208', u'index': 4, u'point': [508513, 196023]}]

links 列表如下所示：

[{u'index': 1, u'term': u'Private Road - Restricted Access', u'nature': u'Single Carriageway', u'negativeNode': u'osgb4000000023183407', u'toid': u'osgb4000000023296573', u'polyline': [492019.481, 156567.076, 492028, 156567, 492041.667, 156570.536, 492063.65, 156578.067, 492126.5, 156602], u'positiveNode': u'osgb4000000023183409'}, {u'index': 2, u'term': u'Private Road - Restricted Access', u'nature': u'Single Carriageway', u'negativeNode': u'osgb4000000023763485', u'toid': u'osgb4000000023296574', u'polyline': [492144.493, 156762.059, 492149.35, 156750, 492195.75, 156630], u'positiveNode': u'osgb4000000023183408'}, {u'index': 3, u'term': u'Private Road - Restricted Access', u'nature': u'Single Carriageway', u'negativeNode': u'osgb4000000023183650', u'toid': u'osgb4000000023296638', u'polyline': [492835.25, 156873.5, 493000, 156923, 493018.061, 156927.938], u'positiveNode': u'osgb4000000023183652'}, {u'index': 4, u'term': u'Local Street', u'nature': u'Single Carriageway', u'negativeNode': u'osgb4000000023181163', u'toid': u'osgb4000000023388466', u'polyline': [498136.506, 149148.313, 498123.784, 149143.969, 498119.223, 149143.411, 498116.43, 149143.318, 498113.638, 149145.179], u'positiveNode': u'osgb4000000023806248'}]

我尝试构建图表：

g = Graph()

# Add nodes (and associated data)
for node in nodes:
    g.add_vertices(node['toid'])
# Add links (and associated data)
for link in links:
    g.add_edges([(link['negativeNode'],link['positiveNode'])])

links 文件包含少量在节点列表中找不到负节点或正节点的情况。因此，iGraph 会抛出以下错误：

ValueError: no such vertex: u'osgb4000000019779815'

我试图从 link 文件中添加 nodes 列表中不存在的那些 nodes。

for node in nodes:
    for link in links:
        if link['negativeNode'] not in node['toid']:
            missing_dict = {
            "toid": link['negativeNode']
            }
            nodes.append(missing_dict)
        if link['positiveNode'] not in node['toid']:
            missing_dict = {
            "toid": link['negativeNode']
            }
            nodes.append(missing_dict)

但是，这导致了以下错误：

Killed: 9

我认为该进程使用了太多内存。我该如何纠正？

Answer 1

首先，您的第二次尝试将尝试多次添加相同的 link；在最坏的情况下，links 向量中最后一个 link 的添加次数可能与 nodes 向量中的节点数一样多。所以，这种方法行不通。

其次，当你一个一个地添加节点或边时，igraph 不是很有效（由于它在每个节点添加或删除后执行的索引操作）。最好在 "batches" 中添加它们，即准备要添加的多个节点或边，然后通过一次调用 add_vertices() 或 add_edges().

一次添加它们

第三，Graph.DictList() 方法是明确为您的目的而设计的：它需要两个字典列表，一个用于节点，一个用于边，然后从中构造一个图，前提是您告诉它字典的哪些成员存储顶点名称和边的端点：

g = Graph.DictList(vertices=nodes, edges=links, vertex_name_attr="toid", edge_foreign_keys=("positiveNode", "negativeNode")

在调用Graph.DictList()之前你需要确保的是边列表中出现的所有节点都在节点列表中找到：

all_node_ids = set(edge["positiveNode"] for edge in links) | set(edge["negativeNode"] for edge in links)
known_node_ids = set(node["toid"] for node in nodes)
for node in all_node_ids - known_node_ids:
    nodes.append({u'toid': node})

已杀死：9 从节点列表和链接列表创建图形

Killed: 9 Creating a graph from a list of nodes and a list of links

python

igraph