Warszawa, styczeń 2005
Grafy i sieci Projekt
Generator Grafów Euklidesowych
Autorzy:
Łukasz Falaciński Tomasz Podlaski
Założenia wstępne :
1. Graf Euklidesowy G jest tworzony w następujący sposób: Dane: n –liczba wierzchołków, k–zasięg wierzchołka. Wierzchołki są umieszczane w sposób losowy (rozkład równomierny) na płaszczyźnie wewnątrz kwadratu o boku jednostkowym. Krawędzie grafu łączą wierzchołki, których odległość Euklidesowa jest nie większa niż k. 2. D - średnica grafu t.j. największa odległość pomiędzy dwoma dowolnymi wierzchołkami w grafie. L - średnia długość ścieżki w grafie, t.j. średnia odległość wierzchołków w grafie, uśredniona po wszystkich parach wierzchołków.
Treść zadania :
Dla grafu G wyznaczyć : o średnicę D i promień r o centra w funkcji parametrów n, k. Przedstawić wykresy zależności współczynników D, r od parametrów modelu n, k.
Rozwiązanie :
Opis programu :
Program został napisany i do poprawnego działania wymaga środowiska JAVA. Sama aplikacja została stworzona w formie appletu i umieszczona na stronie www. Oprócz appletu dostępna jest także aplikacja(bez graficznego interfejsu), która odpowiedzialna jest za dokonywanie serii obliczeń w celu wygodniejszego tworzenia wykresów. Aplikacja oblicza średnicę i promień grafu(grafów) oraz uśrednia wyniki jeżeli zadana liczba symulacji jest większa. Program ten będzie przyjmuje następujące parametry wejściowe: • ilość przeprowadzanych symulacji • początkową wartość parametru n (liczba wierzchołków) dla serii symulacji • końcową wartość parametru n dla serii symulacji • początkową wartość parametru r (zasięg wierzchołków) dla serii symulacji • końcową wartość parametru r dla serii symulacji • nazwa pliku wyjściowego • wielkość, o jaką powinny się zmieniać parametry r/n w każdym kroku symulacji W samym applecie jako dane wejściowe wprowadzać można wartości parametrów k/n, po czym generowany i rysowany jest graf.
Opis algorytmów:
• generacja grafu Generacja grafu zapewnia losową generację(o jednostajnym rozkładzie) współrzędnych wierzchołków grafu. Założenia te spełniają biblioteczne funkcje języka JAVA. Generację grafu można przedstawić następująco (w postaci pseudokodu): aktualna liczba wierzchołków = 0; WHILE (liczba wierzchołków > aktualna liczba wierzchołków) DO { Współrzędna X = RANDOM(0.0,1.0); Współrzędna Y = RANDOM(0.0,1.0); aktualna liczba wierzchołków++; } FOR (i=0; i<liczba wierzchołków; i++) { FOR (k=0; k<liczba wierzchołków; k++) { IF (odległość(wierzchołek_k;wierzchołek_i)) < zasięg THEN połącz wierzchołki(i;k) } } • wyszukiwanie najkrótszej ścieżki w grafie pomiędzy dwoma wierzchołkami Ten algorytm jest głównym algorytmem programu, biorąc pod uwagę złożoność obliczeniową. Jego celem jest znalezienie najkrótszej ścieżki w grafie pomiędzy każdą parą wierzchołków. Do znalezienia tych odległości posłużono się algorytmem Dijkstry. Wyniki działania tego algorytmu(tzn. odległość pomiędzy zadanymi wierzchołkami) jest zapisywana do tablicy (rozmiar n x n, gdzie n to liczba wierzchołków), a jego działanie powtarza się dla kolejnej pary wierzchołków. Po zakończeniu tej procedury otrzymujemy tablicę wypełnioną najmniejszymi odległościami pomiędzy wszystkimi wierzchołkami. Tablica ta jest symetryczna względem swojej przekątnej, ponieważ generowane grafy są grafami prostymi. W algorytmie Dijkstry pamiętany jest zbiór Q wierzchołków, dla których nie obliczono jeszcze najkrótszych ścieżek, oraz wektor D[i] odległości od wierzchołka s do i. Początkowo zbiór Q zawiera wszystkie wierzchołki a wektor D jest pierwszym wierszem macierzy wag krawędzi A. Algorytm przebiega następująco: 1. Dopóki zbiór Q nie jest pusty wykonuj: 2. Pobierz ze zbioru Q wierzchołek v o najmniejszej wartości D[v] i usuń go ze zbioru. 3. Dla każdego następnika i wierzchołka v sprawdź, czy D[i]>D[v]+A[v,i], tzn. czy aktualne oszacowanie odległości do wierzchołka i jest większe od oszacowania odległości do wierzchołka v plus waga krawędzi (v,i) 4. Jeżeli tak jest, to zaktualizuj oszacowanie D[i] przypisując mu prawą stronę nierówności (czyli mniejszą wartość). • znajdowanie średnicy grafu Po obliczeniu wszystkich najmniejszych odległości pomiędzy wierzchołkami, z tabeli je przechowującej wybieramy największą wartość. Wartość ta będzie równa długości średnicy grafu. • znajdowanie promienia i centrów grafu Z tej samej tabeli przechowującej odległości pomiędzy wierzchołkami szukamy największej odległości dla każdego z wierzchołków. Wartość tą otrzymujemy znajdując maksymalną wielkość w każdym wierszu lub kolumnie tabeli. W ten sposób dostajemy listę najdłuższych możliwych do przejścia ścieżek z danego wierzchołka. Z odległości tych wybieramy najmniejszą. Wartość ta będzie równa długości promienia grafu(dla naszego przykładowego grafu promień ma długość 2). Dodatkowo należy zapamiętać wierzchołek(-ki), dla którego wartość tą otrzymaliśmy. Wierzchołek(-ki) ten należy zaznaczyć jako centrum grafu.
Struktury danych :
Do najważniejszych struktur danych użytych w projekcie należą: FTVertex Dynamiczna struktura danych przechowująca parę liczb reprezentujących współrzędne wierzchołków oraz wskaźniki do krawędzi wychodzących z danego wierzchołka. FTEdge Dynamiczna struktura danych przechowująca wskaźniki do dwóch wierzchołków, które łączy oraz długość euklidesową krawędzi. FTGraphTable Graf jest reprezentowany między innymi przez tabelę sąsiedztwa. Dzięki temu bardzo szybko można stwierdzić czy dane dwa wierzchołki są połączone. FTGraph Główna struktura danych reprezentująca graf. Zawiera wskaźniki na strukturę przechowującą wierzchołki, krawędzie oraz tablicę sąsiedztwa(FTGrapgTable) grafu. .
Ograniczenia programu:
W czasie testowania programu stwierdzono istnienie pewnych ograniczeń. Przy każdej generacji grafu dla każdej pary wierzchołków obliczana jest najmniejsza odległość między nimi. Gdy liczba krawędzi gafu będzie ogromna, obliczenia mogą trwać bardzo długo i zajmować dużo czasu procesora. W związku z tym programowe zawiera ograniczenia na liczbę wierzchołków i ich zasięg, które wynoszą odpowiednio 100 i 1,4. Należy pamiętać że Symulacje dla dużej ilości wierzchołków(>50), dużego zasięgu(>0.4), a co za tym idzie dużej ilości krawędzi mogą trwać długo nawet na komputerze o szybkim procesorze i dużej ilości pamięci. Zapotrzebowanie na pamięć operacyjną jest małe i jako ograniczenie można je pominąć.
Wyniki:
Na potrzeby testowania programu oraz wyznaczenia szukanych zależności, stworzono specjalnie przygotowaną funkcję. Procedura ta zapisywała do pliku tekstowego długość promienia grafu oraz jego średnicę dla różnych wartości zasięgu wierzchołka oraz ich liczby. Na wejściu podawano początkową i końcową wartość parametru oraz skok, z jakim miał on się zmieniać. Na wyjściu otrzymywano plik tekstowy, który po zaimportowaniu do arkusza kalkulacyjnego służył do generacji wykresów. Należy zaznaczyć, że w jednym przebiegu funkcji możliwe było zmienianie tylko jednego parametru(zasięgu albo liczby wierzchołków, nigdy dwóch na raz).
Wykresy :
Wykres 1. Zależność długości promienia grafu od wielkości zasięgu wierzchołków, dla różnej liczby wierzchołków.
Wykres 2. Zależność długości średnicy grafu od wielkości zasięgu wierzchołków, dla różnej liczby wierzchołków.
Wykres 3. Zależność długości średnicy i promienia grafu od wielkości zasięgu wierzchołków, dla przykładowego grafu o 25 wierzchołkach.
test przeprowadzono dla różnych wartości liczby wierzchołków(5,15,25,35,45), przy zmieniającej się wartości zasięgu (od 0 do 1.4 ze skokiem 0.02). Z przebiegu symulacji i otrzymanych w ten sposób wykresów widać, jak dla małych wartości zasięgu(<0.2) nawet przy dużej liczbie wierzchołków nie udało się otrzymać grafu spójnego. Należy pamiętać, że zero oznacza tutaj raczej brak średnicy/promienia, a nie zerową ich długość. Dla zasięgu większego od 0.2 ale mniejszego od 0.6 widać, że grafy spójne zaczęły pojawiać się tym „szybciej” im liczba wierzchołków była większa(np. dla 15 wierzchołków przy wartości 0.4, a dla 45 wierzchołków przy wartości zasięgu równej 0.26). Wynika to z oczywistego faktu, że odległość pomiędzy najbliższymi wierzchołkami w grafie euklidesowym jest tym mniejsza, im liczba tych wierzchołków większa. Po przekroczeniu wartości zakresu oscylującej wokół 0.6 za każdym razem generowany graf był grafem spójnym. Wielkość promienia i średnicy początkowo była duża(tym większa im liczba wierzchołków większa), by wraz ze wzrostem zasięgu stopniowo maleć. Warto zauważyć, że spadek wielkości tych parametrów następował w sposób jednostajny a długość promienia była ok. dwóch razy mniejsza od długości średnicy. Działo się tak do momentu, gdy wartość średnicy osiągnęła 2, a promienia 1. Sytuacja ta oznacza, że graf nie jest jeszcze pełny, ale liczba jego krawędzi jest na tyle duża, że dowolne dwa wierzchołki dzieli ścieżka o długości co najwyżej 2. Po przekroczeniu wartości zasięgu równej ok. 1,2-1,3 zaczęto obserwować wystąpienia grafu zupełnego. Na wykresie objawia się to faktem, że zarówno średnica jak i promień przyjmują wartość równą 1(każdy wierzchołek jest centrum).
Wykres 4. Zależność długości promienia grafu od liczby wierzchołków, dla różnych wielkości zasięgu wierzchołków.
Wykres 5. Zależność długości średnicy grafu od liczby jego wierzchołków, dla różnych wielkości zasięgu wierzchołków.
Wykres 6. Zależność długości średnicy i promienia grafu od liczby jego wierzchołków, dla przykładowego grafu o zasięgu wierzchołków równym 0,35.
W tym przypadku symulację przeprowadzano dla zadanej wartości zasięgu (0.35, 0.45, 0.55, 0.65, 0.75), przy zmieniającej się liczbie wierzchołków(od 2 do 50 ze skokiem 1). Z powyższych wykresów widać kilka bardzo wyraźnych zależności. Po pierwsze im zasięg mniejszy tym obserwowana wielkość średnicy i promienia była większa. Po drugie tym szybciej generowane grafy były spójne, im większy był zasięg. Należy zauważyć, że przy małej liczbie wierzchołków nie udawało się wygenerować grafów spójnych. Jeżeli jednak liczba wierzchołków przekroczyła graniczną wartość, to zarówna promień jak i średnica zaczęły przyjmować wartości w bardzo małym stopniu zależne od tego parametru. Dalsze zwiększanie liczby wierzchołków prawie w ogóle nie wpływało na badane parametry. Z tych wykresów również wyraźnie widać, że długość promienia jest prawie dwa razy mniejsza od długości średnicy (stanowi 55%-60% długości średnicy).
Podsumowanie:
Program mimo swej prostoty i ograniczeń pozwala na dość wygodne sprawdzanie właściwości grafów euklidesowych. Zaimplementowana funkcja testująca ułatwia generowanie serii symulacji i okazała się bardzo przydatna w projekcie. Sama analiza zależności długości średnicy i promienia od ilości i zasięgu wierzchołków, okazała się ciekawa, a zbudowana aplikacja analizę tą bardzo ułatwiła.
Źródła :
Dokumentacja projektu: sprawozdanie nr 1 (.doc 28 kB) sprawozdanie nr 2 (.doc 56 kB) sprawozdanie nr 3- Końcowe (.doc 168 kB)	wersja offline tej strony(.zip 74kB) Źródło programu (.zip 14 kB) wyniki symulacji (.xls 434 kB)