Niektóre prace Conora McBride'a, Diff , Dissect , wiążą pochodną typów danych z ich „typem jednootworowych kontekstów”. Oznacza to, że jeśli weźmiesz pochodną typu, pozostanie ci typ danych, który pokazuje, jak typ danych wygląda od wewnątrz w danym punkcie.
Na przykład, jeśli masz listę (w Haskell)
data List a = [] | a : List a
to odpowiada
data List a = 1 + a * List a
a poprzez małą matematyczną magię pochodną jest
data ListDeriv a = List a * List a
co jest interpretowane w ten sposób, że w dowolnym punkcie listy będzie lista po lewej stronie i lista po prawej stronie. Możemy spakować oryginalną listę za pomocą pochodnej struktury danych.
Teraz jestem zainteresowany zrobieniem czegoś podobnego z wykresami. Wspólną reprezentacją wykresów jest zestaw wierzchołków i krawędzi, który można naiwnie implementować za pomocą typu danych, takiego jak:
data Gr a b i = Gr [(i,a)] [(i,i,b)]
Jeśli dobrze to rozumiem, pochodna tego typu danych w odniesieniu do indeksu graficznego i
powinna być podobna.
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)] }
Osiągnąłem to dzięki zastosowaniu reguły produktu i reguł łańcucha dla instrumentów pochodnych i chociaż możliwe, że są pewne błędy, wydaje się, że są zgodne z ogólnym schematem. W tej strukturze będziesz się skupiał na Węzłach (konstruktor InNodes) lub Krawędziach (na krawędziach) i biorąc pod uwagę miejsce, w którym zobaczysz odpowiednie dane.
Ale nie na to liczyłem. Miałem nadzieję na konstrukcję bliższą interfejsowi funkcjonalnej biblioteki grafów Martina Erwigsa. W szczególności chcę zobaczyć w węźle kontekst reprezentujący etykietę węzła i dwie listy przyległości, jedną dla poczty wychodzącej, drugą dla poczty przychodzącej.
Node a b = ([(i,b)],a,[(i,b)])
Widzę jednak nadzieję, ponieważ reprezentacja przylegania ma pewne terminy wspólne z pochodną, samotną etykietą a
, w każdym miejscu otworu, reprezentacją / rozcięciem przyległości każdej krawędzi.
Ponieważ pochodna nie jest taką samą funkcją jak oryginał, ale całkowanie pochodnej jest (kindof), czy istnieje jakiś analog analogowy, który posłuży do przekształcenia pochodnej w zbiór kontekstów węzłów? Pamiętaj, że nie jest to bezpośrednia integracja w celu odzyskania oryginalnej struktury, ale struktura równoważna oryginałowi, ale w bardziej przyjaznej algorytmowi reprezentacji.
Jeśli tak, mam nadzieję, że struktury typów relacji mogą być określone przez jakiś łatwy język „zestaw wierzchołków i krawędzi” i mogę uzyskać wydajną bibliotekę do pracy z tą strukturą. Taka implementacja może być wykorzystana do badania struktur „poza teorią grafów”: hiper grafy, proste kompleksy ...
Więc. Czy ten pomysł wydaje się wykonalny? Przydatny? Czy są jakieś badania dotyczące tego rodzaju rzeczy, o których mógłbym przeczytać więcej?
Uzupełnienie
Jestem pewien, że można to wyrazić (teoria kategorii?) Jako
lub
Z jednej strony wydaje mi się, że to obiecuje, ale brakuje mi wyrafinowania, aby pójść dalej. Wiem, że musi być trochę pracy nad dalszym badaniem połączenia.
* W przypadku gdy link kiedykolwiek się zepsuje, cytowanie: Rhee, Injong i in. „DRAND: rozproszone losowe planowanie TDMA dla bezprzewodowych sieci ad hoc.” Transakcje IEEE na urządzeniach mobilnych 8.10 (2009): 1384–1396.
źródło
Odpowiedzi:
Twój typ
Gr
tak naprawdę nie odpowiada grafom, ponieważ zawiera wiele instancji, które wyraźnie nie są grafami, ponieważ indeksy krawędzi nie muszą być rzeczywistymi indeksami wierzchołków.Na przykład,
nie jest wykresem, ale jest dozwolony w twoim typie jako
Przeciwnie, twoja
Gr
dosłownie odpowiada liście oznaczonych indeksów i osobnej, niepowiązanej liście oznaczonych par indeksów. Dlatego otrzymujesz taką „dosłowną” pochodnąGr
, która nie odpowiada „dziurom” na wykresach.Istnieje również niefortunny problem dbania o kolejność wierzchołków / krawędzi (widocznych w
nodesLeft/Right
iedgesLeft/Right
różnicach), ale można to naprawić za pomocąSet
zamiast listy.Oto typ wyrażony w Haskell, który moim zdaniem bardziej odpowiada (niepustym) wykresom:
Dla uproszczenia rozważę zamiast tego kompletne, proste, bezkierunkowe wykresy:
(Aby rozluźnić kompletność,
e = Bool
zaznacz obecność krawędzi)Zauważ, że
Graph
jest rekurencyjny (i faktycznie parametrycznie rekurencyjny). To pozwala nam ograniczyć ten typ do samych wykresów, a nie tylko list przyległości w połączeniu z listami wierzchołków.Napisane bardziej algebraicznie,
Przez wielokrotne rozszerzanie otrzymujemy punkt stały
Ma to sens, ponieważ jest (kompletny) wykres
Wywołaj typ wykresów wielkości . Następniek Gk(v)=vke(k2) G(v)=G1(v)+G2(v)+…
który ma pochodną
PochodnaG′k(v)=ddv[vkek(k−1)2]=kvk−1ek(k−1)2
Zauważ, że , tak więcGk−1(v)=vk−1e(k−1)(k−2)2 G′k(v)=Gk−1(v)∗k∗ek−1
Oznacza to, że pochodną wykresu węzła jest wykres węzła , w połączeniu z krawędziami od usuniętego węzła do pozostałych węzłów oraz indeksem który węzeł zajmował na liście wierzchołki.k k−1 k−1 k−1 k
Ustalanie kolejności na tym wykresie
Ta wersja struktury danych Wykres jest zasadniczo listą połączoną, dlatego koduje kolejność wierzchołków. Chociaż można to naprawić w wersji z listą przylegania za pomocą zestawu, nie jest to tutaj tak bezpośrednie.
Myślę, że możesz zmodyfikować strukturę danych drzewa, aby wykonać ten sam rodzaj rekurencji parametrycznej, z rdzeniem pełniącym rolę „głowy”
SimpleGraph
. Dzięki interfejsowi powstałych zestawów drzew, kolejność / podstawowa struktura staje się niewidoczna (lub nawet kanoniczna, jeśli nie jesteś zainteresowany szybkimi aktualizacjami).Twoja proponowana pochodna
Zaproponowałeś typ pochodnej; Zmienię to, aby połączyć etykiety i indeksy:
([(v,e)], [(v,e)])
Można to zintegrować jako czyli , lub po prostu . Nie ma wystarczającej ilości informacji do zrekonstruowania całego wykresu , ponieważ informacje o „krawędzi” identyfikują tylko jeden wierzchołek.∫1(1−ve)2 C+v1−ve
(v, [(v, e)])
źródło