Как сгруппировать массив кортежей по общим элементам? ⇐ Python

[Anonymous]

У меня есть серия сегментов, определенная как массив из двух кортежей (двух вершин). Каждый сегмент может иметь общую вершину с другим сегментом, и возможно, что комбинация сегментов образует один или несколько замкнутых контуров.
Чтобы найти замкнутые контуры, мой текущий подход заключается в следующем: найдите, какие линии соединены (общая вершина), и сгруппируйте их, прежде чем упорядочивать каждую группу по часовой стрелке.
Давайте рассмотрим следующий пример (написанный на Python)

Код: Выделить всё

lines = {
"A": [(0, 0), (0, 1)],  # A,B -- B,C
"B": [(0, 1), (1, 1)],  # |       |
"C": [(1, 1), (1, 0)],  # |       |
"D": [(1, 0), (0, 0)],  # A,D -- C,D

"E": [(4, 4), (4, 5)],  # E,F - F,G
"F": [(4, 5), (5, 5)],  # |   /
"G": [(5, 5), (4, 4)],  # E,G
}

answer = ["ABCD", "EFG"]

Как лучше всего сгруппировать записи (с использованием стандартной библиотеки Python), имеющие общую вершину (значение кортежа)? Порядок, в котором строки находятся в словаре, не гарантирован, но здесь он упорядочен по часовой стрелке, чтобы было легче читать.
Я попробовал простой циклический подход (теория графов) для решения этой проблемы. но возвращенные циклы включали гораздо больше, чем мне хотелось, используя вершины в приведенном выше примере, поэтому я пересмотрел свой подход к проблеме, в результате чего я задал этот вопрос.

Подробнее здесь: https://stackoverflow.com/questions/788 ... n-elements