heurystyka (bez poszerzania)

#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 > sekwencja;     // 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] != '>')
        {
            sekwencja.push_back(line);
            jakosc.push_back(line2);
        }
    }
    plik.close();
    plik2.close();
}

void tworzenie_wierzcholkow()
{

    for(int i = 0; i < sekwencja.size(); i++)
    {
        string tmp = sekwencja[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);
			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())
                    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();
        }
}

/*

int expand_to_left()
{
    int to_left = 0;
    int tmp_poz = 1;
    vector < char > nucleotides;

    while(true)
    {
        for(int i=0; i<max_found_clique.size(); i++)
        {
            int tmp = max_found_clique[i];
            int id_seq = vertex_list[tmp].sequence_in;
            int position = vertex_list[tmp].poz;
            char nucleotide = sequence[id_seq][position-tmp_poz];
            nucleotides.push_back(nucleotide);
        }

        char tmp = nucleotides[0];
        for(int i=0 ; i<nucleotides.size(); i++)
        {
            if(tmp != nucleotides[i])
                return to_left;
        }

        to_left = tmp_poz;
        tmp_poz++;
        nucleotides.clear();
    }
}

int expand_to_right()
{
    int to_right = 0;
    int tmp_poz = 1;
    vector < char > nucleotides;

    while(true)
    {
        for(int i=0; i<max_found_clique.size(); i++)
        {
            int tmp = max_found_clique[i];
            int id_seq = vertex_list[tmp].sequence_in;
            int position = vertex_list[tmp].poz;
            position = position+vertex_list[tmp].vert.size();
            char nucleotide = sequence[id_seq][position+tmp_poz-1];
            nucleotides.push_back(nucleotide);
        }

        char tmp = nucleotides[0];
        for(int i=0 ; i<nucleotides.size(); i++)
        {
            if(tmp != nucleotides[i])
                return to_right;
        }

        to_right = tmp_poz;
        tmp_poz++;
        nucleotides.clear();
    }
}

*/


int main()
{


    cout << "Dlugosc okna (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 (wartosc ponizej ktorej nukleotyd moze ulegac delecji (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;

        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<<"sekwencja: "<<wierzcholki[tmp].nrsek<<" ";
                    cout<<"pozycja: "<<wierzcholki[tmp].pozycja<<endl;
                }
                cout<<endl;
            }
        }

        cout<<"\n\nNajwieksza znaleziona klika ma 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<<"numer sekwencji: "<<wierzcholki[tmp].nrsek<<" ";
            cout<<"na pozycji od: "<<wierzcholki[tmp].pozycja<<endl;
        }

        // poszerzamy w lewo i w prawo
    //    int pos_to_left = expand_to_left();
     //   int pos_to_right = expand_to_right();

    //    cout<<"\n\nMaksymalna klika po poszerzeniu: "<<endl<<endl;
    //    cout<<"Motyw: "<<endl;
    //    for(int i=0; i<max_found_clique.size(); i++)
    //    {
    //        int tmp = max_found_clique[i];
    //        string new_vert = sequence[vertex_list[tmp].sequence_in].substr((vertex_list[tmp].poz - pos_to_left),(pos_to_left + vertex_list[tmp].vert.size() + pos_to_right));
    //        cout<<new_vert<<" ";
    //        cout<<"numer sekwencji: "<<vertex_list[tmp].sequence_in<<" ";
    //        cout<<"na pozycji od: "<<vertex_list[tmp].poz - pos_to_left<<endl;
    //    }

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

return 0;
}