时间戳

首页 > 解决方案 > 使用 networkx.algorithms.approximation.steinertree.steiner_tree 提取 Steiner 树时出错

python - 使用 networkx.algorithms.approximation.steinertree.steiner_tree 提取 Steiner 树时出错

问题描述

我导出了两组数据：

  1. 我从 QGIS 导出为 .shp 文件的道路数据
  2. 我从 QGIS 导出为 .shp 文件的节点（经纬度）的点层

我想使用 networkx 库来提取连接给定道路上所有节点的施泰纳树。为此，我在 jupyter notebook 上编写了以下代码：

import networkx as nx #importing the NetworkX library
Road = nx.read_shp('proj_data/roads/cmbRoads.shp') #Reading Road Data 
Base = nx.read_shp('proj_data/bs/bsSnapped.shp') #Reading Terminal Node Data
nodes = list(Base.nodes) #Creating list of terminal nodes
from networkx.algorithms import approximation as ax
st_tree = ax.steinertree.steiner_tree(Road,nodes,weight='length')

直到 Steiner 树提取的所有代码行都已执行，没有任何问题。我收到以下错误消息：

---------------------------------------------------------------------------
NetworkXNotImplemented                    Traceback (most recent call last)
<ipython-input-5-99884445086e> in <module>
      1 from networkx.algorithms import approximation as ax
----> 2 st_tree = ax.steinertree.steiner_tree(Road,nodes,weight='length')

<c:\users\nandula\appdata\local\programs\python\python37\lib\site-packages\decorator.py:decorator-gen-849> in steiner_tree(G, terminal_nodes, weight)

c:\users\nandula\appdata\local\programs\python\python37\lib\site-packages\networkx\utils\decorators.py in _not_implemented_for(not_implement_for_func, *args, **kwargs)
     80             raise nx.NetworkXNotImplemented(msg)
     81         else:
---> 82             return not_implement_for_func(*args, **kwargs)
     83     return _not_implemented_for
     84 

<c:\users\nandula\appdata\local\programs\python\python37\lib\site-packages\decorator.py:decorator-gen-848> in steiner_tree(G, terminal_nodes, weight)

c:\users\nandula\appdata\local\programs\python\python37\lib\site-packages\networkx\utils\decorators.py in _not_implemented_for(not_implement_for_func, *args, **kwargs)
     78         if match:
     79             msg = 'not implemented for %s type' % ' '.join(graph_types)
---> 80             raise nx.NetworkXNotImplemented(msg)
     81         else:
     82             return not_implement_for_func(*args, **kwargs)

NetworkXNotImplemented: not implemented for directed type

对我在这里可能做错的任何见解或我可能完成此操作的替代方式（可能是geopandas）都会有所帮助。

注意：我没有使用 QGIS 本身中的处理工具箱，因为我的个人计算机上的 RAM 不足（数据集非常大），我需要在 CentOS 服务器上运行此代码。

标签： pythonjupyter-notebooknetworkxshapefileqgis

解决方案

问题是您从 QGIS 数据创建的图似乎是有向图，并且该算法仅适用于无向图。

我建议您Road使用nx.is_directedand来检查您的图表是哪种类型的图表nx.is_multigraphical。

您可以转换为无向图undirected_roads = nx.Graph(Road)，然后调用算法ax.steinertree.steiner_tree(undirected_roads,nodes,weight='length')。但是，根据原始图形的不对称程度，您会丢失一些信息。

推荐阅读