python - 将节点树表示为列表
问题描述
我有两组数据 A 和 B,A 是起始节点,B 是结束节点。在每个集合中都有节点的编号,该节点的 X 坐标和 Y 坐标,如下所示。当节点 0 连接到节点 1 并且节点 1 连接到节点 2 时读取该表,节点 0 也连接到节点 3 等等。
A X_A Y_A B X_B Y_B
--------------------------------------------------------------------------
0 x_0 y_0 1 x_1 y_1
1 x_1 y_1 2 x_2 y_2
0 x_0 y_0 3 x_3 y_3
2 x_2 y_2 4 x_4 y_4
0 x_0 y_0 5 x_5 y_5
3 x_3 y_3 6 x_6 y_6
1 x_1 y_1 7 x_7 y_7
每个列表都是一个数组,所以总共有六个数组。
我想提取数据,以便可以通过坐标读取每一段线。一段线由一组节点定义,这些节点的起点和终点要么是一个交叉节点,要么是一个结束节点:交叉节点连接到两个以上的其他节点,而结束节点只连接到一个其他节点。
在此示例中,最终结果应为:
[(x_0, y_0),(x_5, y5)]
[(x_0, y_0),(x_3, y_3),(x_6, y_6)]
[(x_0, y_0),(x_1, y_1)]
[(x_1, y_1),(x_7, y_7)]
[(x_1, y_1),(x_2, y_2),(x_4, y_4)]
我对如何用 python 做到这一点感到很困惑,感谢任何帮助!
解决方案
似乎一个简单的 DFS 就可以解决问题。我将中间节点定义为恰好有两个邻居的节点。您定义了两个规则:
- 我们不能从中间节点开始,也不能从中间节点停止。
- 每个段至少有两个节点(隐式)。
编码:
class SegmentFinder():
def __init__(self, A, B):
# create the adjacency lists
self.__d = {}
self.__reverse_d = {}
for a,b in zip(A,B):
self.__d.setdefault(a, []).append(b)
self.__reverse_d.setdefault(b, []).append(a)
def find(self):
for n in self.__d:
if not self.__is_middle_node(n): # we can't start with a middle node
yield from self.__dfs([n])
def __dfs(self, segment):
# We don't need to store the visited nodes, since we start with a non middle
# node. If it has 1 neighbour, we won't be back. If it has more than 2,
# then it will end the search.
n = segment[-1]
if len(segment) == 1 or self.__is_middle_node(n): # we can't stop with a middle node
for n2 in self.__d[n]:
yield from self.__dfs(segment + [n2])
else: # a segment has at least two nodes
yield segment
def __is_middle_node(self, n):
"""Exactly two neighbours"""
return len(self.__d.get(n, [])) == 1 and len(self.__reverse_d.get(n, [])) == 1
s = SegmentFinder(A, B)
list(s.find())
# [[1, 2, 4], [1, 7], [0, 3, 6], [0, 1], [0, 5]]
要添加坐标,只需将路径中的节点与它们的 x,y 映射。对于任何图算法,通常只在节点上工作id
并在之后添加“装饰”更容易:
coords = dict(zip(A+B, zip(xa+xb,ya+yb)))
[coords[n] for path in s.find() for n in path]
推荐阅读
- ios - 使用未解析的标识符“NSFontAttributeName”
- r - 从子矩阵中提取
- visual-studio - 更新到 Windows 10 并安装 Visual Studio 2017 后出现 Xamarin 表单错误
- python-3.x - ValueError:检查输入时出错:预期 input_1 的形状为 (None, 1) 但得到的数组的形状为 (5, 54)
- django - 504 error when the view loading takes more than 5 s
- rest - ionic 3 - HttpClient 响应显示 inn 明文或如何禁用 httpclient 缓存
- ejb - ConcurrentAccessTimeoutException in EJB singleton bean
- php - 是否可以将函数作为另一个函数参数传递?
- angular - 将角度 5 与 ElasticSearch 连接时出现进程未定义错误?
- firebase - firebase-admin-node 会开始从firestore返回日期作为时间戳吗?