Einige der Arbeiten von Conor McBride, Diff , Dissect , beziehen die Ableitung von Datentypen auf ihre "Art von Ein-Loch-Kontexten". Das heißt, wenn Sie die Ableitung des Typs nehmen, bleibt ein Datentyp übrig, der Ihnen zeigt, wie der Datentyp an einem bestimmten Punkt von innen aussieht.

So zum Beispiel, wenn Sie eine Liste haben (in Haskell)

data List a = [] | a : List a

das entspricht

data List a = 1 + a * List a

und durch ein wenig mathematische Magie ist die Ableitung

data ListDeriv a = List a * List a

Dies bedeutet, dass sich an jeder Stelle der Liste eine Liste links und eine Liste rechts befindet. Wir können die ursprüngliche Liste mithilfe der abgeleiteten Datenstruktur zippen.

Jetzt bin ich daran interessiert, etwas Ähnliches mit Diagrammen zu machen. Eine gebräuchliche Darstellung von Graphen ist eine Reihe von Eckpunkten und Kanten, die mit einem Datentyp wie dem folgenden naiv implementiert werden können:

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

Wenn ich es richtig verstehe, sollte eine Ableitung dieses Datentyps in Bezug auf den Diagrammindex ungefähr iso aussehen.

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

Ich habe dies durch die Verwendung der Produktregel und der Kettenregeln für Derivate herausgefunden, und obwohl möglicherweise einige Fehler vorliegen, scheint es dem allgemeinen Schema zu folgen. In dieser Struktur konzentrieren Sie sich entweder auf Knoten (InNodes-Konstruktor) oder Kanten (In Kanten), und an der angegebenen Stelle werden die relevanten Daten angezeigt.

Aber darauf habe ich nicht gehofft. Ich hatte auf ein Konstrukt gehofft, das enger mit der Schnittstelle der Martin Erwigs Functional Graph Library verwandt ist. Insbesondere möchte ich an einem Knoten einen Kontext sehen, der die Bezeichnung des Knotens darstellt, und zwei Adjazenzlisten, eine für ausgehende und eine für eingehende.

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

Ich sehe jedoch Hoffnung, da die Adjazenzdarstellung einige Begriffe gemeinsam hat mit der Ableitung, dem Einzellabel, aund an jeder Lochposition der Adjazenzdarstellung / Dissektion jeder Kante.

Da ein Derivat nicht dieselbe Funktion wie das Original hat, aber eine Integration des Derivats (irgendwie) ist, gibt es eine Art Integrationsanalogon, das dazu dient, das Derivat in eine Sammlung von Knotenkontexten umzuwandeln? Wohlgemerkt keine direkte Integration, um die ursprüngliche Struktur wiederherzustellen, sondern eine Struktur, die der ursprünglichen entspricht, jedoch algorithmisch darstellbar ist.

Wenn dies der Fall ist, hoffe ich, dass Beziehungstypstrukturen durch eine einfache Sprache für "Scheitelpunkte und Kanten" angegeben werden können, und ich kann eine effiziente Bibliothek für die Arbeit mit dieser Struktur ableiten. Eine solche Implementierung könnte verwendet werden, um Strukturen "jenseits der Graphentheorie" zu untersuchen: Hypergraphen, einfache Komplexe ...

So. Scheint diese Idee machbar? Nützlich? Gab es eine Studie zu dieser Art von Dingen, über die ich mehr lesen konnte?

Nachtrag

Wie von Curtis F kommentiert , ist eine Menge von Knoten und Kanten nicht genau ein Graph. Alle Graphen können jedoch durch solche dargestellt werden, und ich finde es allgemein genug Präsentation. Ich habe gesehen, dass (die sehr grobe Spezifikation) in der Forschung verwendet wird, die die Graphentheorie auf verschiedene Arten auf die Optimierung von drahtlosen Netzwerken anwendet. Hier ist ein Open-Access-Beispiel, DRAND *. Dies wirft die Frage auf, in welcher Beziehung die Präsentation zu der Frage steht, wie bestimmte Software basierend auf den Recherchen implementiert werden könnte. $G=(V,E)$

Das heißt, ich bin nicht ganz dagegen, die Eingangsspezifikation von auf etwas anderes zu ändern . Zum Beispiel kann ein Indextyp gegeben , Knotenetiketten, und Kanten Etiketten, . Dann ist das Diagramm (ungefähr) eine Funktion von Indizes zu einer Beschriftungs- und Kantenliste. $G=(V,E)$ $I$ $V$ $E$

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

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

Ich bin mir ziemlich sicher, dass sich dies so ausdrücken lässt (Kategorietheorie?)

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

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

oder

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

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

das kann als eine Reihe von Ecken und Kanten gesehen werden - mit genügend Einschränkungen. Es ist jedoch nicht klar, ob die Ableitung von sinnvoll ist: $(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})$

Ich denke, es ist vielversprechend, aber mir fehlt die Raffinesse, um noch weiter zu gehen. Ich weiß, dass es da draußen Arbeit geben muss, um die Verbindung weiter zu untersuchen.

* Falls die Verbindung jemals unterbrochen wird, zitieren: Rhee, Injong, et al. "DRAND: Verteilte randomisierte TDMA-Planung für drahtlose Ad-hoc-Netzwerke." IEEE Transactions on Mobile Computing 8.10 (2009): 1384 & ndash; 1396.

graph-theory type-theory Trevor Cook
quelle

Der Link, den Sie für die Forschung bereitstellen, ist tot. Können Sie einen dauerhafteren Link angeben, wie zum Beispiel zu DOI oder der Zeitschrift, in der es veröffentlicht wurde?

Curtis F

Ihr Typ Grentspricht nicht wirklich Grafiken, da er viele Instanzen enthält, die eindeutig keine Grafiken sind, da die Kantenindizes keine tatsächlichen Scheitelpunktindizes sein müssen.

Beispielsweise,

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

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

ist kein Graph, aber in Ihrem Typ als erlaubt

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

Ihr Grentspricht vielmehr wörtlich einer Liste mit beschrifteten Indizes und einer separaten, nicht zusammenhängenden Liste mit beschrifteten Indexpaaren. Aus diesem Grund erhalten Sie eine solche "wörtliche" Ableitung Gr, die nicht "Löchern" in Diagrammen entspricht.

Es gibt auch das unglückliche Problem, sich um die Reihenfolge der Eckpunkte / Kanten zu kümmern (sichtbar in nodesLeft/Rightund edgesLeft/RightUnterscheidungen), aber dies kann durch die Verwendung einer Setanstelle einer Liste behoben werden .

Hier ist ein in Haskell ausgedrückter Typ, der meiner Meinung nach eher (nicht leeren) Diagrammen entspricht:

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

Der Einfachheit halber werde ich stattdessen vollständige, einfache, ungerichtete Diagramme betrachten:

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

(Um die Vollständigkeit zu entspannen, e = Boolmarkieren Sie die Kantenpräsenz.)

Beachten Sie, dass dies Graphrekursiv ist (und zwar parametrisch rekursiv). Dies ermöglicht es uns, den Typ auf nur Diagramme und nicht nur Adjazenzlisten in Kombination mit Scheitelpunktlisten zu beschränken.

Algebraischer geschrieben,

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

Durch wiederholtes Erweitern erhalten wir den Fixpunkt

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$

Dies ist sinnvoll, da es sich entweder um eine (vollständige) Grafik handelt

Ein Eckpunkt und keine Kanten
Zwei Ecken und eine Kante
Drei Ecken und drei Kanten
Vier Eckpunkte und vier wählen 2 = 6 Kanten
....

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

welches Derivat hat

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

Fixing Order in dieser Grafik

Diese Version der Graph-Datenstruktur ist im Grunde genommen eine verknüpfte Liste und kodiert daher die Reihenfolge der Eckpunkte. Während dies in Ihrer Adjazenzlisten-Version mit einem Set behoben werden konnte, ist es hier nicht so direkt.

Ich denke, Sie können eine Baumdatenstruktur ändern, um dieselbe Art von parametrischer Rekursion durchzuführen, wobei die Wurzel die Rolle spielt, in der der "Kopf" spielt SimpleGraph. Durch die Schnittstelle der resultierenden Baumsätze wird die Reihenfolge / zugrunde liegende Struktur unsichtbar (oder sogar kanonisch, wenn Sie nicht an schnellen Updates interessiert sind).

Ihr vorgeschlagenes Derivat

Sie haben einen abgeleiteten Typ vorgeschlagen. Ich ändere es, um die Bezeichnungen und Indizes so zusammenzufügen, wie ich es getan habe:([(v,e)], [(v,e)])

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

Curtis F
quelle

Bezieht sich die Ableitung eines Diagramms auf Adjazenzlisten?

Nachtrag

Antworten:

Fixing Order in dieser Grafik

Ihr vorgeschlagenes Derivat