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

* Tipuga on seotud tema nimi (sõne), vt {@see ee.ut.kiho.graaf.Tipp}.
*

* Kaarega on seotud tema nimi (sõne), vt {@see ee.ut.kiho.graaf.Kaar}.
*

* Soovitatav on vältida silmuseid, st kaari (a, a), a ∈ V,
* kuna graafi ekraanil kuvamise vahend {@see ee.ut.kiho.graaf.GraafiJoonistaja}
* võimaldab joonistada/toimetada ainult silmusteta graafe.
* @author Jüri Kiho
*/
public class Graaf

---

doc Selle graafi tippude hulk.

---


   * Esitatud vektorina, st järjestatult.

---

   protected Vector tipud;

---

doc Selle graafi kaarte hulk.

---


   * Esitatud vektorina, st järjestatult.

---

   protected Vector kaared;

---

konstruktorid

---

---

   public Graaf ()

---

---

doc Konstrueeritakse tühi graaf.

---

---

   tipud = new Vector ();
   kaared = new Vector ();

---

---

   public Graaf (String s)

---

---

doc Konstrueeritakse graaf tabelkuju põhjal.

---


   @param s graaf tabelkujul (meetodi {@see ee.ut.kiho.graaf.Graaf#toString} tulemus).

---

   this();
   String[] rida = s.trim().split("\n");
   int n = rida.length;
   Tipp[] tipp = new Tipp[n];

---

teha tipud  * i = 0 .. n-1

---


   tipp[i] = lisada(new Tipp());

---

---

 * i = 0 .. n-1

---


   String ridas = rida[i];
   int k = ridas.indexOf(")");
   ridas = ridas.substring(k+1).trim(); ilma "nr)"
    tipu nimi:
   String tipuNimi;
   int kv = ridas.indexOf(">");

---

   if (kv == -1)

---

kaari ei ole

   tipuNimi = ridas;
   tipp[i].seadaNimi(tipuNimi);

---

   else

---

   if (ridas.length() == 0)

---


   tipuNimi = "";

---

   else

   int ktyh = ridas.indexOf(" ");
   tipuNimi = ridas.substring(0, ktyh);
   ridas = ridas.substring(ktyh+1).trim(); ilma tipu nimeta

---

   tipp[i].seadaNimi(tipuNimi);

---

teha kaared

---


   String[] kaars = ridas.split(">");
   String kaaremärgend = kaars[0].substring(0, kaars[0].length()-2).trim();

---

 * j = 1 .. kaars.length-1

---


    kaaremärgend on eelmisest (i-1) olemas
   String osa = kaars[j].trim();
    osa: "nr märgend --" või
    "nr --" või
    "nr"

---

   if (osa.endsWith("--"))

---


   osa = osa.substring(0, osa.length()-2).trim(); "--" lõpust ära

---

   int ktyh = osa.indexOf(" ");
   String kuhu;

---

   if (ktyh == -1)

---


   kuhu = osa;

---

   else

   kuhu = osa.substring(0, ktyh);

---

   Tipp lõpptipp = tipp[Integer.parseInt(kuhu)-1];
   lisada(new Kaar(tipp[i], lõpptipp, kaaremärgend));
   
   kaaremärgend = osa.substring(kuhu.length()).trim();

---

---

---

---

---

---

   public Graaf(int n, int maxAste)

---

---

doc 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).
   @param n tippude arvu ülempiir ( > 1)
   @param maxAste tipu (väljund)astme ülempiir ( ≥ 0).

---

   this();
   char c = 'A';

---

 * i = 1 .. n n korda

---


   Tipp uus = lisada(new Tipp("" + (char)(c + i-1)+ "[0;0]") );
   uus.seadaKoordinaadid(juhuarv(0, 500), juhuarv(0, 400) );

---

    kaared:
   int m = juhuarv(0, n+1);

---

 * i = 1 .. m m korda

---


   Tipp a;
   Tipp b;

---

 * 

---


   a = tipp(juhuarv(0, n));
   b = tipp(juhuarv(0, n));

---

   if (a == b) silmusteta

---


   continue;

---

   

---

   if (naabrid(a).contains(b)) multikaarteta

---


   continue;

---

   break;

---

---

   if (aste(a) < maxAste)

---


   lisada(new Kaar(a, b, "" + (char)('a' + i-1)));

---

---

---

   if (maxAste > 0)

---


    eemaldada isoleeritud tipud

---

 * i = 0 .. n()-1

---


   Tipp t = tipp(i);

---

   if (aste(t) == 0 && sisendaste(t) == 0 )

---


   tipud.removeElement(t);
   i--;

---

   if (n() < 3)

---


   break;

---

---

---

---

---

---

---

elementide (tippude ja kaarte) arvud

---

---

   public int n()

---

---

doc Selle graafi tippude arv.

---


   @return Tippude arv selles graafis.

---

   return tipud.size();

---

---

   public int m()

---

---

doc Selle graafi kaarte arv.

---


   @return Kaarte arv selles graafis.

---

   return kaared.size();

---

---

---

elementide lisamised / eemaldamised

---

---

   public Tipp lisada(Tipp t)

---

---

doc Tipu lisamine.

---


   * Sellesse graafi lisatud tipp t (kui veel ei olnud seda tippu).
   @param t lisatav tipp.
   @return Lisatud tipp (t).

---

---

   if (indeks(t) == -1) kui tippu t veel ei ole

---


   tipud.add(t);

---

   return t;

---

---

   public Kaar lisada(Kaar k)

---

---

doc Kaare lisamine.

---


   * Sellesse graafi lisatud kaar k (olemasolev kaar asendatakse).
   @param k lisatav kaar.
   @return Lisatud kaar (k).

---

   Tipp a = k.algus();
   Tipp b = k.lõpp();
   Kaar k0 = kaar(a, b);

---

   if (k0 != null) kui leidub kaar (a; b)

---


   eemaldada(k0);

---

   kaared.add(k);
   return k;

---

---

   public void eemaldada(Tipp t)

---

---

doc Tipu eemaldamine.

---


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

---

---

   if (indeks(t) == -1) sellist tippu graafis ei ole

---


   return;

---

    eemaldada külgnevad kaared:

---

 * for(int i = 0; i < kaared.size(); ) EI: for(Kaar k: kaared)

---


   Kaar k = kaar(i);

---

   if (k.algus() == t || k.lõpp() == t)

---


   eemaldada(k);

---

   else

   i++;

---

---

    eemaldada tipp:
   tipud.removeElement(t);

---

---

   public void eemaldada(Kaar k)

---

---

doc Kaare eemaldamine.

---


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

---

---

   if (indeks(k) == -1) sellist kaart graafis ei ole

---


   return;

---

   kaared.removeElement(k);

---

---

---

elementide indeksid / otsimine

---

---

   public int indeks(Tipp t)

---

---

doc Tipu indeks tippude vektoris.

---


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

---

   return tipud.indexOf(t);

---

---

   public int indeks(Kaar k)

---

---

doc Kaare indeks kaarte vektoris.

---


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

---

   return kaared.indexOf(k);

---

---

   public Tipp tipp(int i)

---

---

doc Antud indeksiga tipp.

---


   @param i tipu indeks ≥ 0.
   @return Tipp järjekorranumbriga i.
   @throws ArrayIndexOutOfBoundsException kui i ¬in {0 ... n()-1}.

---

    Tulemus: tagastatakse i-s tipp
   return tipud.elementAt(i);

---

---

   public Kaar kaar(int i)

---

---

doc Antud indeksiga kaar.

---


   @param i kaare indeks ≥ 0.
   @return Kaar järjekorranumbriga i.
   @throws ArrayIndexOutOfBoundsException kui i ¬in {0 ... m()-1}.

---

    Tulemus: tagastatakse i-s kaar
   return kaared.elementAt(i);

---

---

   public Kaar kaar(Tipp t, Tipp u)

---

---

doc Selle graafi kaar tipust t tippu u.

---


   @param t lähtetipp
   @param u lõpptipp.
   @return Selle graafi kaar t → u, või null (kui kaar t → u puudub).

---

---

 * for(Kaar k: kaared)

---

---

   if (k.algus() == t && k.lõpp() == u)

---


   return k;

---

---

   return null;

---

---

---

tipu naabrus

---

---

   public int aste(Tipp t)

---

---

doc Tipu (väljund)aste.

---


   @param t selle graafi tipp.
   @return Tipust t väljuvate kaarte arv, st tipu t väljundaste.

---

   int s = 0;

---

 * for(Kaar k: kaared)

---

---

   if (k.algus() == t)

---


   s++;

---

---

   return s;

---

---

   public int sisendaste(Tipp t)

---

---

doc Tipu sisendaste.

---


   @param t selle graafi tipp.
   @return Tippu t sisenevate kaarte arv, st tipu t sisendaste.

---

   int s = 0;

---

 * for(Kaar k: kaared)

---

---

   if (k.lõpp() == t)

---


   s++;

---

---

   return s;

---

---

   public Vector naabrid(Tipp t)

---

---

doc Tipu naabrite hulk.

---


   @param t selle graafi tipp.
   @return Tipust t väljuvate kaarte lõpptippudest moodustatud järjend (vektorina).

---

   Vector tulemus = new Vector ();

---

 * for(Kaar k: kaared)

---

---

   if (k.algus() == t)

---


   tulemus.add(k.lõpp());

---

---

   return tulemus;

---

---

   public Vector väljuvad(Tipp t)

---

---

doc Tipust väljuvate kaarte hulk.

---


   @param t selle graafi tipp.
   @return Tipus t väljuvatest kaartest moodustatud järjend (vektorina).

---

   Vector tulemus = new Vector ();

---

 * for(Kaar k: kaared)

---

---

   if (k.algus() == t)

---


   tulemus.add(k);

---

---

   return tulemus;

---

---

   public Vector sisenevad(Tipp t)

---

---

doc Tippu sisenevate kaarte hulk.

---


   @param t selle graafi tipp.
   @return Tippu t sisenevatest kaartest moodustatud järjend (vektorina).

---

   Vector tulemus = new Vector ();

---

 * for(Kaar k: kaared)

---

---

   if (k.lõpp() == t)

---


   tulemus.add(k);

---

---

   return tulemus;

---

---

---

graaf faili / failist

---

---

   public void väljastadaTabelina(String failinimi)

---

---

doc Graafi väljastamine tekstifaili.

---


    * Faili väljastatakse selle graafi sõnekuju (ridade kaupa);
    * vt {@see ee.ut.kiho.graaf.Graaf#toString}.
   @param failinimi tulemusfaili täis- või lihtnimi;
    * viimasel juhul lisatakse lihtnime ette tee System.getProperty("user.dir").

---

---

 !!try

---


   String kuhu = GraafiJoonistaja.täisnimeks(failinimi); väljundfaili nimi
   PrintWriter vfail = writerTo(kuhu); väljundfaili kirjutaja
   
   String[] ss = toString().split("\n");

---

 * for(String rida : ss)

---


   vfail.println(rida); rea kirjutamine väljundfaili

---

    lõpetamine
   vfail.close();

---

   catch (IOException e)

   System.err.println(e.getMessage());

---

---

---

   public static Graaf sisestadaTabelist(String failinimi)

---

---

doc Graafi tekstifailist.

---


    * Eeldus: failis paikneb selle graafi sõnekuju (ridade kaupa),
    * vt {@see ee.ut.kiho.graaf.Graaf#toString}; tippude nimedes ei ole tühikuid.
   @param failinimi tulemusfaili täis- või lihtnimi;
    * viimasel juhul lisatakse lihtnime ette System.getProperty("user.dir").
   @return Failist loetud sõnekuju põhjal konstrueeritud graaf (failitõrke korral null).

---

   Graaf g = new Graaf();
   String s = "";

---

 !!try

---


   String kust = GraafiJoonistaja.täisnimeks(failinimi); sisendfaili nimi
   BufferedReader sfail = readerFrom(kust); sisendfailst lugeja
   String rida = "";

---

 * while((rida = sfail.readLine()) != null) rea lugemine ja lõpu kontroll

---


   s += rida + "\n";

---

    lõpetamine
   sfail.close();

---

   catch (IOException e)

   System.err.println(e.getMessage());
   return null;

---

   return new Graaf(s);

---

---

---

   public String toString()

---

---

doc 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.
   @return Selle graafi sõnekuju.

---

   String s = "";
   int n = n();
   int m = m();

---

 * i = 0 .. n-1 üle tippude

---


   Tipp ti = tipud.elementAt(i);
   s += (i+1) + ") " + ti.nimi();

---

 * j = 0 .. m-1 üle kaarte

---


   Kaar kj = kaared.elementAt(j);

---

   if (kj.algus() == ti)

---


   s += " " + kj.nimi() + " --> " + (tipud.indexOf(kj.lõpp()) + 1);

---

---

   s += "\n";

---

   return s;

---

---

   private static int juhuarv(int a, int b)

---

---

doc Juhu-täisarv.

---


   @param; a mittenegatiivne täisarv
   @param; b mittenegatiivne täisarv.
   @return; Juhuarv poollõigult [a; b) (kui a > b, siis poollõigult [b; a) ).

---

   return (int)(a + Math.random()*(b - a));

---