Найти соединенные ветви из списка сегментов линии
Проблема
У меня есть список сегментов линии:
exampleLineSegments = [(1,2),(2,3),(3,4),(4,5),(5,6),(4,7),(8,7)]
Эти сегменты включают в себя индексы соответствующей точки в отдельном массиве.
Из этого подсписка видно, что есть точка ветвления (4). Таким образом, из этой точки разветвления выходят три разные ветви. (В других, более специфических проблемах может быть несколько точек ветвления для ветвей н.)
Цель
Моя цель - получить словарь, включающий информацию о существующих ветвях, например:
result = { branch_1: [1,2,3,4],
branch_2: [4,5,6],
branch_3: [4,7,8]}
Текущее состояние работы/проблемы
В настоящее время я сначала идентифицирую точки ветвления, устанавливая словарь для каждой точки и проверяя каждую запись, если найдено более 2 соседних точек. Это означает, что есть точка ветвления.
После этого я просматриваю все точки, выходящие из этих точек ветвления, проверяя преемников и т. д.
В этих функциях какой-то для петель и вообще интенсивное "ползание". Это не самое чистое решение, и если количество точек увеличивается, производительность тоже не так хороша.
Вопрос
Каков наилучший/быстрый/наиболее эффективный способ достижения цели в этом случае?
К сожалению нет. В этом примере существует только одна точка ветвления. В других задачах может существовать несколько точек ветвления.
Ладно, я понял. Я работаю над этим.
Ответы 1
Я думаю, вы можете достичь этого, выполнив следующие шаги:
- используйте
neighborsdict для хранения графика - найти все точки ветвления, количество соседей которых > 2
- начать с каждой точки ветвления и использовать дфс, чтобы найти все пути
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):
привет @recnac, во-первых: Большое спасибо. Этот код выглядит таким чистым и отлично работает (и очень быстро!). К сожалению, я перешел к своей самой большой проблеме и столкнулся с проблемой глубины рекурсии (раньше ее никогда не было). Есть ли хороший обходной путь, чтобы избежать этой ошибки? Файл "", строка 32, в dfs, если len(neighbors[cur]) == 1 или (prev и cur в branch_points): RecursionError: превышена максимальная глубина рекурсии по сравнению Я погуглил и нашел что-то вроде import sys sys.setrecursionlimit(3000 ) А есть ли "более умное" решение?
насколько велики ваши данные? Если длина пути больше максимальной глубины рекурсии, вы можете использовать версию iteration вместо версии recursion. Или реализуйте свой собственный stack вместо использования стека системных функций.
если ваши данные большие, вы можете записать только отдельный путь, как я сказал выше.
Я напишу iteration версию для вас.
попробуйте версию iteration :) @BennyS
Это так здорово! Он работает и без «системного решения». Большое спасибо рекнак! На следующей неделе попробую более подробно :)
он содержит только одну точку ветвления?