Эффективный поиск по ориентированному графу - PullRequest
Новая
       17

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

2 голосов
/ 04 января 2011

У меня есть ориентированный граф с миллионами вершин и ребер.Задан набор вершин, предположим, что они называются «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.Каков наиболее эффективный способ сделать это?Это может быть общеизвестной проблемой, но я пока не могу найти решение.

РЕДАКТИРОВАТЬ 6 января:

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

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

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

Ответы [ 3 ]

1 голос
/ 04 января 2011

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

1 голос
/ 04 января 2011

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

0 голосов
/ 04 января 2011

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

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

...