Boost Graph Library - adjacency list

tree 쓰려고 stl 문 두드렸더니 BGL 로 가라고 한다.

가이드 친절히 쓰여있지만 정리해보고 가자.

 

The Boost Graph Library - 1.66.0

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu , C++ Coding Standards This is the documentation for an old version of Boost. Click here to view this page for the latest version. The Boost Graph...

www.boost.org

0. 기타

​

stl 을 재료로 만든게 bgl.

bgl은 adjacency list, adjacency matrix, edge list 자료구조를 제공함.

애네들을 만들때 템플릿으로 조정 가능.

그래프의 두 축인 vertex, edge 를 위 자료구조에 넣으면 그래프 완성.

일단 이 글에선 adjaceny list 로 만든 graph 튜토리얼을 정리할 것임.

​

bgl 사용하는 건 파일 받아서 include 만 하면 됨.

다만 include 잘 되도록 additional directory 설정을 해둬야함.

​

1. 생성 준비

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

#include <../../boost/graph/graph_traits.hpp> #include <../../boost/graph/adjacency_list.hpp> ​ struct MonsterType { MonsterType() : name("monster"), code(-1) {} MonsterType(const std::string& name, const int& code) : name(name), code(code) {} std::string name; int code; }; struct Evolution_Condition { Evolution_Condition() : lv(-1), item(-1) {} Evolution_Condition(const int& lv, const int& itme) : lv(lv), item(item) {} int lv; int item; };

vertex 정보와 index 정보는 BGL 에서 두가지 방법으로 구성할 수 있는데, 위처럼 그냥 struct 나 class 로 하는걸 추천한다. 다른 방법은 튜토리얼이나 구버전에서 나돌아다닌다고 한다.

1 2	typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, MonsterType, Evolution_Condition> Graph;

adjacency_list 생성에 필요한 템플릿은 7개 인자가 있다. 기니까 typedef 로 사용하라고 한다. 그리고 자주 사용되는 건 앞에 5개이다. 차례로 outEdgeList, vertexList, directed, vertexProperties, edgeProperties 인데, 하나씩 살펴보자.

​

edgeList - edge list 를 어떻게 구성할거냐. vecS 면 std::vector 로 edge 를 저장한다는 말. 튜토리얼 보면 여러개 더 있다. 쌍방향 그래프로 하면 이 list 가 두개가 된다.

vertexList - vertex list 를 어떻게 구성할거냐.

directed - 그래프에 edge 의 방향성 여부. bidirectionalS, directionalS, undirectedS 이렇게 있다.

edgeProperties - edge 에 들어갈 정보. 여기에 넣으면 내부적으로 값이 있다. 싫으면 외부에 따로 list 만들어서 여기서 만든 그래프에서 edge index 뽑아서 접근하면 된다. 여기선 위에 있는 struct 를 사용할 것임.

graphProperties - vertex 에 들어갈 정보. 위랑 거의 같다.

​

2.생성

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

typedef std::pair<int, int> Pair; Pair edge_array[9] = { Pair(0,1), Pair(0,2), Pair(0,3), Pair(1,0), Pair(1,2), Pair(1,3), Pair(2,0), Pair(2,1), Pair(2,2) }; MonsterType vertex_property_array[4] = { MonsterType("Slime", 0), MonsterType("Slime", 1), MonsterType("Slime", 2), MonsterType("Slime", 3) }; Evolution_Condition edge_property_array[9] = { Evolution_Condition(1, 2), Evolution_Condition(1, 2), Evolution_Condition(1, 2), Evolution_Condition(3, 7), Evolution_Condition(11, 7), Evolution_Condition(23, 7), Evolution_Condition(5, 11), Evolution_Condition(21, 11), Evolution_Condition(55, 11), };

위부터 지금부터 사용할 edge_array, vertex_property_array, edge_property_array 이다.

여기서 edge/graph Properties 와 edge/vertex index 가 다르다는 것을 주의깊게 봐야한다. index 는 내부적으로 사용되는 것이고, Property 는 index와 따로 저장된다. 한마디로 인덱스 데리고 와서 Property 를 꺼내 쓰는 것이다.

1 2 3

Graph tree(4); // default intialize for (int i = 0; i < sizeof(vertex_property_array) / sizeof(MonsterType); i++) tree[i] = vertex_property_array[i];

생성법 1. Vertex 가 기본생성자로 생성된다. 인덱싱하면 vertex 값이 나오므로 그걸 변경해서 조정함.

1 2 3 4 5

Graph tree(4); // default intialize for (int i = 0; i < sizeof(vertex_property_array) / sizeof(MonsterType); i++) tree[i] = vertex_property_array[i]; for (int i = 0; i < sizeof(edge_array) / sizeof(Evolution_Condition); ++i) boost::add_edge(edge_array[i].first, edge_array[i].second, tree);

생성법 2. add_vertex / edge 로 생성한다.

1 2	Graph tree(edge_array, edge_array + sizeof(edge_array) / sizeof(Pair), sizeof(vertex_property_array) / sizeof(MonsterType)); // default intialize

생성법 3. edge_array 를 만들어서 array 주소, array 끝주소, vertex num 넣어서 초기화.

1 2	Graph tree(edge_array, edge_array + sizeof(edge_array) / sizeof(Pair), edge_property_array, sizeof(vertex_property_array) / sizeof(MonsterType)); // default intialize

생성법 4. edge_array 에 더해서 edge_property 도 한번에 초기화.

​

​

3. iterator

1 2	typedef boost::graph_traits<Graph>::vertex_iterator vertex_iter; typedef boost::graph_traits<Graph>::edge_iterator edge_iter;;

iter 은 일단 저 두개를 쓴다. dereference 를 하면 Graph 에 넣을 vertex / edge 의 인덱스가 뜬다.

1 2 3 4

std::pair<vertex_iter, vertex_iter> vp; std::cout << "vertices = \n"; for (vp = boost::vertices(tree); vp.first != vp.second; ++vp.first) // first 는 그래프 첫번째, second 는 끝부분 std::cout << *vp.first << " " << tree[*vp.first].code << " " << tree[*vp.first].name << std::endl;

vertices(tree), 여기서 tree는 위에서 만든 그래프다. vertices 는 std::pair<vertex_iter, vertex_iter> 을 리턴하며, 앞에건 맨 처음을 가리키는 iter, 뒤에건 맨 뒤를 가리키는 iter 이다. 그래서 위같은 사용이 가능한 것이다.

프린트 값은 vertex index, 그 인덱스의 property 인 code, name 순으로 나온다.

1 2 3 4 5

std::cout << "edges = \n"; edge_iter ei, ei_end; for (boost::tie(ei,ei_end) = boost::edges(tree); ei != ei_end; ++ei) std::cout << "(" << boost::source(*ei, tree) << "," << boost::target(*ei, tree) << ") "<< "property " << tree[*ei].lv << " " << tree[*ei].item << std::endl;

edges(tree) 도 마찬가지. 위처럼 std::pair 쓸수도 있지만, tie 를 사용할 수도 있다.

​

dereference 된 자료형은 boost::graph_traits<Graph>::vertex_descriptorr 이런류라는 걸 여기서 알아두자.

​

​

4. std::for_each

​

std::for_each 는 stl 자료형의 begin 과 end 늘 걸어서 객체의 아이템을 하나씩 처리시키는 방법이다.

처리시킬때 함수를 넣기도 하지만, struct 등에 operator() overloading 을 하면 이게 적용도 되서 자주 쓰인다.

이걸 적용시켜서 in, out edge, adjacency vertex 를 튜토리얼에도 소개하므로 여기도 똑같이 해보자.

1 2 3

std::for_each(boost::vertices(tree).first, boost::vertices(tree).second, print_outedge<Graph>(tree)); std::for_each(boost::vertices(tree).first, boost::vertices(tree).second, print_inedge<Graph>(tree)); std::for_each(boost::vertices(tree).first, boost::vertices(tree).second, print_adjacency<Graph>(tree));

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

template <class Graph> struct print_outedge { typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex; print_outedge(Graph& g_) : g(g_) {} void operator()(const Vertex& v) const { std::cout << "out-edges: " << v << " "; typename boost::graph_traits<Graph>::out_edge_iterator out_i, out_end; typename boost::graph_traits<Graph>::edge_descriptor e; for (boost::tie(out_i, out_end) = boost::out_edges(v, g); out_i != out_end; ++out_i) { Vertex src = boost::source(*out_i, g), targ = boost::target(*out_i, g); std::cout << "(" << src << "," << targ << ") "; } std::cout << std::endl; } Graph& g; };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

template <class Graph> struct print_inedge { typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex; print_inedge(Graph& g_) : g(g_) {} void operator()(const Vertex& v) const { std::cout << "in-edges: "; typename boost::graph_traits<Graph>::in_edge_iterator out_i, out_end; for (boost::tie(out_i, out_end) = boost::in_edges(v, g); out_i != out_end; ++out_i) { Vertex src = boost::source(*out_i, g), targ = boost::target(*out_i, g); std::cout << "(" << src << "," << targ << ") "; } std::cout << std::endl; } Graph& g; };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

template <class Graph> struct print_adjacency { typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex; print_adjacency(Graph& g_) : g(g_) {} void operator()(const Vertex& v) const { std::cout << "adjacent vertices: "; typename boost::graph_traits<Graph>::adjacency_iterator ai, ai_end; for (boost::tie(ai, ai_end) = boost::adjacent_vertices(v, g); ai != ai_end; ++ai) std::cout << *ai << " "; std::cout << std::endl; } //... Graph& g; };

인자가 vertex_iterator 의 dereference 인 vertex_descriptor 라는 점을 인지하자.

​

​

5. 알고리즘

1 2 3 4 5 6 7 8 9

std::vector<int> d(boost::num_vertices(tree)); // invoke variant 2 of Dijkstra's algorithm boost::dijkstra_shortest_paths(tree, *(boost::vertices(tree).first), boost::no_named_parameters(). weight_map(boost::get(&Evolution_Condition::lv, tree)). distance_map(&d[0])); std::cout << "distances from start vertex:" << std::endl; boost::graph_traits<Graph>::vertex_iterator vi; for (vi = vertices(tree).first; vi != vertices(tree).second; ++vi) std::cout << "distance(" << *vi << ") = " << d[*vi] << std::endl; std::cout << std::endl;

알고리즘마다 다른데 dijkstra 는 weight 가지고 distance 를 뽑는 알고리즘임.

BGL은 역사가 오래되서 그런지 bundle property 추천하더니 이거쓰는 예시는 아래빼고 더럽게 안나옴.

 

BGL Dijkstra Shortest Paths with Bundled Properties

I'm trying to use the dijkstra shortest path algorithm in BGL to compute a simple ST path on an unweighted undirected graph. I may care about edge weights in the future, but for now I just want to

stackoverflow.com

bundle property 쓰면 지금까지는 property map 필요없이 운영이 가능함.

근데 이제 써야하니까 대가리가 아파옴.

대충 훑은거 정리하면, property_map 은 . 찍어서 계속 만들수 있음. 위에서 weight 뒤에 distance map 만든거처럼.

boost::no_named_parameters() 로 시작찍고, . 찍고, 내부에서 레지스트된 weight_map 을 boost::get 으로 만들고, 그렇게 만들어진 맵 뒤에 . 찍고, 다시 내부에서 레지스트된 distance_map 을 외부 구조체 주소 들고와서 구성하는 거임. 그리고 distance_map에 결과물이 찍히는 것.