I am trying to make a serial code for Kahn's Algorithm in C. The pseudocode I based it on is the following:

```
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)
```

My code reads a .mtx file that shows the adjacency of the nodes in the graph and it is this one:

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

I use an int array called **indegree** 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. The value indegree[i] is incremented by one whenever i is read as the second number in each line in the file. That signifies that there is an edge pointing to node i.
Here is my code:

```
#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);
}
```

**Now, the problem.** When I run my file (Compiler is gcc), the result I get is this one:

```
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
```

Now first weird thing is that eventhough node 11 is read, node 12 is printed in the 'Node: x with indegree value: x' message. In some nodes these weird numbers keep getting printed as the values of indegree.. But for nodes 8 and 9 this works fine?!

Any help would be appreciated!