分享一下 Boost Graph Library (BGL) 的心得

貼一段自己寫的 BGL example，服用之後可增一星期功力，免於遭受BGL Document 裡面一大堆 template 的騷擾。內容包擴 directed graph，BFS，DFS，其他的東西就請看倌自己去boost.org翻文件了。

 

 

#include <boost/config.hpp>
#include <iostream>
#include <vector>
#include <utility>
#include <string>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp> // for boost::make_list
#include <boost/property_map.hpp>
#include <boost/graph/graph_traits.hpp>

// for BFS
#include <boost/graph/breadth_first_search.hpp>
#include <boost/pending/indirect_cmp.hpp>
#include <boost/pending/integer_range.hpp>

// for DFS
#include <boost/graph/depth_first_search.hpp>

/*
目標 tree (edge direction 全向下)

        0 Sidius
         /   \
    1 Vader   2 KusoKing
         \   /    \
      3 Obi Lee    4 Prince Bala
         /
    5 SkyJoger

1. 建構 tree
2. 進行 BFS DFS
3. 拆tree
*/

// 記得 using namespace !
using namespace boost;
using namespace std;

struct VertexProperties
{
 // add_edge() 會使用此建構子
 VertexProperties() {}
 VertexProperties(int i, const std::string& n) : index(i) ,name(n) { }
 std::size_t index;
 std::string name;

 boost::default_color_type color; // usage unknown :P
 boost::vertex_color_t color_t; // usage unknown :P
};

template < typename FirstContainer >
    class first_bfs_visitor : public default_bfs_visitor
{
 
public:

 // member data 
 FirstContainer m_map;
 typename property_traits < FirstContainer >::value_type & m_time;
 typedef typename property_traits < FirstContainer >::value_type T;
 
 //手賤型 constructor
 first_bfs_visitor(FirstContainer tmap, T & t):m_map(tmap), m_time(t) { }

 // override the visitor function
 template < typename Vertex, typename Graph >
  void discover_vertex(Vertex u, const Graph & g) const
 {
  put(m_map, u, m_time++);
 }

};

template < typename FirstContainer >
    class first_dfs_visitor : public default_dfs_visitor
{

public:

 // member data 
 FirstContainer m_map;
 typename property_traits < FirstContainer >::value_type & m_time;
 typedef typename property_traits < FirstContainer >::value_type T;

 //手賤型 constructor
 first_dfs_visitor(FirstContainer tmap, T & t):m_map(tmap), m_time(t) { }

 // override the visitor function

 template < typename Vertex, typename Graph >
 void initialize_vertex(Vertex u, const Graph& g)
 {

 }
 template < typename Vertex, typename Graph > 
 void start_vertex(Vertex u, const Graph& g)
 {
  
 }
 template < typename Vertex, typename Graph >
 void discover_vertex(Vertex u, const Graph & g) const
 {
  put(m_map, u, m_time++);
 }
 /*
 template < typename Vertex, typename Graph >
 void examine_edge(Edge u, const Graph& g)
 {
   
 }
 template < typename Vertex, typename Graph >
 void tree_edge(Edge u, const Graph& g)
 {
   
 }
 template < typename Vertex, typename Graph >
 void back_edge(Edge u, const Graph& g)
 {
    
 }
 template < typename Vertex, typename Graph >
 void forward_or_cross_edge(Edge u, const Graph& g)
 {
   
 }
 */
 template < typename Vertex, typename Graph >
 void finish_vertex(Vertex u, const Graph& g)
 {
   
 }
};

 

int main(int, char*[])
{

 typedef adjacency_list<vecS,
         vecS,
         directedS,
         VertexProperties
         > MyGraphType;
 MyGraphType GraphExp;

 property_map<MyGraphType, std::size_t VertexProperties::*>::type
  getid = get(&VertexProperties::index, GraphExp);
 property_map<MyGraphType, std::string VertexProperties::*>::type
  getname = get(&VertexProperties::name, GraphExp);
 
 boost::graph_traits < MyGraphType >::vertex_descriptor Sidius, Vader, KusoKing, ObiLee, PrinceBala, SkyJoger;

 // 把 vertex_descriptor 塞入 graph , 並得到 graph_trait 的vertex_description
 Sidius = add_vertex(VertexProperties(0,"Sidius"), GraphExp);
 Vader = add_vertex(VertexProperties(1,"Vader"), GraphExp); 
 KusoKing = add_vertex(VertexProperties(2,"KusoKing"), GraphExp); 
 ObiLee = add_vertex(VertexProperties(3,"Obi Lee"), GraphExp);
 PrinceBala = add_vertex(VertexProperties(4,"Prince Bala"), GraphExp);
 SkyJoger = add_vertex(VertexProperties(5,"SkyJoger"), GraphExp);

 // 目前無須儲存 edge descripter
 add_edge( Sidius, Vader, GraphExp);
 add_edge( Sidius, KusoKing, GraphExp);
 add_edge( Vader, ObiLee, GraphExp);
 add_edge( KusoKing, ObiLee, GraphExp);
 add_edge( KusoKing, PrinceBala, GraphExp);
 add_edge( ObiLee, SkyJoger, GraphExp);

 // 嘗試印出現在的 graph tree
 graph_traits< MyGraphType >::vertex_iterator v_i, v_end;
 v_i = vertices(GraphExp).first;
 v_end = vertices(GraphExp).second;

 graph_traits< MyGraphType >::out_edge_iterator e_i, e_end;

 for(; v_i!=v_end; ++v_i)
 {
  std::cout << getid[*v_i] << getname[*v_i] <<" ";

  boost::tie(e_i,e_end) = out_edges(*v_i, GraphExp);
  for (; e_i != e_end; ++e_i)
  {
   std::cout<< getid[target(*e_i, GraphExp)] << getname[target(*e_i, GraphExp)] <<" ";
  } 
  std::cout << std::endl;
  
 }
 std::cout << std::endl;

 
 //BFS
 // a vector to hold the discover time property for each vertex
 std::vector < graph_traits < MyGraphType >::vertices_size_type > dtime(num_vertices(GraphExp));
 graph_traits < MyGraphType >::vertices_size_type time = 0;

 first_bfs_visitor < graph_traits < MyGraphType >::vertices_size_type * > b_vis(&dtime[0], time);

 breadth_first_search(GraphExp, Sidius, visitor(b_vis));

 std::cout << "BFS discovery: ";
 for (int i = 0; i < num_vertices(GraphExp); ++i)
  std::cout << getname[dtime[i]] << dtime[i] << " ";
 std::cout << std::endl;

 //DFS
 //property_map<MyGraphType, vertex_color_t >::type cmap = get( &VertexProperties::color_t, GraphExp);
 
 

 std::vector < graph_traits < MyGraphType >::vertices_size_type > ftime(num_vertices(GraphExp));
 time = 0;
 
 first_dfs_visitor < graph_traits < MyGraphType >::vertices_size_type * > d_vis(&ftime[0], time);

 

 depth_first_search(GraphExp , d_vis, get( &VertexProperties::color, GraphExp), Sidius);

 

 std::cout << "DFS discovery: ";
 for ( i = 0; i < num_vertices(GraphExp); ++i)
  std::cout << getname[ftime[i]] << ftime[i] << " ";
 std::cout << std::endl;
 

 // 嘗試 delete 一些 edge 跟 vertex
 // void remove_edge(vertex_descriptor u, vertex_descriptor v,adjacency_list& g)
 // 沒存 edge descriptor , 所以用這個
 remove_edge( Sidius, KusoKing, GraphExp );
 remove_edge( KusoKing, PrinceBala, GraphExp );

 for(v_i = vertices(GraphExp).first; v_i!=v_end; ++v_i)
 {
  std::cout << getid[*v_i] << getname[*v_i] <<" ";

  boost::tie(e_i,e_end) = out_edges(*v_i, GraphExp);
  for (; e_i != e_end; ++e_i)
  {
   std::cout<< getid[target(*e_i, GraphExp)] << getname[target(*e_i, GraphExp)] <<" ";
  } 
  std::cout << std::endl;

 }
 std::cout << std::endl;

 //void remove_vertex(vertex_descriptor u, adjacency_list& g)
 remove_vertex( KusoKing, GraphExp );

 v_end = vertices(GraphExp).second;
 for(v_i = vertices(GraphExp).first; v_i!=v_end; ++v_i)
 {
  std::cout << getid[*v_i] << getname[*v_i] <<" ";

  boost::tie(e_i,e_end) = out_edges(*v_i, GraphExp);
  for (; e_i != e_end; ++e_i)
  {
   std::cout<< getid[target(*e_i, GraphExp)] << getname[target(*e_i, GraphExp)] <<" ";
  } 
  std::cout << std::endl;

 }
 std::cout << std::endl;

 return 0;
}