Count outgoing links in adjacency list graph representation in C

Question

I have a graph with adjacency list representation and want to find how many outgoing links each vertices has. I created a function to count nodes of linked list at a specific vertex, however, after calling count function, all nodes (edges) of this vertex are being removed from the graph (at least I'm not able to display them). How can I fix this?

Graph output of vertices and edges without calling count function:

Vertex 0: 3 -> 2 -> 1 -> 
Vertex 1: 4 -> 
Vertex 2: 6 -> 1 -> 5 -> 4 -> 
Vertex 3: 4 -> 5 -> 6 -> 0 -> 
Vertex 4: 6 -> 2 -> 1 -> 
Vertex 5: 0 -> 3 -> 2 -> 6 -> 4 -> 1 -> 
Vertex 6: 0 -> 3 -> 5 -> 2 -> 4 -> 1 ->

After counting number of edges for vertex 4:

Outgoing links: 3

Vertex 0: 3 -> 2 -> 1 -> 
Vertex 1: 4 -> 
Vertex 2: 6 -> 1 -> 5 -> 4 -> 
Vertex 3: 4 -> 5 -> 6 -> 0 -> 
Vertex 4: 
Vertex 5: 0 -> 3 -> 2 -> 6 -> 4 -> 1 -> 
Vertex 6: 0 -> 3 -> 5 -> 2 -> 4 -> 1 ->

Graph structure:

typedef struct graph {
    int numberV;
    int numberE;
    struct vertex **adjList;
} GraphT; 

typedef struct vertex {
    int vertex;
    struct vertex *next; 
} VertexT;

Code for counting:

int countLinks(GraphT *graph, int vertex) {
    int count = 0;
    GraphT *current = graph;
    while (current->adjList[vertex] != NULL) {
        count++;
        current->adjList[vertex] = current->adjList[vertex]->next;
    }
    return count; 
}

int main () {
    ...
    int c = countLinks(graph, 4); 
    printf("Outgoing links: %d\n", c); 
    ...
}

David Ranieri David Ranieri · Accepted Answer · 2021-01-23T09:06:10

all nodes (edges) of this vertex are being removed from the graph (at least I'm not able to display them)

That's because you are updating and setting the pointer to NULL at the very end:

int countLinks(GraphT *graph, int vertex) {
    int count = 0;
    GraphT *current = graph;
    while (current->adjList[vertex] != NULL) {
        count++;
        current->adjList[vertex] = current->adjList[vertex]->next; //here
    }
    return count; 
}

try

int countLinks(GraphT *graph, int vertex) {
    int count = 0;
    GraphT *current = graph;
    struct vertex *temp;

    temp = current->adjList[vertex];
    while (temp != NULL) {
        count++;
        temp = temp->next;
    }
    return count; 
}

Count outgoing links in adjacency list graph representation in C

1 Answers