Připravil jsem 2 nástroje, které by se mohly hodit.
pal_check.exe
Nástroj pal_check.exe slouží ke kontrole výstupu z vašeho řešení. Nástroj zkontroluje, zda se lze ze všech uzlů dostat do všech ostatních uzlů, jestli ve vašem řešení neexistuje cyklus, jestli výsledná nejnižší cena je stejná jako součet cen všech hran. Nástroj tedy kontoluje, jestli je to strom a jestli odpovídá cena.
Nástroj však nedokáže zjistit, jestli nalezený strom má nejnižší cenu ze všech možných stromů.
Použití v přikazovém řádku: pal_check.exe vstupní_soubor počet_uzlů
Př.: pal_check.exe vstup.txt 1500
pal_con.exe
Některá vstupní data a správné výstupy se dají stáhnout odsud: https://cw.felk.cvut.cz/doku.php/courses/a4m33pal/cviceni/data Ovšem v těchto příkladech jsou až desítky tisíc uzlů. Takže pokud máte vlastní řešení, které není správné, lze jen těžko mezi tolika uzly najít chybu.
Tento nástroj vezme dva řešení a větve, které mají stejné hrany v obou řešeních spojí do jediné hrany a jediného uzlu. Graf o 10000 uzlech se tak může zkondenzovat jen na několik málo uzlů a na výstupu uvidíte pouze rozdíly mezi dvěma řeseními.
Názorněji je to vysvětleno na obrázku níže:
Výstupní grafy jsou mnohem jednodušší než vstupní - rozdíly mezi vaším řešením a správným jsou mnohem lépe vidět. Povedlo si mi takto zjednodušit graf o 10000 uzlech na pouhých 9 uzlů a hned je vidět, co je v obou řešeních jinak.
Použití v přikazovém řádku: pal_con.exe prvni_reseni druhe_reseni počet_uzlů
Př.: pal_con.exe reseni1.txt reseni2.txt 10000
GraphViz
Nástroj na snadné vizualizace jakýchkoliv grafů. Pro příklad si uveďme vzorový soubor k vizualizaci:
priklad.dot
digraph G {
1 -> 2;
2 -> 3;
3 -> 4;
4 -> 1;
}