Wrocław,

Struktury danych i złożoność obliczeniowa.

Projekt 2

Temat: Badanie efektywności algorytmów grafowych w zależności od rozmiaru instancji oraz sposobu reprezentacji grafu w pamięci komputera.

1. Cele.

Implementacja 4 algorytmów, Prima i Kruskala wyznaczające minimalne drzewo rozpinające oraz Dijkstry i Forda-Bellmana wyznaczające najkrótszą ścieżkę w grafie. Każdy algorytm implementowany w dwóch wersjach, działający na macierzy i na liście. Następnie zbadanie czasu działania algorytmów dla różnych rozmiarów grafów oraz różnych gęstości.

2. Szczegóły implementacyjne.

2. 1. Generowanie grafu.

Graf jest generowany zgodnie z rozkładem zbliżonym do równomiernego. Najpierw losujemy drzewo rozpinające, a następnie pozostałe krawędzie. Jednocześnie sprawdzając czy nie wystąpiły cykle. Sposób zapobiegania cyklom opisany poniżej (detekcja cykli). Generowany graf jest zapisywany w formie listy a następnie przepisywany do macierzy. Dzięki temu można sprawdzać szybkość działania algorytmu dla dokładnie tego samego grafu.

2. 2. Implementacja listy.

Aby uprościć działanie lista zawiera nie tylko następniki czy poprzedniki, ale wszystkie wierzchołki, z którymi jest połączony dany wierzchołek. Do reprezentacji węzła w grafie zastosowaliśmy strukturę, gdyż może ona przechowywać więcej informacji niż np. liczba całkowita (int). Struktura wygląda następująco:

struct Pole

{

int sas;

int obc;

int nast;

int num;

};

Gdzie poszczególne zmienne oznaczają:

sas - numer w danej liście,

obc - obciążenie,

nast - zawiera informację czy dany wierzchołek jest następnikiem, czy poprzednikiem,

num - numer wierzchołka w grafie.

Odczytywanie danych z listy polega na odnalezieniu odpowiedniego wierzchołka, o którym chcemy uzyskać informację za pomocą indeksu, a następnie przesuwając się przy użyciu iteratora po liście mamy dostęp do poszczególnych jej elementów.

[0] -> lista0

[1] -> lista1

.

.

[N] -> listaN

0 - N to numer wierzchołka, a lista0 do listaN to następniki oraz poprzedniki danego wierzchołka. Mówiąc językiem programistów jest to tablica wskaźników na listy zawierające struktury typu Pole.

2. 3. Implementacja macierzy.

Macierz jest zaimplementowana jako tablica wskaźników na tablice typu int, gdzie w wierszach znajdują się następniki, a w kolumnach poprzedniki.

2. 4. Metody detekcji cykli.

Tworzymy tabelke w którą wpisujemy na początku numery wszystkich wierzchołków każdy wierzchołek traktujemy jako oddzielny graf. Gdy wylosujemy pierwszy graf zmieniamy numery jego wierzcholkow na numer ostatniego grafu ze wszystkich losowanych a numer ostatniego na numer pierwszego z wylosowanych  po czym zmniejszamy zmienna s oznaczajaca iczbe grafow (ta operacja sluzy mozliwosci wylosowania dowolnego grafu z grafow poza wylosowanym jako pierwszy) nastepnie losujemy drugi graf i zmieniamy jego numer na numer pierwzego z wylosowanych numer  grafu o numerze rownym (na ten moment) s+1 rowniz zmieniamy na numer grafu pierwszego a numer grafu o numerzer grafu pierwszego z wylosowanych zmieniamy na numer drugiego z wylosowanych. Jest to potrzebne aby zapewnic prawidlowosc kolejnych losowan (w tabeli z numerami grafow nie moze byc dziur). Jezeli drugi z wylosowanych grafow ma \w chwili losowania numer grafu wylosowanego jako pierwszy to nie trzeba wykonywac ponownych zamian numerow. Wystarczy zamienic numer grafu o numerze s + 1 na numer pierwszego wylosowanego grafu (lub tez jesli ktos woli drugiego gdyz sa to te same numery). 

3. Informacje dotyczące języka oraz sprzętu na którym wykonywany jest eksperyment.

Program został napisany w języku C++ oraz skompilowany w kompilatorze DevC++. Doświadczenie wykonaliśmy na komputerze z procesorem Pentium Dual-Core T4300 2x2.10 GHz. Komputer posiada 3GHz pamięci RAM.

4. Algorytmy znajdujące minimalne drzewo rozpinające.

4. 1. Pod względem rozmiaru grafu.

Rysunek 1

Rysunek 2

Rysunek 3

Rysunek 4

Z powyższych wykresów wynika, że najmniej wydajnym algorytmem w zależności od ilości wierzchołków jest algorytm Kruskala działający na macierzach, a najwydajniejszym algorytm Prima działający również na macierzach. Zatem oba algorytmy lepiej spisują się na macierzach niż na listach. Zauważmy jednak, że w przypadku przeprowadzenia eksperymentu na grafach o tej samej gęstości, jednak różnych rozmiarach najwydajniejszym okazuje się algorytm Kruskala dla list, a najmniej wydajny jest alg. Prima macierzy. W tym przypadku oba algorytmy lepiej spisują się na listach. Gdy zmienia się tylko rozmiar grafu a nie jego gęstość należy zastosować algorytm Kruskala, a dane przechowywać w liście, w przeciwnym razie lepszym rozwiązaniem jest macierz i alg. Prima.

4. 2. Pod względem gęstości grafu.

Rysunek 5

Rysunek 6

Rysunek 7

Rysunek 8

Rysunek 9

W przypadku badania pod względem gęstości grafu można zaobserwować dwa wyniki. Na Rysunk 5 najwolniejszym jest algorytm Kruskala dla list, jednak na pozostałych wolniej działa na macierzach. Zatem w przypadku grafów o małej ilości wierzchołków lepiej przechowywać dane w macierzy, a dla większych przejść na listy. Jeszcze lepszym rozwiązaniem jest algorytm Prima, gdyż nie trzeba się troszczyć o rozmiar grafu, ponieważ działa on identycznie dla wszystkich rozmiarów, jest znacznie szybszy od Kruskala, a najszybszy, gdy dane są umieszczone w macierzy. Czas jego działania nie zmienia się wraz ze wzrostem gęstości, zatem można powiedzieć, że nie jest od niej zależny.

4. 3. Tabele z wynikami (podstawa do sporządzenia wykresów).

n	k	gęstość	K-L[ms]	K-M[ms]	P-L[ms]	P-M[ms]
100	200	2	4	6	4	7
100	200	2	4	6	5	7
100	200	2	3	5	7	7
100	200	2	5	5	4	7
100	200	2	4	6	9	7
średnia			4	5,6	5,8	7
100	1180	11,8	46	34	12	8
100	1180	11,8	45	33	10	8
100	1180	11,8	94	33	9	8
100	1180	11,8	56	31	9	8
100	1180	11,8	40	32	10	8
średnia			56,2	32,6	10	8
100	2160	21,6	69	69	14	8
100	2160	21,6	69	72	14	9
100	2160	21,6	160	58	13	8
100	2160	21,6	69	57	13	8
100	2160	21,6	69	62	13	9
średnia			87,2	63,6	13,4	8,4
100	3140	31,4	108	90	18	9
100	3140	31,4	99	87	17	8
100	3140	31,4	100	84	17	9
100	3140	31,4	99	84	31	9
100	3140	31,4	98	83	17	8
średnia			100,8	85,6	20	8,6
150	300	2	10	18	16	23
150	300	2	11	18	16	23
150	300	2	10	19	18	23
150	300	2	9	18	15	32
150	300	2	10	18	16	24
średnia			10	18,2	16,2	25
150	2520	16,8	94	173	30	24
150	2520	16,8	101	148	29	23
150	2520	16,8	97	149	27	24
150	2520	16,8	95	147	28	25
150	2520	16,8	94	147	29	24
średnia			96,2	152,8	28,6	24
150	4740	31,6	277	275	41	25
150	4740	31,6	276	275	42	25
150	4740	31,6	276	274	42	25
150	4740	31,6	289	291	53	27
150	4740	31,6	291	322	53	28
średnia			281,8	287,4	46,2	26
150	6960	46,4	400	465	80	27
150	6960	46,4	401	456	72	26
150	6960	46,4	393	417	56	24
150	6960	46,4	330	400	58	23
150	6960	46,4	332	401	65	24
średnia			371,2	427,8	66,2	24,8
200	400	2	17	41	33	53
200	400	2	16	43	34	54
200	400	2	17	45	35	59
200	400	2	17	42	33	53
200	400	2	17	41	32	54
średnia			16,8	42,4	33,4	54,6
200	4360	21,8	220	464	68	54
200	4360	21,8	219	451	68	54
200	4360	21,8	224	450	64	54
200	4360	21,8	226	452	64	54
200	4360	21,8	219	443	64	53
średnia			221,6	452	65,6	53,8
200	8320	41,6	528	848	105	55
200	8320	41,6	533	840	103	55
200	8320	41,6	533	842	104	55
200	8320	41,6	531	841	103	55
200	8320	41,6	534	839	106	55
średnia			531,8	842	104,2	55
200	12280	61,4	869	1231	140	53
200	12280	61,4	876	1232	141	55
200	12280	61,4	882	1245	142	53
200	12280	61,4	872	1238	141	53
200	12280	61,4	883	1234	142	53
średnia			876,4	1236	141,2	53,4
250	500	2	26	79	61	102
250	500	2	26	80	61	101
250	500	2	26	80	61	102
250	500	2	26	81	62	104
250	500	2	27	82	62	102
średnia			26,2	80,4	61,4	102,2
250	6700	26,8	609	1047	124	106
250	6700	26,8	610	1047	124	105
250	6700	26,8	611	1057	124	105
250	6700	26,8	610	1051	124	105
250	6700	26,8	611	1045	124	105
średnia			610,2	1049,4	124	105,2
250	12900	51,6	1346	2033	283	116
250	12900	51,6	1396	2015	221	106
250	12900	51,6	1359	2029	221	106
250	12900	51,6	1411	2018	222	106
250	12900	51,6	1379	2024	219	105
średnia			1378,2	2023,8	233,2	107,8
250	19100	76,4	1426	2979	379	98
250	19100	76,4	1440	2990	379	99
250	19100	76,4	1440	2990	372	98
250	19100	76,4	1444	2992	370	99
250	19100	76,4	1448	2996	374	99
średnia			1439,6	2989,4	374,8	98,6
300	600	2	37	137	102	174
300	600	2	36	139	102	174
300	600	2	36	139	101	175
300	600	2	36	141	102	174
300	600	2	36	138	101	174
średnia			36,2	138,8	101,6	174,2
300	9540	31,8	874	2155	224	178
300	9540	31,8	867	2156	223	179
300	9540	31,8	869	2161	226	179
300	9540	31,8	881	2150	223	178
300	9540	31,8	873	2152	226	180
średnia			872,8	2154,8	224,4	178,8
300	18480	61,6	2750	4293	461	184
300	18480	61,6	2859	4355	497	183
300	18480	61,6	2771	4218	460	177
300	18480	61,6	2753	4203	441	177
300	18480	61,6	2775	4201	443	177
średnia			2781,6	4254	460,4	179,6
300	27420	91,4	3219	6195	876	174
300	27420	91,4	3238	6247	844	174
300	27420	91,4	3225	6219	847	174
300	27420	91,4	3248	6349	837	174
300	27420	91,4	3321	6227	858	177
średnia			3250,2	6247,4	852,4	174,6

Tabela 1 Wyniki pomiarów oraz średnie.

n	k	gęstość	K-L[ms]	K-M[ms]	P-L[ms]	P-M[ms]
100	200	2	4	5,6	5,8	7
100	1180	11,8	56,2	32,6	10	8
100	2160	21,6	87,2	63,6	13,4	8,4
100	3140	31,4	100,8	85,6	20	8,6
150	300	2	10	18,2	16,2	25
150	2520	16,8	96,2	152,8	28,6	24
150	4740	31,6	281,8	287,4	46,2	26
150	6960	46,4	371,2	427,8	66,2	24,8
200	400	2	16,8	42,4	33,4	54,6
200	4360	21,8	221,6	452	65,6	53,8
200	8320	41,6	531,8	842	104,2	55
200	12280	61,4	876,4	1236	141,2	53,4
250	500	2	26,2	80,4	61,4	102,2
250	6700	26,8	610,2	1049,4	124	105,2
250	12900	51,6	1378,2	2023,8	233,2	107,8
250	19100	76,4	1439,6	2989,4	374,8	98,6
300	600	2	36,2	138,8	101,6	174,2
300	9540	31,8	872,8	2154,8	224,4	178,8
300	18480	61,6	2781,6	4254	460,4	179,6
300	27420	91,4	3250,2	6247,4	852,4	174,6

Tabela 2 Średnie zebrane w osobnej tabeli.

4. 4. Wnioski ogólne.

Algorytm Prima jest zależny od rozmiaru grafu, ale niezależny od jego gęstości. Dlatego lepiej stosować go w przypadku zmiennej gęstości grafu przy stałym rozmiarze, a dane przechowywać w macierzy. Gdyby zaszła konieczność użycia tego algorytmu przy zmiennym rozmiarze, informacje należy przerzucić do listy.

Odwrotnie jest z algorytmem Kruskala. Działa on wydajniej, gdy zmienia się, a gęstość pozostaje stała. Dlatego najlepiej stosować go dla stałych gęstości z danymi zapisanymi w liście. Gdy zajdzie konieczność wykorzystania go dla zmiennej gęstości, przed wyborem sposobu reprezentacji grafu należy zastanowić się jaki będzie jego rozmiar, ponieważ macierz jest szybsza dla małych grafów, a lista dla dużych.

5. Algorytmy znajdujące nakruszą ścieżkę w grafie.

5. 1. Pod względem liczby wierzchołków.

Rysunek 10

Rysunek 11

Rysunek 12

Rysunek 13

Z powyższych wykresów wynika, że wydajniejszy jest algorytm Dijkstry, a najwydajniejszy, gdy działa na listach. Z kolei algorytm Forda-Bellmana jest o wiele wolniejszy od poprzedniego, ale działa wydajniej, gdy ma do dyspozycji reprezentację macierzową. Wzrost czasu działania algorytmu Forda-Bellmana jest bardzo duży wraz ze wzrostem liczby wierzchołków. Niestety pierwszy wykres (Rysunek 10) daje nam dość dziwne wyniki. Powodem tego może być zastosowanie złych (zbyt małych) rozmiarów, a nagły skok czasu dla Forda-Bellmena, chwilowym obciążeniem procesora innym procesem. Zatem aby znaleźć najkrótszą ścieżkę w grafach o różnych gęstościach i różnej liczbie wierzchołków najlepiej zastosować algorytm Dijkstry, a dane przechowywać w liście. Należy jednak pamiętać, że sprawdza on się tylko w przypadku nieujemnych obciążeń, więc gdy wystąpi ujemne obciążenie należy zastosować algorytm Forda-Bellmena, a dane przepisać do macierzy, gdyż wtedy działa szybciej.

5. 2. Pod względem gęstości.

Rysunek 14

Rysunek 15

Rysunek 16

Rysunek 17

Rysunek 18

Tak samo jak w przypadku zmiennego rozmiaru algorytm Dijkstry sprawdza się lepiej. Algorytm Forda-Bellmana zachowuje się podobnie. Zmienia się jedynie tempo wzrostu czasów działania z wykładniczego na liniowe.

5. 3. Tabele z wynikami (podstawa do sporządzenia wykresów).

n	k	D-L	D-M	FB-L	FB-M
1000	2000	1	0	8	14
1000	2000	0	0	8	13
1000	2000	0	1	9	14
1000	2000	0	0	8	14
1000	2000	0	0	9	13
średnia		0,2	0,2	8,4	13,6
1000	101800	36	87	204	170
1000	101800	37	87	203	175
1000	101800	36	87	202	175
1000	101800	35	88	205	173
1000	101800	35	87	203	172
średnia		36	87,2	203,4	173
1000	201600	42	181	404	336
1000	201600	41	183	408	340
1000	201600	43	183	406	339
1000	201600	41	182	406	339
1000	201600	42	181	401	339
średnia		42	182	405	338,6
1000	301400	49	180	593	505
1000	301400	50	184	586	502
1000	301400	49	180	593	505
1000	301400	50	179	586	503
1000	301400	49	178	587	502
średnia		49	180	589	503,4
1500	3000	0	0	19	0
1500	3000	0	0	18	0
1500	3000	0	0	19	0
1500	3000	0	0	18	0
1500	3000	0	0	19	0
średnia		0	0	18,6	0
1500	227700	82	317	689	573
1500	227700	82	314	687	573
1500	227700	82	314	686	580
1500	227700	83	320	702	600
1500	227700	81	320	693	588
średnia		82	317	691,4	582,8
1500	452400	96	425	1429	1137
1500	452400	90	403	1365	1170
1500	452400	92	414	1364	1181
1500	452400	92	414	1354	1178
1500	452400	93	422	1402	1212
średnia		93	416	1383	1176
1500	677100	114	564	2136	1801
1500	677100	110	563	2136	1778
1500	677100	110	580	2092	1733
1500	677100	104	548	2090	1743
1500	677100	108	563	2076	1699
średnia		109	564	2106	1751
2000	4000	0	0	36	57
2000	4000	0	0	38	58
2000	4000	0	0	35	56
2000	4000	0	0	35	59
2000	4000	0	0	35	56
średnia		0	0	35,8	57,2
2000	403600	132	699	1658	1382
2000	403600	128	683	1653	1387
2000	403600	135	705	1656	1385
2000	403600	134	705	1662	1402
2000	403600	132	700	1665	1414
średnia		132	698	1659	1394
2000	803200	175	1121	3322	2744
2000	803200	165	1071	3317	2804
2000	803200	160	1073	3355	2859
2000	803200	176	1081	3339	2912
2000	803200	169	1109	3341	2886
średnia		169	1091	3335	2841
2000	1202800	193	1361	4823	4046
2000	1202800	192	1350	4776	4030
2000	1202800	193	1334	4863	4062
2000	1202800	190	1398	4847	3993
2000	1202800	194	1373	4920	4014
średnia		192	1363	4846	4029
2500	5000	0	1	53	84
2500	5000	0	2	54	88
2500	5000	1	1	51	85
2500	5000	0	2	53	85
2500	5000	0	2	52	85
średnia		0,2	1,6	52,6	85,4
2500	629500	206	1412	3163	2673
2500	629500	199	1398	3165	2746
2500	629500	192	1379	3161	2756
2500	629500	200	1371	3145	2732
2500	629500	200	1403	3110	2755
średnia		199	1393	3149	2732
2500	1254000	241	2214	6453	5340
2500	1254000	246	2242	6279	5384
2500	1254000	240	2209	6282	5342
2500	1254000	246	2237	6235	5322
2500	1254000	249	2220	6256	5353
średnia		244	2224	6301	5348
2500	1878500	276	2720	9273	8203
2500	1878500	299	2695	9225	8124
2500	1878500	283	2761	9264	8145
2500	1878500	285	2725	9235	8230
2500	1878500	287	2747	9242	8092
średnia		286	2730	9248	8159
3000	6000	0	0	74	0
3000	6000	0	0	77	0
3000	6000	0	0	74	0
3000	6000	0	0	75	0
3000	6000	0	0	75	0
średnia		0	0	75	0
3000	905400	292	1969	5388	4639
3000	905400	291	1992	5414	4594
3000	905400	289	2013	5387	4695
3000	905400	288	1999	5377	4712
3000	905400	283	2039	5407	4698
średnia		289	2002	5395	4668
3000	1804800	345	2609	10732	9300
3000	1804800	370	2608	10744	9269
3000	1804800	350	2610	10786	9266
3000	1804800	343	2625	10833	9302
3000	1804800	359	2578	10958	9236
średnia		353	2606	10811	9275
3000	2704200	412	4333	16216	14367
3000	2704200	417	4338	16274	14338
3000	2704200	423	4355	16125	14294
3000	2704200	414	4271	16100	14353
3000	2704200	411	4301	16164	14342
średnia		415	4320	16176	14339

Tabela 3 Wyniki pomiarów oraz średnie.

n	k	gęstość	D-L[ms]	D-M[ms]	FB-L[ms]	FB-M[ms]
1000	2000	2	0,2	0,2	8,4	13,6
1000	101800	101,8	36	87,2	203,4	173
1000	201600	201,6	42	182	405	338,6
1000	301400	301,4	49	180	589	503,4
1500	3000	2	0	0	18,6	0
1500	227700	151,8	82	317	691,4	582,8
1500	452400	301,6	93	416	1383	1176
1500	677100	451,4	109,2	563,6	2106	1750,8
2000	4000	2	0	0	35,8	57,2
2000	403600	201,8	132,2	698,4	1658,8	1394
2000	803200	401,6	169	1091	3334,8	2841
2000	1202800	601,4	192,4	1363,2	4845,8	4029
2500	5000	2	0,2	1,6	52,6	85,4
2500	629500	251,8	199,4	1392,6	3148,8	2732,4
2500	1254000	501,6	244,4	2224,4	6301	5348,2
2500	1878500	751,4	286	2729,6	9247,8	8158,8
3000	6000	2	0	0	75	0
3000	905400	301,8	288,6	2002,4	5394,6	4667,6
3000	1804800	601,6	353,4	2606	10810,6	9274,6
3000	2704200	901,4	415,4	4319,6	16175,8	14338,8

Tabela 4 Średnie zebrane w jednej tabeli.

5. 4. Wnioski ogólne.

Algorytm Dijkstry jest zdecydowanie szybszy od algorytmu Forda-Bellmana, dlatego należy go stosować zawsze, gdy nie ma potrzeby pracy na ujemnych obciążeniach. Gdy stosujemy algorytm Dijkstry dane należy wrzucać do listy, a gdy zajdzie konieczność zastosowania Forda-Bellmana najlepiej przepisać je do macierzy.

- 1 -

---