Посетитель BGL DFS с приоритетной очередью - PullRequest
Новая
       49

Посетитель BGL DFS с приоритетной очередью

0 голосов
/ 12 августа 2011

У меня есть дерево (в смысле графа) представление дерева (в физическом смысле).Дерево представлено в виде списка смежности BGL, где каждая вершина содержит свойства радиуса и положения, т. Е. Мой граф определен в виде 

struct TreeVertexType {
  double radius;
  double position[3]; 
}

typedef adjacency_list<vecS, vecS, undirectedS, TreeVertexType> Tree;

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

Кажется, что посетитель DFS не поддерживает очередь с приоритетами, и поэтому мне было интересно, есть ли альтернативная формулировка поиска для получения этой информацииможет быть, через A *?

В качестве альтернативы я могу реализовать свой собственный алгоритм DFS путем сортировки вершин, но лучше использовать каркас BGL, если это возможно.

Спасибо

-Джон

Ответы [ 4 ]

3 голосов
/ 16 августа 2011

Во время DFS boost :: graph использует стек для проталкивания смежных вершин, которые будут извлечены позже в том порядке, в котором они выдвинуты.1004 *

в качестве обходного пути вы можете переопределить этот stack с тем же интерфейсом push () и pop (), и вы можете сделать это, когда любой Vertex вставляется в stackпросто отсортируйте элементы your stack таким образом, чтобы вершина с наибольшим радиусом всегда находилась сверху.

Другими словами, имитация интерфейса стека с вашей собственной очередью приоритетов.

Этоизбавит вас от боли написания вашей собственной DFS.

1 голос
/ 09 февраля 2012

Алгоритм поиска в ширину в BGL лучше подходит для вашего варианта использования;оно более общее, чем следует из названия.Вы можете подключить свою очередь с помощью методов push, top и pop, которые выполняют любой порядок, который вы хотите.

1 голос
/ 25 октября 2011

В итоге я следовал логике, предоставленной на http://www.boost.org/doc/libs/1_34_0/libs/graph/example/ordered_out_edges.cpp,, т. Е. 

template <class StoredEdge>
struct weight : public std::binary_function<StoredEdge, StoredEdge, bool>
{
    bool operator()(const StoredEdge &lhs, const StoredEdge &rhs) const {
        return boost::get(boost::edge_weight, lhs) > 
            boost::get(boost::edge_weight, rhs);
    }
};

struct weightS {};

namespace boost {
    template <class ValueType>
    struct container_gen<weightS, ValueType> {
        typedef std::multiset<ValueType, weight<ValueType> > type;
    };

    template <>
    struct parallel_edge_traits<weightS> {
        typedef disallow_parallel_edge_tag type;
    };
}

typedef adjacency_list<weightS, vecS, undirectedS, TreeVertexType> Tree;

Чтобы гарантировать, что out_edges были упорядочены в соответствии с радиусом, я просто определил вес ребра как средний радиусисходных и целевых вершин.

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

Кто-нибудь знает об альтернативном подходе?

Спасибо

-Джон

0 голосов
/ 16 августа 2011

Вы можете использовать setS вместо vecS, чтобы указать контейнер с упорядочением по этому конкретному атрибуту.Например, если вы хотите упорядочить ребра, вы должны использовать adjacency_list<setS, ...> и иметь оператор сравнения для TreeVertexType.

...