heurystyka najnowsza

#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <string>
#include <fstream>
#include <vector>
#include <sstream>
#include <algorithm>
#include <iterator>
#include <cstring>

using namespace std;

vector < string > sekwencje;     // vektor zawierajacy sekwencje
vector < string > jakosc;      // vektor zawierajacy oceny jakosci sekwencjonowania

class wierzcholek                    // klasa wierzcholek
{
public:
    string sekwierzch;                // nazwa wierzcholka
    int nrsek;            // sekwencja zrodlowa od 0 do 7
    int pozycja;                    // pozycja w sekwencji
    vector < int > jakosc_w;        // vektor jakosci sekwencjonowania
};

vector < wierzcholek > wierzcholki;          // vektor wszystkich wierzcholkow
vector < int > stopnie;          // vektor przechowujacy stopien kazdego wierzcholka
vector < vector < int > > macierz;      // macierz incydencji

vector < int > klika;            // znaleziona klika
vector < int > maxklika;        // najwieksza znaleziona do tej pory klika
vector <vector < int > > wektor_kliki;     // lista w ktorej znajduje sie kazda znaleziona klika

int okno,wiarygodnosc;                 // wartosci pobierane od uzytkownika



void show()
{
    /*
    for(int i=0; i<vertex_list.size(); i++)
    {
        cout<<vertex_list[i].vert<<" ";
        cout<<vertex_list[i].sequence_in<<endl;
        for(int j=0; j<window; j++)
            cout<<vertex_list[i].qual[j]<<" ";
    }
    cout<<endl<<endl;
    */
}

vector < string > split( char * napis)      // dzieli string na czesci
{
    const char * ograniczniki = " ";
    vector < string > podzielony_napis;

    for( char * pch = strtok( napis, ograniczniki ); pch != NULL; pch = strtok( NULL, ograniczniki ) )
         podzielony_napis.push_back( pch );

    return podzielony_napis;
}

void wczytaj_plik()         // funkcja wczytuje dane z plikow do dwoch vektorow, sequence i quality
{
    string line = "";
    string line2 = "";
    fstream plik;
    fstream plik2;

    plik.open("sample1.fasta");
    plik2.open("sample1.qual");

    while(getline(plik,line) && getline(plik2,line2))
    {
        if(line[0] != '>' && line2[0] != '>')
        {
            sekwencje.push_back(line);
            jakosc.push_back(line2);
        }
    }
    plik.close();
    plik2.close();
}

void tworzenie_wierzcholkow()
{

    for(int i = 0; i < sekwencje.size(); i++)
    {
        string tmp = sekwencje[i];
        char str [1024];
        char *p = str;
        strcpy(str, jakosc[i].c_str());
        vector < string > tmp2 = split(p);

        for(int j=0; j<(tmp.length() - okno + 1); j++)
        {
            wierzcholek *nowy = new wierzcholek();
            nowy->sekwierzch = tmp.substr(j,okno);
            nowy->nrsek = i;
            nowy->pozycja = j;

            for(int y=j; y<(okno+j); y++)
            {
                int var = atoi( tmp2[y].c_str() );
                nowy->jakosc_w.push_back(var);
            }
            wierzcholki.push_back(*nowy);
        }
    }

    macierz.resize(wierzcholki.size());
    for(int i=0; i<macierz.size(); i++)      // wypelniamy macierz zerami
        for(int j=0; j<macierz.size(); j++)
            macierz[i].push_back(0);
}

void polacz()
{
    int delmax;
    if(okno == 4)
        delmax = 1;
    if(okno == 5)
        delmax = 1;
    if(okno == 6)
        delmax = 2;
    if(okno == 7)
        delmax = 2;

    for(int i=0; i<wierzcholki.size(); i++)
        for(int j=i+1; j<wierzcholki.size(); j++)
        {
            if(wierzcholki[i].sekwierzch == wierzcholki[j].sekwierzch && wierzcholki[i].nrsek != wierzcholki[j].nrsek)
            {
                macierz[i][j] = 1;
                macierz[j][i] = 1;
            }
            else
            {
                if(wierzcholki[i].nrsek != wierzcholki[j].nrsek)
                {
                    // zakladamy ze delecja
                    macierz[i][j] = 1;
                    macierz[j][i] = 1;

                    int tmp = 0;
                    for(int y=0; y<okno; y++)
                    {
                        tmp++;
                        if(wierzcholki[i].sekwierzch[y] != wierzcholki[j].sekwierzch[y]) // dla nukleotydu ktory sie nie zgadza
                        {
                            if(wierzcholki[i].jakosc_w[y] > wiarygodnosc || wierzcholki[j].jakosc_w[y] > wiarygodnosc )
                            {
                                macierz[i][j] = 0;
                                macierz[j][i] = 0;
                            }
                            if(tmp > delmax)
                            {
                                macierz[i][j] = 0;
                                macierz[j][i] = 0;
                            }
                        }
                    }
                }
            }
        }
}

void stopnie_w()                       // oblicza stopnie kazdego wierzcholka
{
    for(int i=0; i<wierzcholki.size(); i++)
       stopnie.push_back(0);

    for(int i=0; i<wierzcholki.size(); i++)
        for(int j=0; j<wierzcholki.size(); j++)
            if(macierz[i][j]==1)
                stopnie[i]++;

 //   for(int i=0; i<wierzcholki.size(); i++)
 //       cout<<stopnie[i]<<" ";
}

vector <int> znajdz_sasiadow(int wierzch_index)        // znajduje sasiadow danego wierzcholka i zwraca ich vektor
{
    vector <int> sasiedzi;
    for(int i = 0; i < wierzcholki.size(); i++)
    {
        if(macierz[wierzch_index][i] == 1)
            sasiedzi.push_back(i);
    }
    return sasiedzi;
}


int wierzcholek_o_naj_st(vector<int> sasiedzi) // znajduje wierzcholek o najwyzszym stopniu
{
    int naj_st_w;
    int st = 0;

    for (int i = 0; i <sasiedzi.size(); i++)
    {
        int tmp_index = sasiedzi[i];
        if(stopnie[tmp_index] > st)
        {
            st = stopnie[tmp_index];
            naj_st_w = tmp_index;
        }
    }
    return naj_st_w;
}

vector <int> sasiedzi_wierzch_o_najst(int wierzch_index, int st)
{
    vector <int> sasiedzi_wierzch_o_najst;

    for(int i = 0; i < wierzcholki.size(); i++)
    {
        if(macierz[wierzch_index][i] == 1 && stopnie[i] >= st)
        {
            sasiedzi_wierzch_o_najst.push_back(i);
        }
    }
    return sasiedzi_wierzch_o_najst;
}

vector <int> znajdz_wspolnych_sasiadow(vector <int> _wybrani_sasiedzi, vector <int> _sasiedzi_wierzch_o_najst) // zwraca czesc wspolna
{
    vector <int> wspolni_sasiedzi;
    set_intersection(_wybrani_sasiedzi.begin(),_wybrani_sasiedzi.end(), _sasiedzi_wierzch_o_najst.begin(), _sasiedzi_wierzch_o_najst.end(), back_inserter(wspolni_sasiedzi));

    return wspolni_sasiedzi;
}

vector <int> &clique_heu(vector <int> &mozliwe_do_kliki, vector<int> &sasiedzi, int size, int &max)
	{
		if(sasiedzi.empty()) // warunek zakonczenia rekurencji
		{
			if(size > max)
                max = size;

            return mozliwe_do_kliki;
		}
		int wierzcholek_o_najst = wierzcholek_o_naj_st(sasiedzi); // znajdujemy sasiada o najwiekszym stopniu
		mozliwe_do_kliki.push_back(wierzcholek_o_najst); // dodajemy go do kliki

		for (int i = 0; i < sasiedzi.size(); i++) // znajdujemy i usuwamy go z vektora sąsiadow
		{
			if(sasiedzi[i] == wierzcholek_o_najst)
				sasiedzi.erase(sasiedzi.begin() + i);
		}

		vector <int> wierzch_o_najst_sasiedzi = sasiedzi_wierzch_o_najst(wierzcholek_o_najst, max);
		vector <int> wspolni_sasiedzi = znajdz_wspolnych_sasiadow(sasiedzi, wierzch_o_najst_sasiedzi);

        clique_heu(mozliwe_do_kliki, wspolni_sasiedzi, size + 1, max);

		return mozliwe_do_kliki;
	}

void max_clique(int max)
{
		vector <int> mozliwe_do_kliki; // wektor wierzcholkow bedacych kandydatami do wyszukania kliki

		for (int i = 0; i < wierzcholki.size(); i++) // dla kazdego wierzcholka w grafie
		{
			mozliwe_do_kliki.push_back(i);//dodajemy wierzcholek
			if(stopnie[i] >= max) // jesli stopien wiekszy lub rowny od najwiekszej znalezionej do tej pory kliki
			{
				vector<int> sasiedzi = znajdz_sasiadow(i); // szuka sasiadow badanego wierzcholka i dodaje ich do vektora
                vector<int> wybrani_sasiedzi;

                for (int j = 0; j < sasiedzi.size(); j++) // dla kazdego sasiada wierzcholka i
				{
                    int tmp_index = sasiedzi[j];

					if(stopnie[tmp_index] >= max) // jesli stopien sasiada wiekszy lub rowny od najwiekszej znalezionej kliki
                    {
                        wybrani_sasiedzi.push_back(tmp_index);
                    }
				}
				if(!wybrani_sasiedzi.empty()) //jesli wektor nie jest pusty
                    klika = clique_heu(mozliwe_do_kliki, wybrani_sasiedzi, 1, max);

				if(klika.size() >= maxklika.size())
                {
                    //wektor_kliki.push_back(klika);
                    maxklika = klika;
                }
			}
			mozliwe_do_kliki.clear();
        }
}

void lewo(vector<int> &lewa)
{

    for(int i = 0; i < lewa.size(); i++)
        {
        if(lewa[i] <= 0) // nie moze, bo jesli wierzcholek zerowy to nie mozna przejscdalej w lewo
        {
            return;
        }
    }

    for (int i = 0; i < lewa.size(); i++)
    {
        for (int j = i + 1; j < lewa.size(); j++)
        {
            if(macierz[lewa[i] - 1][lewa[j] - 1] != 1)
            {
                return;
            }
        }
    }

    for(int i = 0; i < lewa.size(); i++){
        lewa[i]--;
    }

    lewo(lewa);

    return;

}






void prawo(vector<int> &prawa)
{

    for(int i = 0; i < prawa.size(); i++)
        {
            if(prawa[i] >= macierz.size() - 2) //nie mozna poszerzyc, bo ktorys z wierzcholkow jest tym ostatnim
            {
                return;
            }
        }


    for(int i = 0; i < prawa.size(); i++)
        {
            for(int j = i + 1; j < prawa.size(); j++)
            {
                if(macierz[prawa[i] + 1][prawa[j] + 1] != 1)
                {
                    return;
                }
            }
        }

    for(int i = 0; i < prawa.size(); i++)
        {
        prawa[i]++;
        }

    prawo(prawa);

    return;

}






void rozszerz()
{

    vector<int> lewa = maxklika;
    vector<int> prawa = maxklika;

    lewo(lewa);
    prawo(prawa);

  /*  show_c(left_clique);
    show_c(right_clique);*/

    cout<<endl;
    cout<<"Motyw: "<<endl;
    for(int i=0; i< maxklika.size(); i++){
        int start = wierzcholki[lewa[i]].pozycja+1;
        int length = (wierzcholki[prawa[i]].pozycja+okno)-wierzcholki[lewa[i]].pozycja;
        int seq_number = wierzcholki[maxklika[i]].nrsek;

        for(int j=0; j<sekwencje.size(); j++)
            {
            if(j == seq_number)
                {
                //cout << "nr sekwencji: " << j << " na pozycji " << start << "-" << start+length << " znaleziono motyw po rozszerzeniu: " << endl;
                for(int g=0; g<length; g++){
                    cout << sekwencje[j][start+g];
                }
                //cout << "nr sekwencji: " << j << "pozycja " << start << "-" << start+length << " znaleziono motyw po rozszerzeniu: " << endl;
                cout <<" nr sekwencji: "<< j<<" pozycja: "<< start<< endl;

             //   cout << endl;
            }
        }
    }

}



//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////




int main()
{


    cout << "Okno (4-7): ";
    cin >> okno;
    while(1){
        if(okno < 4 || okno > 7){
            cout << "Wartosc nie nalezy do zakresu. Prosze podac prawidlowa wartosc: ";
            cin >> okno;
        }else{
            break;
        }
    }

    cout << "Wiarygodnosc (0-40): ";
    cin >> wiarygodnosc;

    while(1){
        if(wiarygodnosc > 40 || wiarygodnosc<0){
            cout << "Wartosc nie nalezy do zakresu. Prosze podac prawidlowa wartosc: ";
            cin >> wiarygodnosc;
        }else{
            break;
        }
    }

    cout<<endl;



    wczytaj_plik();
    tworzenie_wierzcholkow();
    polacz();
    stopnie_w();
   // show();
    max_clique(3);  // zmiana parametu na wiekszy, zmniejszy liczbe operacji!

    if(maxklika.size() == 0)
        cout<<"Nie znaleziono zadnej kliki"<<endl;

    // wyswietlanie
    else
    {
        //cout<<endl<<endl;
        //cout<<"Seria klik:"<<endl<<endl;
        cout<<"Maxklika: "<<endl;

        sort(wektor_kliki.begin(), wektor_kliki.end());
        for(int i=0; i<wektor_kliki.size(); i++) //clique_list.size()
        {
            if(wektor_kliki[i].size()>= 4)       // wyswietlamy kliki rozpiete conajmniej na czterech sekwencjach
            {
                cout<<wektor_kliki[i].size()<<":"<<endl;
                for(int j=0; j<wektor_kliki[i].size(); j++)
                {
                    int tmp = wektor_kliki[i][j];
                    cout<<wierzcholki[tmp].sekwierzch<<" ";
                    cout<<"nr sekwencji: "<<wierzcholki[tmp].nrsek<<" ";
                    cout<<"pozycja: "<<wierzcholki[tmp].pozycja<<endl;
                }
             //   cout<<endl;
            }
        }

        cout<<"Rozmiar: "<<maxklika.size()<<endl<<endl;
        cout<<"Motyw: "<<endl;
        for(int i=0; i<maxklika.size(); i++)
        {
            int tmp = maxklika[i];
            cout<<wierzcholki[tmp].sekwierzch<<" ";
            cout<<"nr sekwencji: "<<wierzcholki[tmp].nrsek<<" ";
            cout<<"pozycja: "<<wierzcholki[tmp].pozycja<<endl;
        }



sort(maxklika.begin(), maxklika.end());

   // vector<int> lewa = maxklika;
   // vector<int> prawa = maxklika;

    rozszerz();


    }

return 0;
}