[Math] MATLAB code to find distance and eccentricity in graphs

combinatoricscomputer sciencegraph theoryMATLAB

I was trying to find the distances between vertices in graphs. But as the number of vertices are increasing up to 25 vertices or more, its becoming a tedious job for me to calculate $distance$ and $eccentricity$.

Can I draw graphs in MATLAB and then calculate the $dist$ and $ecc$?

For ex. What is the code if I want to draw $P_n$ and then the distances between vertices.

I am very new to MATLAB. Started few days back only. Can anyone help me here.

Edit : I want the code to draw the graph which are Undirected and non-weighted graphs. And also distance between every two vertices. Can I make the graph if I am taking adjacency matrix. Is it possible to make the graph when entries are like ordered pairs of adjacent vertices .

I would be very thankful. thanks

Coding for any small graph like $P_3$ or $K_4$ will be helpful for me.

Best Answer

To work out graph distance use Dijkstra's algorithm which is available for MATLAB here

% K4 does not have edge weights in its definition
%  Make them all 1

K4 = ones(4) - eye(4) % Matrix of ones minus identity

% Find distance between nodes 1 and 2
[cost, route] = dijkstra(K4, 1, 2)

% Find the eccentricity using algorithm below

ecc = eccent(K4)

You could download and install MATLABS graph theory toolbox (can't give a link on SE), which has the functions grEccentricity and grShortPath but it requires the optimization toolbox, which is propriety. So assuming you don't have the money to pay for a toolbox, here is an eccentricity function. There are surely faster algorithms than this one ($O(E^2)\times O(\text{dijkstra})$), but it is really simple - check every pair (assumes undirected edges).

function e = eccent(g)
    e = 0;

    for i=1:length(g)
        for j=1:(i-1) % only i < j

            % Find distance between nodes
            [new_e, path] = dijkstra(g, i, j);

            % If this distance is bigger than saved distance,
            %  make e the new distance

            if new_e > e
                e = new_e;
            end
        end
    end
end

should work, but I don't own MATLAB to test it, you will need to put in a file called "eccent.m" in your working directory, because, well, it's MATLAB and that's how it works.

A function for $K_n$ is:

function g = Kn(n)
    % Puts a distance of one for all edges
    g = ones(n) - eye(n);
end

and for $P_n$ is

function g = Pn(n)
    % Pn is a set of nodes like 1--2--3--4
    %  the edges are length one for neighbouring nodes
    %  so the matrix is tridiagonal with entries 1 on the -1, and 1 diagonals

    g = diag(ones(n-1,1),1) + diag(ones(n-1,1),-1);
end

and the cyclic graphs just add a one to the antidiagonal corners

function g = Cn(n)
    g = Pn(n);
    g(n,1) = 1;
    g(1,n) = 1;
end

These would need to be in files "Kn.m", "Pn.m" and "Cn.m" respectively.

To make a directed graph for a list of pairs of the form:

[[a,b];[c,d]...]

then

function g = directed(pairs, n)
    % make graph with no edges
    g = zeros(n);

    % add each edge
    for p=1:length(pairs)
       i = pairs(p,1);
       j = pairs(p,2);

       g(i,j) = 1;

    end
end

and for an undirected graph

function g = undirected(pairs)

    % make graph with no edges
    g = zeros(n);

    % add each edge
    for p=1:length(pairs)
       i = pairs(p,1);
       j = pairs(p,2);

       g(i,j) = 1;
       g(j,i) = 1;

    end
end
Related Question