#c #boost #graph
#c #boost #График
Вопрос:
Я использую графики Boost. Ребра моего графика имеют направленный смысл. Вот почему я выбрал ориентированный граф. Однако, когда я обхожу график, я обычно хочу сделать это, игнорируя направление. Однако я не нашел решения для обхода моих графиков, например, используя встроенный поиск в глубину.
Есть ли решение для этого, которое не требует создания копии всего графика?
Если нет: я не уверен, действительно ли мой график направлен природой. Может быть, мне следует использовать неориентированный график и добавить некоторые свойства «direction»? Однако я не уверен, как это сделать (простое прикрепление исходного / целевого vertex_descriptors к краю, очевидно, сломается при изменении графика). Есть ли возможность сделать это? Имеет ли это смысл вообще?
Спасибо
Комментарии:
1. Я не уверен в реализации Boost Graphs. Не могли бы вы немного описать свою первоначальную задачу?
2. Ну, в принципе, у меня есть узлы, которые представляют позиции в 3D-пространстве. Теперь к ребру от узла A к узлу B присоединена матрица преобразования, которая преобразуется из системы координат A в B. Мой алгоритм выполняет некоторую оптимизацию позиций узлов этого графика. В качестве шага предварительной обработки мне нужно обойти график, используя BFS / DFS / что угодно, и что-то вычислить — и меня не волнует направление.
Ответ №1:
Я понятия не имею о реализации Boost Graphs, но в вашем случае я вижу два варианта.
- Если ваши графики невелики, то вы могли бы сначала просто создать неориентированный график, вычислить свое «что-то», а затем создать направленную копию. Это должно занять
O(n)время и не повлияет на общую производительность. - Используйте ненаправленный граф и добавьте некоторую информацию о направлении на ребро, например, указатель на исходную вершину. Это решение может немного усложнить ваши алгоритмы, но вы избежите любого копирования данных и получите некоторую производительность на больших графиках.
Комментарии:
1. Спасибо за ваш ответ. Хм, а также для 1) Я, по сути, согласен с его решением. Однако это некрасиво, потому что по существу все алгоритмы могут быть выполнены без этого — информация есть. Но я думаю, мне придется рассмотреть это решение, если я не смогу найти другого способа сделать это. Что касается 2) Я уже предлагал это в исходном вопросе… но здесь вопрос в том, как это сделать в boost graph, поскольку вы не можете использовать исходный vertex_descriptor в edge (я знаю, вы написали, что не знакомы с BGL … может быть, у кого-то еще есть идея здесь)