C++에서 Graphviz로 그래프 이미지 그리기

 자료구조를 공부하거나 특정한 환경을 그림으로 표현하고자 하는 경우가 있습니다. 특히 위상수학 같이 이산수학이 사용되는 분야에서는 각 객체들의 상호관계를 나타내야 하는 것이 중요하지요. 이러한 특성을 이미지로 나타낸 것을 흔히 그래프(Graph)라고 부릅니다.

 위의 그림은 같은 Depth를 유지하는 것을 목적으로 설계된 B+ 트리를 나타냅니다. 각 노드(혹은 Vertex)가 화살표(혹은 Edge)로 연결되어 있습니다. 특정한 프로그램의 알고리즘을 위와 같이 그림으로 표현한 것을 그래프라고 합니다.

 그렇다면 과연 우리들이 직접 설계한 프로그램을 바로 그림으로 나타낼 수 있는 방법이 있을까요? C++의 Boost library에서는 그래프를 생성할 수 있는 Graphviz를 지원합니다. 이산수학의 그래프 이론을 잘 알고 계시다면 Graphviz를 사용 하는 것이 상당히 쉬워질 것입니다.

 Graphviz를 사용하기에 앞서서 간단한 그래프 이론에 대해 설명을 드리겠습니다. 예를들어 다음과 같은 그래프가 있다고 가정합니다.

 위 그래프는 Graphviz로 생성한 4개의 Vertex와 4개의 Edge를 가지고 있는 그래프입니다. 한 눈으로 봐도 각 vertex인 A, B, C와 D가 각각 edge로 어떻게 연결되었는지 한 번에 알 수 있습니다. 이를 인접 행렬(Adjacency matrix)로 나타내면 다음과 같습니다.

 각 행과 열의 첫 번째 부터 A, B, C, D로 보았을 때 나타낸 인접 행렬의 모습입니다. 첫째 열의 경우 [0 1 0 1] 로 나타내어졌는데 각각 A는 두 번째인 B와 4 번째인 D와 연결된 부분을 1로 나타낸 것입니다. 나머지 열의 경우는 직접 위의 그림과 비교해 보신다면 쉽게 아실 수 있으실 겁니다!

 지금까지 우리는 무방향 그래프(Undirectional graph)를 설명하였습니다. 다음으로는 Edge에 방향성이 포함되어 있는 방향 그래프(Directional graph)를 보도록 하겠습니다.

 위에서 보았던 그래프에 화살표로 방향이 추가된 그래프입니다. 이 그래프 또한 인접 행렬로 다음과 같이 나타낼 수 있습니다.

 위에서 보았던 인접 행렬과 다른 점은 각 열은 출발 vertex, 각 행은 도착 vertex를 나타낸 것입니다. 즉 A의 경우 B와 D의 방향으로 향하고 있기 때문에 첫 번째 열의 경우 [0 1 0 1] 순서로 나타나는 것입니다. 반면, C의 경우 무방향 그래프의 경우 A와 같은 [0 1 0 1]이었으나 B로는 연결 방향이 존재하지 않기 때문에 [0 0 0 1]로 나타내는 것입니다. 또한 방향 그래프는 인접 리스트(Adjacency list)로 아래와 같이 나타낼 수 있습니다.

 위에서 보았던 방향 그래프를 생각하시면 이해하기 쉬우실 겁니다. 각각의 Vertex인 A와 B, C, D를 생성한 후 각 Vertex가 향하는 방향의 Vertex를 연결 리스트(Linked list)로 이어주는 것이지요. 연결되는 순서는 상관 없습니다. 즉 [A → B → C] 로 표기하거나 [A → C → B]로 표기하여도 모두 같은 값을 나타낸다고 보시면 되겠습니다. 여기서 D로부터 시작하는 방향은 존재하지 않으므로 D는 그 어떤 Vertex와 연결되있지 않음을 위에서 보실 수 있습니다.

 그러면 이번에는 위에서 설명한 그래프들을 직접 소스코드로 구현해봅시다. 먼저 Boost library를 컴퓨터에 설치해 줍니다.

$ sudo apt install libboost-all-deb graphviz

 다음으로 아래와 같은 소스코드를 입력합니다.

graphviz.cc

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <cstdio>
 
using namespace std;
 
struct VertexP { string tag; };
struct EdgeP { string symbol; };
struct GraphP { string orientation; };
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexP, EdgeP, GraphP, boost::listS> ListGraph;
 
int main()
{
    ListGraph g(GraphP{"Example"});
    boost::dynamic_properties dp;
    dp.property("node_id", get(&VertexP::tag,g));
 
    ofstream dot_file("graph.dot");
    string dcmd = "dot -Tpng graph.dot -o graph.png";
 
    // Create the vertexes
    ListGraph::vertex_descriptor a = add_vertex(VertexP{"A"},g);
    ListGraph::vertex_descriptor b = add_vertex(VertexP{"B"},g);
    ListGraph::vertex_descriptor c = add_vertex(VertexP{"C"},g);
    ListGraph::vertex_descriptor d = add_vertex(VertexP{"D"},g);
 
    // Create the edges
    // A → B
    add_edge(a, b, g);
    // B → D
    add_edge(a, d, g);
    // B → C
    add_edge(b, c, g);
    // C → D
    add_edge(c, d, g);
 
    // Print graph
    write_graphviz_dp(dot_file, g, dp);
 
    std::unique_ptr<FILE, decltype(&pclose)> pipe(popen(dcmd.c_str(), "r"), pclose);
    if (!pipe) {
        throw runtime_error("popen() failed!");
    }
 
    return 0;
}
 

 여기서 소스코드의 중요한 부분을 하나씩 설명해 드리겠습니다.

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexP, EdgeP, GraphP, boost::listS> ListGraph;

 위에서 설명드렸던 인접 리스트(Adjacency list)를 만들수 있도록 해주는 Boost library입니다. Graphviz로 그래프를 만들어주기 위해 사용됩니다.

    ListGraph g(GraphP{"Example"});
    boost::dynamic_properties dp;
    dp.property("node_id", get(&VertexP::tag,g));

하나의 인접 리스트 변수 g를 선언합니다. 인접 리스트의 이름은 "Example" 입니다. dynamic_properties는 Graphviz에서 Adjacency list의 내용을 설정해 주기 위해 사용되는 변수입니다. 각 vertex의 이름은 VertexP 구조에 저장되므로 16번 줄을 작성하여 Adjacency list 변수 g에 선언해줍니다.

    ofstream dot_file("graph.dot");
    string dcmd = "dot -Tpng graph.dot -o graph.png";

 Graphviz를 생성해 주기 위해 파일을 생성합니다. 파일의 이름은 "graph.dot"입니다. Graphviz를 이미지로 생성시켜주는 과정은 Terminal의 명령어로 이루어지므로 명령어를 설정해 줍니다. 명령어는 다음과 같습니다.

$ dot -Tpng graph.dot -o graph.png

 위 명령어는 생성되는 이미지의 확장명은 png로 설정하며 파일명은 graph.png로 저장하겠다는 의미입니다.

    // Create the vertexes
    ListGraph::vertex_descriptor a = add_vertex(VertexP{"A"},g);
    ListGraph::vertex_descriptor b = add_vertex(VertexP{"B"},g);
    ListGraph::vertex_descriptor c = add_vertex(VertexP{"C"},g);
    ListGraph::vertex_descriptor d = add_vertex(VertexP{"D"},g);

 Vertex들을 생성해줍니다. vertex_descriptor에 해당 vertex를 저장해 줍니다.

// Create the edges
// A → B
add_edge(a, b, g);
// B → D
add_edge(a, d, g);
// B → C
add_edge(b, c, g);
// C → D
add_edge(c, d, g);

 바로 이 부분이 제가 위에서 말씀드렸던 인접 리스트의 방식을 나타낸 것입니다. 각 vertex와 연결하고자 하는 vertex를 위의 순서대로 입력하시면 우리가 원하는 방식대로 edge가 연결됩니다.

    // Print graph
    write_graphviz_dp(dot_file, g, dp);

 지금까지 우리들이 만들었던 그래프를 Graphviz로 만듭니다. 이를 실행하면 dot 파일이 생성됩니다.

    std::unique_ptr<FILE, decltype(&pclose)> pipe(popen(dcmd.c_str(), "r"), pclose);
    if (!pipe) {
        throw runtime_error("popen() failed!");
    }

 dot 파일로 생성된 Graphviz를 이미지로 만들기 위해 실행되는 부분입니다. 이 과정은 Graphviz 프로그램에서 직접 실행되기 때문에 위와 같이 설정해 주시면 직접 사용자가 dot 명령어를 입력하지 않고도 이미지가 생성됩니다.

여기까지 완성되었다면 이제 컴파일을 해줍니다. 다음과 같은 파일을 만들어줍니다.

Makefile

CC = g++
CFLAGS = -g -Wall -std=c++11
 
output:graphviz.cc
    $(CC) $(CFLAGS) -o output graphviz.cc

make로 컴파일을 해줍니다.

$ make

이제 컴파일이 실행된 폴더를 확인해보시면 'output' 이라는 이름의 실행파일이 생성됩니다. 이제 실행해봅니다.

$ ./output

 그러면 다음과 같은 이미지 파일이 생성되 있는 것을 확인하실 수 있습니다.

 다음으로 이번에는 방향 그래프를 만들어 보겠습니다. 위 코드에서 다음 부분만 바꿔주시면 되겠습니다.

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexP, EdgeP, GraphP, boost::listS> ListGraph;

 그러면 다음과 같은 방향 그래프가 생성됩니다.

 이번에는 생성된 그래프를 회전 시켜보겠습니다. 다음과 같은 코드를 추가시켜주세요.

    ListGraph g(GraphP{"Example"});
    boost::dynamic_properties dp;
    dp.property("node_id", get(&VertexP::tag,g));
    dp.property("rankdir", boost::make_constant_property<ListGraph*>(string("LR")));

그러면 다음과 같이 그래프가 90도 회전합니다.

만약 위의 vertex의 순서를 반대로 하고자 하시는 분이라면 소스코드를 다음과 같이 고쳐주세요.

    ListGraph g(GraphP{"Example"});
    boost::dynamic_properties dp;
    dp.property("node_id", get(&VertexP::tag,g));
    dp.property("rankdir", boost::make_constant_property<ListGraph*>(string("RL")));

 그러면 vertex의 순서가 좌우 반전으로 다음과 같이 출력됩니다.