Простой алгоритм удаления цикла для диаграммы BGL

Question

Моя проблема должна быть довольно простой, учитывая график (BGL adjacency_list), есть ли простой алгоритм для удаления циклов? Моя первая попытка состояла в том, чтобы использовать посетителя DFS для обнаружения края, который закроет цикл, а затем удалит его, но я не смог его правильно реализовать.

Любые предложения? Примеры кода были бы лучшими.

Answer 1

Boost is great. Он имеет метод depth_first_search, который принимает посетителя. You can see more information about it here.

Все, что вам нужно сделать, это реализовать посетитель так:

class CycleTerminator : public boost::dfs_visitor<> { 
    template <class Edge, class Graph> 
    void back_edge(Edge e, Graph& g) { 
     //implement 
    } 
}; 

вспоминания, конечно, что задняя кромка кромка, которая закрывает цикл на графике.

Answer 2

Это простая DFS, как вы сказали. Каждый раз, когда вы приходите к узлу, который вы посещали раньше, есть цикл. Просто удалите последний край.

Псевдокод на каком-либо конкретном языке.

void walk(current_node, previous_node) 
    if visited[current_node] 
     remove edge between current_node and previous_node 
     return 
    end 

    visited[current_node] = true 
    for (each adjacent node) 
     walk(adjacent_node, current_node) 
    end 
end