CODEWITHSUNDEEP
matlabgraph
Tom Kealy
Tom Kealy

Reputation: 2669

Finding the diameter of a graph

In MATLAB I'm dropping points into the square [0,1]X[0,1] uniformly at random. I'm then placing an edge between two points if the distance between the two points is less than 0.25. The code to do this (and plot the resulting graph is below).

num_Rx = 50
Rx_positions = rand(num_Rx,2);

%Generate edges between pairs of within norm of 0.25.
adj_matrix = zeros(num_Rx, num_Rx);
for i=1:num_Rx
    for j=i+1:num_Rx
        dist = norm(Rx_positions(i,:) - Rx_positions(j,:));
        if dist < 0.25;
            adj_matrix(i,j) = 1;
        end
    end
end

figure
gplot(adj_matrix, Rx_positions)

i.e. this is an undirected graph, with all edge weights equal to 1.

To find the diameter I want to call graphallshortestpaths() (http://www.mathworks.co.uk/help/bioinfo/ref/graphallshortestpaths.html), and take the maximum value returned (the diameter is the longest shortest path).

However, I'm having difficulty calling this function - I can't figure out how to make a call like the examples, from my adjacency matrix and/or my list of node positions. Specifically I don't understand any of the examples, how the matlab code given corresponds to the data presented.

How would I go about doing this.

Upvotes: 2

Views: 3300

Answers (1)

beaker
beaker

Reputation: 16791

It appears that all you're missing is converting your adjacency matrix to a sparse matrix. This should give you what you're looking for:

adj_sparse = sparse(adj_matrix);
distances = graphallshortestpaths(adj_sparse);

% if you don't care which nodes produce the
% longest shortest path, omit long_ind & long_sub
[diameter, long_ind] = max(distances(:));
long_sub = ind2sub(size(distances), long_ind);

Upvotes: 1

Related Questions