Adjacency Matrix (Graph)- DSTC using C Language (Source Code Implemented)

 

ADJACENCY MATRIX
(Representation of Graph through Adjacency Matrix)
Implemented using C Language   

---

ADJMAT.H

---

/* Name : Adhmat.h
Purpose : Representation of Graph through
Adjacency Matrix
Operations defined :
Graph * GetGraph(void);
void init(Graph *g);
void InsEdge(Graph *g,int start, int end);
void DelEdge(Graph *g,int start, int end);
void print(Graph *g);
void Warshall(Graph *g);
void rmat(Graph *g);              */

#include <stdio.h>
#include <stdlib.h>
#define MAX 50

typedef struct {
    int Adj[MAX][MAX];
    int Path[MAX][MAX];
    int node;
}Graph;

//allocating space to graph
Graph * GetGraph(void)
{
    Graph *t;
    t=(Graph *)malloc(sizeof(Graph));
    return t;
}

 

//intializing the graph
void init(Graph *g)
{
    int n,i,j;
    printf("How many nodes are there: ");
    scanf("%d", &n);
    if(n>MAX)
    {
        printf("n cannot be greater than %d\n", MAX);
        exit(0);
    }

    g->node=n;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
            g->Adj[i][j]=0;
    }
}

//getting a new edge
void InsEdge(Graph *g,int start,int end)
{
    if(start > g->node)
    {
        printf("This node number does not exist\n");
        exit(0);
    }

    if(end > g->node)
    {
        printf("This node number does not exist\n");
        exit(0);
    }

if(g->Adj[start-1][end-1] > 0)
    {
        printf("This edge already exists\n");
        exit(0);
    }

    g->Adj[start-1][end-1]=1;
}

//printing graph information
void print(Graph *g)
{
    int i,j;
    printf("----------------Graph details---------------------\n");
    for(i=0;i<g->node;i++)
    {
        printf("All the edges starting from Node : %d --->\n", i+1);
        for(j=0;j<g->node;j++)
        {
            if(g->Adj[i][j]>0)
            {
                printf("To Node: %d\n", j+1);
            }
        }
        fflush(stdin);
        getchar();
    }
    printf("--------------------------------------------------\n");
}

//Warshall algorithm
void Warshall(Graph *g)
{
    int i,j,k;
    for(i=0;i<g->node;i++)
    {
        for(j=0;j<g->node;j++)
            g->Path[i][j]=g->Adj[i][j];
    }for(k=0;k<g->node;k++)
    {
        for(i=0;i<g->node;i++)
        {
            for(j=0;j<g->node;j++)
            {
                if(g->Path[i][j] || (g->Path[i][k] && g->Path[k][j]))
                    g->Path[i][j]=1;
            }
        }
    }
}

//printing reachability matrix
void rmat(Graph *g)
{
    int i,j;
    printf("----------------Graph details---------------------\n");
    for(i=0;i<g->node;i++)
    {
        printf("All the nodes reachable from Node : %d --->\n", i+1);
        for(j=0;j<g->node;j++)
        {
            if(g->Path[i][j]>0)
            {
                printf("Node: %d\n", j+1);
            }
        }

fflush(stdin);
        getchar();
    }
    printf("--------------------------------------------------\n");
} 

---

ADJMAT.CPP

---

 #include "adjmat.h"
#include <conio.h>

void main()
{
    int menu(void);
    Graph *g;
    int c,start,end;
    clrscr();
    g=GetGraph();
    init(g);

    while(1)
    {
        c=menu();
        if(c==5)
            break;
        switch(c) {
case 1:
    printf("Enter starting Node: ");
    scanf("%d", &start);
    printf("Enter ending Node: ");
    scanf("%d", &end);
    InsEdge(g,start,end);
    break;
case 2:

printf("Enter starting Node: ");
    scanf("%d", &start);
    printf("Enter ending Node: ");
    scanf("%d", &end);
    DelEdge(g,start,end);
    break;
case 3:
    print(g);
    break;
case 4:
    Warshall(g);
    rmat(g);
    break;
        }
    }
}

int menu(void)
{
    int ch;
    while(1)
    {
        printf("1. Inserting an edge\n");
        printf("2. Deleting an edge\n");
        printf("3. Printing the Graph\n");
        printf("4. Print reachability matrix\n");
        printf("5. Quit\n");

printf("Enter the choice: ");
        scanf("%d", &ch);
        if(ch<1 || ch > 5)
            printf("Invalid choice\n");
        else
            return ch;
    }
}