CSR и BFS всегда находят с 0 шагов - PullRequest
Новая
       55

CSR и BFS всегда находят с 0 шагов

2 голосов
/ 15 января 2020

Я пытаюсь создать программу, которая создает график в формате CSR (Compressed Sparse Rows) с двумя массивами, где один массив является смещением каждого узла, а второй - ребрами. Данные читаются из файла, и я использую словарь / карту для резервирования в памяти. Затем он запрашивает узел и ребро и, используя BFS-способ поиска графа, должен печатать, если путь существует. Однако, независимо от того, что я печатаю, программа всегда возвращает найденное, но не печатает, что оно существует, и шаги равны 0.

Файл выглядит так: 

737 6340
1740    1199
1738    1199
1738    1811
1738    2085
1739    1199
1741    214
1741    1199
1741    1419
1741    1496
1741    1723

Программа выглядит следующим образом: 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct{
  int* num;
  int size;
  int top;

} stack;


int nodesdoublesize(int** array,int n){
  int* new_array=malloc(n*2*sizeof(int));
  if(new_array==NULL){
    printf("Error allocating memory\n");
    abort();
  }
  n*=2;
  for(int i=0;i<n;i++){
    new_array[i]=(*array)[i];
  }
  free(*array);
  *array=new_array;
  return n;
}
void stack_destroy(stack *s){
  free(s->num);
  free(s);
}




int hashcmp(const void *a,const void *b){
  return ( *(int*)a - *(int*)b );
}

int hashdoublesize(int** hash,int nodes){
    int* new_array=malloc(nodes*2*sizeof(int));
    if(new_array==NULL){
        printf("Error allocating memory\n");
        abort();
    }

    for(int i=0;i<nodes;i++){
        new_array[i]=(*hash)[i];
    }
    nodes*=2;

    free(*hash);
    *hash=new_array;
    return nodes;
}

typedef struct {
    int start;
    int end;   
} path;






stack* stack_create(){  
  stack *s=malloc(sizeof(stack));
  if(s==NULL){
    printf("Error allocating memory for stack\n");
    abort();
  }
  s->top=0;
  s->size=10;
  s->num=malloc(s->size*sizeof(int));
  if(s->num==NULL){
    printf("Error allocating memory\n");
    abort();
  }
  return s;
}





int cmp(const void *a,const void *b){
    int l=((path*)a)->start;
    int r=((path*)b)->start;

    if(l>r)
        return 1;
    if(l<r)
        return -1;
    else
        return 0;
}

int doublesize(path** array,int n){
    path* new_array=malloc(n*2*sizeof(path));
    if(new_array==NULL){
        printf("Error allocating memory\n");
        abort();
    }

    for(int i=0;i<n;i++){
        new_array[i]=(*array)[i];
    }
    free(*array);
    *array=new_array;
    n*=2;
    return n;

}
int bfs(int* arraynodes,int* arrayedges,int n,int st,int end){
  stack *s=stack_create();
  int color[n];
  for(int i=0;i<n;i++){
    color[i]=-1;
  }
    color[st]=0;
  s->num[s->top]=st;
  while (s->top!=0){
    for (int i = arraynodes[st]; i < arraynodes[st+1];i++){
      if (color[i]==-1){
        color[i]=0;
        s->top++;
        s->num[s->top]=i;
        if(s->top==s->size){
         s->top=nodesdoublesize(&s->num,s->size);
        }
        if(s->num[s->top]==end){
          printf("Exists\n");
          return 0;
        }
      }
      s->top--;
    color[i]=1;

    }
  }
  return 1;
}







int main()
{
    int maxsize=10;
    int test;
    char buff[200];
    int counter=0;
    char c;
    int i;
    path* array=malloc(maxsize*sizeof(path));
    if(array==NULL) {
        printf("Error allocating memory\n");
        abort();
    }


    FILE* fd=fopen("Wiki-Vote.txt","r");
    if(fd==NULL) {
        printf("Error opening file\n");
        abort();
    }


  while(fgets(buff,200,fd)) {

        c=buff[0];
        if(c=='#') {
            continue;
        }
    sscanf(buff,"%d%d",&array[counter].start,&array[counter].end);
        counter++;
        if(counter==maxsize){
           maxsize=doublesize(&array,maxsize); 
    }

    }

  maxsize=counter;
    counter=0;
    qsort(&array[0],maxsize,sizeof(path),cmp);




  counter=1;
  int nodes=10;
  int* hash=malloc(nodes*sizeof(int));
  if(hash==NULL){
    printf("Error allocating memory\n");
    abort();
  }

for(i=0;i<maxsize;i++){
  if(hash[counter-1]==array[i].start)
    continue;
        hash[counter]=array[i].start;
        counter++;
        if(counter==nodes){
          nodes=hashdoublesize(&hash,nodes);
        }
}
int j;
for(i=0;i<maxsize;i++){
  for(j=0;j<counter;j++){
    if(hash[j]==array[i].end)
      break;
  }
  if(j!=counter)
    continue;
  hash[counter]=array[i].end;
  counter++;
  if(counter==nodes)
    nodes=hashdoublesize(&hash,nodes);
}

nodes=counter;
qsort(&hash[0],nodes,sizeof(int),hashcmp);


  int* arraynodes=malloc(nodes*sizeof(int));
  int* arrayedges=malloc(maxsize*sizeof(int));
  if(arraynodes==NULL||arrayedges==NULL){
    printf("Error allocating memory\n");
    abort();
  }
  int edge_count=maxsize;
  int edge_offset=0;
  for(int i=0;i<nodes;i++){
    int current_node=hash[i];
    arraynodes[i]=edge_offset;
    while(edge_offset<edge_count&& array[edge_offset].start == current_node){
      edge_offset++;
    }
  }
  for (int i = 0; i < edge_count; i++){
    arrayedges[i]=array[i].end;
  }








int x;
  printf("give number to search: "); 
  scanf("%d",&x);
  for(i=0;i<nodes;i++){
    if(x==hash[i]){
      printf("found \n");
      break;
    }
  }
  if(i==nodes){
    printf("not found \n");
    abort();
  }

/*  for(j=arraynodes[i];j<arraynodes[i+1];j++){
    printf("%d\n",arrayedges[j]);
  }*/

  int en=hash[i];
  int st;
  printf("From where would you like to start: ");
  scanf("%d",&st);
  printf("\n");
  int found;
  found=bfs(arraynodes,arrayedges,nodes,st,en);
  if(found){
    printf("Found\n");
  }
  else
    printf("Not found\n");







  free(arraynodes);
  free(arrayedges);
  free(hash);
    fclose(fd);
    free(array);
        return 0;
}

Спасибо за ваше время, и любая помощь будет оценена.

1 Ответ

1 голос
/ 15 января 2020

Ваша stack_doublesize функция очень неверна и может быть причиной ваших проблем, поскольку ее использование приведет к неопределенному поведению .

В настоящее время, как показано (когда я пишу этот ответ), он в основном перераспределяет одну stack структуру в массив 20 stack структур. Затем он будет обрабатывать одну исходную структуру stack как массив структуры 10 и скопировать эти 10 в новый массив. Это, конечно, будет go за пределами, поскольку у вас нет массива 10 структур, только одна структура.

Кроме того, вы не перераспределяете память, на которую указывает stack сама структура, элемент num останется прежним. Это означает, что вы также go выйдете за пределы этой памяти.

В качестве решения этих проблем я предлагаю вам изменить функции перераспределения на что-то вроде этого: 

// Reallocate a dynamically allocated array, doubling its size
int nodesdoublesize(int **array,int n)
{
    int* new_array = realloc(*array, n * 2 * sizeof *new_array);
    if (new_array == NULL)
    {
        fprintf(stderr, "Out of memory\n");
        abort();
    }

    *array = new_array;
    return n * 2;
}

// Reallocate the data of the stack
void stack_doublesize(stack *s)
{
    s->size = nodesdoublesize(&s->num, s->size);
}

Изменить ваш звонок stack_doublesize, чтобы следовать новой функции.

Возможно, в вашем коде больше ошибок и проблем, которых я не нашел. Я предлагаю вам начать с построения с включенными дополнительными предупреждениями (-Wall -Wextra -Wpedantic при использовании G CC или Clang и /W4 при использовании MSV C) и рассматривать все предупреждения как ошибки, которые необходимо исправить.

...