I started testing graph acceleration classes. To do this, I created a simple example, as shown below. When passing a graph through a node depth search algorithm that I did not add. Here is the code:
#include <boost\graph\adjacency_list.hpp> #include <boost\graph\depth_first_search.hpp> #include <iostream> typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS> GraphType; typedef boost::graph_traits<GraphType>::vertex_descriptor VertexType; class VertexVisitor : public boost::default_dfs_visitor { public: void discover_vertex(VertexType v, GraphType g) { std::cout << v << std::endl; } }; int main() { GraphType g; boost::add_edge(1,2,g); boost::add_edge(1,3,g); boost::add_edge(2,3,g); boost::add_edge(1,4,g); boost::add_edge(4,5,g); VertexVisitor vis; boost::depth_first_search(g, boost::visitor(vis)); return 0; }
Result of this
0 1 2 3 4 5
But where does 0 come from, have I ever added it? Is this some kind of dummy node? But if so, why is he being visited bypass and how can I achieve the desired behavior?
EDIT 1:. Having tried what PlasmaHH suggested, and debugging the forcing code that boost: add_edge causes a change in the size of the graph vertex structure. Thus, the number of elements is added and visited by the search algorithm, although they are not related to each other. Btw: I am using boost 1.47.
EDIT 2:. He showed that depth_first_search behaves (with the exception of its native difference) different from the breadth_first_search algorithm, since DFS crosses all nodes on the graph, even if they are not connected. I don’t see anything good in it, because I just want to find the path from one node to another related to this, but normal. As mentioned earlier, the solution to my problem was to use the BFS algorithm, which does not go through all the subgraphs. For those interested, I add a litte example:
#include <boost\graph\adjacency_list.hpp> #include <boost\graph\depth_first_search.hpp> #include <boost\graph\breadth_first_search.hpp> #include <iostream> typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS> GraphType; typedef boost::graph_traits<GraphType>::vertex_descriptor VertexType; class DFSVertexVisitor : public boost::default_dfs_visitor { public: void discover_vertex(GraphType::vertex_descriptor v, GraphType g) { std::cout << v << std::endl; } }; class BFSVertexVisitor : public boost::default_bfs_visitor { public: void discover_vertex(GraphType::vertex_descriptor v, GraphType g) { std::cout << v << std::endl; } }; int main(int argc, char *argv[]) { GraphType g; boost::add_edge(1, 2, g); boost::add_edge(2, 3, g); boost::add_edge(1, 3, g); boost::add_edge(4, 5, g); std::cout << "Performing BFS" << std::endl; BFSVertexVisitor bfsVisitor; boost::breadth_first_search(g, boost::vertex(1, g), boost::visitor(bfsVisitor)); std::cout << "Performing DFS" << std::endl; DFSVertexVisitor dfsVisitor; boost::depth_first_search(g, boost::visitor(dfsVisitor).root_vertex(1)); return 0; }
Please note that nodes 4 and 5 are not connected to nodes 1, 2 and 3!
Conclusion:
Performing BFS 1 2 3 Performing DFS 1 2 3 0 4 5
EDIT 3: I had to think again. The numbers i associated with add_edge are not the nodes themselves, but only their indices, as soon as nm. So just adding edges is not the final solution, I think, since deleting one of the vertices does not work properly.