Geek Answers Handbook

Simple loop removal algorithm for BGL graphics

My problem should be pretty simple, given the graph (BGL adjacency_list), is there a simple algorithm for deleting loops? My first attempt was to use the DFS visitor to detect an edge that would close the loop and then delete it, but I could not implement it correctly.

Any suggestions? Code examples would be better.

0
source share
2 answers

The acceleration is great. It has a method depth_first_searchthat takes a visitor. You can see more information about this here .

All you have to do is implement the visitor as follows:

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

, , - , .

+5

DFS, . , node, , . .

- .

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
0

More articles:


All Articles