![„kruskalizace“ hran a vrcholů
C#
pokud již existují oba dva a mají stejné domény
pokud již existují oba dva a mají různé domény Dochází ke spojování dvou domén do sebe
Hrana je duplicitní nebo by vytvořila cyklus, proto se nepřidá
int domainSmaller = (domains[1.].Count < domains[2.].Count) ? 1. : 2.; //určí ve které doméně je méně vrcholů
int domainGreater = (domains[1.].Count >= domains[2.].Count) ? 1. : 2.; //určí ve které doméně je více vrcholů
foreach (Vertex bod in domains[domainSmaller])
{ bod.Domain = domainGreater; } //rename domain in transfered vertexes
domains[domainGreater].AddRange(domains[domainSmaller]); //move
domains[domainSmaller].Clear(); //remove unused
pouzitehrany.Add(hrana); //finally add edge](https://image.slidesharecdn.com/kos0148kruskaluvalg-160104225334/85/Kruskaluv-algoritmus-implementace-16-320.jpg)
![Pokračování implementace algoritmu
…
//pro graf potřebuji mít seznamy hran a vrcholů v samostatných listech, vytvořím si předobraz (zatím je mám všechny
Dictionary<int, List<Vertex>> domenovevrcholy = new Dictionary<int, List<Vertex>>();
Dictionary<int, List<Edge>> domenovehrany = new Dictionary<int, List<Edge>>();
//inicialializace seznamů podle příslušnosti k doménám
foreach (int i in domains.Keys)
{
if (domains[i].Count == 0)
{ continue; }
domenovevrcholy.Add(i, new List<Vertex>());
domenovehrany.Add(i, new List<Edge>());
}
//rozřazení vrcholů podle domén do slovníku, klíčem je ID domény
foreach (Vertex vrchol in pouzitevrcholy)
{
domenovevrcholy[vrchol.Domain].Add(vrchol);
}
…
C#](https://image.slidesharecdn.com/kos0148kruskaluvalg-160104225334/85/Kruskaluv-algoritmus-implementace-17-320.jpg)
![Dokončení implementace algoritmu
…
//rozřazení hran podle domén do slovníku, klíčem je ID domény prvního vrcholu
foreach (Edge hrana in pouzitehrany)
{
if (hrana.Vertex1.Domain != hrana.Vertex2.Domain) //pouze pokud by něco dříve selhalo
{ continue; }
domenovehrany[hrana.Vertex1.Domain].Add(hrana);
}
//podle toho, kolik skupin vrcholů je, tolik je nesouvislých grafů, ty je třeba vytvořit
foreach (int i in domenovevrcholy.Keys)
{
grafy.Add(new Graph(domenovevrcholy[i], domenovehrany[i]));
}
return grafy; //konec kruskalova algoritmu
}
C#](https://image.slidesharecdn.com/kos0148kruskaluvalg-160104225334/85/Kruskaluv-algoritmus-implementace-18-320.jpg)
Kruskalův algoritmus - implementace
- 1. Ivo Kostecký, kos0148 projekt předmětu Matematika pro zpracování znalostí na VŠB-TUO Implementace: Kruskalův algoritmus
- 2. V ohodnocených grafech určete všechny nejlevnější kostry grafu pomocí Kruskalova algoritmu. Zadání
- 3. Neumím si přečíst zadání… V ohodnocených grafech určete všechny nejlevnější kostry grafu pomocí Kruskalova algoritmu. …zpracoval jsem: V ohodnocených grafech jsem určil první nejlevnější kostru grafu pomocí Kruskalova algoritmu. Problém
- 4. Kostra grafu V teorii grafů je kostra souvislého grafu G takový podgraf souvislého grafu G na množině všech jeho vrcholů, který je stromem. Pojmy
- 5. Kdy má smysl hledat kostru? • Graf je souvislý (projekt umí najít i více koster ve více grafech, pokud je zdroj nespojitý) • Graf je neorientovaný (případnou orientaci zahazuje) • Graf je vážený (hrany mají kladné ohodnocení) Pojmy
- 6. Proč hledat minimální kostru v grafových úlohách? Motivace Návrh elektrické sítě Máme k dispozici seznam odběrných míst a chceme je propojit tak, abychom využili co nejmenší množství drátů.
- 7. Proč hledat minimální kostru v grafových úlohách? Motivace Smyčky v počítačových sítích Spanning Tree Protocol (v překladu protokol kostry grafu) je v informatice název pro síťový protokol, který v ethernetových sítích odstraňuje smyčky na druhé vrstvě ISO/OSI modelu.
- 10. Myšlenka implementace algoritmu 1.Seřadit hrany podle ceny od nejmenší po největší 2.Nastavit všem vrcholům stejnou doménu značící nezařazenost 3.Procházet všechny hrany a u jejich vrcholů sledovat, zda splňují podmínky a zpracovat je (viz dále) • pokud jsou oba vrcholy nové • pokud je první vrchol nový a druhý již existuje • pokud je druhý vrchol nový a první již existuje • pokud již existují oba dva a mají stejné domény • pokud již existují oba dva a mají různé domény Výsledkem je • seznam hran splňující podmínku acykličnosti a nejmenší metriky • seznam vrcholů s doménami podle grafových souvislostí C#
- 12. Implementace algoritmu public List<Graph> Kruskal() { List<Graph> grafy = new List<Graph>(); //seznam koster nalezených v grafech List<Vertex> pouzitevrcholy = new List<Vertex>(); //pouzite vrcholy jednotlivych grafu List<Edge> pouzitehrany = new List<Edge>(); //pouzite hrany jednotlivych grafu Dictionary<int, List<Vertex>> domains = new Dictionary<int, List<Vertex>>(); //seznam vrcholů roztřízený podle domén Seznamhran.Sort(new EdgeComparer()); //serazeni hran podle ceny foreach (Vertex v in Seznamvrcholu) //reset domén při opakovaném běhu { v.Domain = -1; } int domainCounter = 0; //čítač nesouvislých domén foreach (Edge hrana in Seznamhran) //pridavani hran do komponent { //viz podmínky dříve, viz implementace dále } … C#
- 13. Všimněte si využití existujících struktur: List<Edge> pouzitehrany = new List<Edge>(); Dictionary<int, List<Vertex>> domains = new Dictionary<int, List<Vertex>>(); Seznam má časovou složitost O(n) – lineární Slovník má časovou složitost O(1) - konstatní Výhodné pro rychlý běh programu! Datové struktury 2
- 14. „kruskalizace“ hran a vrcholů C# pokud ani jeden vrchol ještě nebyl zpracován *Pardon, momentálně trpím obdobím psaním komentářů ve dvou jazycích.
- 15. „kruskalizace“ hran a vrcholů C# pokud byl dosud zpracován pouze jeden vrchol z hrany
- 16. „kruskalizace“ hran a vrcholů C# pokud již existují oba dva a mají stejné domény pokud již existují oba dva a mají různé domény Dochází ke spojování dvou domén do sebe Hrana je duplicitní nebo by vytvořila cyklus, proto se nepřidá int domainSmaller = (domains[1.].Count < domains[2.].Count) ? 1. : 2.; //určí ve které doméně je méně vrcholů int domainGreater = (domains[1.].Count >= domains[2.].Count) ? 1. : 2.; //určí ve které doméně je více vrcholů foreach (Vertex bod in domains[domainSmaller]) { bod.Domain = domainGreater; } //rename domain in transfered vertexes domains[domainGreater].AddRange(domains[domainSmaller]); //move domains[domainSmaller].Clear(); //remove unused pouzitehrany.Add(hrana); //finally add edge
- 17. Pokračování implementace algoritmu … //pro graf potřebuji mít seznamy hran a vrcholů v samostatných listech, vytvořím si předobraz (zatím je mám všechny Dictionary<int, List<Vertex>> domenovevrcholy = new Dictionary<int, List<Vertex>>(); Dictionary<int, List<Edge>> domenovehrany = new Dictionary<int, List<Edge>>(); //inicialializace seznamů podle příslušnosti k doménám foreach (int i in domains.Keys) { if (domains[i].Count == 0) { continue; } domenovevrcholy.Add(i, new List<Vertex>()); domenovehrany.Add(i, new List<Edge>()); } //rozřazení vrcholů podle domén do slovníku, klíčem je ID domény foreach (Vertex vrchol in pouzitevrcholy) { domenovevrcholy[vrchol.Domain].Add(vrchol); } … C#
- 18. Dokončení implementace algoritmu … //rozřazení hran podle domén do slovníku, klíčem je ID domény prvního vrcholu foreach (Edge hrana in pouzitehrany) { if (hrana.Vertex1.Domain != hrana.Vertex2.Domain) //pouze pokud by něco dříve selhalo { continue; } domenovehrany[hrana.Vertex1.Domain].Add(hrana); } //podle toho, kolik skupin vrcholů je, tolik je nesouvislých grafů, ty je třeba vytvořit foreach (int i in domenovevrcholy.Keys) { grafy.Add(new Graph(domenovevrcholy[i], domenovehrany[i])); } return grafy; //konec kruskalova algoritmu } C#
- 19. Výsledné GUI
- 20. Vyhodnocení • Algoritmus již dle mého nelze jednoduše urychlit • Metoda má na délku běhu celé úlohy minimální význam (načítání vstupních dat je mnohem pomalejší)
- 21. • CSV ve formátu, který popisuje tabulka • Očekáván velký rozsah (zbytečně) • Nedefinovány platné vstupy Způsob vyhodnocení Zdroj dat • Korektnost výstupu (nedosažena) • délka běhu v závislosti na vstupních datech
- 22. Možnost opravy 1 Najde další nejlevnější kostry pomocí Kruskalova algoritmu Nový proces (fork) si zkopíruje obsah paměti, proto si graf dále „žije vlastním životem“
- 23. Možnost opravy 2 Zcela nezávislá možnost je implementace Jarníkova algoritmu
- 24. Děkuji za pozornost Text této prezentace na blog.kostecky.cz Zdrojový kód na www.kostecky.cz/archiv/mpzz-kruscal-source.zip
Editor's Notes
- #2: Projekt MPZZ číslo 17
- #3: Ilustrační obrázek „kostry grafu“ Zdroj: http://mj.ucw.cz/vyuka/ads/27-kostry.pdf
- #4: Nicméně jsem vyřešil podúlohu, která rovněž dává jako výsledek kostru. Oprava je naznačena v závěru prezentace. Myšlenkový proud při zpackání zadání: Přečíst si zadání Implementovat datové struktury Zpracovat vizualizační / testovací funkce Vytvořit náhodné generování Implementovat Kruskalův algoritmus Implementovat vstup dat ze souborů Doplnit implementaci na hledající v nesouvislých grafech Otestovat rychlost Zpracovat dokumentaci Odevzdat Z čehož je zřejmé, že jsem se po vyřešení množství podproblémů tak těšil na dokončení, že jsem se znovu nezamyslel nad zadáním i když teď je mi to naprosto evidentní.
- #5: Zdroj: https://jeremykun.files.wordpress.com/2014/08/example-spanning-tree.gif?w=1800
- #6: Zdroj: https://jeremykun.files.wordpress.com/2014/08/example-spanning-tree.gif?w=1800
- #7: Zdroj: http://cs.umw.edu/~finlayson/class/spring15/cpsc230/notes/images/mst.png (ten obrázek je nějaký divný, ale pro ilustraci postačuje)
- #9: Zdroj: https://networklessons.com/wp-content/uploads/2014/07/4-switches-spanning-tree-port-states.png
- #10: Pro potřeby dalšího textu je akademický termín komponenta nahrazen slovem doména předpokládá, že každý vrchol je ve zvláštní doméně vezme nejmenší hranu a tu přidá, pokud jsou domény vrcholů různé po přidání aktualizuje zbývající část komponenty pokud by hranou spojil stejné domény, vznikne nežádoucí cyklus až dojdou hrany, pak je algoritmus dokončen Uvedený algoritmus pracuje s unikátními vahami, mnou implementovaný použije první nejmenší a pak každou další stejné váhy.
- #11: Zdroj: http://mj.ucw.cz/vyuka/ads/27-kostry.pdf
- #12: Seřadit hrany podle ceny od nejmenší po největší Nastavím všem vrcholům stejnou doménu značící nezařazenost Procházím všechny hrany a u jejich vrcholů sleduji, zda splňují podmínky pokud jsou oba vrcholy nové: hrana.Vertex1.Domain == -1 && hrana.Vertex2.Domain == -1 pokud je první vrchol nový a druhý již existuje: hrana.Vertex1.Domain == -1 pokud je druhý vrchol nový a první již existuje: hrana.Vertex2.Domain == -1 pokud již existují oba dva a mají stejné domény pokud již existují oba dva a mají různé domény
- #13: Jaké údaje v sobě nesou objekty problému: Všimněte si, že vrchol v sobě nese údaj o doméně. Vrchol lze taktéž doplnit o jakékoliv údaje o souřadnicích, čímž by získal pravý význam, v této úloze to však není potřeba. Unikátnost hrany zajišťuje údaj odkud a kam vede. Podstatou algoritmu jsou hrany neorientované, pokud je nějaká orientována je při importu otestována na existenci v současné orientaci i existenci hrany opačné a pokud chybí, tak je vložena. Graf je abstraktní struktura, která v sobě nese příslušné seznamy. Pro použití v tomto programu je neužitečnější při „kruskalizaci“ nesouvislých grafů.
- #14: Proč mám slovník seznamu vrcholů tříděných podle domén, když mám seznam použitých vrcholů? Protože u nich používám seznam, který má složitost přístupu O(1) konstantní, zatímco seznam má složitost O(n) lineární. Proč tedy u vrcholů průběžně aktaulizuji doménu, když už ji nepotřebuju? Aby nebyl v datech nepořádek, po skončení Kruskalova algoritmu si mohu všechna data vypsat a nechci v nich mít nepořádek, ale ano, odstranění příslušného řádku je možné.
- #15: Toto se hodí znát! Slovník je vnitřně řešen jako hashovací tabulka, proto je tak extrémně efektivní.
- #16: založ novou doménu do té vlož oba dva vrcholy vrcholům nastav tuto doménu jako mateřskou zvyš čítač, kdyby se opět přidávala doména přidej vrcholy do použitých vrcholů přidej hranu do použitých hran
- #17: zatřiď nový vrchol do seznamu vrcholů se stejnou doménou jako má bod již existující nastav původnímu vrcholu doménu podle již existujícího vrcholu přidej vrcholy do použitých vrcholů přidej hranu do použitých hran
- #18: pokud by hrana vytvořila cyklus nesmí být přidána, proto se neobjeví v seznamu použitých hran, vrcholy už použité jsou. tady vlastně dochází k formování kostry Během tvorby kostry se dochází do stádia, kdy je třeba spojit k sobě dosud rozdělené domény. Jde o postup, kdy se musí vrcholy z menší domény aktualizovat na doménu větší Po přesunu v seznamu vrcholů třízeného podle domén je vhodné původní doménu vyčistit Na závěr se spojující hrana rovněž přidá do seznamu hran
- #19: Proč do doménových vrcholů nenakopíruji vrcholy ze slovníku domains? Čistě z pohodlnosti a orientace v kódu. Mělo by to být rychlejší.
- #20: V této fázi dochází jen k překopírování hrany do výsledného seznamu hran. V této fázi by nutně měly domény obou vrcholů být stejné, přesto je zde záchytná podmínka. Netestoval jsem ji, ale pravděpodobně by k její vyhodnocení nemělo nikdy dojít. V úplné závěru vytvářím ze seznamů doménových vrcholů a hran grafy, které předávám do dalšího seznamu výsledných grafů. Tím získává volací konstrukce požadované grafy koster.
- #21: Jde v podstatě o vývojovou verzi s příliš velkým množstvím ovládacích prvků. Civilní release by měl rozhodně být mnohem více zjednodušený. Implementace v C# a frameworku .NET 3.5
- #22: Nemůže být efektivnější, protože žádný cyklus již nelze odebrat. Šlo by si pohrát s implementací, ale zde nebylo třeba komplikovat pochopení kódu. Chtěl jsem upozornit na to, že importování dat a jejich korektní uložení do paměti zabere mnohem více času než výsledná „kruskalizace“ na své kostry a to v poměrně vysokých řádech.
- #23: Prozkoumejte kolik je tam cyklů a to nejsou všechny v parsovací metodě. A to do prezentace nezveřejňuji ošetření duplicity vrcholů, neboť je to „zábava na delší chvíle“.
- #24: Dle průběžných informací se vyvinulo očekávání, že finální hodnocení se bude provádět na obrovských datech a porovnávat se čas. Při odevzdání došlo jen na marginální data. Jsem rád, že jsem neimplementoval nějakou extrémní variantu jako kolegové. (C++ a vlastní hashmapa) Pokud je zadání vágní, pak nelze jednoznačně určit, co lze považovat za korektní vstup. Že „odkud“ a „kam“ jsou celočíselné identifikátory vrcholů si bylo třeba uhodnout z dat. Cena je decimal i když byla původně také celočíselná. Prostě to funguje… Má implementace přijme i záporná čísla jako atributy Odkud, Kam a Cena, protože dle definice algoritmus s takovými čísly nemůže pracovat. Proč by tedy byly ve zdrojových datech… Když nevím, tak si nevymýšlím omezení. Pokud jde o korektnost řešení, není splněn předpoklad daný zadáním, zde nelze pochybovat, na svou obhajobu však doplňuji, že výstup programu poskytuje korektní kostry.
- #25: Fork se provede pouze v případě, že máme více možností na stejné úrovni při probírání seřazených hran. Máme 4 jedničky, provedeme 5x fork. Máme další hranu 2 pouze jednu? Přidáme a testujeme podmínky.
- #27: http://blog.kostecky.cz/2016/01/kruskaluv-algoritmus-implementace-rozbor.html Presentation theme & photo by Tieto Czech s.r.o