ee.ut.kiho.graaf
Class Graaf

java.lang.Object
  ee.ut.kiho.graaf.Graaf

public class Graaf
extends Object

GRAAF.

Graaf on paar (V, E), kus V on tippude hulk, E ⊆ V×V on kaarte hulk.

Tipuga on seotud tema nimi (sõne), vt Tipp.

Kaarega on seotud tema nimi (sõne), vt Kaar.

Soovitatav on vältida silmuseid, st kaari (a, a), a ∈ V, kuna graafi ekraanil kuvamise vahend GraafiJoonistaja võimaldab joonistada/toimetada ainult silmusteta graafe.

Author:

Jüri Kiho

Field Summary

protected Vector<Kaar>	kaared Selle graafi kaarte hulk.
protected Vector<Tipp>	tipud Selle graafi tippude hulk.

Constructor Summary

Graaf()
Konstrueeritakse tühi graaf.

Graaf(int n, int maxAste)
Konstrueeritakse juhugraaf.

Graaf(String s)
Konstrueeritakse graaf tabelkuju põhjal.

Method Summary

int	aste(Tipp t) Tipu (väljund)aste.
void	eemaldada(Kaar k) Kaare eemaldamine.
void	eemaldada(Tipp t) Tipu eemaldamine.
int	indeks(Kaar k) Kaare indeks kaarte vektoris.
int	indeks(Tipp t) Tipu indeks tippude vektoris.
Kaar	kaar(int i) Antud indeksiga kaar.
Kaar	kaar(Tipp t, Tipp u) Selle graafi kaar tipust t tippu u.
Kaar	lisada(Kaar k) Kaare lisamine.
Tipp	lisada(Tipp t) Tipu lisamine.
int	m() Selle graafi kaarte arv.
int	n() Selle graafi tippude arv.
Vector<Tipp>	naabrid(Tipp t) Tipu naabrite hulk.
int	sisendaste(Tipp t) Tipu sisendaste.
Vector<Kaar>	sisenevad(Tipp t) Tippu sisenevate kaarte hulk.
static Graaf	sisestadaTabelist(String failinimi) Graafi tekstifailist.
Tipp	tipp(int i) Antud indeksiga tipp.
String	toString() Graafi sõnekuju ehk tabelkuju.
void	väljastadaTabelina(String failinimi) Graafi väljastamine tekstifaili.
Vector<Kaar>	väljuvad(Tipp t) Tipust väljuvate kaarte hulk.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

tipud

protected Vector<Tipp> tipud

Selle graafi tippude hulk. Esitatud vektorina, st järjestatult.

kaared

protected Vector<Kaar> kaared

Selle graafi kaarte hulk. Esitatud vektorina, st järjestatult.

Constructor Detail

Graaf

public Graaf()

Konstrueeritakse tühi graaf.

Graaf

public Graaf(String s)

Konstrueeritakse graaf tabelkuju põhjal.

Parameters:

s - graaf tabelkujul (meetodi toString() tulemus).

Graaf

public Graaf(int n,
             int maxAste)

Konstrueeritakse juhugraaf.

Konstrueeritakse silmusteta ja multikaarteta juhugraaf, milles tippuda arv ≤ n,

tipuaste <= maxAste ja puuduvad isoleeritud tipud (va juht maxAste == 0);

tipumärgendid on hulgast {"A","B", "C", ...}; kaaremärgendid: "" (tühisõned).

Parameters:

n - tippude arvu ülempiir ( > 1)

maxAste - tipu (väljund)astme ülempiir ( ≥ 0).

Method Detail

n

public int n()

Selle graafi tippude arv.

Returns:

Tippude arv selles graafis.

m

public int m()

Selle graafi kaarte arv.

Returns:

Kaarte arv selles graafis.

lisada

public Tipp lisada(Tipp t)

Tipu lisamine.

Sellesse graafi lisatud tipp t (kui veel ei olnud seda tippu).

Parameters:

t - lisatav tipp.

Returns:

Lisatud tipp (t).

lisada

public Kaar lisada(Kaar k)

Kaare lisamine.

Sellesse graafi lisatud kaar k (olemasolev kaar asendatakse).

Parameters:

k - lisatav kaar.

Returns:

Lisatud kaar (k).

eemaldada

public void eemaldada(Tipp t)

Tipu eemaldamine.

Tipp t eemaldatakse sellest graafist (kui tipp t oli selles graafis).

Parameters:

t - eemaldatav tipp.

eemaldada

public void eemaldada(Kaar k)

Kaare eemaldamine.

Kaar k eemaldatakse sellest graafist (kui kaar k oli selles graafis).

Parameters:

k - eemaldatav kaar.

indeks

public int indeks(Tipp t)

Tipu indeks tippude vektoris.

Parameters:

t - tipp.

Returns:

Tipu t järjekorranumber ≥ 0 (või -1, kui t ei ole selle graafi tipp).

indeks

public int indeks(Kaar k)

Kaare indeks kaarte vektoris.

Parameters:

k - kaar.

Returns:

Kaare k järjekorranumber ≥ 0 (või -1, kui k ei ole selle graafi kaar).

tipp

public Tipp tipp(int i)

Antud indeksiga tipp.

Parameters:

i - tipu indeks ≥ 0.

Returns:

Tipp järjekorranumbriga i.

Throws:

ArrayIndexOutOfBoundsException - kui i ¬in {0 ... n()-1}.

kaar

public Kaar kaar(int i)

Antud indeksiga kaar.

Parameters:

i - kaare indeks ≥ 0.

Returns:

Kaar järjekorranumbriga i.

Throws:

ArrayIndexOutOfBoundsException - kui i ¬in {0 ... m()-1}.

kaar

public Kaar kaar(Tipp t,
                 Tipp u)

Selle graafi kaar tipust t tippu u.

Parameters:

t - lähtetipp

u - lõpptipp.

Returns:

Selle graafi kaar t → u, või null (kui kaar t → u puudub).

aste

public int aste(Tipp t)

Tipu (väljund)aste.

Parameters:

t - selle graafi tipp.

Returns:

Tipust t väljuvate kaarte arv, st tipu t väljundaste.

sisendaste

public int sisendaste(Tipp t)

Tipu sisendaste.

Parameters:

t - selle graafi tipp.

Returns:

Tippu t sisenevate kaarte arv, st tipu t sisendaste.

naabrid

public Vector<Tipp> naabrid(Tipp t)

Tipu naabrite hulk.

Parameters:

t - selle graafi tipp.

Returns:

Tipust t väljuvate kaarte lõpptippudest moodustatud järjend (vektorina).

väljuvad

public Vector<Kaar> väljuvad(Tipp t)

Tipust väljuvate kaarte hulk.

Parameters:

t - selle graafi tipp.

Returns:

Tipus t väljuvatest kaartest moodustatud järjend (vektorina).

sisenevad

public Vector<Kaar> sisenevad(Tipp t)

Tippu sisenevate kaarte hulk.

Parameters:

t - selle graafi tipp.

Returns:

Tippu t sisenevatest kaartest moodustatud järjend (vektorina).

väljastadaTabelina

public void väljastadaTabelina(String failinimi)

Graafi väljastamine tekstifaili.

Faili väljastatakse selle graafi sõnekuju (ridade kaupa); vt toString().

Parameters:

failinimi - tulemusfaili täis- või lihtnimi; viimasel juhul lisatakse lihtnime ette tee System.getProperty("user.dir").

sisestadaTabelist

public static Graaf sisestadaTabelist(String failinimi)

Graafi tekstifailist.

Eeldus: failis paikneb selle graafi sõnekuju (ridade kaupa), vt toString(); tippude nimedes ei ole tühikuid.

Parameters:

failinimi - tulemusfaili täis- või lihtnimi; viimasel juhul lisatakse lihtnime ette System.getProperty("user.dir").

Returns:

Failist loetud sõnekuju põhjal konstrueeritud graaf (failitõrke korral null).

toString

public String toString()

Graafi sõnekuju ehk tabelkuju.

Sõnekuju koosneb ridadest (rea lõpetab sümbol '\n'). Graafi igale tipule vastab parajasti üks rida, i-ndale tipule vastav rida on kujul

i) <i-nda tipu nimi> <k1> <k2> ...

kus <k1>, <k2> ... on sellest tipust väljuvate kaarte kirjeldused kujul <kaare nimi> --> <kaare lõpptipu number>.

Tippude numeratsioon algab numbrist 1.

Overrides:

toString in class Object

Returns:

Selle graafi sõnekuju.