// Kiss Endre Farkas (KIELAAT.elte)
// Fesz�t�fa sz�less�gi bej�r�ssal.
#include <iostream>
using namespace std;
typedef enum{NEM, IGEN} logikai;
typedef int PontTip;
typedef int szamSor[10];
typedef PontTip Sor[10];
typedef logikai Graf[10][10];
// A halmaz egy logikai t�mb, adott indexen IGEN jelzi, ha benne van valami
typedef logikai Halmaz[10];

struct grafEl{
        int kezd;
        int veg;
};

// A sz�less�gi bej�r�sok �br�zol�s�ra szolg�l� adatstrukt�ra
struct bejarasEredmeny{
        szamSor sorozat;
        int pontSzam;
};


class alapGraf {
  private:
    int x, y;
    // Sorhoz sz�ks�ges v�ltoz�k:
    int SorEleje, SorVege;
    int SorHossz;
    logikai SorHiba;

  public:
    // Adatstrukt�r�k (sor, halmaz, cs�csm�trixos gr�f) deklar�l�sa
    Sor se;
    Halmaz ha;
    Graf ge;
    void probaAdatok();
    void csucsmatrixRajzol();
    int pontSzam();
    // Sor m�veletek:
    void SorUres ();
    logikai SorUresE();
    logikai SorTeleE();
    PontTip SorElso();
    void Sorba(PontTip);
    PontTip Sorbol();
    logikai SorHibasE ();
    // Halmaz m�veletek:
    void HalmazUres();
    void Halmazba(PontTip);
    void PontKiir(PontTip);
    logikai Eleme(PontTip);
    // gr�f m�veletek:
    void GrafUres();
    void Osszekot (PontTip, PontTip);
    void Elszakit (PontTip, PontTip);
    logikai vanEl (PontTip, PontTip);
    int SzomszedPontokSzama(PontTip);
    int minimumPont();
    PontTip SzomszedPont(PontTip, int);

    grafEl grafBeolvas();

    // konstruktor:
    alapGraf(){
               SorUres();
               HalmazUres();
               GrafUres();
    }
    // destruktor:
    ~alapGraf(){
    }

};

// lesz�zmazott oszt�ly
class bejaras : public alapGraf
{
 public:
      alapGraf grafom;
      bejarasEredmeny szelessegiBejaras (PontTip);
      bejaras operator+(int ezSor);
};

bejaras bejaras::operator+(int ezSor) {
  bejaras helyi;
  int i;
  helyi.GrafUres();
  for (i=1; i<=10; i++) {
      helyi.ge[ezSor][i]=IGEN;
  }
  return (helyi);
}

bejarasEredmeny bejaras::szelessegiBejaras(PontTip tol) {
PontTip pont, szomszed;
int i;
    bejarasEredmeny eredmeny;
    eredmeny.pontSzam=0;
    for (i=1; i<=10; i++) {eredmeny.sorozat[i]=0;}

    pont=tol;
    SorUres(); HalmazUres();
    Sorba(pont); Halmazba(pont);
    while (SorUresE()==NEM)
    {
       pont=Sorbol();
       eredmeny.pontSzam++;
       eredmeny.sorozat[eredmeny.pontSzam]=pont;
       // PontKiir(pont);
       for (i=1; i<=SzomszedPontokSzama(pont); i++) {
           szomszed=SzomszedPont(pont, i);
           if (Eleme(szomszed)==NEM) {
              Sorba(szomszed);
              Halmazba(szomszed);
           }
       }
    }
    return eredmeny;
}

int alapGraf::minimumPont() {
    // Megadja a legkisebb indexu pontot, ahonnan indul ki el
    int kiindulo,d,f;
    kiindulo=11;
    for (d=10; d>=1; d--) {
         f=10;
         while (f>=1) {
             if (ge[d][f]==IGEN) {
                if (kiindulo>d) {kiindulo=d;}
                f=1;
             }
         f--;
         }
     }
     return kiindulo;
}

int alapGraf::pontSzam() {
    // Megadja, hogy hany pont van a grafban, amikol indul ki el
    int ennyi,i,j;
    ennyi=0; i=1;
    while (i<=10)
    {
         j=1;
         while (j<=10)
         {
             if (ge[i][j]==IGEN)
             {
                ennyi++;
                j=11;
             }
             j++;
         }
         i++;
     }
     return ennyi;
}

void alapGraf::csucsmatrixRajzol() {
     int i,j;
     cout<<"\nCsucsmatrix\n";
     cout<<"(- - nincs kapcsolat, T - van kapcsolat) \n";
     for (i=1; i<=10; i++) {
         for (j=1; j<=10; j++) {
             if (ge[i][j]==IGEN) {cout<<"T ";} else {cout<<"- ";}
         }
         cout<<"\n";
     }
     cout<<"\n";
}

void alapGraf::probaAdatok() {

     Osszekot(1,2);
     Osszekot(1,3);
     Osszekot(2,3);
     Osszekot(2,4);
     Osszekot(3,4);
     Osszekot(2,6);
     Osszekot(3,5);
     Osszekot(4,5);
     Osszekot(4,6);
     Osszekot(5,6);

     cout<<"\nProba adatok sikeresen betoltve.\n";
}
void alapGraf::PontKiir(PontTip p) {
     cout<<" "<< p<<" ";
}

// Halmatm�veletek kidolgozva:
void alapGraf::HalmazUres() {
int i;
    for (i=1; i<=10; i++) {
        ha[i]=NEM;
    }
}
void alapGraf::Halmazba(PontTip p) {
     ha[p]=IGEN;
}
logikai alapGraf::Eleme(PontTip p) {
    return ha[p];
}

// Sor m�veletek kidolgozva:

void alapGraf::SorUres() {
     SorEleje=1;
     SorVege=1;
     SorHossz=0;
     SorHiba=NEM;
}
logikai alapGraf::SorUresE() {
     // cout<<"SorUresE\n";
     logikai logik;
     if (SorHossz==0) {logik=IGEN;} else {logik=NEM;}
     return logik;
}
logikai alapGraf::SorTeleE() {
     logikai logik;
     if (SorHossz==10) {logik=IGEN;} else {logik=NEM;}
     return logik;
}
PontTip alapGraf::SorElso() {
     PontTip ez;
     if (SorHossz>0) {
        ez=se[SorEleje];
     } else {
       SorHiba==IGEN;
     }
     return ez;
}
void alapGraf::Sorba(PontTip pont) {
     if (SorHossz<10) {
        se[SorVege]=pont;
        SorHossz++;
        SorVege++;
        if (SorVege==10) { SorVege=1; }
     } else {
        SorHiba=IGEN;
     }
}
PontTip alapGraf::Sorbol() {
     PontTip pont;
     if (SorHossz>0)
     {
        pont=se[SorEleje];
        SorHossz--;
        SorEleje++;
        if (SorEleje==10) { SorEleje=1; }
     }
     return pont;
}
logikai alapGraf::SorHibasE() {
        logikai logik;
        if (SorHiba==IGEN) {logik=IGEN;} else {logik=NEM;}
        return logik;
}

// Gr�f m�veletek kidolgozva:
void alapGraf::GrafUres() {
     int i,j;

     for (i=1; i<=10; i++) {
         for (j=1; j<=10; j++) {
             ge[i][j]=NEM;
         }
     }
}
void alapGraf::Osszekot (PontTip p, PontTip q) {
     ge[p][q]=IGEN;
     ge[q][p]=IGEN; // visszafele is lehet menni
}
void alapGraf::Elszakit (PontTip p, PontTip q) {
     ge[p][q]=NEM;
}
logikai alapGraf::vanEl (PontTip p, PontTip q) {
        return ge[p][q];
}
int alapGraf::SzomszedPontokSzama(PontTip p) {
    int db;
    PontTip i;
    db=0;
    for (i=1; i<=10; i++) {
        if (ge[p][i]==IGEN) {db++;}
    }
    return db;
}
PontTip alapGraf::SzomszedPont(PontTip p, int i) {
    logikai megvan;
    PontTip j,k;
    megvan=NEM;
    j=0; k=0;
    while (megvan==NEM) {
          j++;
          if (ge[p][j]==IGEN) {k++;}
          if (k==i) {megvan=IGEN;}
    }
    return j;
}
grafEl alapGraf::grafBeolvas() {
     logikai joszam;
     int innen, ide;
     grafEl eredmeny;
     cout << "Graf adatainak beolvas�sa. \n";
     joszam=IGEN;
     while (joszam==IGEN) {
           cout<<"El kiindulo pontja (1-10)?";
           cin>>innen;
           cout<<"\n";
           if (innen>10)
            {
              cout<<"HIBAS ADAT! (Csak 10 pont van!) \n";
              joszam=IGEN;
            } else {
              joszam=NEM;
            }
     }

     joszam=IGEN;
     while (joszam==IGEN) {
           cout<<"Kivalasztott kezdopont: "; cout<<innen; cout<<"\n";
           cout<<"El vegpontja (1-10)?";
           cin>>ide;
           cout<<"\n";
           if (ide>10)
           {
              cout<<"HIBAS ADAT! (Csak 10 pont van!) \n";
              joszam=IGEN;
           } else {
             joszam=NEM;
           }

     }
     eredmeny.kezd=innen;
     eredmeny.veg=ide;

     return eredmeny;
}

void menu () {
    cout<<"- SZELESSEGI BEJARAS CSUCSMATRIX GRAFBAN -  \n\n";
    cout<<"1) Csucsmatrix megjelenitese. \n";
    cout<<"2) Grafelek bevitele. \n";
    cout<<"3) Proba adatok betoltese. \n";
    cout<<"4) Feszitofa megadasa. \n";
    cout<<"5) Segitseg. \n";
    cout<<"6) Pontot mindennel osszekot. \n";
    cout<<"7) Kilepes. \n\n";
}

void segitseg () {
     cout<<"\n- SEGITSEG -  \n\n";
     cout<<"Ennek a programnak az a feladata, hogy egy \n";
     cout<<"csucsmatrix-szal abzazolt grafnak adja meg\n";
     cout<<"egy feszitofajat szelessegi bejaras alapjan.\n";
     cout<<"A program kezelesi a kezdeti menupontok alapjan.\n\n";
}

int menuPontBeker(int min, int max) {
    // Bek�r egy 'min' �s 'max' k�z�tti sz�mot, majd visszaadja
    logikai helyesValasz;
    helyesValasz=NEM;
    int valaszom;
    valaszom=0;
    while (helyesValasz==NEM) {
            cout<<"\n Valasszon ("<<min<<"-"<<max<<"), majd <ENTER>!";
            cin>>valaszom;
            if (valaszom<min) {
                helyesValasz=NEM;
            } else {
                if (valaszom<=max) {
                    helyesValasz=IGEN;
                }
            }
            if (valaszom>max) {
                helyesValasz=NEM;
            }
            if (helyesValasz==NEM)
            {
                cout<<"\n HIBAS valasztas! ("<<min<<" es " <<max<<" kozott valasszon!)\n";
            }
    }
    return valaszom;
}

void eredmenyKiir(bejarasEredmeny eredmeny) {
     int i;
     cout<<"A megtalalt feszitofa:\n";
     i=1;
     while (i<=eredmeny.pontSzam) {
           cout<<eredmeny.sorozat[i]<<" ";
           i++;
     }
}

int main () {
  int funkcio, kezdes, pontokSzama, i, maxFeszitofa, maxFeszitofaIndex, extraPont;
  bejarasEredmeny eredmeny;
  grafEl aktualEl;
  bejaras helyigraf;
  alapGraf alap;
  helyigraf.GrafUres();
  funkcio=0;
  cout<<"\nUdvozoljuk a fesztitofa kereso programban!";
  cout<<"\nKesztette: Kiss Endre Farkas (KIELAAT.elte)";
  while (funkcio<7) {
        system("PAUSE");cout<<"\n";
        menu();
        funkcio=menuPontBeker(1,7);
        switch (funkcio)
        {
         case 1:
              helyigraf.csucsmatrixRajzol(); break;
         case 2:
              aktualEl=helyigraf.grafBeolvas();
              helyigraf.Osszekot(aktualEl.kezd, aktualEl.veg);
              cout<<"Grafel sikeresen rogzitve. \n\n";
         break;
         case 3: helyigraf.probaAdatok(); break;
         case 4:
                 cout<<"\nFeszitofa szelessegi bejarassal:\n\n";
                 kezdes=helyigraf.minimumPont(); //A legkisebb, �llel rendelkez� pont
                 if (kezdes==11) {
                   cout<<"Nincsenek elek a grafban.\n";
                   cout<<"Igy nem kesztitheto feszitofa.\n\n";
                 } else {
                   pontokSzama=helyigraf.pontSzam();

                   // Minden kezdponttal megpr�b�lunk gener�lni fesz�t�f�t
                   maxFeszitofa=0;
                   maxFeszitofaIndex=1;
                   for (i=1; i<=10; i++) {
                       eredmeny=helyigraf.szelessegiBejaras(i);
                       if (eredmeny.pontSzam>maxFeszitofa)
                       {
                          maxFeszitofa=eredmeny.pontSzam;
                          maxFeszitofaIndex=i;
                       }
                   }
                   // V�g�l a legt�bb pontot �rtint� eredm�nyt vessz�k alapul
                   eredmeny=helyigraf.szelessegiBejaras(maxFeszitofaIndex);
                   if (eredmeny.pontSzam==pontokSzama) {
                      eredmenyKiir(eredmeny);
                      cout<<"\n\nSikeres bejaras.\n\n";
                   } else {
                     cout<<"\nA grafban sajnos vannak izolalt pontok,\n";
                     cout<<"ezert nem lehet fesztifat megadni hozza.\n\n";
                   }
                 }
                 break;
         case 5: segitseg(); break;
         case 6:
              cout<<"\nA grafban minden pont torlese, majd.";
              cout<<"\negy pont osszekotese az osszes t�bbivel.";
              cout<<"\nMelyik ponttal vegezzem el a muveletet? (1-10)";
              extraPont=menuPontBeker(1,10);
              // Oper�tor tesztel�se
              helyigraf = helyigraf+extraPont;
              break;
         case 7: cout<<"Viszlat!\n"; break;
         default: break;
        }
  }
  return 0;
}