Skip to content

Instantly share code, notes, and snippets.

@drenge

drenge/nussinov_parallel.c

Last active December 22, 2015 01:19
Show Gist options
  • Save drenge/6395472 to your computer and use it in GitHub Desktop.
Save drenge/6395472 to your computer and use it in GitHub Desktop.
Download ZIP
Nussinov
Raw
nussinov_parallel.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/time.h>
#include <pthread.h>
#include <errno.h>
#define MAX 1024
int delta (char x, char y)
{
if ((( x == 'A') && (y == 'U'))||(( x == 'G') && (y == 'C'))||(( x == 'C') && (y == 'G'))||(( x == 'U') && (y == 'A'))||(( x == 'a') && (y == 'u'))||(( x == 'g') && (y == 'c'))||(( x == 'c') && (y == 'g'))||(( x == 'u') && (y == 'a')))
return 1;
return 0;
}
typedef struct Pilha
{
int i;
int j;
struct Pilha *anterior;
} pilha;
pilha* pop(pilha *x)
{
pilha *y=x->anterior;
free(x);
return y;
}
pilha* push(int i,int j,pilha *z)
{
pilha *nova=malloc(sizeof(pilha));
nova->i=i;
nova->j=j;
nova->anterior=z;
return nova;
}
void parse(pilha *baseP,int L)
{
char* answer=malloc(sizeof(char)*L+1);
int i,j;
memset(answer,'.',L);
pilha *pointer;
while(baseP)
{
i=baseP->i;
j=baseP->j;
pointer=baseP;
baseP=baseP->anterior;
answer[i]='(';
answer[j]=')';
}
printf("\n\nResposta:\n->\n%s",answer);
}
void *nussinov(const void *string)
{
int gamma[MAX][MAX];
int i, j, k, d;
int L;
int max = -1000;
int aux;
pilha *stack;
pilha *baseP=NULL;
char *s;
s=(char *)string;
//char s[100] = "GUGUCCAA";
L = strlen (s);
/* inicialização */
for (i = 1; i < L; i++)
gamma[i][i - 1] = 0;
for (i = 0; i < L; i++)
gamma[i][i] = 0;
for (d = 1; d < L; d++)
{
for (i = 0; i < L - d; i++)
{
j = i + d;
max = gamma[i + 1][j];
if (gamma[i][j - 1] > max)
max = gamma[i][j - 1];
aux = gamma[i + 1][j - 1] + delta(s[i], s[j]);
if (aux > max)
max = aux;
for (k = i + 1; k < j; k++)
{
aux = gamma[i][k] + gamma[k+1][j];
if (aux > max)
max = aux;
}
gamma[i][j] = max;
}
}
/* recursão */
for (i = 0; i < L; i++)
{
for (j = 0; j < L; j++)
{
//#Debug -> printf ("%d ", gamma[i][j]);
}
//#Debug -> printf("\n");
}
//inicialização da pilha
stack=push(0,L-1,NULL);
i=stack->i;
j=stack->j;
//#Debug -> printf("\n0-PUSH[%d,%d]",0,L-1);
while((stack!=NULL)&&(i<j))
{
stack=pop(stack);
//#Debug -> printf("\n0-POP[%d,%d]",i,j);
if(gamma[i][j]==gamma[i+1][j])
{
stack=push(i+1,j,stack);
//#Debug -> printf("\n1-PUSH[%d,%d]",i+1,j);
//break;
}
if(gamma[i][j]==gamma[i][j-1])
{
stack=push(i,j-1,stack);
//#Debug -> printf("\n2-PUSH[%d,%d]",i,j-1);
//break;
}
for(k=i+1; k<=j-1; k++)
{
if((gamma[i][k]+gamma[k+1][j])==gamma[i][j])
{
stack=push(k+1,j,stack);
//#Debug -> printf("\n3-PUSH[%d,%d]",k+1,j);
stack=push(i,k,stack);
//#Debug -> printf("\n3-PUSH[%d,%d]",i,k);
}
}
aux=gamma[i+1][j-1];
d=delta(s[i],s[j]);
if(gamma[i][j]==(aux+d))
{
stack=push(i+1,j-1,stack);
//#Debug -> printf("\n4-PUSH[%d,%d]",i+1,j-1);
baseP=push(i,j,baseP);
//#Debug -> printf("\n4-PUSH_BaseP[%d,%d]",i,j);
}
i=stack->i;
j=stack->j;
}
parse(baseP,L);
return 0;
}
int main(void)
{
pthread_t nussinov_threads[MAX];
char *texto;
texto=malloc(sizeof(char)*MAX);
int index=0;
do
{
memset(texto,'\0',MAX);
scanf("%s",texto);
pthread_create(&nussinov_threads[index],NULL,nussinov,texto);
}
while(!feof(stdin));
for(int j;j<=index; j++)
{
pthread_join(nussinov_threads[j],NULL);
}
pthread_exit(0);
return 0;
}
Raw
nussinov_sequential.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/time.h>
#include <pthread.h>
#include <errno.h>
#define MAX 1024
int delta (char x, char y)
{
if ((( x == 'A') && (y == 'U'))||(( x == 'G') && (y == 'C'))||(( x == 'C') && (y == 'G'))||(( x == 'U') && (y == 'A'))||(( x == 'a') && (y == 'u'))||(( x == 'g') && (y == 'c'))||(( x == 'c') && (y == 'g'))||(( x == 'u') && (y == 'a')))
return 1;
return 0;
}
typedef struct Pilha
{
int i;
int j;
struct Pilha *anterior;
} pilha;
pilha* pop(pilha *x)
{
pilha *y=x->anterior;
free(x);
return y;
}
pilha* push(int i,int j,pilha *z)
{
pilha *nova=malloc(sizeof(pilha));
nova->i=i;
nova->j=j;
nova->anterior=z;
return nova;
}
void parse(pilha *baseP,int L)
{
char* answer=malloc(sizeof(char)*L+1);
int i,j;
memset(answer,'.',L);
pilha *pointer;
while(baseP)
{
i=baseP->i;
j=baseP->j;
pointer=baseP;
baseP=baseP->anterior;
answer[i]='(';
answer[j]=')';
}
printf("\n\nResposta:\n->\n%s",answer);
}
void *nussinov(const void *string)
{
int gamma[MAX][MAX];
int i, j, k, d;
int L;
int max = -1000;
int aux;
pilha *stack;
pilha *baseP=NULL;
char *s;
s=(char *)string;
//char s[100] = "GUGUCCAA";
L = strlen (s);
/* inicialização */
for (i = 1; i < L; i++)
gamma[i][i - 1] = 0;
for (i = 0; i < L; i++)
gamma[i][i] = 0;
for (d = 1; d < L; d++)
{
for (i = 0; i < L - d; i++)
{
j = i + d;
max = gamma[i + 1][j];
if (gamma[i][j - 1] > max)
max = gamma[i][j - 1];
aux = gamma[i + 1][j - 1] + delta(s[i], s[j]);
if (aux > max)
max = aux;
for (k = i + 1; k < j; k++)
{
aux = gamma[i][k] + gamma[k+1][j];
if (aux > max)
max = aux;
}
gamma[i][j] = max;
}
}
/* recursão */
for (i = 0; i < L; i++)
{
for (j = 0; j < L; j++)
{
//#Debug -> printf ("%d ", gamma[i][j]);
}
//#Debug -> printf("\n");
}
//inicialização da pilha
stack=push(0,L-1,NULL);
i=stack->i;
j=stack->j;
//#Debug -> printf("\n0-PUSH[%d,%d]",0,L-1);
while((stack!=NULL)&&(i<j))
{
stack=pop(stack);
//#Debug -> printf("\n0-POP[%d,%d]",i,j);
if(gamma[i][j]==gamma[i+1][j])
{
stack=push(i+1,j,stack);
//#Debug -> printf("\n1-PUSH[%d,%d]",i+1,j);
//break;
}
if(gamma[i][j]==gamma[i][j-1])
{
stack=push(i,j-1,stack);
//#Debug -> printf("\n2-PUSH[%d,%d]",i,j-1);
//break;
}
for(k=i+1; k<=j-1; k++)
{
if((gamma[i][k]+gamma[k+1][j])==gamma[i][j])
{
stack=push(k+1,j,stack);
//#Debug -> printf("\n3-PUSH[%d,%d]",k+1,j);
stack=push(i,k,stack);
//#Debug -> printf("\n3-PUSH[%d,%d]",i,k);
}
}
aux=gamma[i+1][j-1];
d=delta(s[i],s[j]);
if(gamma[i][j]==(aux+d))
{
stack=push(i+1,j-1,stack);
//#Debug -> printf("\n4-PUSH[%d,%d]",i+1,j-1);
baseP=push(i,j,baseP);
//#Debug -> printf("\n4-PUSH_BaseP[%d,%d]",i,j);
}
i=stack->i;
j=stack->j;
}
parse(baseP,L);
return 0;
}
int main(void)
{
pthread_t nussinov_threads[MAX];
char *texto;
texto=malloc(sizeof(char)*MAX);
int index=0;
do
{
memset(texto,'\0',MAX);
scanf("%s",texto);
pthread_create(&nussinov_threads[index],NULL,nussinov,texto);
}
while(!feof(stdin));
for(int j;j<=index; j++)
{
pthread_join(nussinov_threads[j],NULL);
}
pthread_exit(0);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment