如何从networkx中按特定顺序提取图边？

Question

我试图找到穿过一组几乎对齐的点的最短路径。这需要在各个方向上起作用，所以我不能只按 x 或 y 值对它们进行排序。

我想出的解决方案是使用networkx制作一个图，找到最小生成树，并导出最短路径。我想最终得到一个匀称的 LineString （不是 MultiLineString）

事实证明，networkx 绘制的正是我想要的，但我没有找到一种方法以正确的顺序导出边缘来构建 LineString，它总是弄得一团糟。为了做到这一点，我需要按正确的顺序排列顶点（或节点），如图所示。

有人可以帮助我吗？下面是示例代码：

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
from scipy.spatial.distance import pdist, squareform

points_line = np.array([[  0.46734317, 149.36430674],
       [  0.46734547, 149.36334419],
       [  0.46744031, 149.36238631],
       [  0.4676268 , 149.36144199],
       [  0.46734317, 149.36430674],
       [  0.46743343, 149.36526506],
       [  0.4676154 , 149.36621026],
       [  0.46788741, 149.36713358],
       [  0.46824692, 149.36802648],
       [  0.94443392, 150.40378967],
       [  0.4676268 , 149.36144199],
       [  1.55364459, 144.98283937],
       [  0.94443392, 150.40378967],
       [  0.68606383, 157.76059211],
       [  0.68606634, 157.76135963],
       [  1.55364459, 144.98283937],
       [  1.6347943 , 136.57997287],
       [  0.92188273, 132.24795534],
       [  0.92178416, 132.24715728],
       [  0.92175003, 132.24635387],
       [  0.90765426, 125.94462804],
       [  0.90769726, 125.94367903],
       [  0.68606634, 157.76135963],
       [  1.08596441, 167.35367069],
       [  0.66299718, 175.68436124],
       [  0.90769726, 125.94367903],
       [  1.8455184 , 115.86662374],
       [  1.22148527, 103.42945831],
       [  1.22148224, 103.42852062],
       [  1.22156706, 103.42758676],
       [  1.22173897, 103.42666495],
       [  1.89690364, 100.55965775],
       [  1.23628246,  92.47574962],
       [  1.23624942,  92.47487388],
       [  1.23629318,  92.47399861],
       [  1.23641341,  92.47313053],
       [  2.28757468,  86.74385772],
       [  2.28778124,  86.74296467],
       [  2.2880687 ,  86.74209429],
       [  2.28843466,  86.74125389],
       [  2.28887603,  86.74045053],
       [  2.2893891 ,  86.73969096],
       [  2.82731279,  86.01709145]])

# Create a graph
G = nx.Graph()

# Add nodes to the graph
for i, point in enumerate(points_line):
    G.add_node(i, pos=point)

# Calculate pairwise distances between all points
distances = pdist(points_line)
distance_matrix = squareform(distances)

# Add edges to the graph with weights based on distances
for i in range(len(points_line)):
    for j in range(i+1, len(points_line)):
        G.add_edge(i, j, weight=distance_matrix[i][j])

# Calculate the minimum spanning tree
mst = nx.minimum_spanning_tree(G)

# Extract edges from the minimum spanning tree
edges = list(mst.edges())

# Extract consecutive points from the edges to form the sequence of points
consecutive_points = []
for edge in edges:
    consecutive_points.append(points_line[edge[0]])
    consecutive_points.append(points_line[edge[1]])

# Convert the consecutive points to a numpy array
consecutive_points_array = np.array(consecutive_points)

# Find indices where the next point is not the same as the current point
indices = np.concatenate(([True], np.any(np.diff(consecutive_points_array, axis=0) != 0, axis=1)))

# Filter out the points based on the indices
filtered_points_array = consecutive_points_array[indices]

# Plot the original points and the minimum spanning tree
pos = nx.get_node_attributes(G, 'pos')
positions = dict(zip(mst.nodes, 'pos'))

plt.figure(figsize=(12, 8))
nx.draw_networkx_nodes(G, pos, node_size=20)
nx.draw_networkx_edges(mst, pos, edge_color='r', width=1)
plt.title("Minimum Spanning Tree")
plt.axis('equal')
plt.show()

我尝试了networkx中内置的所有导出函数来尝试获取numpy数组，但它有重复节点，并且即使在清理后也不起作用。尝试了法学硕士的一些解决方案，但没有成功。

Answer 1

一个简单的选择是

remove_edges_from

树排除重叠节点（权重/距离为 0 的点），然后使用

all_simple_paths

重新索引 points_line 数组（即，一个包含节点索引) :

from shapely import LineString

mst.remove_edges_from(
    [(u, v) for (u, v, w) in mst.edges(data=True) if w["weight"] == 0]
)

# must be exactly two, e.g: 24, 42
extremities = [n for n, d in mst.degree() if d == 1]

ls = LineString(points_line[list(nx.all_simple_paths(mst, *extremities))].squeeze())