Блог

Проблема

У меня есть список линейных сегментов:

 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]}
  

Текущее состояние работы / проблемы

В настоящее время я сначала определяю точки ветвления, настраивая словарь для каждой точки и проверяя для каждой записи, найдено ли более 2 соседних точек. Это означает, что существует точка ветвления.

После этого я просматриваю все точки, возникающие из этих точек ветвления, проверяя наличие преемников и т.д.

В этих функциях есть несколько циклов for и, как правило, интенсивное «сканирование». Это не самое чистое решение, и если количество точек увеличивается, производительность тоже не так хороша.

Вопрос

Каков наилучший / самый быстрый / самый эффективный способ достижения цели в этом случае?

Я думаю, вы можете достичь этого, выполнив следующие шаги:

1. используйте neighbors dict для хранения графика
2. найдите все точки ветвления, количество соседей которых> 2
3. начните с каждой точки ветвления и используйте 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):