Message Boards Message Boards

[✓] How does GraphDistanceMatrix works?

GROUPS:

Hello everybody!

I want to compute the distance between edges of a small tree:

Land = {1 -> 2, 1 -> 15, 2 -> 3, 2 -> 4, 3 -> 7, 3 -> 8, 15 -> 5, 
   15 -> 6, 5 -> 9, 5 -> 10, 10 -> 11, 10 -> 12, 6 -> 13, 6 -> 14};
Etiq = {"All", "Flat", "Plain", "tl", "Hills", "Mountain", "fp", "ip",
    "rlh", "Lowslope", "hh", "slh", "hm", "lm", "\[Not]Flat"};
Codes = Inner[Rule, Range[Length@Etiq], Etiq, List];

The distance matrix is obtained from:

Gr = Graph[Land, DirectedEdges -> False, VertexLabels -> Codes]
Print@TableForm[GraphDistanceMatrix[Gr], 
   TableHeadings -> {Etiq, Etiq}];

but something is wrong: the distance between "ip" and "fp" should be 2, while in the table, it's 5! Building myself the table

Dis = Table[
   GraphDistance[Gr, i, j], {i, Length@Etiq}, {j, Length@Etiq}];
Print@TableForm[Dis, TableHeadings -> {Etiq, Etiq}];

I could obtain the right distance matrix, but I dont' understand how GraphDistanceMatrix put away the distances! Isn't it misleading?

Regards, Claude

POSTED BY: Claude Mante
Answer
2 months ago

Look at VertexList[Gr]: the 3rd vertex is not vertex 3, but vertex 15. GraphDistanceMatrix returns its result according to the vertex ordering. You are confusing the names of vertices (which happen to be integers in your graph, but in general they don't need to) with the indices of vertices, i.e. their position in VertexList[Gr].

Construct your graph as Graph[Range[15], Land] to control the vertex ordering.

POSTED BY: Szabolcs Horvát
Answer
2 months ago

Ok, I see.

Thanks a lot!

POSTED BY: Claude Mante
Answer
2 months ago

Group Abstract Group Abstract