Trzy sposoby przechowywania wykresu w pamięci, zalety i wady


90

Istnieją trzy sposoby przechowywania wykresu w pamięci:

  1. Węzły jako obiekty i krawędzie jako wskaźniki
  2. Macierz zawierająca wszystkie wagi krawędzi między numerowanymi węzłami x i y
  3. Lista krawędzi między numerowanymi węzłami

Wiem, jak napisać wszystkie trzy, ale nie jestem pewien, czy wymyśliłem wszystkie zalety i wady każdego z nich.

Jakie są zalety i wady każdego z tych sposobów przechowywania wykresu w pamięci?


3
Rozważałbym macierz tylko wtedy, gdyby wykres był bardzo połączony lub bardzo mały. W przypadku rzadko połączonych grafów, podejście obiekt / wskaźnik lub lista krawędzi zapewniłoby znacznie lepsze wykorzystanie pamięci. Ciekaw jestem, co oprócz przechowywania przeoczyłem. ;)
sarnold

2
Różnią się również złożonością czasową, macierz to O (1), a inne reprezentacje mogą się znacznie różnić w zależności od tego, czego szukasz.
msw

1
Pamiętam, że jakiś czas temu czytałem artykuł opisujący zalety sprzętowe implementacji wykresu jako macierzy na liście wskaźników. Niewiele o tym pamiętam, z wyjątkiem tego, że ponieważ masz do czynienia z ciągłym blokiem pamięci, w dowolnym momencie znaczna część zestawu roboczego może znajdować się w pamięci podręcznej L2. Z drugiej strony lista węzłów / wskaźników może zostać wystrzelona w pamięci i prawdopodobnie będzie wymagać pobrania, które nie trafi do pamięci podręcznej. Nie jestem pewien, czy się zgadzam, ale to ciekawa myśl.
nerraga

1
@Dean J: tylko pytanie o „węzły jako obiekty i krawędzie jako reprezentacje wskaźników”. Jakiej struktury danych używasz do przechowywania wskaźników w obiekcie? Czy to lista?
Timofey,

4
Nazwy zwyczajowe to: (1) odpowiednik listy sąsiedztwa , (2) macierz sąsiedztwa , (3) lista krawędzi .
Evgeni Sergeev

Odpowiedzi:


51

Jednym ze sposobów ich analizy jest pamięć i złożoność czasowa (która zależy od tego, jak chcesz uzyskać dostęp do wykresu).

Przechowywanie węzłów jako obiektów ze wskaźnikami do siebie

  • Złożoność pamięci dla tego podejścia wynosi O (n), ponieważ masz tyle obiektów, ile masz węzłów. Wymagana liczba wskaźników (do węzłów) wynosi maksymalnie O (n ^ 2), ponieważ każdy obiekt węzła może zawierać wskaźniki do maksymalnie n węzłów.
  • Złożoność czasowa dla tej struktury danych wynosi O (n) dla dostępu do dowolnego danego węzła.

Przechowywanie macierzy wag krawędzi

  • Byłaby to złożoność pamięci O (n ^ 2) dla macierzy.
  • Zaletą tej struktury danych jest to, że złożoność czasowa dostępu do dowolnego danego węzła wynosi O (1).

W zależności od algorytmu uruchomionego na wykresie i liczby węzłów, będziesz musiał wybrać odpowiednią reprezentację.


3
Uważam, że złożoność czasowa dla wyszukiwań w modelu obiektu / wskaźnika wynosi tylko O ​​(n), jeśli również przechowujesz węzły w oddzielnej tablicy. W przeciwnym razie musiałbyś przejść przez wykres w poszukiwaniu żądanego węzła, nie? Przechodzenie przez każdy węzeł (ale niekoniecznie przez każdą krawędź) na dowolnym grafie nie może być wykonane w O (n), prawda?
Barry Fruitman,

@BarryFruitman Jestem prawie pewien, że masz rację. BFS jest O (V + E). Ponadto, jeśli szukasz węzła, który nie jest połączony z innymi węzłami, nigdy go nie znajdziesz.
WilderField

10

Jeszcze kilka rzeczy do rozważenia:

  1. Model macierzowy łatwiej nadaje się do tworzenia wykresów z ważonymi krawędziami, dzięki przechowywaniu wag w macierzy. Model obiektu / wskaźnika musiałby przechowywać wagi krawędzi w tablicy równoległej, co wymaga synchronizacji z tablicą wskaźników.

  2. Model obiekt / wskaźnik działa lepiej z wykresami skierowanymi niż z wykresami nieukierunkowanymi, ponieważ wskaźniki musiałyby być utrzymywane w parach, które mogą stać się niezsynchronizowane.


1
Masz na myśli, że wskaźniki musiałyby być utrzymywane w parach z nieukierunkowanymi wykresami, prawda? Jeśli jest skierowany, po prostu dodajesz wierzchołek do listy sąsiedztwa określonego wierzchołka, ale jeśli jest niekierowany, musisz dodać jeden do listy sąsiedztwa obu wierzchołków?
FrostyStraw

@FrostyStraw Tak, dokładnie.
Barry Fruitman

8

Metoda obiektów i wskaźników ma trudności z wyszukiwaniem, jak niektórzy zauważyli, ale jest całkiem naturalna do robienia takich rzeczy, jak budowanie binarnych drzew wyszukiwania, gdzie jest dużo dodatkowej struktury.

Osobiście uwielbiam macierze sąsiedztwa, ponieważ znacznie ułatwiają wszelkiego rodzaju problemy, używając narzędzi z teorii grafów algebraicznych. (Na przykład k-ta potęga macierzy sąsiedztwa daje liczbę ścieżek o długości k od wierzchołka i do wierzchołka j. Dodaj macierz tożsamości przed pobraniem k-tej potęgi, aby uzyskać liczbę ścieżek o długości <= k. Weź rangę n-1 moll Laplacian, aby uzyskać liczbę rozpinanych drzew ... i tak dalej.)

Ale wszyscy mówią, że macierze sąsiedztwa są drogie w pamięci! Są tylko w połowie poprawne: możesz to obejść, używając rzadkich macierzy, gdy wykres ma kilka krawędzi. Rzadkie macierzowe struktury danych wykonują dokładnie pracę polegającą na utrzymywaniu listy przylegania, ale nadal mają pełną gamę dostępnych standardowych operacji macierzowych, zapewniając to, co najlepsze z obu światów.


7

Myślę, że twój pierwszy przykład jest trochę niejednoznaczny - węzły jako obiekty i krawędzie jako wskaźniki. Możesz je śledzić, przechowując tylko wskaźnik do jakiegoś węzła głównego, w którym to przypadku dostęp do danego węzła może być nieefektywny (powiedzmy, że chcesz węzła 4 - jeśli obiekt węzła nie jest dostarczony, może być konieczne wyszukanie go) . W takim przypadku stracisz również części wykresu, do których nie można dotrzeć z węzła głównego. Myślę, że tak właśnie jest w przypadku f64 rainbow, który przyjmuje, gdy mówi, że złożoność czasowa dostępu do danego węzła wynosi O (n).

W przeciwnym razie możesz również zachować tablicę (lub tablicę mieszającą) pełną wskaźników do każdego węzła. Umożliwia to O (1) dostęp do danego węzła, ale nieco zwiększa zużycie pamięci. Jeśli n jest liczbą węzłów, a e jest liczbą krawędzi, złożoność przestrzenna tego podejścia wyniosłaby O (n + e).

Złożoność przestrzeni dla podejścia macierzowego byłaby wzdłuż linii O (n ^ 2) (zakładając, że krawędzie są jednokierunkowe). Jeśli wykres jest rzadki, w macierzy będzie dużo pustych komórek. Ale jeśli twój wykres jest w pełni połączony (e = n ^ 2), wypada to korzystnie w porównaniu z pierwszym podejściem. Jak mówi RG, przy takim podejściu możesz mieć mniej błędów pamięci podręcznej, jeśli alokujesz macierz jako jeden fragment pamięci, co może przyspieszyć śledzenie wielu krawędzi wokół wykresu.

Trzecie podejście jest prawdopodobnie najbardziej efektywne pod względem miejsca w większości przypadków - O (e) - ale oznaczałoby, że znalezienie wszystkich krawędzi danego węzła byłoby zadaniem O (e). Nie przychodzi mi do głowy przypadek, w którym byłoby to bardzo przydatne.


Lista krawędzi jest naturalna dla algorytmu Kruskala („dla każdej krawędzi spójrz w górę w Union-find”). Również Skiena (wyd. 2, strona 157) mówi o listach krawędzi jako o podstawowej strukturze danych dla wykresów w swojej bibliotece Combinatorica (która jest biblioteką ogólnego przeznaczenia wielu algorytmów). Wspomina, że ​​jedną z przyczyn takiego stanu rzeczy są ograniczenia nałożone przez model obliczeniowy Mathematica, czyli środowisko, w którym żyje Combinatorica.
Evgeni Sergeev


4

Jest jeszcze jedna opcja: węzły jako obiekty, krawędzie też jako obiekty, każda krawędź jest jednocześnie na dwóch podwójnie połączonych listach: lista wszystkich krawędzi wychodzących z tego samego węzła i lista wszystkich krawędzi wchodzących do tego samego węzła .

struct Node {
    ... node payload ...
    Edge *first_in;    // All incoming edges
    Edge *first_out;   // All outgoing edges
};

struct Edge {
    ... edge payload ...
    Node *from, *to;
    Edge *prev_in_from, *next_in_from; // dlist of same "from"
    Edge *prev_in_to, *next_in_to;     // dlist of same "to"
};

Narzut pamięci jest duży (2 wskaźniki na węzeł i 6 wskaźników na krawędź), ale otrzymujesz

  • Wstawienie węzła O (1)
  • O (1) wstawienie krawędzi (podane wskaźniki do węzłów „od” i „do”)
  • O (1) usunięcie krawędzi (biorąc pod uwagę wskaźnik)
  • Usunięcie węzła O (deg (n)) (biorąc pod uwagę wskaźnik)
  • O (deg (n)) znajdowanie sąsiadów węzła

Struktura może również przedstawiać raczej ogólny wykres: zorientowany multigraf z pętlami (tj. Możesz mieć wiele różnych krawędzi między tymi samymi dwoma węzłami, w tym wiele różnych pętli - krawędzie przechodzące od x do x).

Bardziej szczegółowe wyjaśnienie tego podejścia jest dostępne tutaj .


3

Okay, więc jeśli krawędzie nie mają wag, macierz może być tablicą binarną, a użycie operatorów binarnych może w tym przypadku sprawić, że wszystko pójdzie naprawdę, bardzo szybko.

Jeśli wykres jest rzadki, metoda obiektu / wskaźnika wydaje się znacznie wydajniejsza. Trzymanie obiektu / wskaźników w strukturze danych specjalnie w celu nakłonienia ich do jednego kawałka pamięci może być również dobrym planem lub inną metodą połączenia ich.

Lista sąsiedztwa - po prostu lista połączonych węzłów - wydaje się zdecydowanie najbardziej wydajna pod względem pamięci, ale prawdopodobnie również najwolniejsza.

Odwrócenie skierowanego wykresu jest łatwe w przypadku reprezentacji macierzowej i łatwe w przypadku listy sąsiedztwa, ale nie jest tak dobre w przypadku reprezentacji obiektu / wskaźnika.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.