Jak przedstawić wykres z wieloma krawędziami dozwolonymi między węzłami i krawędziami, które mogą selektywnie znikać

11

Próbuję dowiedzieć się, jakiej struktury danych użyć do modelowania hipotetycznego, wyidealizowanego użycia sieci.

W moim scenariuszu wielu wrogich sobie nawzajem użytkowników próbuje utworzyć sieci komputerów, na których znane są wszystkie potencjalne połączenia. Komputery, z którymi musi się połączyć jeden użytkownik, mogą nie być takie same, jak komputery, z którymi musi się połączyć inny użytkownik; użytkownik 1 może potrzebować połączyć komputery A, B i D, podczas gdy użytkownik 2 może potrzebować połączyć komputery B, C i E.

wprowadź opis zdjęcia tutaj

Obraz wygenerowany przy pomocy NCTM Graph Creator

Myślę, że rdzeniem tego będzie niekierowany cykliczny wykres z węzłami reprezentującymi komputery i krawędziami reprezentującymi kable Ethernet. Jednak ze względu na charakter scenariusza istnieje kilka nietypowych funkcji, które wykluczają listy i macierze sąsiedztwa (przynajmniej bez nietrywialnych modyfikacji):

  1. krawędzie mogą zostać ograniczone do użycia; to znaczy, jeśli jeden użytkownik uzyska dane połączenie sieciowe, żaden inny użytkownik nie może z niego korzystać
    • w tym przykładzie zielony użytkownik nie może połączyć się z komputerem A, ale czerwony użytkownik podłączył B do E, mimo że nie ma bezpośredniego połączenia między nimi
  2. w niektórych przypadkach dana para węzłów zostanie połączona przez więcej niż jedną krawędź
    • w tym przykładzie istnieją dwa niezależne kable biegnące od D do E, więc zarówno zielony, jak i niebieski użytkownicy byli w stanie podłączyć te maszyny bezpośrednio; czerwony nie może jednak nawiązać takiego połączenia
  3. jeśli dwa komputery są połączone więcej niż jednym kablem, każdy użytkownik może posiadać nie więcej niż jeden z tych kabli

Będę musiał wykonać kilka operacji na tym wykresie, takich jak:

  • określanie, czy jakaś konkretna para komputerów jest podłączona dla danego użytkownika
  • określenie optymalnej ścieżki dla danego użytkownika do połączenia komputerów docelowych
  • identyfikacja połączenia komputerowego o największym opóźnieniu dla danego użytkownika (tj. najdłuższa ścieżka bez rozgałęzienia)

Moją pierwszą myślą było po prostu utworzenie kolekcji wszystkich krawędzi, ale to straszne przy wyszukiwaniu. Najlepszą rzeczą, jaką mogę teraz zrobić, jest zmodyfikowanie listy sąsiadów, tak aby każda pozycja na liście zawierała nie tylko długość krawędzi, ale także jej koszt i obecnego właściciela. Czy to rozsądne podejście? Zakładając, że przestrzeń nie stanowi problemu, czy rozsądne byłoby utworzenie wielu kopii wykresu (jednej dla każdego użytkownika) zamiast jednego wykresu?

Wyskakuje
źródło
To w jakiś sposób wydaje się istotne. youtube.com/watch?v=xdiL-ADRTxQ
RubberDuck
Naprawdę nie rozumiem, jak to tutaj pomoże.
Wyskakuje
Pomyślałem o tym przez chwilę. W większości algorytmów graficznych masz przede wszystkim dwie rzeczy, które musisz zrobić: wyliczyć sąsiadów lub znaleźć wagę krawędzi. Wszystkie wymienione pytania dotyczą tylko jednego użytkownika. W przypadku pojedynczego użytkownika, na wyliczenie sąsiadów lub znalezienie ciężaru krawędzi można odpowiedzieć albo w stałym czasie (jeśli liczba użytkowników jest ograniczona), albo w log N, po prostu odzwierciedlając albo listę sąsiadów, albo macierz z „własnością”. W tym celu uważam, że albo można go łatwo rozszerzyć i należy go wybrać w oparciu o tradycyjne mocne strony, zamiast rozpraszać użytkownika.
J Trana,

Odpowiedzi:

6

Zakładając, że przestrzeń nie stanowi problemu, czy rozsądne byłoby utworzenie wielu kopii wykresu (jednej dla każdego użytkownika) zamiast jednego wykresu?

Wydaje mi się, że powinieneś użyć tego, co moglibyśmy nazwać „wykresami warstwowymi”, tj. Dodać kombinator wykresów, powiedzmy @, aby:

  • Jeśli A i B są wykresami, to A @ B jest również grafem (tzn. Może być zasilany algorytmami biblioteki grafów).
  • Zbiór wierzchołków w A @ B jest sumą wierzchołków w A i B.
  • Zbiór krawędzi w A @ B to połączenie krawędzi w A i B.
  • Struktura A @ B nie posiada żadnego wierzchołka ani krawędzi, ale raczej wykorzystuje A i B jako kontenery danych.

Za pomocą takich warstwowych wykresów możesz zdefiniować K jako wspólną dostępną informację oraz R, G, B każdą prywatną informację, tak aby każdy gracz faktycznie widział R @ K, G @ K, B @ K.

Aby faktycznie to zaimplementować, możesz poszukać algorytmów implementujących bibliotekę grafów ogólnie, tj. Aby algorytm najdłuższej ścieżki itp. Był parametryzowany przez rzeczywistą reprezentację twojego wykresu. Więc jeśli twoja biblioteka mówi

ConcreteGraphAlgorithms = GenericAlgorithms(ConcreteGraphImplementation)

możesz go łatwo zastąpić

LayeredGraphAlgorithms = GenericAlgorithms(LayeredGraphs(ConcreteGraphImplementation))

gdzie dostarczasz LayeredGraphsi pożyczasz resztę z biblioteki.

Michael Le Barbier Grünewald
źródło
Ups, zignoruj ​​mój poprzedni komentarz, trochę źle odczytałem twoją odpowiedź. Zasadniczo to robię, chociaż nie skorzystałem z istniejących bibliotek grafów, ponieważ głupio nie pomyślałem, aby zobaczyć, czy istnieje.
Wyskakuje
1

To, czego potrzebujesz, nazywa się „grafem przypisanym”. Na przypisanym wykresie informacje (atrybuty) są dołączone do łuków. Ważony wykres jest jednym z najprostszych przypisywanych wykresów.

Aby przedstawić przypisany wykres, możesz użyć listy sąsiedztwa, dodając dodatkowe kolumny lub macierze sąsiedztwa, dodając więcej informacji w każdej komórce. Większość algorytmów dla wykresów bez atrybutów będzie działać, jeśli filtrujesz łuki na podstawie atrybutów. Opracowano wiele algorytmów dla przypisanych grafów, więc nie będę ich tutaj opisywał.

walrii
źródło
1
z pewnością macierz przylegania zwykle nie może reprezentować więcej niż 1 krawędzi między każdą parą węzłów
jk.
1
@ jk, zwykle masz rację. Ale informacje dołączone do macierzy przyległości mogą mieć liczbę łuków i oddzielne atrybuty dla każdego łuku. Ale w większości przypadków używałbym listy sąsiedztwa, ponieważ byłoby to prostsze.
walrii
1
jeśli dołączasz informacje do każdej krawędzi do komórki, to i tak faktycznie masz listę sąsiadów, tracisz korzyść, jaką daje ci matryca dla gęstych wykresów
jk.