Floyd-Warshallův srandovní algoritmus
(Hledání nejkratších cest mezi všemi páry uzlů pomocí Floyd-Warshallova algoritmu (semestrální práce X36TI))
zadání znělo:
Tematický okruh 2 – Implementačně vizualizační
Vytvořte demonstrační nástroj, který bude velmi názornou formou zobrazovat chování Floyd-Warshallova algoritmu. Aplikace musí splňovat tyto podmínky:
- Graf, na kterém se bude demonstrovat, si může uživatel sám definovat (editorem, vstupním souborem aj.)
- Aplikace bude prezentovat spojitost mezi algoritmem zapsaným pseudokódem (doporučuji použít ten ze skript) a vizualizovanými změnami na grafu.
- Průběh algoritmu bude minimálně možno pozastavit nebo restartovat
- spustitelný program
- zdrojové kódy (jako netbeans projekt)
- licencováno pod GPL v2 (český překlad)
Realizace nebo tak něco…
Program je napsaný v Javě a měl by proto bez problémů běžet všude, kde je nainstalované Java Runtime Environment, což by mělo být úplně všude.
Spustí se to jednoduše přes .jar archiv ve složce dist. Když nemáte v systému
jar soubory asociované s javou (což je samo o sobě dost divné), tak je tady pro
Linux shellový skript tin.sh nebo pro Windows
tin.bat, který udělá všechnu špinavou práci. Nebo taky funguje
saré dobré konzolové java -jar TIN.jar. K běhu je potřeba
přibalený jar archiv ve složce lib.
Zdrojové kódy (připravené jako projekt pro NetBeans. Nemám žaludek na to, abych
z projektu vytáhnul jenom složku src) se dají stáhnou extra.
Dopředu řeknu, že to není hezký pohled. Několik míst by se dalo vylepšit, ale
když to funguje…
Ovládání
Interface programu je rozdělen na tři části:
v levé části se kreslí graf.
- levý klik do volného prostoru nakreslí uzel
- levý klik na uzel vybere daný uzel, další výběr uzlu vytvoří hranu mezi dvěma vybranými uzly
- levý klik na číslo s ohodnocením změní ohodnocení hrany (aktivuje kolonku wigth vlevo dole)
- pravý klik do volného prostoru zruší výběr
- pravý klik na uzel smaže zaměřený uzel
- pravý klik na číslo s ohodnocením hrany smaže hranu
- tažení uzlu levým tlačítkem myši přesune uzel
V prostřední části jsou matice délek a předchůdců a tlačítka, která spustí kompletní FW algoritmus nebo zahájí krokování
V pravé části je pak pseudo kód, který se zvýrazňuje podle toho, jaká část se právě provádí.
* 14. června 2008