A derivada de um gráfico está relacionada às listas de adjacência?

Alguns dos trabalhos de Conor McBride, Diff , Dissect , relacionam a derivada de tipos de dados ao seu "tipo de contextos de um buraco". Ou seja, se você pegar a derivada do tipo, ficará com um tipo de dado que mostra como o tipo de dado fica por dentro em qualquer ponto.

Então, por exemplo, se você tem uma lista (em Haskell)

data List a = [] | a : List a

isso corresponde a

data List a = 1 + a * List a

e através de um pouco de magia matemática, a derivada é

data ListDeriv a = List a * List a

que é interpretado como significando que, em qualquer ponto da lista, haverá uma lista à esquerda e uma lista à direita. Podemos percorrer a lista original usando a estrutura de dados derivada.

Agora, estou interessado em fazer algo semelhante com gráficos. Uma representação comum de gráficos é um conjunto de vértices e arestas, que podem ser implementados ingenuamente com um tipo de dados como:

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

Se eu entendi direito, uma derivada desse tipo de dados, com relação ao índice do gráfico i, deve ser algo parecido.

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)] }

Entendi isso através do uso da regra do produto e das regras da cadeia para derivativos e, embora possivelmente haja alguns erros, parece seguir o esquema geral. Nesta estrutura, você estará focado nos Nós (construtor InNodes) ou nas Arestas (nas arestas) e, considerando o local em que verá os dados relevantes.

Mas não era isso que eu esperava. Eu esperava um construto mais estreitamente relacionado à interface da Martin Erwigs Functional Graph Library. Especificamente, quero ver em um nó um contexto que representa o rótulo do nó e duas listas de adjacências, uma para saída e outra para entrada.

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

No entanto, vejo esperança, pois a representação de adjacência tem alguns termos em comum com a derivada, a etiqueta solitária a, em cada localização do furo, a representação / dissecção de adjacência de cada aresta.

Como uma derivada não tem a mesma função que a original, mas uma integração da derivada é (tipo), existe algum tipo de analógico de integração que servirá para transformar a derivada em uma coleção de contextos de nós? Não é uma integração direta para recuperar a estrutura original, lembre-se, mas uma estrutura equivalente à original, mas em uma representação mais amigável ao algoritmo.

Se houver, espero que as estruturas do tipo de relacionamento possam ser especificadas por uma linguagem fácil de "conjunto de vértices e arestas" e que eu possa derivar uma biblioteca eficiente para trabalhar com essa estrutura. Tal implementação poderia ser usada para estudar estruturas "além da teoria dos grafos": hiper grafos, complexos simples ...

Então. Essa ideia parece viável? Útil? Existe algum estudo sobre esse tipo de coisa sobre o qual eu possa ler mais?

Termo aditivo

$G=(V,E)$

$G=(V,E)$ $I$ $V$ $E$

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

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

Tenho certeza de que isso pode ser expresso (teoria das categorias?) Como

\begin{matrix} (1) & G = (V * E^{I})^{I} \end{matrix}

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

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

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

$(1)$

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

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

Eu acho que isso mostra alguma promessa, mas me falta sofisticação para ir além. Eu sei que deve haver algum trabalho por aí explorando a conexão ainda mais.

* Caso o link se quebre, cite: Rhee, Injong, et al. "DRAND: programação aleatória distribuída de TDMA para redes sem fio ad hoc." Transações IEEE sobre Computação Móvel 8.10 (2009): 1384-1396.

graph-theory type-theory cozinheiro de Trevor
fonte

O link que você fornece para a pesquisa está morto. Você pode fornecer um link mais permanente, como o DOI ou a revista em que foi publicado?

Curtis F

Respostas:

Seu tipo Grnão corresponde realmente a gráficos, porque inclui muitas instâncias que claramente não são gráficos, porque os índices de aresta não precisam ser índices reais de vértices.

Por exemplo,

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

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

não é um gráfico, mas é permitido no seu tipo como

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

Pelo contrário, o seu Gr corresponde literalmente a uma lista de índices rotulados e a uma lista separada e não relacionada de pares de índices rotulados. É por isso que você obtém uma derivada "literal" Grque não corresponde a "buracos" nos gráficos.

Há também o infeliz problema de se importar com a ordem dos vértices / arestas (visível no nodesLeft/RighteedgesLeft/Right distinções ), mas isso pode ser corrigido usando Setuma lista em vez de uma lista.

Aqui está um tipo expresso em Haskell que, penso, corresponde mais de perto aos gráficos (não vazios):

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

Para simplificar, considerarei gráficos completos, simples e não direcionados:

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

(Para relaxar a plenitude, deixe e = Bool marque a presença da borda)

Observe que Graph é recursivo (e, de fato, parametricamente recursivo). Isso é o que nos permite restringir o tipo a apenas gráficos e não apenas listas de adjacência combinadas com listas de vértices.

Escrito mais algebricamente,

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

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

$e$ $v$ $G$

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

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

Ao expandir repetidamente, obtemos o ponto fixo

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})} + ...

$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$

Isso faz sentido, já que um gráfico (completo) é

Um vértices e sem arestas
Dois vértices e uma aresta
Três vértices e três arestas
Quatro vértices e quatro escolhem 2 = 6 arestas
....

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

que tem derivado

\frac{d}{d v} G (v) = \sum_{i = 1} G_{i}^{'} (v)

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

G_{k}^{'} (v) = \frac{d}{d v} [v^{k} e^{\frac{k (k - 1)}{2}}] = k v^{k - 1} e^{\frac{k (k - 1)}{2}}

$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)

Ordem de Fixação neste gráfico

Esta versão da estrutura de dados do Graph é fundamentalmente uma lista vinculada e, portanto, codifica a ordem dos vértices. Embora isso possa ser corrigido na sua versão da lista de adjacências usando um Conjunto, não é tão direto aqui.

Eu acho que você pode modificar uma estrutura de dados em árvore para fazer o mesmo tipo de recursão paramétrica, com a raiz desempenhando o papel que a "cabeça" desempenha SimpleGraph . Pela interface dos conjuntos de árvores resultantes, a estrutura de ordem / subjacente se torna invisível (ou mesmo canônica, se você não estiver interessado em atualizações rápidas).

Sua derivada proposta

Você propôs um tipo derivado; Vou alterá-lo para confundir os rótulos e índices como fiz:([(v,e)], [(v,e)])

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

Curtis F
fonte