Home » Data Structure

Addition and deletion of nodes and edges in a graph using adjacency matrix

In this article, we will learn about what is graph and how to add and delete nodes and edges in it by adjacency matrix? By Manu Jemini, on January 06, 2018

Overview of nodes and edges in a graph using adjacency matrix

A graph is a set of nodes or known number of vertices. When these vertices are paired together, we call it edges. An Edge is a line from one node to other. Every edge can have its cost or weight.

Graphs are two types Directed and Undirected. Directed graphs are the graphs in which the vertices are ordered and in undirected graphs the vertices are unordered.

Implementation and Explanation

In the Example below, a graph is implemented with the help of adjacency matrix. An Adjacency matrix is a square matrix used to represent a finite graph. It contains the information about the edges and its cost. If the value at the I^th row and J^th column are zero, it means an edge does not exist between these two vertices. Else you got the edge and cost of that edge.

Image source: http://2.bp.blogspot.com/-KS2IS_wQ99k/Ux5EYJg2SZI/AAAAAAAACL8/xn2mJDQto8o/s1600/Adjacency+Matrix+Representation+of+Weighted+Graph.JPG

In the code below the function, create_graph() ask for the number of nodes, then create a matrix. According to the input of user, program ask for the edges. The function add_node() and delete_node() are using the global index of the matrix to manipulate the matrix.

The Fifth in the menu, display function is iterating through the matrix and showing all the values.

C program for addition and deletion of nodes and edges in a graph using adjacency matrix

#include<stdio.h>

#define max 20
int adj[max][max];
int n;

void create_graph() {
  int i, max_edges, origin, destin;

  printf("Enter number of nodes : ");
  scanf("%d", & n);
  max_edges = n * (n - 1); /* Taking directed graph */

  for (i = 1; i <= max_edges; i++) {
    printf("Enter edge %d( 0 0 ) to quit : ", i);
    scanf("%d %d", & origin, & destin);
    if ((origin == 0) && (destin == 0))
      break;
    if (origin > n || destin > n || origin <= 0 || destin <= 0) {
      printf("Invalid edge!\n");
      i--;
    } else
      adj[origin][destin] = 1;
  } /*End of for*/
} /*End of create_graph()*/

void display() {
  int i, j;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++)
      printf("%4d", adj[i][j]);
    printf("\n");
  }
} /*End of display()*/

void insert_node() {
  int i;
  n++; /*Increase number of nodes in the graph*/
  printf("The inserted node is %d \n", n);
  for (i = 1; i <= n; i++) {
    adj[i][n] = 0;
    adj[n][i] = 0;
  }
} /*End of insert_node()*/

void delete_node(char u) {
  int i, j;
  if (n == 0) {
    printf("Graph is empty\n");
    return;
  }
  if (u > n) {
    printf("This node is not present in the graph\n");
    return;
  }
  for (i = u; i <= n - 1; i++)
    for (j = 1; j <= n; j++) {
      adj[j][i] = adj[j][i + 1]; /* Shift columns left */
      adj[i][j] = adj[i + 1][j]; /* Shift rows up */
    }
  n--; /*Decrease the number of nodes in the graph */
} /*End of delete_node*/

void insert_edge(char u, char v) {
  if (u > n) {
    printf("Source node does not exist\n");
    return;
  }
  if (v > n) {
    printf("Destination node does not exist\n");
    return;
  }
  adj[u][v] = 1;
} /*End of insert_edge()*/

void del_edge(char u, char v) {
  if (u > n || v > n || adj[u][v] == 0) {
    printf("This edge does not exist\n");
    return;
  }
  adj[u][v] = 0;
} /*End of del_edge()*/

int main() {
  int choice;
  int node, origin, destin;

  create_graph();
  while (1) {
    printf("1.Insert a node\n");
    printf("2.Insert an edge\n");
    printf("3.Delete a node\n");
    printf("4.Delete an edge\n");
    printf("5.Dispaly\n");
    printf("6.Exit\n");
    printf("Enter your choice : ");
    scanf("%d", & choice);

    switch (choice) {
    case 1:
      insert_node();
      break;
    case 2:
      printf("Enter an edge to be inserted : ");
      fflush(stdin);
      scanf("%d %d", & origin, & destin);
      insert_edge(origin, destin);
      break;
    case 3:
      printf("Enter a node to be deleted : ");
      fflush(stdin);
      scanf("%d", & node);
      delete_node(node);
      break;
    case 4:
      printf("Enter an edge to be deleted : ");
      fflush(stdin);
      scanf("%d %d", & origin, & destin);
      del_edge(origin, destin);
      break;
    case 5:
      display();
      break;
    case 6:
      break;
    default:
      printf("Wrong choice\n");
      break;
    } /*End of switch*/
  } /*End of while*/
  return 0;
} /*End of main()*/

Output