Uživatelské rozhraní obsahuje obrázek grafu a v dolni části obrazovky
prikazovou radku a info řádku. Uzly v grafu jsou uspořádány ekvidistantně na kružnici a
označeny 1-n, kde n je počet uzlů. Z příkazového řádku se ovládá celý program. Prikazem
help se zruší obrázek a umožní se zobrazeni sady všech užívaných příkazů a algoritmů, které byly
implementovany. Info řádek zobrazuje informace o průběhu zpracování příkazů, chyby případně komentuje výsledky
algoritmu.
Program pracuje s datovými soubory (standardní přípona .dat), které reprezentují grafy.
Program umožňuje nahrávání a ukládání grafů a přes sadu příkazů editaci grafu a spouštění
implementovaných algoritmů. Program se spouští příkazem :
galg1.exe [graph.dat]
kde nepovinný parametr [graph.dat] udává název datového souboru, který bude po spuštění
programu automaticky načten.
| nazev prikazu | zkratka | parametry a popis
| pridej vrchol | addv [n] | vrcholy se cisluji
automaticky; nepovinny par. udava pocet pridanych vrcholu
| uber vrchol | delv v | zada se cislo vrcholu
| uber hranu | dele pv kv | zada se PV a KV
| nastav hranu | sete pv kv ch | zada se PV, KV a
CH (pokud se nezada cena hrany, nastavi se CH automaticky na 1)
| uloz graf | save grX | zada se nazev grafu (napr.
gr1)
| nahrej graf | load grX | zada se nazev grafu
| spust alg. | runa 1-Y | zada se cislo algoritmu
| napoveda | help |
| ukonci program | quit |
| |
PV - pocatecni vrchol hrany; KV - koncovy vrchol hrany; CH - cena hrany
1 - Jarníkuv algoritmus hledání nejlevnější kostry
2 - Borůvkův algoritmus hledání nejlevnější kostry
3 - topologické uspořádání vrcholů a hran
4 - (silně) souvislé komponenty grafu
5 - hledání nejlevnější kostry pomocí topologického uspořádání
Algoritmus 5 potřebuje ke své činnosti zadat počáteční vrchol ( priklad : RUNA 5 2 ).
Zdrojový kód prostředí je umístěn v souborech :
GALG2.CPP, GALG2.H - samotný algoritmus pro zpracování příkazů
GRAF.CPP, GRAF.H - modul reprezentace grafu
OOMKGUI.CPP, OOMKGUI.H - modul prostředí
V prostředí je graf zpracován objektově (implementace v GRAF.*):
class Hrana
{
private:
int poc;
int kon;
int cena;
public:
Hrana(int _poc,int _kon,int _cena) { poc=_poc; kon=_kon; cena=_cena; }
void zobraz(int colorh,int colors,int pocetv); // zobrazi hranu
void vypiscenu(int color,int pocetv); // zobrazi cenu hrany
void vypiscislo(int cis,int color,int pocetv); // zobrazi cislo hrany
void setpoc(int _poc) { poc=_poc; }
int getpoc() const { return poc; }
void setkon(int _kon) { kon=_kon; }
int getkon() const { return kon; }
void setcena(int _cena) { cena=_cena; }
int getcena() const { return cena; }
};
// struktura pro uchovavani hran ve spojovem seznamu
typedef struct titem {
titem *next;
Hrana *ref;
};
class Graf
{
friend class GrafIter;
private:
int pocetv;
titem *item;
titem *end;
public:
Graf();
~Graf();
void pridejvrcholy(int pocet) { pocetv+=pocet; }
void odebervrchol(int cislo);
void pridejhranu(Hrana *ref);
void odeberhranu(int poc,int kon);
void odebervse();
void save(char *filename);
void zobraz(int zobrazvrch,int zobrazceny,int zobrazcisla,int color); // zobrazi graf
void zobrazvrchol(int cislo,int popis,int color); // zobrazi vrchol cislo
TGraf *export();
int import(TGraf *_graf);
void setpocetv(int _pv) { pocetv=_pv; }
int getpocetv() const { return pocetv; }
};
Následující struktury jsou standardně používány pro předávání informací mezi prostředím a algoritmy. Pokud algoritmus potřebuje krom grafu ještě další informace jsou předávány podle potřeb jednotlivých algoritmů a jsou popsány v dokumentaci těchto algoritmů.
struct THrana {
int pv;
int kv;
int cena;
};
struct TGraf {
int nvrch;
int nhran;
THrana *phran;
};
Pro převádění těchto struktur na objekty zpracovávané prostředím jsou používány členské funkce
třídy Graf a to Graff::export a Graf::import.
Celý program se skládá z těchto zdrojových souborů :
GALG2.CPP, GALG2.H - samotný algoritmus pro zpracování příkazů
GRAF.CPP, GRAF.H - modul reprezentace grafu
OOMKGUI.CPP, OOMKGUI.H - modul prostředí
ALG1.CPP, ALG1.H - modul algoritmů 1 a 2
ALG3.CPP - modul algoritmů 3
ALG4.CPP - modul algoritmů 4
ALG5.CPP, ALG5.H - modul algoritmů 5
Pro úspěšný překlad vytvořte projekt obsahující soubory :GALG2.CPP, GRAF.CPP, OOMKGUI.CPP, ALG1.CPP, ALG3.CPP, ALG4.CPP, ALG5.CPP. V adresáři, kde bude výsledný spustitelný kód zlinkován, by také měly být soubory EGAVGA.BGI (podpora grafiky) a LITT.CHR (znaková sada).
Během vývoje prostředí byly dodefinovány pomocné "extra" příkazy, které sloužily ke zrychlení
ladění. Přesto by však mohly být užitečné i při používání programu. Pokud má program přesně splňovat
zadání je nutné odstranit (oddefinovat) makro EXTRA.
Tady si můžete stáhnout všechny soubory potřebné ke kompilaci a zlinkování : download