Euclidean distance for a graph

11 views (last 30 days)
Hari on 1 Nov 2020
Commented: Walter Roberson on 1 Nov 2020
Is there an inbuilt function in matlab or a short cut which calculates the Eucliedan distance or crow fly distance between every node pair in a graph

Answers (2)

Ameer Hamza
Ameer Hamza on 1 Nov 2020
Ameer Hamza
Ameer Hamza on 1 Nov 2020
Yes. first, OP needs to get the coordinates for all nodes. Then pdist() can be used. Unless OP only wants distances between nodes that have an edge between them.
Walter Roberson
Walter Roberson on 1 Nov 2020
Euclidean distance simply does not apply for graph objects.
What could apply is if the user had added coordinates for each point to the table, and wanted to know:
for each pair of nodes that are connected in the graph, use the stored coordinates to calculate the Euclidean distance.
If, for example, it were a map and the user wanted not just the driving distance (graph traversal) but also the Euclidean, so as to compare the driving distance to the direct distance.
If so then the user should perhaps be asking not for the Euclidean distance but instead for the Great Circle distance.

Sign in to comment.

Walter Roberson
Walter Roberson on 1 Nov 2020
Edited: Walter Roberson on 1 Nov 2020
No there is no function for that purpose.
Euclidean distance and crow-fly distance are only meaningful for continuous travel between points — continuous in the mathematical sense that for all finite small enough dx, dy, (x+dx, y+dy) is a separate point that also exists in the surface. (I say "small enough" because for closed curves, for large enough dx, dy, you might arrive back at the origin.) For Euclidean distance you have to be able to visit all points in-between.
Graphs, on the other hand, have only nodes and edges, and costs associated with each edge. Travel is permitted only along the defined edges, and the travel is always along the whole edge, with it not being permitted to stop part way along the way. The distance between two nodes is defined by the sum of the costs of the edges traveled.
Imagine for example a series of roads and villages around the base of a mountain. You might be able to get to the other side of the mountain by following the roads, but going directly over the mountain is not possible.
I am having difficulty finding information about the maximum altitude at which crows fly. They are not among the top 10 record holders. The only hard number I can seem to find is one fighter pilot who reports that he has never encountered a crow above 4000 feet. I have encountered material about birds flying over Himalaya mountains in the past; I think it was either ducks or geese.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!