Выделение «плетеных сечений» в графе

Question

Предположим, у меня есть график с графическим представлением, подобным этому:

Как вы можете видеть, есть "плетеная секция", в какие разные пути можно пройти, но, если вы продолжите идти (хотя бы в одном направлении вдоль главной оси), вы неизменно окажетесь в одной и той же точке в конце «оплетки».

Этот график может простираться в любом направлении на большое расстояние и иметь несколько косичек произвольной сложности на этом пути.

Существует ли какой-либо алгоритм, способный изолировать узлы в синих кружках, указывая начало и конец "оплетка"? Или go еще дальше и просто вернуть подграф, содержащий косу, отсекаемую в этих узлах?

У меня проблемы с формулированием этой проблемы в Google, и документация для моей библиотеки графов не объясняет различные алгоритмы он реализует.

В настоящее время я использую Python NetworkX, но я не против реализации алгоритма вручную, если он не имеет прямой реализации.

Я должен также указать, что Граф в идеале может быть направлен так, чтобы все ребра были направлены вдоль одного направления большой оси, но решение, которое также могло бы использовать ориентированный граф, было бы лучше.

РЕДАКТИРОВАТЬ: Вот моя реализация, основанная на ответе из @ kaya3:

articulation_points = nx.articulation_points(graph)
for node in articulation_points:
    if nx.degree(graph, node) > 2:
        print(node)

Answer 1

Эта проблема может быть решена путем нахождения точек сочленения (также называемых вершинами разреза) графа; это вершины, которые, если вы удалите их из графа, будут отключены. Множество всех точек сочленения можно найти за линейное время с помощью поиска в глубину.

Очевидно, что точки сочленения являются либо началом, либо концом косы, или точки вдоль путей между концом одной косы и началом другой. Таким образом, начало и конец кос - это точки сочленения, которые имеют либо степень превышения, либо степень превышения, соответственно, 1. (Если график ненаправленный, то вам нужны точки сочленения со степенью больше 2.)

Существует особый случай, если коса начинается сразу в первой вершине или заканчивается в последней. В этом случае это не точка артикуляции, но вы хотите ее посчитать. Поэтому вам следует включить первую точку, если ее (вне) степень больше 1, и последнюю точку, если ее (вне) степень больше 1.

Answer 2

Я не знаю определенного c алгоритма, который делает это, но реализовать его достаточно просто. Вы перебираете узлы в ширину и отслеживаете количество исследуемых ветвей. Когда число увеличивается выше 1, вы находитесь в начале «косы». Когда количество одновременно исследуемых веток уменьшается до 1, вы только что нашли конец косы. Это может быть неоптимальным, так как ваша сложность больше, чем O (n), поскольку вы не можете пропустить уже посещенные узлы, если у вас есть разное количество узлов в ваших различных ветвях (если вы это сделали, вы можете пропустить конец косы) , но если вы не имеете дело с миллионами узлов, высоким коэффициентом ветвления и большим дисбалансом, я ожидаю, что с вами все будет в порядке.

Answer 3

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