# 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. – Yves Klett Jun 9 '14 at 10:26
@YvesKlett I edited with the link.. :) I guess it's "enough" – Öskå Jun 9 '14 at 10:26
@Öskå in any case, is the Q clear to you? – Yves Klett Jun 9 '14 at 10:32
@YvesKlett Apart from what I already commented above.., I don't see what could be the answer :) – Öskå Jun 9 '14 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. – Michael E2 Jun 9 '14 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? – user15850 Jun 17 '14 at 9:43
@user15850 Is this what you seek?: ReplacePart[matOP, MapIndexed[#1 -> dist[First@#2] &, pos]] – Michael E2 Jun 17 '14 at 14:19
Yes. Thank you very much for the help! – user15850 Jun 17 '14 at 14:28
@user15850 You're welcome. – Michael E2 Jun 17 '14 at 14:46