Wykres (abstrakcyjny typ danych) - Graph (abstract data type)

Skierowane wykres z trzech wierzchołków (niebieski kółka) i trzech krawędzi (czarne strzałki).

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.

Pamięć współdzielona

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ż

Bibliografia

Zewnętrzne linki