В функциональной библиотеке Haskell (FGL) большинство алгоритмов графа зависят от функции "match", которая при заданных Node n
и a Graph g
возвращает c & g'
, где c
является Context
n
, а g'
- остальная часть графика (в котором нет ссылок на n
).
Единственный способ, которым я могу это сделать, - изучить каждый из контекстов в g
и удалить любые ребра, относящиеся к n
, и добавить их в контекст c
. Полагаю, это займет линейное время.
Мартин Эрвиг, который написал библиотеку, предлагает в эту бумагу, что это преобразование может быть выполнено в постоянном или, по крайней мере, подлинейном времени, Может ли кто-нибудь объяснить мне, как это делается?