Czy pochodna wykresu jest związana z listami przyległości?

14

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

G=(V,E)

G=(V,E)IVE

G=I(VIE)

Jestem pewien, że można to wyrazić (teoria kategorii?) Jako

(1)G=(VEI)I

lub

G=VIEII

(1)

G=ln(VEI)(VEI)I(ln(E)VEI)

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.

trevor cook
źródło
Link, który podajesz do badań, jest martwy. Czy możesz podać bardziej trwały link, na przykład DOI lub czasopismo, w którym został opublikowany?
Curtis F

Odpowiedzi:

5

Twój typ Grtak 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,

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

nie jest wykresem, ale jest dozwolony w twoim typie jako

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

Przeciwnie, twoja Grdosł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/Righti edgesLeft/Rightróżnicach), ale można to naprawić za pomocą Setzamiast listy.


Oto typ wyrażony w Haskell, który moim zdaniem bardziej odpowiada (niepustym) wykresom:

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

Dla uproszczenia rozważę zamiast tego kompletne, proste, bezkierunkowe wykresy:

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

(Aby rozluźnić kompletność, e = Boolzaznacz obecność krawędzi)

Zauważ, że Graphjest 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,

G(v,e)=v+vG(ve,e)

evG

G(v)=v+vG(ve)

Przez wielokrotne rozszerzanie otrzymujemy punkt stały

G(v)=v1e(12)+v2e(22)+v3e(32)+v4e(42)+

Ma to sens, ponieważ jest (kompletny) wykres

  • Jeden wierzchołek i bez krawędzi
  • Dwa wierzchołki i jedna krawędź
  • Trzy wierzchołki i trzy krawędzie
  • Cztery wierzchołki i cztery wybierają 2 = 6 krawędzi

Wywołaj typ wykresów wielkości . NastępniekGk(v)=vke(k2)G(v)=G1(v)+G2(v)+

który ma pochodną

ddvG(v)=i=1Gi(v)

Pochodna

Gk(v)=ddv[vkek(k1)2]=kvk1ek(k1)2

Zauważ, że , tak więcGk1(v)=vk1e(k1)(k2)2Gk(v)=Gk1(v)kek1

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.kk1k1k1k

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)

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(1ve)2C+v1ve(v, [(v, e)])

Curtis F.
źródło