2
$\begingroup$

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}]]

enter image description here

$\endgroup$
8
  • $\begingroup$ The code you are showing seems to be from @Öskå´s answer in the linked thread, and you should attribute it accordingly. $\endgroup$
    – Yves Klett
    Jun 9, 2014 at 10:26
  • 1
    $\begingroup$ @YvesKlett I edited with the link.. :) I guess it's "enough" $\endgroup$
    – Öskå
    Jun 9, 2014 at 10:26
  • $\begingroup$ @Öskå in any case, is the Q clear to you? $\endgroup$
    – Yves Klett
    Jun 9, 2014 at 10:32
  • $\begingroup$ @YvesKlett Apart from what I already commented above.., I don't see what could be the answer :) $\endgroup$
    – Öskå
    Jun 9, 2014 at 10:34
  • $\begingroup$ 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. $\endgroup$
    – Michael E2
    Jun 9, 2014 at 14:23

1 Answer 1

2
$\begingroup$

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]} &)]

Mathematica graphics

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.