Performing a Depth first search and breadth first search in Boost

Question

I am pretty much new to both Boost library and c++ language.

I have created a graph using Boost and added vertex and edges and output the graph in graphviz.

Now I would like to perform a breadth first and depth first search from a vertex to all the other vertex in the graph.

The result should should be the shortest path from start vertex to other vertex in the graph.

How can I accomplish this in Boost? Any help would be appreciated.

Thanks a ton in advance.

I have also added my source code for your reference.

#include "stdafx.h"
#include <iostream>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/pending/indirect_cmp.hpp>
#include <boost/range/irange.hpp>
#include <boost/graph/graphviz.hpp>

int main()
{
            using namespace std;
            using namespace boost;


        // Property types
            typedef property<vertex_name_t, std::string,
            property<vertex_index2_t, int> > VertexProperties;

        // Graph type
            typedef adjacency_list<vecS, vecS, undirectedS,
            VertexProperties> Graph;

        // Graph instance
            Graph g;

        // Property accessors
            property_map<Graph, vertex_name_t>::type
            profinet_name = get(vertex_name, g);
            property_map<Graph, vertex_index2_t>::type
            profinet_index2 = get(vertex_index2, g);

        // Create the vertices
            typedef graph_traits<Graph>::vertex_descriptor Vertex;
            Vertex u1;
            u1 = add_vertex(g);
            profinet_name[u1] = "Profinet 1";
            profinet_index2[u1] = 1;

            Vertex u2;
            u2 = add_vertex(g);
            profinet_name[u2] = "Profinet 2";
            profinet_index2[u2] = 2;

            Vertex u3;
            u3 = add_vertex(g);
            profinet_name[u3] = "Profinet 3";
            profinet_index2[u3] = 3;

            Vertex u4;
            u4 = add_vertex(g);
            profinet_name[u4] = "Profinet 4";
            profinet_index2[u4] = 4;

            Vertex u5;
            u5 = add_vertex(g);
            profinet_name[u5] = "Profinet 5";
            profinet_index2[u5] = 5;

            Vertex u6;
            u6 = add_vertex(g);
            profinet_name[u6] = "Profinet 6";
            profinet_index2[u6] = 6;


        // Create the edges
            typedef graph_traits<Graph>::edge_descriptor Edge;
            Edge e1;
            e1 = (add_edge(u1, u2, g)).first;

            Edge e2;
            e2 = add_edge(u1, u4, g).first;

            Edge e3;
            e3 = (add_edge(u1, u6, g)).first;

            Edge e4;
            e4 = (add_edge(u2, u3, g)).first;

            Edge e5;
            e5 = (add_edge(u2, u4, g)).first;

            Edge e6;
            e6 = (add_edge(u2, u5, g)).first;

            Edge e7;
            e7 = (add_edge(u3, u6, g)).first;

            Edge e8;
            e8 = (add_edge(u6, u5, g)).first;

            Edge e9;
            e9 = (add_edge(u5, u4, g)).first;


            write_graphviz(cout, g);

            return 0;


}

Answer 1

If you want to perform a shortest path from a to b, you should rather use the Dijkstra algorithm.

A BFS is theoreticaly better if all your edges have a cost of 1, but in boost::graph it requires some effort (it is just an empty shell and you need to implement your own visitors in order to store the distance from the origins).

However, in order to use the dijkstra, you need to add Edge properties with weights on the edges and use it in the algorithm.

In the following example http://www.boost.org/doc/libs/1_51_0/libs/graph/example/dijkstra-example.cpp you can unwind the shortest path from s to t by looking at the predecessors map : p[t] is the node before t in the shortest path.

I hope this is enough :)