4. Domácí úkol: Vizualizace grafů

Typ Graph a související metody

Balíček bude exportovat typ Graph modelující jednoduchý (mezi vrcholy vede maximálně jedna hrana, hrany začínající a končící ve stejném vrcholu nejsou povoleny) souvislý (z každého vrcholu se po hranách lze dostat do libovolného jiného vrcholu) a neorientovaný (hrany $(a,b)$ a $(b, a)$ považujeme za totožné) graf, jehož konstruktor bude přijímat hrany ve formě pole (1D Array, resp. Vector) dvojic (Tuple). Vrcholy mohou být celá čísla (podtyp Integer) nebo řetězce (podtyp AbstractString).

Dále bude balíček exportovat následující metody:

Typ i metody budou vybaveny alespoň stručným docstringem, případně i s ukázkou použití ve formě doctestů.

Dále doporučuji pro přehlednost vhodně rozšířit metodu show aby výpis v interaktivních prostředích byl přehledný.

Vizualizace

Dále bude balíček exportovat dvě metody umožňující reprezentovat graf jakožto množinu bodů v rovině.

Metoda coordinates(G::Graph; alpha = 2, beta = 1, …​) se pokusí hezky přiřadit vrcholům souřadnice v rovině ($\mathbb{R}^2$). Tato metoda vrací dvojici polí (xs, ys), kde pole xs, resp. ys, obsahuje $x$-ové, resp. $y$-ové, souřadnice vrcholů v pořadí odpovídajícím vertices(G).

Prvním krokem výpočtu souřadnic vrcholů spočívá ve fyzikální realizaci: na vrcholy grafu se budeme dívat jako na odpuzující se částice a na hrany jako na smršťující se pružinky. Inspirujeme se Coulombovým a Hookovým zákonem z fyziky:

Souřadnice pak získáme minimalizací celkové potenciální energie (součet přes všechny dvojice vrcholů a přes všechny hrany výrazů uvedených výše).

Po této minimalizaci je vhodné ještě body například posunout tak, aby těžiště celého grafu bylo v počátku souřadného systému a případně se pokusit o vhodnou rotaci, nebo alespoň škálování do nějakého zvoleného prostoru (požadovaná velikost obrázku).

Metoda draw(G::Graph; filename = nothing, labels = true, …​) pak vykreslí (nebo uloží do souboru filename) grafickou reprezentaci grafu: hrany reprezentujeme úsečkami, vrcholy kolečky/puntíky se souřadnicemi získanými dříve zmíněnou metodou coordinates. Pokud je argument labels roven true, pak u vrcholů vykreslíme i jejich popisky (což byly integery nebo řetězce). Výstup případně může být ovlivněn i dalšími keyword argumenty.

Minimalizace potenciální energie

Minimum potenciální energie minimalizujte přirozeně pomocí JuMP.jl, jako řešič můžete zkusit použít Ipopt.jl. Pravděpodobně budete muset nastavit náhodně počáteční hodnoty proměnných pomocí metody set_start_value, řešič (Ipopt ano) totiž začne s nulovými hodnotami všech souřadnic a ty kvůli faktorům $1/r$ v objektivní funkci nejsou vhodné. Volba těchto hodnot samozřejmě není úplně bezvýznamná, v tento okamžik se ale můžeme spokojit s dostatečně náhodným nastavením. Znamená to, že opakované vykreslení grafu dá často jiný výsledek. U komplikovanějších grafů může být i výrazně jiný. Celková potenciální energie bude mít typicky větší množství lokálních minim.

Výsledné kreslení grafu

K finálnímu vykreslování by šlo použít některou z grafických knihoven, které jsme si během semestru ukazovali. Pro naše účely bude ale daleko vhodnější využít například Luxor.jl. Tento balíček umožňuje jednoduše vytvářet vektorovou grafiku a navíc má velmi podrobnou dokumentaci.

Následující obrázek

byl vytvořen pomocí tohoto kódu:

using Luxor

Drawing(500, 500, :svg) # :svg lze nahradit názvem souboru
origin()

# Tři vrcholy A, B a C
A = Point(100, 100)
B = Point(50, -20)
C = Point(200, 50)

# A-B
move(A)
line(B)
strokepath()

# A-C
move(A)
line(C)
strokepath()

# Vrcholy
sethue("light blue")
circle(A, 10)
fillpath()

circle(B, 10)
fillpath()

circle(C, 10)
fillpath()

# Popisky
sethue("black")
text("1", A, halign=:center, valign=:middle)
text("2", B, halign=:center, valign=:middle)
text("3", C, halign=:center, valign=:middle)

finish()
preview()

Pro inspiraci viz Jupyter notebok usage.ipynb.

Julia balíček

Julia balíček bude vybaven automatizovanými unit testy, ty jsou v repozitáři již připraveny a generátorem dokumentace pomocí Documenter.jl. Dokumentaci nemusíte vystavovat veřejně přístupnou na webu. Stačí, když půjde lokálně vytvořit. Inspirovat se můžete v balíčku, který jsme vytvářeli v semestru DobbleExample.jl

Strukturu balíčku vytvořte ve svém repozitáři ve větvi solution/04-graphs. Uživatel/opravující ho pak bude moci instalovat v Pkg módu příkazem

] add https://gitlab.fit.cvut.cz/BI-JUL/B211/USERNAME#solution/04-graphs

případně

] dev https://gitlab.fit.cvut.cz/BI-JUL/B211/USERNAME#solution/04-graphs