从线段列表中查找连接的分支

Question

问题

我有一个线段列表：

exampleLineSegments = [(1,2),(2,3),(3,4),(4,5),(5,6),(4,7),(8,7)]

这些段包括单独数组中对应点的索引。

从这个子表可以看出有一个分支点(4)。所以三个不同的分支从这个分支点出现。（在其他更具体的问题中，n 个分支可能有多个分支点。）

目标

我的目标是获取包含现有分支信息的字典，例如：

result = { branch_1: [1,2,3,4],
           branch_2: [4,5,6],
           branch_3: [4,7,8]}

work/problems

的现状

目前，我首先通过为每个点设置字典并检查每个条目是否找到超过 2 个相邻点来识别分支点。这意味着有一个分支点。

之后，我遍历从这些分支点出现的所有点，检查后继者等。

在这些函数中，有一些for 循环，通常是密集的"crawling"。这不是最干净的解决方案，如果点数增加，性能也不是很好。

问题

在这种情况下实现目标的最好/最快/最有效的方法是什么？

Answer 1

我认为您可以通过以下步骤实现它：

使用 neighbors 字典存储图形
找到所有分支点，其中邻居计数> 2
从每个分支点开始，用dfs找到所有路径

from collections import defaultdict
def find_branch_paths(exampleLineSegments):
    # use dict to store the graph
    neighbors = defaultdict(list)
    for p1, p2 in exampleLineSegments:
        neighbors[p1].append(p2)
        neighbors[p2].append(p1)

    # find all branch points
    branch_points = [k for k, v in neighbors.items() if len(v) > 2]

    res = []

    def dfs(cur, prev, path):
        # reach the leaf
        if len(neighbors[cur]) == 1:
            res.append(path)
            return
        for neighbor in neighbors[cur]:
            if neighbor != prev:
                dfs(neighbor, cur, path + [neighbor])

    # start from all the branch points
    for branch_point in branch_points:
        dfs(branch_point, None, [branch_point])

    return res

更新一个iteration版本，用于大数据，这可能会导致a recursion depth problem:

def find_branch_paths(exampleLineSegments):
    # use dict to store the graph
    neighbors = defaultdict(list)
    for p1, p2 in exampleLineSegments:
        neighbors[p1].append(p2)
        neighbors[p2].append(p1)

    # find all branch points
    branch_points = [k for k, v in neighbors.items() if len(v) > 2]

    res = []
    # iteration way to dfs
    stack = [(bp, None, [bp]) for bp in branch_points]
    while stack:
        cur, prev, path = stack.pop()

        if len(neighbors[cur]) == 1 or (prev and cur in branch_points):
            res.append(path)
            continue

        for neighbor in neighbors[cur]:
            if neighbor != prev:
                stack.append((neighbor, cur, path + [neighbor]))

    return res

测试和输出：

print(find_branch_paths([(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (4, 7), (8, 7)]))
# output: 
# [[4, 3, 2, 1], [4, 5, 6], [4, 7, 8]]

希望对您有所帮助，如有其他问题，请评论。 :)

更新：如果有很多分支点，路径将呈指数增长。所以如果你只想要不同的段，你可以在遇到另一个分支点时结束路径。

更改此行
if len(neighbors[cur]) == 1:
至
if len(neighbors[cur]) == 1 or (prev and cur in branch_points):

从线段列表中查找连接的分支

Find connected branches from list of line segments

python

geometry

shapely

line-segment