Boost Graph Library(BGL)은 Graph를 처리하는 범용 그래픽 라이브러리 입니다.
그래프(Graph)는 정점(vertex), 선(edge)으로 이루어져 있습니다.
1차원을 구성하는 점과 선이 기본 요소이기 때문에 1차원 이상의 고차원에 존재하는 모든 표현이 가능합니다.
그래프로 할 수 있는 일이 굉장히 많습니다.
- UML 다이어그램
- Node 기반 그래프(퀘스트 연결 관계 등..)
- C++ 헤더 파일 포함 관계 그래프
- 최단거리 길 찾기
- ...
이번에는 BGL을 이용하여 Dijkstra(다익스트라) 최단거리 알고리즘을 활용해 보겠습니다.
위와 같은 그래프를 BGL Dijkstra Shortest Path 알고리즘을 활용하여 처리한 결과는 다음과 같습니다.
#include "ShortestPath.h"
int _tmain(int argc, _TCHAR* argv[])
{
setlocale( LC_ALL, "Korean" );
CShortestPath ShortestPath;
ShortestPath.BuildGraph();
return 0;
}
main 함수에서 하는 일은 없습니다. CShortestPath 클래스가 핵심입니다.BuildGraph()에서 하는 일은 다음과 같습니다.
- Vertex 추가 / 이름 설정
- Edge 추가 / 이름 / 가중치 설정
- boost::dijkstra_shortest_paths()로 최단 거리 구하기
- PrintShortestPath( vStartVertex )에서 시작 vertex를 지정하고 최단거리 Console로 출력하기
- WriteGraphviz()에서 Graphviz.dot 파일로 그래프 파일 출력하기
void CShortestPath::BuildGraph()
{
//////////////////////////////////////////////////////////////////////////
// Vertex 추가하기
const VertexDescriptor vA = boost::add_vertex( m_Graph );
const VertexDescriptor vB = boost::add_vertex( m_Graph );
const VertexDescriptor vC = boost::add_vertex( m_Graph );
const VertexDescriptor vD = boost::add_vertex( m_Graph );
const VertexDescriptor vE = boost::add_vertex( m_Graph );
// Vertex 이름 설정하기
boost::put( boost::vertex_name, m_Graph, vA, "A" );
boost::put( boost::vertex_name, m_Graph, vB, "B" );
boost::put( boost::vertex_name, m_Graph, vC, "C" );
boost::put( boost::vertex_name, m_Graph, vD, "D" );
boost::put( boost::vertex_name, m_Graph, vE, "E" );
//////////////////////////////////////////////////////////////////////////
// Edge 추가하기
const EdgeDescriptor eAC = boost::add_edge( vA, vC, m_Graph ).first;
const EdgeDescriptor eBB = boost::add_edge( vB, vB, m_Graph ).first;
const EdgeDescriptor eBD = boost::add_edge( vB, vD, m_Graph ).first;
const EdgeDescriptor eBE = boost::add_edge( vB, vE, m_Graph ).first;
const EdgeDescriptor eCB = boost::add_edge( vC, vB, m_Graph ).first;
const EdgeDescriptor eCD = boost::add_edge( vC, vD, m_Graph ).first;
const EdgeDescriptor eDE = boost::add_edge( vD, vE, m_Graph ).first;
const EdgeDescriptor eEB = boost::add_edge( vE, vB, m_Graph ).first;
const EdgeDescriptor eEA = boost::add_edge( vE, vA, m_Graph ).first;
// Edge 이름 설정하기
boost::put( boost::edge_name, m_Graph, eAC, "AC" );
boost::put( boost::edge_name, m_Graph, eBB, "BB" );
boost::put( boost::edge_name, m_Graph, eBD, "BD" );
boost::put( boost::edge_name, m_Graph, eBE, "BE" );
boost::put( boost::edge_name, m_Graph, eCB, "CB" );
boost::put( boost::edge_name, m_Graph, eCD, "CD" );
boost::put( boost::edge_name, m_Graph, eDE, "DE" );
boost::put( boost::edge_name, m_Graph, eEB, "EB" );
boost::put( boost::edge_name, m_Graph, eEA, "EA" );
// Edge에 가중치 설정하기
boost::put( boost::edge_weight, m_Graph, eAC, 1 );
boost::put( boost::edge_weight, m_Graph, eBB, 2 );
boost::put( boost::edge_weight, m_Graph, eBD, 1 );
boost::put( boost::edge_weight, m_Graph, eBE, 2 );
boost::put( boost::edge_weight, m_Graph, eCB, 7 );
boost::put( boost::edge_weight, m_Graph, eCD, 3 );
boost::put( boost::edge_weight, m_Graph, eDE, 1 );
boost::put( boost::edge_weight, m_Graph, eEB, 1 );
boost::put( boost::edge_weight, m_Graph, eEA, 1 );
//////////////////////////////////////////////////////////////////////////
// Shortest Path 구하기
// Property Map 가져오기
boost::property_map< Graph, boost::edge_weight_t >::type mapEdgeWeight = boost::get( boost::edge_weight, m_Graph );
boost::property_map< Graph, boost::vertex_index_t >::type mapVertexIndex = boost::get( boost::vertex_index, m_Graph );
boost::property_map< Graph, boost::vertex_distance_t >::type mapVertexDistance = boost::get( boost::vertex_distance, m_Graph );
boost::property_map< Graph, boost::vertex_predecessor_t >::type mapVertexPredecessor = boost::get( boost::vertex_predecessor, m_Graph );
// 다익스트라 최단거리 알고리즘
const VertexDescriptor vStartVertex = vA;
boost::dijkstra_shortest_paths(
m_Graph,
vStartVertex,
boost::weight_map( mapEdgeWeight ).vertex_index_map( mapVertexIndex ).distance_map( mapVertexDistance ).predecessor_map( mapVertexPredecessor )
);
//////////////////////////////////////////////////////////////////////////
// 최단거리 결과 출력
PrintShortestPath( vStartVertex );
// Dot 파일로 출력
WriteGraphviz();
}기존 BGL 책에 소개된 배열 기반의 예제를 탈피해서,
STL을 주로 사용하시는 분들에 맞게 코드를 작성하였습니다.
BoostGraph_ShortestPath.zip다른 기능을 추가하고자 하신다면, boost.org의 Graph 라이브러리 페이지를 참조하세요.
덧글을 달아 주세요
hanstar17 2011/06/11 21:21 고유주소 고치기 답하기
기본도 모자라, 이젠 다익스트라같은 응용 알고리즘까지 라이브러리로 제공되는군요!!ㅋㅋ 신기하네요.ㅎㅎ 좋은글 감사합니다~!
TTF 2011/06/14 03:00 고유주소 고치기
네, Boost에 검증된 라이브러리를 사용하실 수록 그 매력에 빠져드실 꺼에요.
actin 2011/06/12 01:33 고유주소 고치기 답하기
이렇게 깔끔하게 정리되었군요 ^^
TTF 2011/06/14 03:01 고유주소 고치기
네 ㅎㅎ.
나중에 다시 봐도 알아볼 수는 있을까요?
soomong 2011/06/13 16:40 고유주소 고치기 답하기
와우! 다익스트라 알고리즘을 Lib 로 제공해준다니!!!
멋집니다~
TTF 2011/06/14 03:02 고유주소 고치기
저도 Boost 만드신 분들께 감사드려요. ㅎㅎ