I want to create a 2d Grid graph with 10000 Nodes ( actually 100*100 ) with periodic conditions in C . I don't know exactly how should I do that ?
after that I want to get adjacency matrix of that graph and again I have no idea about that .
I do these things in python easily with Networkx . but in C I don't know how to do that . please help .
Adjacency matrix
An adjacency matrix is a way of representing a graph G = {V, E} as a matrix of booleans.
The size of the matrix is VxV where V is the number of vertices in the graph and the value of an entry Aij is either 1 or 0 depending on whether there is an edge from vertex i to vertex j.
In case of directed graph, the matrix is symmetric about the diagonal because of every edge (i,j), there is also an edge (j,i).
Pseudocode :
int Node,Edge;
int matrix[100][100];
scanf("%d%d",&Node,&Edge);
for(i=0;i<Edge;i++)
{
int n1,n2,cost;
scanf("%d%d%d",&n1,&n2,&cost);
matrix[n1][n2]=cost;
matrix[n2][n1]=cost;
}
Cons of adjacency matrix
The VxV space requirement of adjacency matrix makes it a memory hog. Graphs out in the wild usually don't have too many connections and this is the major reason why adjacency lists are the better choice for most tasks.
While basic operations are easy, operations like inEdges and outEdges are expensive when using the adjacency matrix representation.
Adjacency List
An adjacency list represents a graph as an array of linked list.
The index of the array represents a vertex and each element in its linked list represents the other vertices that form an edge with the vertex.
Pseudocode :
#include <stdio.h>
#include <stdlib.h>
struct node
{
int vertex;
struct node* next;
};
struct node* createNode(int);
struct Graph
{
int numVertices;
struct node** adjLists;
};
struct Graph* createGraph(int vertices);
void addEdge(struct Graph* graph, int src, int dest);
void printGraph(struct Graph* graph);
int main()
{
struct Graph* graph = createGraph(6);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 1, 4);
addEdge(graph, 1, 3);
addEdge(graph, 2, 4);
addEdge(graph, 3, 4);
addEdge(graph, 4, 6);
addEdge(graph, 5, 1);
addEdge(graph, 5, 6);
printGraph(graph);
return 0;
}
struct node* createNode(int v)
{
struct node* newNode = malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
struct Graph* createGraph(int vertices)
{
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(struct node*));
int i;
for (i = 0; i < vertices; i++)
graph->adjLists[i] = NULL;
return graph;
}
void addEdge(struct Graph* graph, int src, int dest)
{
// Add edge from src to dest
struct node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
// Add edge from dest to src
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
void printGraph(struct Graph* graph)
{
int v;
for (v = 0; v < graph->numVertices; v++)
{
struct node* temp = graph->adjLists[v];
printf("\n Adjacency list of vertex %d\n ", v);
while (temp)
{
printf("%d -> ", temp->vertex);
temp = temp->next;
}
printf("\n");
}
}
Adjacency List using Vector:
By using `Vector' you don't need to mention the size , just need to mention the maximum node .
Input :
6 8 //node-edge
1 2 //node1-node2
1 4
2 4
2 5
4 5
5 3
3 6
6 6
The the code would be like this.
Pseudocode :
#include<cstdio>
#include<vector>
using namespace std;
#define MAX 100000 //maximum node
vector<int>edges[MAX];
vector<int>cost[MAX]; //parallel vector to store costs;
int main()
{
int N,E,i;
scanf("%d%d",&N,&E);
for(i=1;i<=E;i++)
{
int x,y;
scanf("%d%d",&x,&y);
edges[x].push_back(y);
edges[y].push_back(x);
cost[x].push_back(1);
cost[y].push_back(1);
}
return 0;
}
