Эффективный поиск в ориентированном графе

Question

У меня есть ориентированный граф с миллионами вершин и ребер. Набор вершин задан, предположим, что они называются «START_POINTS». Также задан еще один набор вершин, называемый «END_POINTS». Проблема заключается в том, чтобы найти, какие END_POINTS могут быть достигнуты, из которых START_POINTS.

Вот пример:

START_POINTS: S1 S2 S3 S4 S5 S6 S7 ... 
END_POINTS : E1 E2 E3 E4 E5 E6 E7 ... 

Алгоритм должен быть в состоянии сказать следующее:

S1 can reach to E1, E2, E6 
S2 can reach to E9, E10 
S3 cannot reach any END_POINT 
S4 can reach to ..... 
.... 

Некоторые из END_POINTS не может быть достигнуто из любого START_POINT.

Теперь вопрос в том, что представляет собой наиболее эффективный способ его реализации?

Я попытался начать с каждого START_POINT один за другим и найти доступные END_POINTS с использованием поиска по глубине (или BFS, это сильно изменило время выполнения). Однако это занимает много времени, потому что существует так много START_POINTS (также есть много END_POINTS).

Поиск можно оптимизировать, так как существует огромное перекрытие между прослеживаемыми путями START_POINTS. Нужно помнить, какие пути могут достигать END_POINTS. Каков наиболее эффективный способ сделать это? Это может быть хорошо известная проблема, но пока не удалось найти решение.

EDIT 6 января:

Я пытался реализовать идею highBandWidth (в аналогично тому, что предложил Кейт Randall): Для каждого узла, если этот узел не начальные или конечной точки, соединить все входы на выходы, затем удалите узел.

foreach NODE in NODES 
    Skip if NODE is START_POINT or END_POINT 
    foreach OUTPUT_NODE of NODE 
     Disconnect NODE from INPUT_NODE 
    end 
    foreach INPUT_NODE of NODE 
     Disconnect NODE from INPUT_NODE 
     foreach OUTPUT_NODE of NODE 
      Connect INPUT_NODE to OUTPUT_NODE 
     end 
    end 
    Remove NODE from NODES 
end 

Это начинается очень быстро, и быстро становится очень медленным, в основном потому, что входные/выходные отсчеты остальных узлов становятся очень большими и вложенными для петель убивает производительность. Любая идея, как это можно сделать более эффективным?

Answer 1

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

Answer 2

Это может быть излишним, но вы можете проверить Dijkstra. Я использовал его в прошлом при создании моей собственной таблицы маршрутизации виртуальных узлов. В этом случае все ваши узлы будут иметь значение 1, то есть каждый узел будет стоить одно и то же путешествие.

Answer 3

Сначала выполните алгоритм strongly connected components. Затем соедините все подключенные компоненты с одним узлом. Затем выполните график topological sort. Затем за один проход вы можете вычислить, какие начальные узлы могут достигать каждого узла в графе (инициализировать каждый начальный узел s до набора {s}, а затем выполнить объединение входящих ребер в каждом узле в топологическом порядке).

У вас есть потенциальная проблема в том, что ответ может быть таким же большим, как # start nodes * # end nodes, который может быть большим. Надеюсь, у вас есть несколько крупных SCC, которые будут заключать контракты на отдельные узлы, поскольку это может сделать ответ гораздо более кратким (все стартовые узлы в одном SCC могут достигать тех же мест, поэтому вам нужно использовать только один представитель в ваших наборах).