Hacker News 의견

• Graphviz는 독자적인 그래프 라이브러리를 가지고 있으며, 이는 다른 프로젝트에서 사용되지 않는다. 이 라이브러리는 장단점이 있다.

  • 이 경험을 바탕으로, 그들은 자신들만의 '두 번째 시스템 증후군'을 겪었다.
  • 그래프 라이브러리는 모듈식이며, 타입 안전하고, 효율적이어야 한다고 결정했다. 이는 "좋고, 빠르고, 저렴하게 - 둘 중 하나를 선택하라"는 말의 변형일 수 있다.
  • 모듈식이란 독립적으로 개발되고 컴파일되는 그래프 알고리즘 라이브러리 모음을 작성하고자 함을 의미한다.
  • 타입 안전이란 컴파일 시 또는 늦어도 링크 시 프로그래밍 오류를 감지하고자 함을 의미한다. 실행 시간 오류는 원치 않는다.
  • 효율성이란 그래프의 속성에 접근하는 것이 C 구조체의 필드처럼 저렴해야 함을 의미한다.
  • 이러한 목표가 가치가 있는지 논란의 여지가 있지만, 그들이 원하는 바였다. 유명한 C++ 창시자들이 그들의 연구실에 있었기 때문에 도움을 받을 수 있을 것으로 기대했고, C++에 다시 한 번 기회를 주기로 했다.
  • 인턴 출신인 Gordon Woodhull은 뛰어난 프로그래머로, 템플릿 C++에서 이러한 종류의 그래프 라이브러리를 구현했다. 이는 sourceforge를 통해 https://www.dynagraph.org/에서 공개되었다.
  • 다른 사람들은 코드가 어떻게 작동하는지 이해할 수 있을지 확신하지 못했기 때문에, 유명한 C++ 발명가들과 코드 리뷰를 진행했다. 복잡성의 벼랑을 넘어섰을 수도 있다는 것을 알았다.
  • 이는 Gordon의 잘못이 아니었고, 그는 계속해서 플러그를 꽂고 마이크로소프트 OLE에서도 동적 그래프 레이아웃 작업을 성공적으로 수행했다. 회고해보면, 이는 그들만의 프로젝트 자나두였을 수 있다.
  • 그들이 이에 몰두하는 동안, Gephi(Java)와 NetworkX 및 NetworKit(Python)과 같은 많은 것들이 등장했다.
  • John Ellson은 Graphviz의 일부를 작성한 매우 재능 있는 소프트웨어 엔지니어로, 주요 노력을 되살렸다.

• .NET에서 코딩하는 경우, 작고 기능이 풍부하지 않은 그래프 라이브러리 Arborescence를 시도해보길 바란다.

  • 이 라이브러리는 추상화, 알고리즘, 데이터 구조 사이의 좋은 분리를 제공한다고 믿는다.
  • 사용자는 자체 ID가 있는 엣지를 사용할 수도 있고, 즉석에서 펼쳐지는 암시적 그래프를 사용할 수도 있다.
  • 인접성(밖으로 향하는 이웃)과 인접성(밖으로 향하는 엣지 + 머리) 인터페이스를 모두 사용할 수 있다.
  • 라이브러리는 엣지 타입을 강제하지 않지만, 기본적인 꼬리-머리 쌍 구조를 유틸리티로 제공한다.

• 그래프는 데이터 구조나 데이터 타입이 아니라 추상화이다.

  • 기본적으로 그래프를 정의하는 데 필요한 것은 정점 집합과 이웃 함수뿐이다.
  • 모든 다른 것들은 사례별 제약 조건이다.
  • 하이퍼그래프를 고려하면, 그래프는 단순히 특별한 경우에 불과하다.
  • 데이터베이스 관점에서 생각하면, 그래프는 쿼리 최적화 및 인덱싱 문제이다.

• 프로그래밍 언어에 내장된 그래프 데이터 타입이 없는 이유에 대한 질문을 많이 받았다.

  • 이제 이 글과 같은 더 심도 있는 분석을 가리킬 수 있어 기쁘다.

• 중앙 장애물은 다음과 같다:

  • 간단하고 작은 그래프 문제의 경우, 벡터의 벡터 인접 리스트를 코딩하는 것이 충분히 쉽다.
  • 복잡하고 거대한 그래프 문제의 경우, 문제에 맞는 그래프 구현을 맞춤화하는 것 외에는 성능을 얻을 수 있는 방법이 없다.
  • 어떤 종류의 언어 지원이 도움이 될지 명확하지 않다.

• 이 글은 프로그래밍 언어에서 그래프 _알고리즘_이 더 잘 지원되지 않는 이유에 대한 질문에 대부분 답한다.

  • 그래프 지원을 일반적으로 살펴보면, OGM이 ORM만큼 인기가 없는 이유, JSON이 RDF보다 널리 사용되는 이유 등 더 넓은 질문을 볼 수 있다.
  • 결국 역사적인 이유와 그래프의 복잡성 때문에 개발자들 사이에서 잘 확장되지 않는다.

• 그래프 그리기 도구도 매우 실망스럽다.

  • 500개 이상의 노드가 있는 그래프에서는 출력물이 이해하기 어렵거나 복잡해진다.
  • 그래프를 계층적 구조로 자동으로 구성하고 탐색하기 좋은 인터페이스를 제공하는 기능이 부족하다.

• 이 글은 정말 멋지다.

  • "구현 선택지가 너무 많다"는 핵심 관찰에 대해, 실제로는 그렇지 않다.
  • 실제로 라이브러리는 모든 적합한 그래프 표현을 구현할 수 있다.
  • 알고리즘을 표현에 맞게 맞춤화하고, 하나의 표현에서 다른 표현으로 변환할 수 있다.

• Electric Clojure는 Clojure 자체(s-표현식)를 그래프 저작 구문으로 사용한다.

  • 그래프 저작 DSL은 범위, 제어 흐름, 추상화를 표현해야 하며, 이는 본질적으로 프로그래밍 언어와 동일하다.

• 테이블(데이터베이스 내의 테이블과 같은)과 같은 또 다른 유용한 데이터 타입이 있다.

  • 컴파일러가 데이터 구조의 구현을 선택하게 하면 프로그래밍 언어에서 진전이 있을 것이다.
  • 추상 구조(시퀀스, 맵, 세트, 테이블, 그래프 등)를 사용하고 프로그램 프로필에 기반하여 컴파일러가 구체적인 구현을 선택한다.