(방향성) 그래프는 화살표(간선)로 연결된 노드들의 집합이다. 노드와 간선은 데이터를 담을 수 있다. 다음은 몇 가지 그래프의 예이다:

그래프는 소프트웨어 엔지니어링 어디에나 존재한다:

1. 패키지 의존성은 방향 그래프를 이루며, 모듈 임포트도 마찬가지다.
2. 인터넷은 웹페이지 간의 링크로 이루어진 그래프다.
3. 모델 체커는 모든 가능한 설정의 “상태 공간”을 탐색해 소프트웨어를 분석한다. 노드는 상태이며, 간선은 상태 간의 유효한 전이다.
4. 관계형 데이터베이스는 레코드가 노드이고 외래 키가 간선인 그래프다.
5. 그래프는 연결 리스트, 이진 트리, 해시 테이블을 일반화한 것이다.¹

그래프는 비즈니스 로직에서도 널리 쓰인다. 참고 문헌이 있는 백서는 인용 관계의 그래프를 이룬다. 교통 네트워크는 경로의 그래프이며, 소셜 네트워크는 연결 관계의 그래프다. 소프트웨어 개발을 오래 하다 보면 결국 어딘가에서 그래프를 마주하게 된다.

나는 어디서나 그래프를 발견하고 온갖 시스템을 분석하는 데 그래프를 활용한다. 동시에 코드에서 그래프를 실제로 사용하는 것은 끔찍하게 여긴다. 주류 언어 중 그래프를 제대로 지원하는 언어는 거의 없다. 내장 타입으로 그래프를 제공하는 언어는 하나도 없고, 표준 라이브러리에 그래프를 포함한 경우도 매우 드물며, 생태계에 제대로 된 서드파티 라이브러리조차 없는 경우도 많다. 대부분 직접 그래프를 처음부터 구현해야 한다. 소프트웨어 엔지니어가 그래프를 활용할 수 있는 빈도와 프로그래밍 생태계가 그래프를 지원하는 수준 사이에는 큰 간극이 존재한다. 도대체 그래프 타입은 어디에 있는 걸까?

일을 하면서 그래프를 점점 더 많이 마주할수록 이 질문은 점점 더 흥미로워졌다. 그래서 작년 말에 마침내 답을 찾기로 했다. 모집 글을 내 뉴스레터에 올려 관련 전문가—그래프 알고리즘 개발자, 언어 위원회 위원, 그래프 라이브러리 메인테이너—에게 연락을 부탁했다. 열 명 정도를 인터뷰할 것으로 예상했지만, 결국 네 명과 이야기하는 것만으로 충분했다:

1. Zayenz: Gecode 제약 솔버의 전직 핵심 개발자이며, “존재하는 모든 그래프 알고리즘을 구현해 본” 사람
2. Bradford: Nosey Parker 보안 라이브러리의 저자이자 여러 새로운 그래프 알고리즘의 발명자
3. Nicole: 전직 그래프 데이터베이스 엔지니어
4. Kelly: NetworkX 파이썬 그래프 라이브러리의 메인테이너이자 컴파일러 개발자

이 네 명이 모두 비슷한 답을 내놓은 뒤, 나는 인터뷰를 중단하고 글을 쓰기 시작했다.

그 이유들

설계 선택지가 너무 많다

지금까지 나는 방향 그래프에 대해 설명해 왔다. 간선에 방향이 없는 무방향 그래프도 있다. 방향 그래프와 무방향 그래프 모두 단순 그래프일 수도 있고 멀티그래프일 수도 있다. 단순 그래프에서는 두 노드 사이에 간선이 최대 하나만 존재하고, 멀티그래프에서는 여러 개의 간선이 존재할 수 있다. 그리고 그런 유형들 각각에 대해 하이퍼그래프—간선 하나가 세 개 이상의 노드를 연결하는 그래프—와 우버그래프—간선이 다른 간선을 가리킬 수 있는 그래프—가 있다. 가능한 모든 변형마다 또 다른 선택을 해야 한다. 간선에도 ID를 부여할 것인가, 아니면 노드에만 부여할 것인가? 노드에는 어떤 데이터를 저장할 수 있고, 간선에는 어떤 데이터를 저장할 수 있는가? 라이브러리가 내려야 할 결정이 너무나 많다!

하지만 잠깐, 이런 구분이 정말 중요한가? 단순 그래프는 그저 퇴화된 멀티그래프일 뿐이고, 무방향 간선은 두 개의 방향 간선으로 손실 없이 변환할 수 있다. 언어는 그냥 방향성 하이퍼우버멀티그래프 하나만 제공하고 사용자가 원하는 대로 제한해서 쓰게 하면 되지 않을까?

여기에는 두 가지 문제가 있다. 첫째, 인터페이스가 달라진다. 예를 들어 여러 연산이 단일 값을 반환할지 리스트를 반환할지가 바뀌는 식이다. 둘째, 뒤에서 논하겠지만 그래프 알고리즘의 성능은 매우 중요한 고려 사항이며 특수한 경우들이 정말 중요하다. Kelly는 최대 가중치 매칭의 예를 들었다. 그래프가 “이분 그래프”임을 알고 있다면 매칭을 찾기 위해 특정한 빠른 알고리즘을 사용할 수 있지만, 다른 그래프에서는 느리고 일반적인 알고리즘을 써야 한다.

[이건] “알고리즘 디스패치 문제”와 연결됩니다. 문제 P와 그래프 G, 그리고 G에서 P를 풀기 위한 알고리즘 A, B, C가 있을 때… 어떤 걸 실행해야 할까요? G가 이분 그래프인지 모르고, 알고리즘 C가 이분 그래프에서만 동작한다면, G가 이분 그래프인지 판단하는 데 얼마나 많은 시간을 쓸 수 있을까요? — Kelly

완벽한 그래프 라이브러리라면 아주 다양한 종류의 그래프를 지원해야 할 것이다. 하지만 그러다 보면 사람들이 그래프를 이용해 하고 싶어 하는 일들을 지원하는 데 쓸 시간이 줄어든다. 그래프 알고리즘은 제대로 구현하기가 악명 높게 어렵다. 이 에세이에서 파이썬의 창시자는 직접 find_shortest_path 알고리즘을 구현했는데, 다섯 번이나 수정해야 했다!

제가 비교해 본 pagerank 구현은 전부 틀렸습니다. — Nicole

그렇다면 라이브러리에는 어떤 알고리즘을 포함해야 할까? Kelly는 내게 이렇게 말했다. “사람들이 그래프로 하고 싶어 하는 일의 양은 터무니없이 많아요.” 이는 내 경험과 인터뷰한 모든 사람의 경험과 일치한다. 때때로 그래프는 너무 강력해서 그 모든 가능성이 이해를 넘어서는 것처럼 느껴진다. Kelly는 말했다. “문제는 어디서 선을 긋느냐는 거죠.”

NetworkX의 경우, 그 “선”은 약 500개의 서로 다른 그래프 알고리즘에 해당하며, 이것만으로 거의 60,000줄의 코드에 이른다. 비교하자면 300개의 패키지로 구성된 파이썬 표준 라이브러리 전체가 600,000줄이 채 되지 않는다.²

이를 고려하면 표준 라이브러리에서 그래프를 볼 수 없는 게 놀랍지 않다. 언어 메인테이너들은 어떤 종류의 그래프를 지원할지, 어떤 토폴로지를 특수 처리할지, 어떤 알고리즘을 포함할지를 결정해야 한다. 이런 유지보수 작업을 서드파티에 맡기는 것이 합리적이다. 이는 이미 언어 개발의 주류적 흐름이기도 하다. “배터리 포함”으로 유명한 파이썬조차 20개의 배터리를 제거하고 있다.

서드파티는 그래프를 어떻게 설계하고 어떤 알고리즘을 포함할지에 대해 독자적인 결정을 내릴 수 있다. 하지만 그러면 다음 문제에 직면하게 된다. 그래프 인터페이스를 만들었다면, 그것을 내부적으로 어떻게 표현할 것인가?

구현 선택지도 너무 많다

가장 기본적인 단순 방향 그래프만 지원한다고 상상해 보자. 노드는 식별자를 가지고 간선은 가지지 않으며, 둘 다 연관된 데이터가 없는 경우다. 이 그래프를 어떻게 인코딩할 수 있을까?

프로그래밍 언어가 이를 내부적으로 저장할 수 있는 네 가지 방법은 다음과 같다:

1. 간선 리스트: [[a, b], [b, c], [c, a], [c, b]]
2. 인접 리스트: [[b], [c], [a, b]]
3. 인접 행렬: [0 1 0; 0 0 1; 1 1 0]
4. 서로를 참조하는 세 개의 구조체 집합

서로 다른 그래프 연산은 표현 방식에 따라 성능 특성이 다르다. 100개의 노드와 200개의 간선을 가진 방향 그래프를 예로 들어보자. 인접 행렬 표현을 사용하면 200개의 1과 9,800개의 0을 포함하는 100×100 행렬이 필요하다. 대신 간선 리스트를 사용하면 노드 쌍 200개만 있으면 된다. 프로그래밍 언어와 최적화 수준에 따라 이는 20배 이상의 메모리 차이가 될 수 있다.

이번에는 100개의 노드와 8,000개의 간선을 가진 그래프에서 노드 0과 노드 93 사이에 간선이 존재하는지 찾아보자. 행렬 표현에서는 graph[0][93]을 통한 O(1) 조회로 끝난다. 간선 리스트 표현에서는 8,000개의 간선 전체를 순회하는 O(|edge|) 탐색이 필요하다.³

간선이 몇 개 없는 그래프는 희소하고, 간선이 거의 모두 존재하는 그래프는 밀집하다. 같은 프로그램이 두 종류의 그래프 토폴로지 모두에서 두 연산을 모두 수행해야 할 수도 있다. 외부 데이터로부터 그래프를 구성한다면 처음에는 희소 그래프였다가 나중에는 밀집 그래프가 될 수도 있기 때문이다. 내부 그래프 표현에 “좋은 선택지”라는 것은 존재하지 않는다.

그리고 이 모든 문제는 가장 기본적인 방향 그래프에만 해당하는 것이다! 노드 데이터는 어떻게 구현할 것인가? 간선 데이터는? 서로 다른 유형의 노드와 간선은? 대부분의 서드파티 라이브러리는 대략 두 가지 범주 중 하나에 속한다:

1. 효율성을 희생하는 대신 모든 사용 사례를 포괄하는 단일하고 풍부한 데이터 타입을 제공한다. NetworkX는 노드와 간선 모두 임의의 데이터를 가질 수 있도록 그래프를 dict의 dict의 dict 형태로 저장한다.⁴

2. 표현 방식마다 별도의 그래프 타입을 제공하고, 노드와 간선 데이터는 그래프 타입과 별도로 저장하도록 사용자에게 맡긴다.

두 번째 경우의 예로는 Rust에서 가장 인기 있는 그래프 라이브러리인 Petgraph가 있다. Petgraph는 서로 다른 사용 사례를 위해 graph, graphmap, matrix_graph를 제공한다. Bradford는 git 저장소의 전체 히스토리에서 시크릿을 스캔하는 보안 도구인 Nosey Parker에 Petgraph를 사용했다. 그의 벤치마크 그래프는 25만 개의 커밋과 130만 개의 오브젝트를 가지지만 커밋 노드당 간선은 몇 개뿐인 CPython이었다. 그는 인접 리스트를 선택했다.

많은 표현 방식을 지원하면 심각한 단점이 생긴다. 알고리즘을 추가하기 위해 훨씬 더 많은 작업을 해야 한다는 것이다. 그래프 표현마다 알고리즘의 별도 버전을 작성한다면 유지보수 부담이 세 배, 네 배로 늘어난다. 대신 다형 타입에 대한 제네릭 추상화를 작성하면 라이브러리의 성능이 떨어진다. 내가 이야기한 한 프로그래머는 직접 만든 그래프 알고리즘이 제네릭 알고리즘보다 20배 이상 빠를 수 있다고 추정했다.

그리고 이는 모든 인터뷰이가 제기한 가장 큰 불만으로 이어진다.

성능이 너무 중요하다

“제네릭한” 그래프 구현은 대체로 충분하지 않습니다. — Bradford

이것이 핵심이다.

수많은 그래프 알고리즘이 NP-완전 혹은 그 이상이다.⁵ NP-완전이 규모가 큰 문제에서는 종종 다루기 가능하다고는 하지만, 그래프는 그 자체로 엄청나게 큰 문제가 될 수 있다. 표현 방식의 선택은 알고리즘 구현의 세부 사항과 마찬가지로 얼마나 빠르게 문제를 해결할 수 있는지에 큰 역할을 한다.

내가 이야기한 모든 사람은 이와 관련된 일화를 가지고 있었다. Nosey Parker에서 Bradford는 각 커밋마다 파일시스템의 스냅샷을 재구성해야 했는데, 이는 오브젝트 그래프를 순회해야 함을 의미했다. 제공된 네 가지 그래프 탐색기 중 어느 것도 그의 사용 사례에서는 확장되지 않았다. 대신 그는 즉석에서 “반쯤 새로운” 그래프 순회 알고리즘을 설계해야 했고, 이를 통해 메모리 사용량을 1,000분의 1로 줄였다.

[petgraph]로 개념 증명은 꽤 빠르게 만들 수 있었지만, 그 다음엔… 바로 성능 제약이 현실과 마주하는 그런 경우였죠. — Bradford

Zayenz는 다른 문제를 제기했다. 그래프 자체가 다루기에는 너무 커지면 어떻게 할 것인가? 그는 15 퍼즐의 해법을 찾는 예를 들었다. 이는 상태 공간에 대해 A* 탐색을 실행함으로써 이루어지는데, 그 상태 공간은 20조 개가 넘는 상태를 가진다.

모든 노드를 생성하는 순간 이미 실패한 겁니다. — Zayenz

Zayenz는 Gecode 제약 솔버에 그래프를 추가하는 한 연구 프로젝트를 감독했다. 그들은 결국 제네릭 그래프 타입이 문제에 맞춰 표현 방식을 직접 선택하는 방식과는 경쟁할 수 없다는 결론에 도달했다.

복잡한 그래프 알고리즘을 실행하는 것 자체를 목적으로 설계된 그래프 데이터베이스조차 이 문제로 어려움을 겪는다. 그래프 데이터베이스 엔지니어인 Nicole은 기본적인 그래프 연산조차 최적화하는 데 따르는 어려움에 대해 이야기해 주었다.

탐색을 할 때는 깊이를 제한하거나, 전체 그래프를 방문하게 될 것을 감수해야 합니다. “여기서 세 단계 밖으로 나가 경로가 존재하면 찾는” 식의 깊이 탐색을 하면, 결국 꽤 많은 데이터를 방문하겠다고 결심하는 셈이죠. — Nicole

그 직장을 떠난 후, 그녀는 그래프 쿼리 성능 컨설턴트로 일했다. 이는 보통 그래프 데이터베이스에서 다른 곳으로 이전하는 것을 의미했다. 그녀는 그런 프로젝트 중 하나에 대해 이야기해 주었다. 그래프 쿼리 속도를 높이기 위해 하나의 연산은 그대로 두고 나머지는 MapReduce 절차로 다시 작성했다는 것이다. 그녀는 말했다. “이해하기는 훨씬 더 어려웠죠. 하지만 밤새 돌리면 실제로 끝나긴 했습니다.”

이 모든 것은 풀고 싶은 그래프 문제가 있다면 데이터 표현과 알고리즘의 세부 사항에 대해 많은 제어권을 가져야 함을 의미한다. 성능을 조금이라도 놓칠 여유가 없는 것이다.

의견은 만장일치였다

그렇다면 우리가 광범위한 그래프 지원을 갖추지 못한 이유는 다음과 같다:

• 그래프의 종류가 너무나 다양하다
• 각 종류의 그래프마다 표현 방식도 너무나 다양하다
• 그래프 알고리즘도 너무나 다양하다
• 그래프 알고리즘의 성능은 그래프 표현 방식과 구현 세부 사항에 매우 민감하다
• 사람들은 매우 큰 그래프에 대해 매우 비용이 큰 알고리즘을 실행한다.

이것이 언어들이 표준 라이브러리에서 그래프를 지원하지 않는 이유를 설명한다. 내려야 할 설계 결정이 너무 많고, 절충해야 할 것이 너무 많으며, 유지보수 부담이 너무 크기 때문이다. 또한 프로그래머들이 서드파티 그래프 라이브러리를 기피하는 이유도 설명한다. 라이브러리가 너무 제한적이거나 너무 느리기 때문이다. 그리고 프로그래머들이 극단적인 상황이 아니면 사물을 그래프 관점에서 생각하고 싶어 하지 않는 이유도 설명한다. 그래프를 다루는 것이 너무 어렵기 때문이다.

이 연구를 시작한 이후로 나는 업무에서 여러 새로운 그래프 문제를 마주했다. 나는 여전히 시스템을 그래프로 분석하는 것을 좋아하면서도, 이를 구현하는 것은 끔찍하게 여긴다. 하지만 이제는 다른 모든 사람들도 왜 그것을 끔찍해하는지 알게 되었다. 읽어 주셔서 감사합니다!

Predrag Gruevski의 연구 도움과 Lars Hupel, Predrag Gruevski, Dan Luu, Marianne Bellotti의 피드백, 그리고 인터뷰에 응해 준 모든 분께 감사드립니다. 이 글이 마음에 들었다면 뉴스레터에 가입해 주세요! 매주 새로운 에세이를 올리고 있습니다.

저는 기업을 대상으로 형식 기법을 교육하여 소프트웨어 개발을 더 빠르고, 더 저렴하고, 더 안전하게 만듭니다. 더 자세한 내용은 여기에서 확인하세요.

부록: 그래프 타입을 가진 언어들

그래프 질의 언어

그래프 질의 언어(GQL)⁶는 관계형 데이터베이스에서의 SQL이 그래프 데이터베이스에서 하는 역할과 같다. 널리 쓰이는 표준은 없지만, 가장 인기 있는 두 가지는 RDF 트리플을 조회하기 위한 SPARQL과 Neo4j의 Cypher다. 아이러니하게도 GraphQL은 그래프 질의 언어가 아니다. 대신 Facebook Graph Search와의 연관성 때문에 붙은 이름이다. 나는 그래프 데이터베이스 자체는 프로그래밍 언어의 그래프와는 대체로 별개라고 생각했지만, 그 질의 언어들은 그래프가 PL에서 어떻게 동작할 수 있는지를 보여준다.

모든 GQL과 SQL의 가장 큰 차이는 “조인”(관계)이 일급 개체라는 점이다. 영화와 사람으로 이루어진 데이터셋이 있고, 사람들이 영화에 출연하거나, 감독하거나, 제작한다고 상상해 보자. SQL에서는 각 관계를 다대다 테이블로 구현하는데, 이는 “영화 X에 출연한 사람은 누구인가”를 조회하기는 쉽지만 “영화 Y에 어떤 역할로든 참여한 사람은 누구이며 그 역할은 무엇인가”를 조회하기는 어렵게 만든다. SPARQL에서는 관계가 그저 간선일 뿐이므로 같은 조회가 쉬워진다.

PREFIX mv: <your_movie_ontology_URL>
SELECT ?person ?role
WHERE {
    ?person ?role mv:casablanca.
}

Cypher도 비슷한 구문을 가지고 있다. GQL은 간선을 조작할 수도 있다. 간선을 뒤집거나, 서로 합성하거나, 추이적 폐쇄를 구하는 등이다. 케빈 베이컨으로부터 일정 단계 떨어진 모든 배우를 찾고 싶다면 다음과 같이 작성할 수 있다

PREFIX mv: <your_movie_ontology_URL>
SELECT ?a
WHERE {
    mv:kbacon (:acted_in/^:acted_in)+ ?a.
    # a/b = join two lookups
    # ^a = reverse a
    # a+ = transitive closure
}

SPARQL은 경로의 길이를 알려줄 수 없고, 두 배우를 연결하는 영화 체인을 수집하는 것처럼 경로를 따라 계산을 수행할 수도 없다. 이를 지원하는 GQL은 훨씬 더 복잡하다.

GQL을 살펴보면서 얻은 나의 주요 결론은 그래프를 지원하는 PL이 제공해야 할 유용한 순회 프리미티브 집합이 존재한다는 것이다. 흥미롭게도 형식 명세 언어인 Alloy는 “relation” 데이터 타입에 대해 이러한 프리미티브를 모두 갖추고 있다. 그래서 나는 Alloy에서 그래프 표현을 다루는 것이 일반 프로그래밍 언어에서보다 훨씬 쉽다고 느낀다. 다만 이들은 모두 레이블이 붙은 간선에서 동작하며 다른 그래프 표현에서는 동작하지 않을 수도 있다.

표준 라이브러리에 그래프를 포함한 주류 언어들

파이썬은 2020년에 graphlib을 추가했다. 여기의 논의를 보면, 위상 정렬이 “기본적인 알고리즘”이며 “MRO[메서드 결정 순서] 로직의 순수 파이썬 구현”에 유용할 것이기 때문이었다. graphlib은 노드 딕셔너리로 표현된 그래프만 받는 TopologicalSorter 외에는 다른 메서드가 없다. 특이하게도 노드 딕셔너리의 방향은 역전되어 있다. 그래프 a -> b는 {b: [a]}로 표현된다.

2023년 기준으로 CPython 중 graphlib을 사용하는 곳은 없으며 Github에서 이를 참조하는 파일은 900개 미만이다. 비교하자면 2020년에 추가된 또 다른 패키지인 zoneinfo는 6,000개가 넘는 파일에 등장하고, def topological_sort(라는 용어는 4,000개에 등장한다. 다만 이들 중 다수는 2020년 이전부터 존재하던 것일 거라 짐작한다. 대략 훑어본 바로는 이러한 커스텀 위상 정렬들은 모두 graphlib과 다른 그래프 표현을 사용하므로 어차피 변환할 수도 없다. 그래프 표현 방식은 중요하다.

내가 찾은 그래프 타입을 가진 다른 언어는 두 개가 더 있다. Erlang과 SWI-Prolog다. 나는 두 언어 모두 잘 알지 못하며 언제 추가되었는지도 알 수 없다. 적어도 Erlang의 경우 2008년 이전이었다. Erlang 핵심 언어 위원회의 한 사람에게 연락을 시도했지만 답을 받지 못했다.

그래프 언어

bash에서는 모든 것이 문자열이고 Lisp에서는 모든 것이 리스트인 것처럼 “모든 것이 그래프”인 프로그래밍 언어들이다. 몇 가지 예로는 GP2와 Grape가 있다. 이 분야 사람들과 주고받은 서신에 따르면, 현재로서는 여전히 매우 학술적인 단계에 머물러 있다.

수학 소프트웨어 언어

Mathematica, MATLAB, Maple 등은 모두 어떤 형태로든 그래프 라이브러리를 가지고 있다. 더 자세히 알아보기 위해 수천 달러의 라이선스 비용을 지불할 생각은 없다.

업데이트 2024-03-18

이 글에 대해 받은 댓글 중 일부를 여기에 모았다.

1. 정말이다. 해시 테이블은 이분 그래프다. 이는 뻐꾸기 해싱 연산의 성능을 증명하는 데 사용되었다. ^{[돌아가기]}
2. 두 계산 모두 cloc 1.96으로 도출했다. networkx/networkx/algorithms(56989)와 cpython/Lib(588167)에서 cloc을 실행했다. 전체 networkX 라이브러리는 약 90,000줄의 코드다. ^{[돌아가기]}
3. 간선 리스트를 정렬된 상태로 유지하고 O(log(|e|)) 이진 탐색을 수행하면 더 효율적으로 만들 수 있지만, 간선 삽입 비용이 더 비싸진다는 대가가 따른다. ^{[돌아가기]}
4. NetworkX에는 그래프를 다른 표현으로 변환하는 함수는 있지만, 그 표현을 직접 다루기 위한 기능은 없다. ^{[돌아가기]}
5. 21개의 표준 NP-완전 문제 중 14개가 그래프 문제다. ^{[돌아가기]}
6. GQL 언어, 즉 아직 개발 중인 제안된 GQL 표준과 혼동하지 말 것. ^{[돌아가기]}