Boost logo

Boost :

From: Rozgonyi Szabolcs (rszabolcs_at_[hidden])
Date: 2002-10-23 16:11:52


Hello,
I would like to record the predecessor information to
somewhere (here
I tried use std::map for this), but this implementation
doesn't work.
The aim is to know the "parent" of every vertex in the
BFS-tree after
BFS.
If you can correct this, please inform me as fast as you can. :)
Thank you,
Szabolcs ROZGONYI

#include <boost/config.hpp>
#include <algorithm>
#include <vector>
#include <utility>
#include <iostream>
#include <map>
#include <boost/graph/visitors.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/property_map.hpp>

typedef boost::property<boost::vertex_index1_t,std::string,
        boost::property<boost::vertex_index2_t,std::string>
> VertexProperty;

typedef boost::adjacency_list<boost::listS,
                              boost::listS,
                              boost::directedS,
                              VertexProperty> EquVarGraph2;
                              
typedef boost::graph_traits<EquVarGraph2>::vertex_iterator
vertex_iter;
typedef EquVarGraph2::vertex_descriptor Vertex;

EquVarGraph2 G;

boost::property_map<EquVarGraph2,boost::vertex_index1_t>::type
  index1=boost::get(boost::vertex_index1_t(),G);

boost::property_map<EquVarGraph2,boost::vertex_index2_t>::type
  index2=boost::get(boost::vertex_index2_t(),G);

int main()
{
  Vertex a,b,c,d,e;

  a=boost::add_vertex(G);index1[a]="a";index2[a]="aa";
  b=boost::add_vertex(G);index1[a]="b";index2[a]="bb";
  c=boost::add_vertex(G);index1[a]="c";index2[a]="cc";
  d=boost::add_vertex(G);index1[a]="d";index2[a]="dd";
  e=boost::add_vertex(G);index1[a]="e";index2[a]="ee";
  
 
boost::add_edge(a,c,G);boost::add_edge(b,b,G);boost::add_edge(b,d,G);
 
boost::add_edge(b,e,G);boost::add_edge(c,b,G);boost::add_edge(c,d,G);
 
boost::add_edge(c,e,G);boost::add_edge(d,b,G);boost::add_edge(d,e,G);
  boost::add_edge(e,a,G);boost::add_edge(e,b,G);

Vertex s = a;
//********** the probles is here
  std::map<Vertex,Vertex> p;
  boost::breadth_first_search(G,s,
     boost::visitor(boost::make_bfs_visitor(
       boost::record_predecessors(
         p.begin(),boost::on_tree_edge()
       ))));
//***********

  std::pair<vertex_iter,vertex_iter> vp;
  for (vp=boost::vertices(G);vp.first!=vp.second;++vp.first)
    std::cout << index1[*vp.first] << ": " <<
index1[p[*vp.first]] << std::endl;
}


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk