Найти связанные ветви из списка отрезков - PullRequest
Новая
       38

Найти связанные ветви из списка отрезков

0 голосов
/ 09 апреля 2019

Проблема

У меня есть список отрезков: 

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 соседних точек.Это означает, что есть точка ветвления.

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

В этих функциях есть некоторые для петель и вообще интенсивного "ползания".Это не самое чистое решение, и если количество очков увеличивается, производительность тоже не так хороша.

Вопрос

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

1 Ответ

0 голосов
/ 09 апреля 2019

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

  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):

...