Проблема с внутренними градусами в реализации алгоритма Кана в c

Question

Я пытаюсь создать серийный код для алгоритма Кана в C. Псевдокод, на котором я его основываю, следующий:

S ← Set of all nodes with no incoming edge 

while S is non-empty do     
    remove a node n from S     
    add n to tail of L
    for each node m with an edge e from n to m do
         remove edge e from the graph
         if m has no other incoming edges then
             insert m into S 

if graph has edges then
    return error   (graph has at least one cycle) 
else      
    return L       (a topologically sorted order)

Мой код читает файл .mtx, который показывает смежность узлов в графе, и это:

7 11
7 8
3 8
11 2
11 9
11 10
8 9
3 10

Я использую массив int с именем indegree , который содержит внутренние градусы для каждого узла i. Например, если узел 5 имеет внутреннее значение 3, тогда: indegree [5] = 3. Значение indegree [i] увеличивается на единицу всякий раз, когда i читается как второе число в каждой строке файла. Это означает, что есть край, указывающий на узел i. Вот мой код:

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

//struct for queues L and S
struct Queue
{
    int front, rear, size;
    unsigned capacity;
    int* array;
};

struct Queue* createQueue(unsigned capacity)
{
    struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));
    queue->capacity = capacity;
    queue->front = queue->size = 0;  
    queue->rear = capacity - 1;  
    queue->array = (int*) malloc(queue->capacity * sizeof(int));
    return queue;
}

int isFull(struct Queue* queue)
{  return (queue->size == queue->capacity);  }

int isEmpty(struct Queue* queue)
{  return (queue->size == 0); }


//inserting element
void enqueue(struct Queue* queue, int item)
{
    if (isFull(queue))
        return;
    queue->rear = (queue->rear + 1)%queue->capacity;
    queue->array[queue->rear] = item;
    queue->size = queue->size + 1;
    printf("%d enqueued to queue\n", item);
}

//dequeueing element
int dequeue(struct Queue* queue)
{
    if (isEmpty(queue))
        return -1;
    int item = queue->array[queue->front];
    queue->front = (queue->front + 1)%queue->capacity;
    queue->size = queue->size - 1;
    return item;
}

//print queue
void print_queue(struct Queue* queue)
{
    int j;

    for(j=queue->front; j < queue->rear; j++)
{
printf("I put this number: %d in list L", queue->array[j]);
printf("\n");
}
}

int main()

{
FILE *fp; //filestream
int K,j,i,k;
int N=7;
char line[50];

fp = fopen("/home/konst/Documents/Project_Parallel/ibm32.mtx", "r");

//array that holds the in-degrees for each node i. For example if node 5 has an in-degree value of 3 then: indegree[5]=3
int indegree[N];

//when in .mtx file, it reads only the second number in each line, in this case i, and increases by one the value of indegree[i] (since there is an edge from node j to node i)
while(fgets(line,50,fp)!=NULL)  
    {  
sscanf(line, "%*d %d", &i);
printf("%d\n" , i);  //I inserted this print to check if the .mtx file is read correctly(it is!)
indegree[i] ++;
printf("Node : %d with indegree value: %d\n",i,indegree[i]);  //I inserted this print to check the indegree value that is incremented in each iteration 
    }


struct Queue* L = createQueue(N);  //N number of nodes
struct Queue* S = createQueue(N);  //N number of nodes

for (i=0; i<N; i++)
{

 if (indegree[i] == 0) //if this is true then node i doesnt have any incoming edges therefore I enqueue it in S
 {
printf("I found a value that has indegree[%d]=0 and put it in S queue\n", i);
enqueue(S, i);
 }

}

while (isEmpty(S) != 0) 
{
i = dequeue(S); 
enqueue(L,i);

while(fgets(line,50,fp)!=NULL)  
{  

sscanf(line, "%d%d",&j, &k); 
if (j == i)
{
indegree[k]--; 
break; 
}
}
if (indegree[k] == 0) 
enqueue(S,k);


}

if (isFull(L) !=0)
{
return -1; 
}
else
{
print_queue(L); 
}

fclose(fp);

}

Теперь проблема. Когда я запускаю свой файл (компилятор - g cc), я получаю следующий результат:

11
Node : 12 with indegree value: -1
11
Node : 12 with indegree value: -1
8
Node : 8 with indegree value: 1
8
Node : 8 with indegree value: 2
2
Node : 2 with indegree value: 482383745
9
Node : 9 with indegree value: 1
10
Node : 10 with indegree value: -908997711
9
Node : 9 with indegree value: 2
10
Node : 10 with indegree value: -908997710
-1 enqueued to queue
-1 enqueued to queue
-1 enqueued to queue
-1 enqueued to queue
-1 enqueued to queue
-1 enqueued to queue
-1 enqueued to queue

Теперь первая странность заключается в том, что хотя узел 11 читается, узел 12 печатается в сообщении «Узел: x со значением степени: x». В некоторых узлах эти странные числа продолжают печататься как значения степени ... Но для узлов 8 и 9 это работает нормально?!

Любая помощь будет принята с благодарностью!

Answer 1

Во-первых, сделайте отступ в коде.

Во-вторых, вам нужно инициализировать значения indegree. Вот почему некоторые градусы, которые вы печатаете, НЕОБХОДИМЫ.

В-третьих, ваш N слишком мал. Вы устанавливаете его на 7, но в примере .mtx файл вы go вплоть до 11. Для этого файла вам потребуется N равным 12.

В-четвертых, если предоставленный вами вывод - это все, что выводила программа, то вы не читаете файл .mtx, поскольку вы печатаете строку для каждого строка, которую вы читаете.

В-пятых, почему вы нарушаете l oop здесь:

if (j == i)
{
indegree[k]--; 
break; 
}

Это будет означать, что вы никогда не добавляете в очередь более одного узла за раз . Имеет ли это смысл?

В-шестых, у вас, мягко говоря, отсутствует реализация. Вы просматриваете список смежности на каждой итерации l oop. Это дает нам наихудший случай O(N^3), когда алгоритм Кана на самом деле линейен.

В-седьмых, я думаю, что первая строка в .mtx отделена от остальных. Я думаю, это говорит о том, что в графе 7 концов и 11 узлов. Вы, однако, относитесь к этому как к описанию края. Если мое предположение верно, то эту информацию можно использовать для динамического определения N вместо жесткого кодирования, как это делаете вы. Затем вы должны установить N как второе число в первой строке.

В-восьмых, вам нужно сбросить указатель файла. Поэтому, когда вы снова попытаетесь прочитать файл, ничего не произойдет. Я также рекомендую не читать файл несколько раз. Скорее сохраняйте значения в массиве.

В-девятых, приятно видеть, что вы вызываете fclose в конце, но если ваш график включает цикл, вы возвращаете -1 и не вызываете fclose .

Относительно комментария ниже:

Чтобы прояснить четвертый пункт, если это все, что выводит ваша программа, то

11
Node : 12 with indegree value: -1
11
Node : 12 with indegree value: -1
8
Node : 8 with indegree value: 1
8
Node : 8 with indegree value: 2
2
Node : 2 with indegree value: 482383745
9
Node : 9 with indegree value: 1
10
Node : 10 with indegree value: -908997711
9
Node : 9 with indegree value: 2
10
Node : 10 with indegree value: -908997710
-1 enqueued to queue
-1 enqueued to queue
-1 enqueued to queue
-1 enqueued to queue
-1 enqueued to queue
-1 enqueued to queue
-1 enqueued to queue

тогда это l oop никогда не запускается:

while(fgets(line,50,fp)!=NULL)  
    {  
sscanf(line, "%*d %d", &i);
printf("%d\n" , i);  //I inserted this print to check if the .mtx file is read correctly(it is!)
indegree[i] ++;
printf("Node : %d with indegree value: %d\n",i,indegree[i]);  //I inserted this print to check the indegree value that is incremented in each iteration 
    }

Я бы просто инициализировал indegree с помощью for-l oop.

Что касается N, вам нужно, чтобы он был по крайней мере, на единицу больше, чем имя самого большого узла во входных данных. Если некоторые узлы не появляются в файле, как в приведенном вами примере, они по-прежнему являются частью вашего графика, и их не следует (как правило) игнорировать. Если вы реализуете, например, алгоритм поиска по графу Дейкстры, вы можете игнорировать эти узлы, но для Кана вам нужно поместить их где-нибудь в вашем топологическом порядке (их расположение, однако, не имеет значения). Если бы вы игнорировали изолированные узлы, вам пришлось бы делать это осторожно. Если вы сделаете это так, как вы это сделаете, вы укажете за пределы indegree, поскольку он имеет размер 7, но некоторые узлы больше этого. Вам нужно будет сопоставить их значения с 0, 1, ..., 6, чтобы поместиться в массив. Это несложно и может быть выполнено путем сортировки (логарифмически линейное время) или с помощью карты ha sh (линейное время). Для повторной передачи это не идеальный вариант в алгоритме Кана, потому что вам нужно учитывать расположение всех узлов в топологическом порядке, поэтому просто введите N = 12 и игнорируйте узел 0. Вы также можете установить N = 11 и уменьшить все значения в файле .mtx.