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

Question

我导出了两组数据:

1. 我从 QGIS 导出为 .shp 文件的道路数据
2. 我从 QGIS 导出为 .shp 文件的节点点层(长、纬度)

我想使用networkx库来提取连接给定道路上所有节点的斯坦纳树。为此，我在 jupyter 笔记本上编写了以下代码:

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')

斯坦纳树提取之前的所有代码行均已执行，没有任何问题。我收到以下错误消息:

---------------------------------------------------------------------------
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 服务器上运行此代码。

Answer 1

问题是您从 QGIS 数据创建的图似乎是有向图，并且该算法仅针对无向图实现。

我建议您使用 nx.is_directed 和 nx.is_multigraphical 检查您的 Road 图属于哪种类型。

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