How to find maximum eccentricity of a vertex of non-directed graph?

How to find maximum eccentricity of a vertex of non-directed graph?

[ANKUR KUMAR]

Please attach your code along with the required formulations.

[Walter Roberson]

Are you trying to find the graph diameter, or trying to find the eccentricity for a given node?

[Anjani Chaudhary]

I am trying to get the maximum eccentricity of each node and then find graph diameter.

[Walter Roberson]

Eccentricity is defined in terms of maximum shortest path between a given node and all the other nodes in a (sub-) graph. It would not seem to make sense to talk about the maximum eccentricity for a particular node?

[Anjani Chaudhary]

Yes, I understand concept of eccentricity. Sorry my question was not clear. I want to find eccentricity of each node and then get diameter of the graph.

thanks,

[Bruno Luong]

Did you check out FEX for shortest path algorithms? There are a bunch of them. Not sure if you need Floyd–Warshall algorithm or loop on Dijkstra for the all edges containing the considered vertex.

[Anjani Chaudhary]

I have a graph like this.

s = [1 1 1 2 2 2 2 3 3 3 4 4 4 5 5 5 5 6 6 6 7 7 7 7 8 8 8 8 9 9 10 10 11 11 12 12 12 12 13 13 13 14 14 14 15 15];
t = [3 8 15 3 7 8 13 1 2 11 8 10 15 7 8 10 12 7 14 13 2 5 6 12 1 2 4 5 12 14 4 5 3 13 5 7 9 14 2 6 11 6 9 12 1 4];
G = digraph(s,t)
A = adjacency(G)
TR = shortestpathtree(G,1);
p = plot(G);
A = adjacency(G)
highlight(p,TR,'EdgeColor','r')

Here I need to find eccentricity of each node and diameter of the graph. And at end check which node eccentricity is equal as the graph diameter.

Answer 1

[Walter Roberson]

%need a graph
s = [1 1 2 3 3 4 4 6 6 7 8 7 5];
t = [2 3 4 4 5 5 6 1 8 1 3 2 8];
G = digraph(s,t);

%now process it
allnodes = unique(G.Edges.EndNodes);
numnodes = length(allnodes);
eccentricities = zeros(1, numnodes);
for N = 1 : numnodes
  thisnode = allnodes(N);
  [~, D] = shortestpathtree(G,thisnode);
  eccentricities(N) = max(D);
end

graph_diameter = max(eccentricities);

[Anjani Chaudhary]

Thanks Walter. I will try to do this.

[Anjani Chaudhary]

This code is working. Thanks. at the end how can I check which node has eccentricity equal to graph diameter?

[Walter Roberson]

which_node = find(eccentricities == graph_diameter);

I did it this way because there could easily be multiple nodes that imply the same graph diameter.

[Anjani Chaudhary]

Thanks so much Walter! :-)

[Sumari Van Zyl]

Hi Walter, I know this is an old answer but I hope you're still around to answer! I don't understand the graph definition part of your answer i.e. the s= and t=...

Do you happen to have an illustration of what that graph would look like? I have an illustration of a graph and I don't know how to code it in your format.

Thanks

[Bruno Luong]

https://www.mathworks.com/help/matlab/ref/graph.html

[Walter Roberson]

s = [1 1 2 3 3 4 4 6 6 7 8 7 5];
t = [2 3 4 4 5 5 6 1 8 1 3 2 8];
G = digraph(s,t);
plot(G)