4
\$\begingroup\$

I haven't yet implemented any sort of graph thus far in C and decided to give it a go by trying to implement an adjacency list in C. Is there anything in my code that you see that I can improve and is there any other sort of basic functionality that is missing in my adjacency list and should be added?

Graph.h

#ifndef GRAPH_H_INCLUDED
#define GRAPH_H_INCLUDED

typedef struct AdjListNode AdjListNode_t;
typedef struct AdjList AdjList_t;

typedef enum {UNDIRECTED = 0, DIRECTED} Edge_t;

typedef struct Graph
{
    Edge_t typeOfGraph;
    int totalVertices;
    int totalEdges;
    AdjList_t *adjListArr;
}Graph_t;

AdjListNode_t *createAdjacentNode(int);
Graph_t *createGraph(int, Edge_t);
void deleteGraph(Graph_t *);
void addEdge(Graph_t *, int, int);
int doesEdgeExist(Graph_t *, int, int);
int calculateNumOfEdges(int, Edge_t);
void displayGraph(Graph_t *);

#endif

Graph.c

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

struct AdjListNode
{
    int vertex;
    struct AdjListNode *next;
};

struct AdjList
{
    int totalMembers;
    struct AdjListNode *head;
};

AdjListNode_t *createAdjacentNode(int vertex)
{
    AdjListNode_t *newNode = (AdjListNode_t *)malloc(sizeof(AdjListNode_t));

    if(newNode == NULL)
    {
        return NULL;
    }

    newNode->vertex = vertex;
    newNode->next = NULL;

    return newNode;
}

Graph_t *createGraph(int totalVertices, Edge_t typeOfGraph)
{
    int i;

    Graph_t *graph = (Graph_t *)malloc(sizeof(Graph_t));

    if(graph == NULL)
    {
        return NULL;
    }

    graph->totalVertices = totalVertices;
    graph->totalEdges = 0;
    graph->typeOfGraph = typeOfGraph;

    graph->adjListArr = (AdjList_t *)malloc(totalVertices * sizeof(AdjList_t));

    if(graph->adjListArr == NULL)
    {
        free(graph);
        return NULL;
    }

    for(i = 0; i < totalVertices; i++)
    {
        graph->adjListArr[i].head = NULL;
        graph->adjListArr[i].totalMembers = 0;
    }

    return graph;
}

void deleteGraph(Graph_t *graph)
{
    if(graph != NULL)
    {
        if(graph->adjListArr != NULL)
        {
            int vertex;

            for(vertex = 0; vertex < graph->totalVertices; vertex++)
            {
                AdjListNode_t *listIterator = graph->adjListArr[vertex].head;

                while(listIterator != NULL)
                {
                    AdjListNode_t *temp = listIterator;
                    listIterator = listIterator->next;
                    free(temp);
                }
            }

            free(graph->adjListArr);
        }

        free(graph);
    }
}

void addEdge(Graph_t *graph, int src, int dest)
{
    if((src >= graph->totalVertices || src  < 0) || (dest >= graph->totalVertices || dest < 0))
        return;

    if(doesEdgeExist(graph, src, dest))
        return;

    AdjListNode_t *newNode = createAdjacentNode(dest);

    if(newNode != NULL)
    {
        newNode->next = graph->adjListArr[src].head;
        graph->adjListArr[src].head = newNode;
        graph->adjListArr[src].totalMembers++;
        graph->totalEdges++;

        if(graph->typeOfGraph == UNDIRECTED)
        {
            newNode = createAdjacentNode(src);

            if(newNode != NULL)
            {
                newNode->next = graph->adjListArr[dest].head;
                graph->adjListArr[dest].head = newNode;
                graph->adjListArr[dest].totalMembers++;
                graph->totalEdges++;
            }
        }
    }
}

int doesEdgeExist(Graph_t *graph, int src, int dest)
{
    AdjListNode_t *srcVertexPtr = graph->adjListArr[src].head;

    while(srcVertexPtr != NULL)
    {
        if(srcVertexPtr->vertex == dest)
        {
            return 1;
        }
        else
            srcVertexPtr = srcVertexPtr->next;
    }

    return 0;
}

int calculateNumOfEdges(int totalNumberOfEdges, Edge_t typeOfGraph)
{
    /*
        I'm assuming the graph has no self loops or multi-edges.
    */

    if(typeOfGraph == UNDIRECTED)
    {
        return totalNumberOfEdges / 2;
    }
    else
        return totalNumberOfEdges;
}

void displayGraph(Graph_t *graph)
{
    int vertex;

    for(vertex = 0; vertex < graph->totalVertices; vertex++)
    {
        AdjListNode_t *listIterator = graph->adjListArr[vertex].head;

        printf("Vertex %d is adjacent to ", vertex);

        while(listIterator != NULL)
        {
            printf("%d->", listIterator->vertex);
            listIterator = listIterator->next;
        }

        printf("NULL\n");
    }
}

Main.c

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

int main()
{
    Graph_t *uGraph = createGraph(5, UNDIRECTED);

    if(uGraph == NULL)
    {
        printf("Couldn't not allocate any memory. Terminating Program. ");
        exit(EXIT_FAILURE);
    }

    addEdge(uGraph, 0, 1);
    addEdge(uGraph, 0, 4);
    addEdge(uGraph, 0, 2);
    addEdge(uGraph, 1, 2);
    addEdge(uGraph, 1, 3);
    addEdge(uGraph, 1, 4);
    addEdge(uGraph, 2, 3);
    addEdge(uGraph, 3, 4);

    printf("Undirected Graph\n\n");
    displayGraph(uGraph);

    printf("\nThe total number edges in this graph is %d\n",
           calculateNumOfEdges(uGraph->totalEdges, uGraph->typeOfGraph));

    deleteGraph(uGraph);

    return 0;
}

Output

Adjacency List Output

\$\endgroup\$

1 Answer 1

Reset to default
4
\$\begingroup\$

General comments

Your code is pretty clean, but it's unclear what you imagine it being used for, except possibly just to illustrate adjacency lists. If you're looking to build something actually useful, then I suggest coming up with a few model applications, and thinking about what you need to provide to serve those applications efficiently and easily. For example, how would you model a shortest-path problem with your graph, and how would you implement Dijkstra's algorithm to solve that problem? Or how would you compute (and represent) a minimal spanning tree?

graph.h

As to specifics, I'll start with your API definition, as presented in the header file:

  • Graph_t.totalVertices and Graph_t.totalEdges cannot meaningfully take negative values, so you should consider declaring them to have unsigned types. If you do change these, however, then you'll need to propagate corresponding changes throughout.

  • Your function prototypes do not include parameter names. Although these are optional, including them makes the header easier to understand, and it may help the compiler produce more meaningful diagnostic messages.

  • You declare function createAdjacentNode(int), returning AdjListNode_t *. There's nothing inherently wrong with that, but AdjListNode_t is an opaque type, and you've no other function or other data type declared that uses AdjListNode_t, so what use does anyone who cannot see the definition of AdjListNode_t have for createAdjacentNode(int)? It looks like that function wants instead to have internal linkage in graph.c (and be omitted from the header).

  • public function calculateNumOfEdges() sticks out as an oddball on account of accepting as its arguments members (presumably) of a Graph_t, instead of accepting a Graph_t *. Your API is mixing different levels of abstraction.

  • As a matter of style (only), I recommend against spelling names in camel case in C code.

  • The suffix _t for type names is reserved by POSIX. That perhaps can be ignored if you don't intend your code to be used in a POSIX environment. In practice, your use of that suffix will probably not present a problem even in a POSIX environment, but as a matter of form, I recommend against using it.

graph.c

Your implementation code is fairly straightforward, but it does present a few issues:

  • do not cast the return value of malloc() in C
  • addEdge() fails silently in the event of an allocation error. It should somehow alert the caller if it is unable to add the requested edge.
  • When operating on an undirected graph, an allocation failure in the wrong place can make addEdge() add just one (directed) edge instead of the two it normally would add. This failure mode is also silent.
  • doesEdgeExist() is a public function, so it ought to perform proper argument checking. As it is, if its first argument is a null pointer, the function will attempt to dereference it, and if its second argument is not a valid vertex number for the provided graph then an out-of-bounds array access will be performed.
  • the (documented) assumption by calculateNumOfEdges() that the graph has no multi-edges is reasonable because addEdge() enforces it. If you want to also assume (as you do) that there are no self-edges, then you should enforce that constraint, too.

Missing features

You asked about missing features. I can imagine a lot of things that you could provide, but here is a fairly minimal list of additional things I think you should provide:

  • Many graph-based algorithms rely on or work with data associated with edges and / or vertices, such as tags and weights. You have no built-in mechanism for associating any such data with either vertices or edges.

  • On the other hand, all the adjacency information is opaque to users anyway, so there are not many interesting things one can actually do with the graphs you provide for.

  • There is no mechanism for adding or removing vertices.

  • There is no mechanism for deleting edges.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.