Самый длинный путь между двумя вершинами одного типа - PullRequest
Новая
       12

Самый длинный путь между двумя вершинами одного типа

0 голосов
/ 20 марта 2020

У меня есть невзвешенный ориентированный граф, который содержит циклы. Я использую связанные свойства Boost-графа, где вершины имеют типы: 

enum   VertexType     {A B C};
struct VertexProperty { VertexType type };

using Graph_t = adjacency_list<vecS, vecS, bidirectionalS, VertexProperty, no_property>;
Graph_t g;

Я пытаюсь найти максимальное расстояние между вершинами одного типа (скажем, типа A), где путь, достигающий этого максимального расстояния, должен не содержат никаких вершин этого типа - за исключением, конечно, конечных точек.

Я думал об итерации по вершинам, и когда вершина имеет тип A, запускайте BFS с пользовательским посетителем: 

BGL_FORALL_VERTICES(v, g, Graph_t) {
    if (g[v].type == VertexType::A) {
        CustomVisitor vis;
        breadth_first_search(g, v, visitor(vis));
    }   
}

Посетитель должен остановиться, когда все «пути» из v содержат тип A, и вернуть максимальное расстояние. Однако я не уверен, как написать этому посетителю или есть более эффективное решение.

Спасибо.

...