BGL 範例更正! 修正BFS DFS 及增加 Edge Property

// BGL_experiment.cpp : Defines the entry point for the console application.
//
// for DFS
#include "depth_first_search.hpp"  // Modify by myself
//#include "stdafx.h"
#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>

 

/*
目標 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;
 boost::vertex_color_t color_t; // usage unknown :P
};

struct EdgeProperties
{
 EdgeProperties() {}
 EdgeProperties(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
};

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;

 unsigned int* pMatrix;
 // constructor
 first_dfs_visitor(FirstContainer tmap, T & t, unsigned int* pMat):m_map(tmap), m_time(t)
 {
  pMatrix = pMat;
 }

 // override the visitor function
 // more function to find in depth_first_search.hpp

 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++);
  pMatrix[(unsigned int)m_time -1] = (unsigned int) u;
 }
 
 template < typename Vertex, typename Graph >
 void finish_vertex(Vertex u, const Graph& g)
 {
  
 }
 
};

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;

 unsigned int* pMatrix;

 // constructor
 first_bfs_visitor(FirstContainer tmap, T & t, unsigned int* pMat):m_map(tmap), m_time(t)
 {
  pMatrix = pMat;
 }

 // override the visitor function
 // more function to find in breadth_first_search.hpp
 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_vertex(Vertex u, const Graph & g)
 {
  put(m_map, u, m_time++);
  pMatrix[(unsigned int)m_time -1] = (unsigned int) u;
 }

};

int main(int, char*[])
{

 typedef adjacency_list<vecS,
         vecS,
         directedS,
         VertexProperties,
         EdgeProperties
         > 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);

 property_map<MyGraphType, std::size_t EdgeProperties::*>::type
  getEid = get(&EdgeProperties::index, GraphExp);
 property_map<MyGraphType, std::string EdgeProperties::*>::type
  getEname = get(&EdgeProperties::name, GraphExp);

 
 boost::graph_traits < MyGraphType >::vertex_descriptor Sidius, Vader, KusoKing, ObiLee, PrinceBala, SkyJoger;

 boost::graph_traits < MyGraphType >::edge_descriptor S_V, S_K, V_O, K_O, K_P, O_S;
 //the bool flag returned is false and the returned edge descriptor points to the already existing edge
 std::pair<boost::graph_traits < MyGraphType >::edge_descriptor, bool> ResultOfAddEdge;

 // 把 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
 ResultOfAddEdge = add_edge( Sidius, Vader, GraphExp);
 S_V = ResultOfAddEdge.first;
 ResultOfAddEdge = add_edge( Sidius, KusoKing, GraphExp);
 S_K = ResultOfAddEdge.first;
 ResultOfAddEdge = add_edge( Vader, ObiLee, GraphExp);
 V_O = ResultOfAddEdge.first;
 ResultOfAddEdge = add_edge( KusoKing, ObiLee, GraphExp);
 K_O = ResultOfAddEdge.first;
 ResultOfAddEdge = add_edge( KusoKing, PrinceBala, GraphExp);
 K_P = ResultOfAddEdge.first;
 ResultOfAddEdge = add_edge( ObiLee, SkyJoger, GraphExp);
 O_S = ResultOfAddEdge.first;

 // 嘗試印出現在的 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<< " " << getEid[*e_i] << getEname[*e_i] <<" ";  // test ok
   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 >::vertex_descriptor > dtime(num_vertices(GraphExp));
 graph_traits < MyGraphType >::vertices_size_type time = 0;
 unsigned int* p_bfs_result = new unsigned int[num_vertices(GraphExp)];

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

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

 std::cout << "BFS discovery: ";
 for (int i = 0; i < b_vis.m_time; ++i)
  std::cout << getname[p_bfs_result[i]] << getid[p_bfs_result[i]] << " ";//std::cout << getname[dtime[i]] << dtime[i] << " ";
 std::cout << std::endl;

 delete [] p_bfs_result;

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

 

 std::vector < graph_traits < MyGraphType >::vertex_descriptor > ftime(num_vertices(GraphExp));
 time = 0;
 unsigned int* p_dfs_result = new unsigned int[num_vertices(GraphExp)];

 first_dfs_visitor < graph_traits < MyGraphType >::vertex_descriptor * > d_vis(&ftime[0], time, p_dfs_result);

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

 std::cout << "DFS discovery: ";
 for ( i = 0; i < d_vis.m_time; ++i)
  std::cout << getname[p_dfs_result[i]] << getid[p_dfs_result[i]] << " ";//std::cout << getname[ftime[i]] << ftime[i] << " ";
 std::cout << std::endl;
 delete [] p_dfs_result;

 // 嘗試 delete 一些 edge 跟 vertex
 // void remove_edge(vertex_descriptor u, vertex_descriptor v,adjacency_list& g)

 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;
}