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

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.

^{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?

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.

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