c++ - print - depth first search java




How to create a C++ Boost undirected graph and traverse it in depth first search(DFS) order? (6)

How to create a C++ Boost undirected graph and traverse it in depth first search (DFS) order?


I faced the same problem, but compared to the answer provided by user1252091 my vertex type is a struct that doesn't include an integer that can be used to create a vertex_index_map, therefore the line

breadth_first_search(graph, a, boost::visitor(vis).vertex_index_map(get(boost::vertex_bundle,graph)));

wouldn't work in my case. Eventually I figured out how to create an external vertex_index_map (thanks also to this answer) and pass it to the breadth_first_search function. Here is a working example in case it helps others:

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <iostream>

struct Person
{
    std::string Name;
    unsigned int YearBorn;
};

typedef boost::adjacency_list <boost::vecS, boost::hash_setS, boost::bidirectionalS, Person, boost::no_property > FamilyTree;
typedef boost::graph_traits<FamilyTree>::vertex_descriptor  Vertex;
typedef boost::graph_traits<FamilyTree>::edge_descriptor    Edge;

template <class Graph>
class BfsVisitor : public boost::default_bfs_visitor
{
public:
    typedef typename boost::graph_traits<Graph>::vertex_descriptor VertexDescriptor;
    typedef typename boost::graph_traits<Graph>::edge_descriptor   EdgeDescriptor;

    BfsVisitor(std::vector<VertexDescriptor>& nodesVisited)
    : m_nodesVisited(nodesVisited){}

    void tree_edge(EdgeDescriptor e, const Graph& g) const
    {
        VertexDescriptor u = source(e, g);
        VertexDescriptor v = target(e, g);
        m_nodesVisited.push_back(v);
    }

private:
    std::vector<VertexDescriptor>& m_nodesVisited;
};


const Person Abe_Simpson        {"Abe_Simpson", 0};
const Person Mona_Simpson       { "Mona_Simpson", 0};
const Person Herb_Simpson       { "Herb_Simpson", 0};
const Person Homer_Simpson      { "Homer_Simpson", 0};

const Person Clancy_Bouvier     { "Clancy_Bouvier", 0};
const Person Jacqueline_Bouvier { "Jacqueline_Bouvier", 0};
const Person Marge_Bouvier      { "Marge_Bouvier", 0};
const Person Patty_Bouvier      { "Patty_Bouvier", 0};
const Person Selma_Bouvier      { "Selma_Bouvier", 0};

const Person Bart_Simpson       { "Bart_Simpson", 0};
const Person Lisa_Simpson       { "Lisa_Simpson", 0};
const Person Maggie_Simpson     { "Maggie_Simpson", 0};
const Person Ling_Bouvier       { "Ling_Bouvier", 0};





int main(void)
{
    std::cout << __FUNCTION__ << "\n";

    FamilyTree g;


    // nodes
    auto v_Abe_Simpson = boost::add_vertex(Abe_Simpson,g);
    auto v_Mona_Simpson = boost::add_vertex(Mona_Simpson,g);
    auto v_Herb_Simpson = boost::add_vertex(Herb_Simpson,g);
    auto v_Homer_Simpson = boost::add_vertex(Homer_Simpson,g);

    auto v_Clancy_Bouvier = boost::add_vertex(Clancy_Bouvier,g);
    auto v_Jacqueline_Bouvier = boost::add_vertex(Jacqueline_Bouvier,g);
    auto v_Marge_Bouvier = boost::add_vertex(Marge_Bouvier,g);
    auto v_Patty_Bouvier = boost::add_vertex(Patty_Bouvier,g);
    auto v_Selma_Bouvier = boost::add_vertex(Selma_Bouvier,g);

    auto v_Bart_Simpson = boost::add_vertex(Bart_Simpson,g);
    auto v_Lisa_Simpson = boost::add_vertex(Lisa_Simpson,g);
    auto v_Maggie_Simpson = boost::add_vertex(Maggie_Simpson,g);
    auto v_Ling_Bouvier = boost::add_vertex(Ling_Bouvier,g);

    // connections
    boost::add_edge(v_Abe_Simpson, v_Herb_Simpson, g);
    boost::add_edge(v_Abe_Simpson, v_Homer_Simpson, g);
    boost::add_edge(v_Mona_Simpson, v_Herb_Simpson, g);
    boost::add_edge(v_Mona_Simpson, v_Homer_Simpson, g);

    boost::add_edge(v_Clancy_Bouvier, v_Marge_Bouvier, g);
    boost::add_edge(v_Clancy_Bouvier, v_Patty_Bouvier, g);
    boost::add_edge(v_Clancy_Bouvier, v_Selma_Bouvier, g);
    boost::add_edge(v_Jacqueline_Bouvier, v_Marge_Bouvier, g);
    boost::add_edge(v_Jacqueline_Bouvier, v_Patty_Bouvier, g);
    boost::add_edge(v_Jacqueline_Bouvier, v_Selma_Bouvier, g);

    boost::add_edge(v_Homer_Simpson, v_Bart_Simpson, g);
    boost::add_edge(v_Homer_Simpson, v_Lisa_Simpson, g);
    boost::add_edge(v_Homer_Simpson, v_Maggie_Simpson, g);
    boost::add_edge(v_Marge_Bouvier, v_Bart_Simpson, g);
    boost::add_edge(v_Marge_Bouvier, v_Lisa_Simpson, g);
    boost::add_edge(v_Marge_Bouvier, v_Maggie_Simpson, g);

    boost::add_edge(v_Selma_Bouvier, v_Ling_Bouvier, g);


    typedef std::map<Vertex, size_t>IndexMap;
    IndexMap mapIndex;
    boost::associative_property_map<IndexMap> propmapIndex(mapIndex);
    size_t i=0;
    FamilyTree::vertex_iterator vi, vi_end;
    for (boost::tie(vi, vi_end) = boost::vertices(g); vi != vi_end; ++vi)
    {
        boost::put(propmapIndex, *vi, i++);
    }


    for (boost::tie(vi, vi_end) = boost::vertices(g); vi != vi_end; ++vi)
    {
        Vertex vParent = *vi;

        std::vector<Vertex> vertexDescriptors;
        BfsVisitor<FamilyTree> bfsVisitor(vertexDescriptors);
        breadth_first_search(g, vParent, visitor(bfsVisitor).vertex_index_map(propmapIndex));


        std::cout << "\nDecendants of " << g[vParent].Name << ":\n";
        for (auto v : vertexDescriptors)
        {   
            Person p = g[v];
            std::cout << p.Name << "\n";
        }   
    }

    getchar();
    return 0;
}

Okay, I've compiled the Time and Space complexities of basic operations on graphs.
The image below should be self-explanatory.
Notice how Adjacency Matrix is preferable when we expect the graph to be dense, and how Adjacency List is preferable when we expect the graph to be sparse.
I've made some assumptions. Ask me if a complexity (Time or Space) needs clarification. (For example, For a sparse graph, I've taken En to be a small constant, as I've assumed that addition of a new vertex will add only a few edges, because we expect the graph to remain sparse even after adding that vertex.)

Please tell me if there are any mistakes.


Yes, do breadth_first_search() starting from u.

FOR every vertex i meet
  IF i==v: BREAK
  record predecessor of i as i.p

To find the shortest path, start from v:

PRINT_PATH(u, v)
  IF v==u
    print u
  ELSEIF v.p==NIL
    print 'no path from u to v exists'
  ELSE PRINT_PATH(u, v.p)
    print v

You need to use a minimum spanning tree: search algorithm. It's quite a simple straightforward greedy algorithm.


How to traverse graph in boost use BFS

You can see here a list of the overloads of breadth_first_search. If you don't want to specify every one of the parameters you need to use the named-parameter version. It would look like this:

breadth_first_search(graph, a, boost::visitor(bfs_visitor));

This would work as is if you had used vecS as your VertexList storage in your graph definition or if you had constructed and initialized an internal vertex_index property map. Since you are using hash_setS you need to change the invocation to:

breath_first_search(graph, a, boost::visitor(bfs_visitor).vertex_index_map(my_index_map));

You are already using an index map in your uint32_t bundled property. You can use get(boost::vertex_bundle, graph) to access it.

There was also a problem with your visitor. You should derive it from boost::default_bfs_visitor and the graph_t parameter of your member functions needs to be const qualified.

Full code:

#include <stdint.h>
#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>

typedef boost::adjacency_list<boost::vecS, boost::hash_setS, boost::undirectedS, uint32_t, uint32_t, boost::no_property> graph_t;


struct my_visitor : boost::default_bfs_visitor{

    void initialize_vertex(const graph_t::vertex_descriptor &s, const graph_t &g) const {
      std::cout << "Initialize: " << g[s] << std::endl;
    }
    void discover_vertex(const graph_t::vertex_descriptor &s, const graph_t &g) const {
      std::cout << "Discover: " << g[s] << std::endl;
    }
    void examine_vertex(const graph_t::vertex_descriptor &s, const graph_t &g) const {
      std::cout << "Examine vertex: " << g[s] << std::endl;
    }
    void examine_edge(const graph_t::edge_descriptor &e, const graph_t &g) const {
      std::cout << "Examine edge: " << g[e] << std::endl;
    }
    void tree_edge(const graph_t::edge_descriptor &e, const graph_t &g) const {
      std::cout << "Tree edge: " << g[e] << std::endl;
    }
    void non_tree_edge(const graph_t::edge_descriptor &e, const graph_t &g) const {
      std::cout << "Non-Tree edge: " << g[e] << std::endl;
    }
    void gray_target(const graph_t::edge_descriptor &e, const graph_t &g) const {
      std::cout << "Gray target: " << g[e] << std::endl;
    }
    void black_target(const graph_t::edge_descriptor &e, const graph_t &g) const {
      std::cout << "Black target: " << g[e] << std::endl;
    }
    void finish_vertex(const graph_t::vertex_descriptor &s, const graph_t &g) const {
      std::cout << "Finish vertex: " << g[s] << std::endl;
    }
  };

int main() {
  graph_t graph(4);
  graph_t::vertex_descriptor a = boost::vertex(0, graph);
  graph_t::vertex_descriptor b = boost::vertex(1, graph);
  graph_t::vertex_descriptor c = boost::vertex(2, graph);
  graph_t::vertex_descriptor d = boost::vertex(3, graph);
  graph[a] = 0;
  graph[b] = 1;
  graph[c] = 2;
  graph[d] = 3;
  std::pair<graph_t::edge_descriptor, bool> result = boost::add_edge(a, b, 0, graph);
  result = boost::add_edge(a, c, 1, graph);
  result = boost::add_edge(c, b, 2, graph);

  my_visitor vis;

  breadth_first_search(graph, a, boost::visitor(vis).vertex_index_map(get(boost::vertex_bundle,graph)));
  return 0;
} 

Using Boost's graph breadth_first_search() to find a path in an unweighted, undirected graph

You should use one of the shortest path algorithms, Dijkstra Shortest Path being the most suitable since you need to find the path between just two vertexes. There is an example for its usage in the boost distribution. There are several options for obtaining output from that function: either by supplying a distance property map or build a predecessor map or writing a custom visitor.





boost-graph