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