Programiranje 2

Enostaven graf je množica točk (vozlišč), pri čemer so lahko nekateri pari točk med seboj povezani. Za predstavitev posamezne točke definiramo razred Tocka, ki lahko poleg imena točke in množice sosednih točk vsebuje še druge podatke o točki (koordinate, barvo, vrednost, ...), ki pa jih zaenkrat ne bomo potrebovali. Za predstavitev grafa definiramo razred Graf, ki vsebuje slovar vseh njegovih točk (ključi so imena točk, vrednosti pa objekti razreda Tocka).

Množico točk in slovar, ki ima za ključe nize, za vrednosti pa točke, deklariramo takole:

Set<Tocka> mnozica;
Map<String, Tocka> slovar;

Pri tem Set in Map nista prava razreda, pač pa samo vmesnika. Ko želimo ustvariti prazno množico ali prazen slovar, moramo ustvariti nov objekt razreda, ki implementira vse metode tega vmesnika. Za množico sta takšna razreda HashSet in TreeSet, za slovar pa HashMap in TreeMap. Torej bi pisali:

mnozica = new HashSet<Tocka>();
slovar = new HashMap<String, Tocka>();

Naloga

Sestavi razrede Tocka, Graf in Test. Prvi je namenjen predstavitvi posamezne točke, drugi predstavitvi celotnega grafa, tretji pa preverjanju delovanja prvih dveh. Če ni navedeno drugače, so spodaj navedene komponente zaščitene, metode pa javne in objektne.

Razred Tocka naj vsebuje:

• komponento ime (niz)
• komponento sosedi (množica točk)
• konstruktor, ki ustvari novo izolirano točko (to je točko brez sosedov) z danim imenom
• metodo stopnja, ki vrne število sosednjih točk
• metodo toString, ki vrne ime točke (to metodo uporablja print, če mora izpisati objekt). Uporabi @Override.

Razred Graf naj vsebuje:

• privatno komponento stevec (celo število). Števec bomo uporabljali pri samodejnem poimenovanju točk.
• komponento tocke (slovar)
• konstruktor, ki ustvari nov graf brez točk
• metodo tocka, ki vrne točko z danim imenom (če takšne točke v grafu ni, vrne null)
• metodo povezava, ki preveri, ali obstaja povezava med danima točkama

• metodo dodajTocko, ki ustvari točko z danim imenom in jo doda grafu. Vrne naj dodano točko. Če točka z istim imenom v grafu že obstaja, naj ne naredi ničesar in vrne točko iz grafa.
• metodo dodajTocko, ki ustvari samodejno poimenovano točko in jo doda grafu. Vrne naj dodano točko. Izbrano ime naj bo takšno, da točke s tem imenom še ni v grafu (uporabi komponento stevec).
• metodo dodajPovezavo, ki grafu doda povezavo med danima točkama, če sta točki različni
• metodo odstraniPovezavo, ki iz grafa odstrani povezavo med danima točkama
• metodo odstraniTocko, ki iz grafa odstrani dano točko, še prej pa vse povezave, ki imajo eno krajišče v tej točki. Pazi pri odstranjevanju povezav. Zanka bo tekla po vseh sosedah, vendar ne smeš uporabiti metode odstraniPovezavo, saj bi s tem spremenil množico, po kateri teče zanka.

• privatno metodo dodajTocke, ki grafu doda n novih izoliranih točk, poleg tega vse nove točke vrne v tabeli (pomožna metoda)
• statično metodo prazen, ki ustvari in vrne nov prazen graf na n točkah
• statično metodo cikel, ki ustvari in vrne nov cikel na n točkah
• statično metodo poln, ki ustvari in vrne nov poln graf na n točkah
• statično metodo polnDvodelen, ki ustvari in vrne nov poln dvodelen graf na n + m točkah

• metodo izpis, ki v pregledni obliki izpiše, katere točke so v grafu in s katerimi točkami so povezane

Razred Test naj vsebuje:

• statično metodo main, ki preveri delovanje metod iz razredov Tocka in Graf

Dodatno: Razredu Graf dodaj še:

• metodo povezan, ki preveri, ali je graf povezan
• metodo steviloKomponent, ki prešteje, iz koliko povezanih komponent je sestavljen graf