Practical UseCases of Graphs in C Programming

Graphs are a fundamental data structure in computer science, representing a collection of vertices (nodes) and edges that connect these vertices. In C programming, graphs can be used to solve a wide variety of real - world problems. From social network analysis to path - finding in maps, graphs offer a flexible and powerful way to model relationships between different entities. This blog will explore some practical use cases of graphs in C programming, along with the necessary concepts, usage methods, and best practices.

Table of Contents

  1. Fundamental Concepts of Graphs
  2. Representing Graphs in C
  3. Practical Use Cases
    • Social Network Analysis
    • Shortest Path Finding
    • Web Page Crawling
  4. Common Practices and Best Practices
  5. Conclusion
  6. References

Fundamental Concepts of Graphs

Basic Definitions

  • Vertex (Node): A fundamental unit in a graph. It can represent anything, such as a person in a social network, a city on a map, or a web page on the internet.
  • Edge: A connection between two vertices. Edges can be directed (pointing from one vertex to another) or undirected (no specific direction).
  • Degree: For an undirected graph, the degree of a vertex is the number of edges incident to it. In a directed graph, we have in - degree (number of incoming edges) and out - degree (number of outgoing edges).

Types of Graphs

  • Undirected Graph: Edges have no direction. If there is an edge between vertex A and vertex B, you can move from A to B and vice versa.
  • Directed Graph: Edges have a specific direction. An edge from A to B does not imply an edge from B to A.
  • Weighted Graph: Each edge has an associated weight, which can represent a cost, distance, or any other numerical value.

Representing Graphs in C

Adjacency Matrix

An adjacency matrix is a 2D array of size V x V, where V is the number of vertices in the graph. If there is an edge between vertex i and vertex j, then matrix[i][j] = 1 (or the weight of the edge in a weighted graph), otherwise matrix[i][j]=0.

#include <stdio.h>

#define V 5

void printGraph(int graph[V][V]) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int graph[V][V] = {
        {0, 1, 1, 0, 0},
        {1, 0, 0, 1, 1},
        {1, 0, 0, 0, 1},
        {0, 1, 0, 0, 0},
        {0, 1, 1, 0, 0}
    };
    printGraph(graph);
    return 0;
}

Adjacency List

An adjacency list is an array of linked lists. Each element in the array represents a vertex, and the linked list associated with it contains all the vertices adjacent to that vertex.

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

// Structure to represent an adjacency list node
struct AdjListNode {
    int dest;
    struct AdjListNode* next;
};

// Structure to represent an adjacency list
struct AdjList {
    struct AdjListNode *head;
};

// Structure to represent a graph
struct Graph {
    int V;
    struct AdjList* array;
};

// Function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest) {
    struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// Function to create a graph of V vertices
struct Graph* createGraph(int V) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;

    // Create an array of adjacency lists.  Size of array will be V
    graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));

    // Initialize each adjacency list as empty by making head as NULL
    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

// Function to add an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest) {
    // Add an edge from src to dest.  A new node is added to the adjacency
    // list of src.  The node is added at the beginning
    struct AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // Since graph is undirected, add an edge from dest to src also
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// Function to print the adjacency list representation of graph
void printGraph(struct Graph* graph) {
    for (int v = 0; v < graph->V; ++v) {
        struct AdjListNode* pCrawl = graph->array[v].head;
        printf("\n Adjacency list of vertex %d\n head ", v);
        while (pCrawl) {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

int main() {
    int V = 5;
    struct Graph* graph = createGraph(V);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printGraph(graph);

    return 0;
}

Practical Use Cases

Social Network Analysis

In a social network, users can be represented as vertices, and friendships can be represented as edges. Graph algorithms can be used to find mutual friends, suggest new friends, or analyze the connectivity of the network.

// Assume we have a graph representing a social network
// We can find the number of mutual friends between two users
#include <stdio.h>

#define V 5

int mutualFriends(int graph[V][V], int user1, int user2) {
    int count = 0;
    for (int i = 0; i < V; i++) {
        if (graph[user1][i] == 1 && graph[user2][i] == 1) {
            count++;
        }
    }
    return count;
}

int main() {
    int graph[V][V] = {
        {0, 1, 1, 0, 0},
        {1, 0, 1, 1, 1},
        {1, 1, 0, 0, 1},
        {0, 1, 0, 0, 0},
        {0, 1, 1, 0, 0}
    };
    int user1 = 0;
    int user2 = 1;
    int numMutual = mutualFriends(graph, user1, user2);
    printf("Number of mutual friends between user %d and user %d is %d\n", user1, user2, numMutual);
    return 0;
}

Shortest Path Finding

In a map, cities can be represented as vertices, and roads between them can be represented as edges. The weight of an edge can represent the distance between two cities. Dijkstra’s algorithm can be used to find the shortest path between two cities.

#include <stdio.h>
#include <limits.h>

#define V 9

// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], int sptSet[]) {
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (sptSet[v] == 0 && dist[v] <= min)
            min = dist[v], min_index = v;

    return min_index;
}

// A utility function to print the constructed distance array
void printSolution(int dist[], int n) {
    printf("Vertex   Distance from Source\n");
    for (int i = 0; i < V; i++)
        printf("%d \t\t %d\n", i, dist[i]);
}

// Function that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
void dijkstra(int graph[V][V], int src) {
    int dist[V];  // The output array.  dist[i] will hold the shortest
    // distance from src to i

    int sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest
    // path tree or shortest distance from src to i is finalized

    // Initialize all distances as INFINITE and stpSet[] as false
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = 0;

    // Distance of source vertex from itself is always 0
    dist[src] = 0;

    // Find shortest path for all vertices
    for (int count = 0; count < V - 1; count++) {
        // Pick the minimum distance vertex from the set of vertices not
        // yet processed. u is always equal to src in the first iteration.
        int u = minDistance(dist, sptSet);

        // Mark the picked vertex as processed
        sptSet[u] = 1;

        // Update dist value of the adjacent vertices of the picked vertex.
        for (int v = 0; v < V; v++)

            // Update dist[v] only if is not in sptSet, there is an edge from
            // u to v, and total weight of path from src to  v through u is
            // smaller than current value of dist[v]
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }

    // print the constructed distance array
    printSolution(dist, V);
}

int main() {
    int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                       {4, 0, 8, 0, 0, 0, 0, 11, 0},
                       {0, 8, 0, 7, 0, 4, 0, 0, 2},
                       {0, 0, 7, 0, 9, 14, 0, 0, 0},
                       {0, 0, 0, 9, 0, 10, 0, 0, 0},
                       {0, 0, 4, 14, 10, 0, 2, 0, 0},
                       {0, 0, 0, 0, 0, 2, 0, 1, 6},
                       {8, 11, 0, 0, 0, 0, 1, 0, 7},
                       {0, 0, 2, 0, 0, 0, 6, 7, 0}
    };

    dijkstra(graph, 0);

    return 0;
}

Web Page Crawling

Web pages can be represented as vertices, and hyperlinks between them can be represented as edges. A graph traversal algorithm like Breadth - First Search (BFS) can be used to crawl the web.

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

#define V 5

// Structure to represent a queue
struct Queue {
    int front, rear, size;
    unsigned capacity;
    int* array;
};

// Function to create a queue of given capacity.
// It initializes size of queue as 0
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;  // This is important, see the enqueue
    queue->array = (int*)malloc(queue->capacity * sizeof(int));
    return queue;
}

// Queue is full when size becomes equal to the capacity
bool isFull(struct Queue* queue) {
    return (queue->size == queue->capacity);
}

// Queue is empty when size is 0
bool isEmpty(struct Queue* queue) {
    return (queue->size == 0);
}

// Function to add an item to the queue.
// It changes rear and size
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;
}

// Function to remove an item from queue.
// It changes front and size
int dequeue(struct Queue* queue) {
    if (isEmpty(queue))
        return INT_MIN;
    int item = queue->array[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size = queue->size - 1;
    return item;
}

// Function to get front of queue
int front(struct Queue* queue) {
    if (isEmpty(queue))
        return INT_MIN;
    return queue->array[queue->front];
}

// Function to do BFS traversal of a graph
void BFS(int graph[V][V], int start) {
    bool visited[V];
    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }

    struct Queue* queue = createQueue(V);

    visited[start] = true;
    enqueue(queue, start);

    while (!isEmpty(queue)) {
        int s = dequeue(queue);
        printf("%d ", s);

        for (int i = 0; i < V; i++) {
            if (graph[s][i] == 1 &&!visited[i]) {
                visited[i] = true;
                enqueue(queue, i);
            }
        }
    }
}

int main() {
    int graph[V][V] = {
        {0, 1, 1, 0, 0},
        {1, 0, 0, 1, 1},
        {1, 0, 0, 0, 1},
        {0, 1, 0, 0, 0},
        {0, 1, 1, 0, 0}
    };
    int start = 0;
    printf("BFS traversal starting from vertex %d: ", start);
    BFS(graph, start);
    return 0;
}

Common Practices and Best Practices

  • Choose the Right Representation: Use an adjacency matrix when the graph is dense (a large number of edges), and use an adjacency list when the graph is sparse (a small number of edges).
  • Memory Management: When using dynamic memory allocation (e.g., for adjacency lists), make sure to free the allocated memory to avoid memory leaks.
  • Error Handling: Check for errors such as invalid input (e.g., non - existent vertices) and handle them gracefully.
  • Algorithm Complexity: Be aware of the time and space complexity of graph algorithms. For example, Dijkstra’s algorithm has a time complexity of $O(V^2)$ using an adjacency matrix, but can be optimized to $O((V + E)\log V)$ using a priority queue.

Conclusion

Graphs are a powerful data structure with a wide range of practical applications in C programming. By understanding the fundamental concepts, choosing the right representation, and applying appropriate algorithms, we can solve complex real - world problems such as social network analysis, shortest path finding, and web page crawling. It is important to follow common practices and best practices to ensure the efficiency and reliability of our code.

References

  • Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
  • Data Structures and Algorithms in C by Adam Drozdek.
  • GeeksforGeeks - A computer science portal for geeks ( https://www.geeksforgeeks.org/) .