Некоторые из работ Конора МакБрайда, Diff , Dissect , связывают производную типов данных с их «типом контекстов с одной дырой». То есть, если вы берете производную от типа, который у вас остался, с типом данных, который показывает вам, как тип данных выглядит изнутри в любой заданной точке.

Так, например, если у вас есть список (в Haskell)

data List a = [] | a : List a

это соответствует

data List a = 1 + a * List a

и благодаря небольшой математической магии, производная

data ListDeriv a = List a * List a

что означает, что в любой точке списка будет список слева и список справа. Мы можем перебрать оригинальный список, используя производную структуру данных.

Теперь мне интересно сделать что-то похожее с графиками. Общее представление графов - это набор вершин и ребер, которые могут быть наивно реализованы с помощью типа данных, такого как:

data Gr a b i = Gr [(i,a)] [(i,i,b)]

Если я правильно понимаю, производная этого типа данных по отношению к индексу графа iдолжна выглядеть примерно так.

data GrDeriv a b i = d/di (Gr a b i)
     = d\di ( [a*i] * [b*i^2] )
     = (d\di [a*i]) * [b*i^2] ) + [a*i]*(d/di [b*i^2])
     = (a* [a*i] * [a*i]) * [b*i^2] ) 
       + [a*i] * (2*b*i) *[b*i^2]*[b*i^2])
     = InNodes { nodesLeft :: [(a,i)]
               , nodeLbl :: a
               , nodesRight :: [(a,i)]
               , edges :: [(b,i,i)] }
     | InEdges { nodes :: [(a,i)]
               , adjNode :: Either (b,i) (b,i)
               , edgesLeft :: [(b,i,i)]
               , edgesRight :: [(b,i,i)] }

Я понял это благодаря использованию правила продукта и правил цепочки для деривативов, и, хотя, возможно, есть некоторые ошибки, похоже, что он следует общей схеме. В этой структуре вы будете либо сфокусированы на узлах (конструктор InNodes), либо на кромках (в ребрах) и вам будет предоставлено место, где вы увидите соответствующие данные.

Но это не то, на что я надеялся. Я надеялся на конструкцию, более тесно связанную с интерфейсом библиотеки функциональных графов Мартина Эрвигса. В частности, я хочу видеть в узле контекст, представляющий метку узла и два списка смежности, один для исходящего, один для входящего.

Node a b = ([(i,b)],a,[(i,b)])

Однако я действительно надеюсь, что у представления смежности есть некоторые общие термины с производной, одинокой табличкой a, в каждом месте отверстия представление соседства / расчленение каждого ребра.

Поскольку производная не является той же функцией, что и оригинал, но интеграция производной является (своего рода), существует ли какой-либо аналог интеграции, который будет служить для преобразования производной в коллекцию контекстов узла? Заметьте, не прямая интеграция для восстановления исходной структуры, а структура, эквивалентная исходной, но в более дружественном алгоритму представлении.

Если есть, я надеюсь, что структуры типов отношений могут быть определены с помощью некоторого простого языка «набора вершин и ребер», и я могу получить эффективную библиотеку для работы с этой структурой. Такая реализация может быть использована для изучения структур "вне теории графов": гиперграфы, симплициальные комплексы ...

Так. Эта идея кажется осуществимой? Полезно? Было ли какое-нибудь исследование этого типа вещей, о котором я мог бы прочитать больше?

добавление

Как прокомментировал Кертис F , множество узлов и ребер не является точно графом. Тем не менее, все графики могут быть представлены такими, и я считаю это достаточно распространенным представлением. Я видел (очень грубую спецификацию) используемую в исследованиях, которые применяют теорию графов для оптимизации беспроводных сетей различными способами. Вот пример открытого доступа, DRAND *. Это поднимает вопрос, какова связь между презентацией и как какое-то программное обеспечение может быть реализовано на основе исследования.$G=(V,E)$

Тем не менее, я не совсем против изменения входной спецификации с на что-то другое. Например, с учетом типа индекса , узлы метки, и метки ребер, . Тогда график (приблизительно) является функцией от индексов до метки и списка ребер.$G=(V,E)$$I$$V$$E$

$$G = I \to (V * I \to E)$$

Это, я уверен, может быть выражено (теория категорий?) Как

$$G = (V * E^{I})^{I} \tag{1}$$

или

$$G = V^I * E^{I*I}$$

который можно рассматривать как набор вершин и ребер - учитывая достаточно предостережений. Однако не ясно, имеет ли значение производная :$(1)$

$$G' = \ln(V * E^{I}) * (V * E^{I})^{I} * (\ln(E) * V * E^{I})$$

Я, например, думаю, что это показывает некоторые обещания, но мне не хватает изощренности, чтобы идти дальше. Я знаю, что должна быть какая-то работа по изучению связи дальше.

* В случае разрыва связи, цитирование: Rhee, Injong, et al. «DRAND: распределенное рандомизированное планирование TDMA для беспроводных специальных сетей». Операции IEEE по мобильным вычислениям 8.10 (2009): 1384-1396.

Ваш тип на Grсамом деле не соответствует графам, потому что он включает много экземпляров, которые явно не являются графами, потому что индексы ребер не обязательно должны быть фактическими индексами вершин.

Например,

$$V = \{A, B\} \;\;\;\; E = \{(C, D, e)\}$$

не является графиком, но допускается в вашем типе как

Gr [(1, A), (2, B)] [(3, 4, e)]

Скорее, ваш Grсоответствует буквально списку помеченных индексов и отдельному, не связанному, списку помеченных пар индексов. Вот почему вы получаете такую ​​«буквальную» производную Gr, которая не соответствует «дырам» в графах.

Существует также печальная проблема заботы о порядке вершин / ребер (видимых в nodesLeft/Rightи edgesLeft/Rightразличиях), но это можно исправить, используя Setвместо списка.

---

Вот тип, выраженный в Haskell, который, я думаю, более точно соответствует (непустым) графам:

data Graph v e = Lone v | Joined v (Graph (v, ([e], [e])) e)

Для простоты я вместо этого рассмотрю полные, простые, неориентированные графы:

data Graph v e = Lone v | Joined v (Graph (v, e) e)

(Для полноты расслабления e = Boolотметьте наличие краев)

Обратите внимание, что Graphэто рекурсивный (и фактически параметрически рекурсивный). Это то, что позволяет нам ограничивать тип только графами, а не просто списками смежности в сочетании со списками вершин.

Написано более алгебраически,

$$G(v, e) = v + v * G(v * e, e)$$

$e$$v$$G$

$$G(v) = v + v * G(v * e)$$

Повторно расширяясь, мы получаем фиксированную точку

$$G(v) = v^1 e^{\binom 1 2} + v^2 e^{\binom 2 2} + v^3 e^{\binom 3 2} + v^4 e^{\binom 4 2} + \dots$$

Это имеет смысл, так как (полный) граф

• Одна вершина и нет ребер
• Две вершины и одно ребро
• Три вершины и три ребра
• Четыре вершины и четыре выбирают 2 = 6 ребер
• ....

$k$$G_k(v) = v^k e^{\binom k 2}$$G(v) = G_1(v) + G_2(v) + \dots$

который имеет производную

$$\frac d {dv} G(v) = \sum_{i=1} G_i'(v)$$

$$G_k'(v) = \frac d {dv} \left[ v^k e^{\frac {k(k-1)} 2} \right] = k v^{k-1} e^{\frac {k(k-1)} 2}$$

$G_{k-1}(v) = v^{k-1} e^{\frac {(k-1)(k-2)} 2}$$G_k'(v) = G_{k-1}(v) * k * e^{k-1}$

$k$$k-1$$k-1$$k-1$$k$

data SimpleGraph v e = Lone v | Joined v (SimpleGraph (v, e) e)

data SimpleGraphHole v e = Empty
                         | InsertLater v (SimpleGraphHole (v, e) e)
                         | InsertHere (SimpleGraph (v, e) e)

Исправление порядка в этом графике

Эта версия структуры данных Graph является в основном связанным списком, и поэтому она кодирует порядок вершин. Хотя это может быть исправлено в вашей версии списка смежности с помощью набора, это не так прямо здесь.

Я думаю, что вы можете изменить древовидную структуру данных, чтобы выполнить тот же тип параметрической рекурсии, когда корень играет роль, которую играет «голова» SimpleGraph. Благодаря интерфейсу результирующих наборов деревьев порядок / базовая структура становится невидимой (или даже канонической, если вас не интересуют быстрые обновления).

Ваше предлагаемое производное

Вы предложили производный тип; Я изменю это, чтобы сопоставить метки и индексы, как я сделал:([(v,e)], [(v,e)])

$\int \frac 1 {(1 - ve)^2}$$C + \frac v {1 - ve}$(v, [(v, e)])