Inserting an element in a graph represented with adjacency matrix

Question

I'm learning about graph data structure in C and I have represented a graph with the adjacency matrix. So far I created the adjacency matrix which means(in my understanding at least) that I have specified 'between which vertices there will be edges' altough I have not yet created any actual nodes. Now after I have done that I want to actually populate my graph with nodes which contain a data type of my own(say each node in a structure which contains some elements). I have googled a lot but all I found was examples on how to create the adjacency matrix but the explanations would stop there without showing how you actually insert new elements in the graph.

I have written the code to populate the adjacency matrix. I have provided the code below:

#include<stdio.h>
#define V 5

void init(int arr[][V])
{
  int i,j;
  for(i = 0; i < V; i++)
  for(j = 0; j < V; j++)
   arr[i][j] = 0;
}

void addEdge(int arr[][V],int src, int dest)
{
  arr[src][dest] = 1;
}

void printAdjMatrix(int arr[][V])
{
     int i, j;

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

int main()
{
  int adjMatrix[V][V];

  init(adjMatrix);
  addEdge(adjMatrix,0,1);
  addEdge(adjMatrix,0,2);
  addEdge(adjMatrix,0,3);
  addEdge(adjMatrix,1,3);
  addEdge(adjMatrix,1,4);
  addEdge(adjMatrix,2,3);
  addEdge(adjMatrix,3,4);

  printAdjMatrix(adjMatrix);

  return 0;
}

Now my question is: to populate my graph with new nodes do I have to create another array of size noofnodes x noofnodes and populate it? Is that the correct way to do it or is there any other way? I want to know how the normal and considered correct way to do this is.

Thank you for reading.

I don't understand your question, to create your graph (nodes) it is not mandatory to have an array supporting the adjacency matrix, I mean you can create it directly so to populate it with new nodes it is the same — bruno
@bruno so I have created the adjacency matrix which shows where connections between nodes are or better said 'will be' after nodes are created. Now say I want to create two nodes. How do I 'link' the newly created nodes with the adjacency matrix I have just created? Could you give an example please? — Cantaff0rd
basically this example should help: I have an edge between node 0 to node 1. Please show me how can I create these 2 nodes and link them so they have a connection as shown in the matrix(from 0 to 1). I understand I may not explain everything clearly but I hope you understand what I mean :D. Thanks — Cantaff0rd

Joris Schellekens Joris Schellekens · Accepted Answer · 2019-01-29T11:27:47

I think the easiest way to achieve is this is the following:

map every node (e.g. represented by string) to an integer
store this mapping in a class representing the Graph object
instead of storing an array of ints, store an std::vector<std::vector<int>>

Now when you add something, the process becomes very straightforward:

add the new node to the mapping, its corresponding integer is the size of the adjecency matrix std::vector<std::vector<int>>
add a new std::vector<int> to the adjecency matrix, filled with zeros

updating the adjecency matrix is easy:

public void setAdjMat(const std::string& n0, const std::string& n1, int c){
    int i0 = nodeMap[n0];
    int i1 = nodeMap[n1];
    adjecencyMatrix[i0][i1] = c;
}

The advantages:

adding requires very little effort, and does not need to restructure the entire adjecency matrix
removal can be implemented in two ways; removal from nodeMap and/or removal from adjecencyMatrix

Inserting an element in a graph represented with adjacency matrix

1 Answers