使用提取Steiner树时出错网络X.算法.近似.施泰纳树.steiner_

Question

我导出了两组数据：

1. 我从QGIS中导出为.shp文件的道路数据
2. 一个节点的点图层（长，纬度），我从QGIS导出为一个.shp文件

我想使用networkx库来提取连接给定道路上所有节点的Steiner树。为此，我在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')

所有到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

任何关于我在这里可能做错了什么的洞察，或者一个我可能完成这件事的创造性的方式（也许是地球帆）都会很有帮助。你知道吗

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

Answer 1

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

我建议您使用nx.is_directed和nx.is_multigraphical检查您的Road图形是哪种类型的图形。你知道吗

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