Найти все достижимые вершины в графе Boost BGL эффективно - PullRequest
Новая
       45

Найти все достижимые вершины в графе Boost BGL эффективно

0 голосов
/ 11 декабря 2018

Я новичок в улучшении библиотеки графов и пытаюсь решить следующую проблему:

В графе (boost :: adjacency_list) у меня есть 3 разных типа вершин (реализованных с использованием std :: варианта) и в настоящее времянеориентированные ребра:

  1. Разъем (1)
  2. Switch (2)
  3. SwitchState (3) - (ON / OFF)

Типичная иерархия в моем графике выглядит следующим образом: 

(1a) - (2a) - (1b) - (1d) - (2b) - (1e)
        |                    |
       (3a)                 (3b)
        |                    |
       (1c)

Мне нужно найти все достижимые вершины из определенной начальной точки (например, 1a):

1a ->2a -> 1b -> 1d -> 2b -> 1e

Конечно, сразу же приходит на ум просто использование BFS или DFS!: -)

Однако: состояние вершины (2) (переключатель или реле) контролируется состоянием (булево) непосредственно связанной вершины (3).Это означает, что нет пути для перехода от (1a) к (1b) через вершину (2a), если (3a) является (скажем, ложным).И наконец: нельзя переходить от вершин типа (2) к вершинам (3).

Мой вопрос: есть ли у кого-нибудь предложения о том, как эффективно реализовать такой обход графа?Я реализовал это в простом C ++, используя множество векторов / карт и т. Д. И уже в DFS, но хотел бы переместить код в более высокую, более абстрактную (но, надеюсь, все еще эффективную) реализацию базового графа!

I 'Я не уверен, стоит ли мне:

  1. Использовать фильтр_графа и просто использовать BFS или DFS для обхода?
  2. Создать тогда под_граф в зависимости от состояния вершин типа 3 и применить BFS / DFS?
  3. Есть способ достичь этого "на лету" при поиске через BFS / DFSvisitor?
  4. Другое решение?

Полезные идеи приветствуются!

PS: код используется для имитации электрической сети - на всякий случай.

1 Ответ

0 голосов
/ 12 декабря 2018

Использовать фильтр_графа и просто использовать BFS или DFS для обхода?

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

Создайте подграф в зависимости от вершин типа 3затем укажите и примените BFS / DFS?

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

Есть способ достичь этого "налетать "во время поиска через BFS / DFSvisitor?

Я так думаю.Вы можете сделать так, чтобы посетитель воздействовал на событие «exam_edge» и отмечал нижнюю вершину на цветовой карте.Вы должны проверить документацию алгоритма, чтобы увидеть, задокументирована ли семантика цветовой карты.

Если это так, то это, по-видимому, наиболее оптимальное решение, хотя концептуально оно несколько сложнее, чем подход фильтрованного графика.

Если нет,Я дважды подумал, прежде чем основывать оптимизацию на недокументированных деталях реализации.Он может сломаться в будущих версиях или иметь неожиданные взаимодействия, например, со скрытыми особыми случаями в библиотеке.

...