# distance between each vertex of a graph and its output

I have a question regarding this Q&A.

Let's call a vertex that is not the tail of any directed edge an output of the graph. The graph below has only one output (at the far right). If I want the distance from each vertex to the output of the graph, what should I do?

This one is on my graph:

matOP = {{0, 1, 0, 0, 1, 0, 1, 0}, {0, 1, 0, 0, 1, 0, 1, 0}, {0, 0, 1, 0, 1, 0, 1, 0},
{0, 0, 0, 1, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 1, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0}};

pos = Position[matOP, 1];
edge = Subsets[Range@Length@pos, {2}];
dedge = DeleteDuplicates[
DirectedEdge @@@ (Extract[edge, #] & /@
With[{dist =
N@(EuclideanDistance[pos[[#]], pos[[#2]]] & @@@ edge)},
Flatten[Position[dist, #] & /@
DeleteDuplicates@N@Select[dist, # <= 1.5 &]]])];

Graph[dedge,
VertexCoordinates -> Rule @@@ Thread[{Range@Length@pos, pos}]]


• The code you are showing seems to be from @Öskå´s answer in the linked thread, and you should attribute it accordingly. Jun 9, 2014 at 10:26
• @YvesKlett I edited with the link.. :) I guess it's "enough"
– Öskå
Jun 9, 2014 at 10:26
• @Öskå in any case, is the Q clear to you? Jun 9, 2014 at 10:32
• @YvesKlett Apart from what I already commented above.., I don't see what could be the answer :)
– Öskå
Jun 9, 2014 at 10:34
• Do you mean you want a function that computes the number of edges of the shortest path from any vertex to the final vertex (at the far right)? If so, look at FindShortestPath. Jun 9, 2014 at 14:23

With the OP's definitions:

gr = Graph[dedge, VertexCoordinates -> Rule @@@ Thread[{Range@Length@pos, pos}]]

With[{spFN = FindShortestPath[gr, All,
First @ DeleteCases[Sort@VertexList[gr],
n_ /; MemberQ[EdgeList[gr], n \[DirectedEdge] _]]]},
dist[v_] := Length[spFN[v]] - 1
];


Then dist[v] gives the number of edges between v and the output vertex, which is found by the code

First@DeleteCases[Sort@VertexList[gr],
n_ /; MemberQ[EdgeList[gr], n \[DirectedEdge] _]]


One could check that there is only one output vertex, but it is clearly the case for the OP's graph.

Here's a visualization: Each vertex is labelled by its distance to the output vertex.

GraphPlot[gr,
VertexRenderingFunction -> ({EdgeForm[Black], White, Disk[#1, 0.15],
Black, Text[dist@VertexList[gr][[#2]], #1]} &)]


• if I wanted to bring back the values ​​of the distances in the original matrix, substituting the values ​​of 1, how should I do? Jun 17, 2014 at 9:43
• @user15850 Is this what you seek?: ReplacePart[matOP, MapIndexed[#1 -> dist[First@#2] &, pos]] Jun 17, 2014 at 14:19
• Yes. Thank you very much for the help! Jun 17, 2014 at 14:28
• @user15850 You're welcome. Jun 17, 2014 at 14:46