Что внутри орграфа Эрланга? - PullRequest
Новая
       29

Что внутри орграфа Эрланга?

2 голосов
/ 15 июля 2011

Отказ от ответственности: Автор новичок в Erlang.

Я хотел бы реализовать какой-нибудь алгоритм кратчайшего пути в Erlang.

Существует стандартная реализация структуры данных графа в Erlang: http://www.erlang.org/doc/man/digraph.html

Однако я не нашел никакой информации о фактической структуре данных, которую он использует.

В основном я хотел бы знать:

  • Каков наихудший результат получения всех «соседей» для действия вершины?
  • Какова наихудшая производительность при извлечении вершины из графа?

1 Ответ

7 голосов
/ 16 июля 2011

В орграфе используются 3 таблицы (вершины, ребра и соседние вершины).

Итак, обе эти операции являются O (1).

Взгляните на OTP-код, он чистый и в большинстве случаев идиоматичный Erlang. Gen.erl + gen_server.erl, proc_lib.erl и sys.erl в stdlib должны читаться :)

...