King’s Graph and Grid Graph

Can anyone give me a code or function to generate King’s Graph and Grid Graph of any size in Matlab? Mainly, I need the adjacency matrices.

Answer 1

[Sunny Choudhary]

Sure, here's an example code that can generate an adjacency matrix and plot a King's graph and a Grid graph using the built-in function graph() in MATLAB.

% Define the size of the King's graph
n = 5; 

% Generate adjacency matrix for King's graph
A = zeros(n^2);
for i = 1:n^2
    for j = i+1:n^2
        xi = mod(i-1,n)+1;
        yi = ceil(i/n);
        xj = mod(j-1,n)+1;
        yj = ceil(j/n);
        
        % Define the pairwise rule for adjacent cells in King's graph
        if abs(xi-xj)<=1 && abs(yi-yj)<=1 && ~(xi==xj && yi==yj)
             A(i,j) = 1;
             A(j,i) = 1;
        end
    end
end

% Generate the King's graph
G_Kings = graph(A);
figure;
plot(G_Kings, 'NodeLabel',{}); % 'NodeLabel',{} is to remove the node labels

% Generate adjacency matrix for Grid graph
B = zeros(n^2);
for i=1:n^2
    if i<n^2
        B(i,i+1) = 1;
        B(i+1,i) = 1;
    end
    if mod(i,n)~=0
        B(i,i+1) = 1;
        B(i+1,i) = 1;
    end
    if i<=(n-1)*n
        B(i,i+n) = 1;
        B(i+n,i) = 1;
    end
end

% Generate the Grid graph
G_Grid = graph(B);
figure;
plot(G_Grid, 'NodeLabel',{}); % 'NodeLabel',{} is to remove the node labels

In the above code, we first define the size of the graph by setting n to the desired value. Then, we generate the adjacency matrix for the King's graph and the Grid graph using nested loops. We set the pairwise rule for Kings graph and grid graph, namely checking adjacent cells for connectivity, respectively. Finally, we use the built-in function graph() to create an undirected graph for each adjacency matrix and plot the graph with adjacency matrix A founded in Kings graph and adjacency matrix B founded in Grid graph.