Wykres (abstrakcyjny typ danych) - Graph (abstract data type)
W informatyce , o wykres jest abstrakcyjny typ danych , który ma na celu wdrożenie nieukierunkowane wykres i graf skierowany pojęć z zakresu teorii grafów w matematyce .
Struktura danych zawiera diagram skończonej (ewentualnie zmienny) zestawie z wierzchołkami (zwanych również węzły lub punkty ), wraz z zestawem nieuporządkowanych par tych wierzchołków w nieukierunkowane wykresu lub zestawu par uporządkowanych do skierowanego na wykresie. Te pary są znane jako krawędzie (zwane również linkami lub liniami ), a dla grafu skierowanego są również znane jako krawędzie, ale czasami także strzałki lub łuki . Wierzchołki mogą być częścią struktury grafu lub mogą być zewnętrznymi jednostkami reprezentowanymi przez indeksy całkowite lub referencje .
Struktura danych wykresu może również powiązać z każdą krawędzią pewną wartość krawędzi , taką jak etykieta symboliczna lub atrybut liczbowy (koszt, pojemność, długość itp.).
Operacje
Podstawowe operacje zapewniane przez grafową strukturę danych G zwykle obejmują:
- przylega( G , x , y ) : sprawdza, czy istnieje krawędź od wierzchołka x do wierzchołka y ;
- sąsiedzi( G , x ) : wyświetla wszystkie wierzchołki y takie, że istnieje krawędź od wierzchołka x do wierzchołka y ;
- add_vertex( G , x ) : dodaje wierzchołek x , jeśli go tam nie ma;
- remove_vertex( G , x ) : usuwa wierzchołek x , jeśli tam jest;
- add_edge( G , x , y ) : dodaje krawędź z wierzchołka x do wierzchołka y , jeśli go tam nie ma;
- remove_edge( G , x , y ) : usuwa krawędź z wierzchołka x do wierzchołka y , jeśli tam jest;
- get_vertex_value( G , x ) : zwraca wartość skojarzoną z wierzchołkiem x ;
- set_vertex_value( G , x , v ) : ustawia wartość skojarzoną z wierzchołkiem x na v .
Struktury, które kojarzą wartości z krawędziami, zwykle zapewniają również:
- get_edge_value( G , x , y ) : zwraca wartość skojarzoną z krawędzią ( x , y );
- set_edge_value( G , x , y , v ) : ustawia wartość skojarzoną z krawędzią ( x , y ) na v .
Wspólne struktury danych do reprezentacji na wykresach
- Lista sąsiedztwa
- Wierzchołki są przechowywane jako rekordy lub obiekty, a każdy wierzchołek przechowuje listę sąsiednich wierzchołków. Ta struktura danych umożliwia przechowywanie dodatkowych danych na wierzchołkach. Dodatkowe dane mogą być przechowywane, jeśli krawędzie są również przechowywane jako obiekty, w którym to przypadku każdy wierzchołek przechowuje swoje incydentalne krawędzie, a każda krawędź przechowuje swoje incydentalne wierzchołki.
- Macierz sąsiedztwa
- Dwuwymiarowa macierz, w której wiersze reprezentują wierzchołki źródłowe, a kolumny wierzchołki docelowe. Dane na krawędziach i wierzchołkach muszą być przechowywane zewnętrznie. Między każdą parą wierzchołków można przechowywać tylko koszt jednej krawędzi.
- Macierz incydentów
- Dwuwymiarowa macierz, w której wiersze reprezentują wierzchołki, a kolumny krawędzie. Wpisy wskazują relację padania między wierzchołkiem w rzędzie a krawędzią w kolumnie.
Poniższa tabela podaje koszt złożoności czasowej wykonywania różnych operacji na wykresach, dla każdej z tych reprezentacji, przy czym | V | liczba wierzchołków i | E | liczba krawędzi. W reprezentacjach macierzowych wpisy kodują koszt podążania za krawędzią. Zakłada się, że koszt krawędzi, które nie występują, wynosi ∞.
Lista sąsiedztwa | Macierz sąsiedztwa | Macierz incydentów | |
---|---|---|---|
Wykres sklepu | |||
Dodaj wierzchołek | |||
Dodaj krawędź | |||
Usuń wierzchołek | |||
Usuń krawędź | |||
Są wierzchołki x i y w sąsiedztwie (przy założeniu, że ich położenie składowania są znane)? | |||
Uwagi | Powoli usuwa wierzchołki i krawędzie, ponieważ musi znaleźć wszystkie wierzchołki lub krawędzie | Powoli dodawanie lub usuwanie wierzchołków, ponieważ macierz musi zostać zmieniona/skopiowana | Powoli dodawanie lub usuwanie wierzchołków i krawędzi, ponieważ macierz musi zostać przeskalowana/skopiowana |
Listy sąsiedztwa są generalnie preferowane, ponieważ skutecznie reprezentują rzadkie wykresy . Macierz sąsiedztwa jest preferowana, jeśli graf jest gęsty, czyli liczba krawędzi | E | jest zbliżona do kwadratu liczby wierzchołków, | V | 2 , lub jeśli trzeba być w stanie szybko spojrzeć w górę, jeśli istnieje krawędź łącząca dwa wierzchołki.
reprezentacje równoległe
Równoległość problemów z grafami napotyka poważne wyzwania: obliczenia oparte na danych, problemy nieustrukturyzowane, słaba lokalizacja i wysoki współczynnik dostępu danych do obliczeń. Reprezentacja graficzna stosowana w architekturach równoległych odgrywa znaczącą rolę w sprostaniu tym wyzwaniom. Źle dobrane reprezentacje mogą niepotrzebnie podnosić koszt komunikacji algorytmu, co zmniejszy jego skalowalność . Poniżej rozważane są architektury pamięci współdzielonej i rozproszonej.
W przypadku modelu pamięci współdzielonej reprezentacje grafowe używane do przetwarzania równoległego są takie same jak w przypadku sekwencyjnym, ponieważ równoległy dostęp tylko do odczytu do reprezentacji grafowej (np. listy sąsiedztwa ) jest wydajny w przypadku pamięci współdzielonej.
Pamięć rozproszona
W modelu pamięci rozproszonej typowym podejściem jest podzielenie zbioru wierzchołków grafu na zbiory . Oto ilość dostępnych elementów przetwarzających (PE). Partycje zestawu wierzchołków są następnie rozdzielane na PE z dopasowanym indeksem, dodatkowo do odpowiednich krawędzi. Każdy PE ma własną reprezentację podgrafu , gdzie krawędzie z punktem końcowym w innej partycji wymagają szczególnej uwagi. W przypadku standardowych interfejsów komunikacyjnych, takich jak MPI , identyfikator PE będącego właścicielem drugiego punktu końcowego musi być możliwy do zidentyfikowania. Podczas obliczeń w algorytmach grafu rozproszonego przekazywanie informacji wzdłuż tych krawędzi implikuje komunikację.
Podział grafu na partycje musi być wykonany ostrożnie — istnieje kompromis między niską komunikacją a partycjonowaniem o równym rozmiarze. Podział grafu na partycje to problem NP-trudny, więc nie jest możliwe ich obliczenie. Zamiast tego używane są następujące heurystyki.
Partycjonowanie 1D: każdy procesor otrzymuje wierzchołki i odpowiadające im krawędzie wychodzące. Można to rozumieć jako rozkład macierzy sąsiedztwa na wiersze lub kolumny. W przypadku algorytmów działających na tej reprezentacji wymaga to etapu komunikacji „wszystko do wszystkich”, a także rozmiarów buforów komunikatów, ponieważ każdy PE potencjalnie ma krawędzie wychodzące do każdego innego PE.
Partycjonowanie 2D: każdy procesor otrzymuje podmacierz macierzy sąsiedztwa. Załóżmy, że procesory są wyrównane w prostokącie , gdzie i oznaczają liczbę elementów przetwarzających odpowiednio w każdym wierszu i kolumnie. Następnie każdy procesor otrzymuje podmatrycę matrycy przylegania wymiaru . Można to zwizualizować jako wzór szachownicy w macierzy. Dlatego każda jednostka przetwarzania może mieć tylko krawędzie wychodzące do PE w tym samym rzędzie i kolumnie. Ten ograniczającą ilość partnerów komunikacyjnych dla każdego PE do wyczerpania możliwych nich.
Skompresowane reprezentacje
Wykresy z bilionami krawędzi występują w uczeniu maszynowym , analizie sieci społecznościowych i innych obszarach. Reprezentacje skompresowanych wykresów zostały opracowane w celu zmniejszenia wymagań we/wy i pamięci. Ogólne techniki, takie jak kodowanie Huffmana, mają zastosowanie, ale listę sąsiedztwa lub macierz sąsiedztwa można przetwarzać w określony sposób, aby zwiększyć wydajność.
Zobacz też
- Przechodzenie po wykresach dla strategii chodzenia po wykresach
- Baza wykresów dla trwałości wykresu (struktury danych)
- Przepisywanie wykresów dla transformacji wykresów opartych na regułach (struktury danych wykresów)
- Oprogramowanie do rysowania wykresów dla oprogramowania, systemów i dostawców systemów do rysowania wykresów
Bibliografia
Zewnętrzne linki
- Boost Graph Library: potężna biblioteka grafów C++ sa Boost (biblioteki C++)
- Networkx: biblioteka grafów Pythona
- GraphMatcher program Java do wyrównywania skierowanych/niekierowanych wykresów.
- GraphBLAS Specyfikacja interfejsu bibliotecznego dla operacji na grafach, ze szczególnym uwzględnieniem grafów rzadkich.