Certaines œuvres de Conor McBride, Diff , Dissect , relient la dérivée des types de données à leur "type de contextes à un trou". Autrement dit, si vous prenez la dérivée du type, vous vous retrouvez avec un type de données qui vous montre à quoi ressemble le type de données de l'intérieur à un moment donné.

Donc, par exemple, si vous avez une liste (en Haskell)

data List a = [] | a : List a

cela correspond à

data List a = 1 + a * List a

et à travers un peu de magie mathématique, le dérivé est

data ListDeriv a = List a * List a

ce qui signifie que, à tout moment de la liste, il y aura une liste à gauche et une liste à droite. Nous pouvons parcourir la liste d'origine en utilisant la structure de données dérivée.

Maintenant, je suis intéressé à faire quelque chose de similaire avec des graphiques. Une représentation courante des graphiques est un ensemble de sommets et d'arêtes, qui peut être implémenté naïvement avec un type de données tel que:

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

Si je comprends bien, un dérivé de ce type de données, par rapport à l'index du graphique i, devrait ressembler à quelque chose.

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

Je l'ai obtenu grâce à l'utilisation de la règle de produit et des règles de chaîne pour les produits dérivés, et bien qu'il puisse y avoir des erreurs, il semble suivre le schéma général. Dans cette structure, vous serez concentré sur les nœuds (constructeur InNodes) ou les bords (dans les bords) et compte tenu de la place, vous verrez les données pertinentes.

Mais ce n'est pas ce que j'espérais. J'espérais une construction plus étroitement liée à l'interface de Martin Erwigs Functional Graph Library. Plus précisément, je veux voir à un nœud un contexte représentant l'étiquette du nœud et deux listes d'adjacence, une pour les sorties, une pour les entrées.

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

Je vois cependant de l'espoir, car la représentation de l'adjacence a des termes en commun avec le dérivé, la seule étiquette,, aà chaque emplacement de trou, la représentation / dissection de l'adjacence de chaque bord.

Puisqu'un dérivé n'est pas la même fonction que l'original, mais une intégration du dérivé est (kindof), existe-t-il une sorte d'analogue d'intégration qui servira à transformer le dérivé en une collection de contextes de nœuds? Pas une intégration directe pour récupérer la structure d'origine, rappelez-vous, mais une structure équivalente à l'original mais dans une représentation plus conviviale pour les algorithmes.

S'il y en a, j'espère que les structures de type relation peuvent être spécifiées par un langage simple "ensemble de sommets et d'arêtes" et je peux dériver une bibliothèque efficace pour travailler avec cette structure. Une telle implémentation pourrait être utilisée pour étudier des structures "au-delà de la théorie des graphes": hyper graphes, complexes simpliciaux ...

Donc. Cette idée semble-t-elle réalisable? Utile? Y a-t-il eu une étude sur ce type de chose sur laquelle je pourrais en savoir plus?

Addenda

Comme l'a commenté Curtis F , un ensemble de nœuds et d'arêtes n'est pas exactement un graphique. Cependant, tous les graphiques peuvent être représentés par un tel, et je le trouve assez courant. J'ai vu (la spécification très grossière) utilisé dans la recherche qui applique la théorie des graphes aux optimisations des réseaux sans fil de diverses manières. Voici un exemple en accès libre, DRAND *. Cela soulève la question de savoir quel est le lien entre la présentation et comment certains logiciels pourraient être mis en œuvre sur la base de la recherche. $G=(V,E)$

Cela dit, je ne suis pas entièrement opposé au changement de la spécification d'entrée de à autre chose. Par exemple, étant donné un type d'index , les étiquettes de noeud, , et les étiquettes de bord, . Ensuite, le graphique est (approximativement) une fonction des index à une liste d'étiquettes et de bords. $G=(V,E)$ $I$ $V$ $E$

g = je \to (V * je \to E)

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

Je suis sûr que cela peut être exprimé (théorie des catégories?) Comme

\begin{matrix} (1) & g = (V * E^{je})^{je} \end{matrix}

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

g = V^{je} * E^{je * je}

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

qui peut être vu comme un ensemble de sommets et d'arêtes - avec suffisamment de mises en garde. Cependant, il n'est pas clair si la dérivée de est significative: $(1)$

g^{'} = \ln (V * E^{je}) * (V * E^{je})^{je} * (\ln (E) * V * E^{je})

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

Pour ma part, je pense que cela semble prometteur, mais je manque de sophistication pour aller plus loin. Je sais qu'il doit y avoir un peu de travail à explorer la connexion plus loin.

* En cas de rupture du lien, citation: Rhee, Injong, et al. "DRAND: planification TDMA randomisée distribuée pour les réseaux ad hoc sans fil." Transactions IEEE sur l'informatique mobile 8.10 (2009): 1384-1396.

graph-theory type-theory cuisinier trevor
la source

Le lien que vous fournissez pour la recherche est mort. Pouvez-vous donner un lien plus permanent, comme DOI ou le journal dans lequel il a été publié?

Curtis F

Votre type Grne correspond pas vraiment aux graphiques, car il comprend de nombreuses instances qui ne sont clairement pas des graphiques, car les indices de bord n'ont pas besoin d'être de véritables indices de sommet.

Par exemple,

V = {UNE, B} E = {(C, ré, e)}

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

n'est pas un graphique, mais est autorisé dans votre type en tant que

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

Au contraire, votre Grcorrespond littéralement à une liste d'index étiquetés et à une liste distincte, sans rapport, de paires d'index étiquetées. C'est pourquoi vous obtenez un tel dérivé "littéral" Grqui ne correspond pas aux "trous" dans les graphiques.

Il y a aussi le malheureux problème de se soucier de l'ordre des sommets / arêtes (visible dans les distinctions nodesLeft/Rightet edgesLeft/Right), mais cela peut être résolu en utilisant un Setau lieu d'une liste.

Voici un type exprimé en Haskell qui, je pense, correspond plus étroitement aux graphiques (non vides):

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

Par souci de simplicité, je considérerai plutôt des graphiques complets, simples et non orientés:

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

(Pour détendre la plénitude, laissez la e = Boolprésence de bord de marque)

Notez que Graph c'est récursif (et en fait, récursif paramétriquement). C'est ce qui nous permet de nous limiter le type aux seuls graphes et pas seulement aux listes d'adjacence combinées aux listes de sommets.

Écrit plus algébriquement,

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

En augmentant à plusieurs reprises, nous obtenons le point fixe

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

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

Cela a du sens, car un graphique (complet) est soit

Un sommet et pas d'arêtes
Deux sommets et un bord
Trois sommets et trois arêtes
Quatre sommets et quatre choisissent 2 = 6 arêtes
....

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

qui a un dérivé

\frac{ré}{ré v} g (v) = \sum_{je = 1} g_{je}^{'} (v)

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

g_{k}^{'} (v) = \frac{ré}{ré 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)

Ordre de fixation dans ce graphique

Cette version de la structure de données Graph est fondamentalement une liste chaînée, et donc elle code l'ordre des sommets. Bien que cela puisse être corrigé dans votre version de liste d'adjacence en utilisant un ensemble, ce n'est pas si direct ici.

Je pense que vous pouvez modifier une structure de données arborescente pour effectuer le même type de récursivité paramétrique, la racine jouant le rôle de la "tête" SimpleGraph. Par l'interface des ensembles d'arbres résultants, l'ordre / la structure sous-jacente devient invisible (ou même canonique, si vous n'êtes pas intéressé par les mises à jour rapides).

Votre dérivé proposé

Vous avez proposé un type dérivé; Je vais le changer pour confondre les étiquettes et les indices comme je l'ai fait:([(v,e)], [(v,e)])

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

Curtis F
la source

La dérivée d'un graphique est-elle liée aux listes d'adjacence?

Addenda

Réponses:

Ordre de fixation dans ce graphique

Votre dérivé proposé