2
$\begingroup$

I have a walk $v_1 \ldots v_n$ on a graph $G$ and I want to apply the following operation to it: I wish to choose two indexes, $l$, $k$, and replace the sub-path from $v_l$ to $v_k$ with one of the shortest paths from $v_l$ to $v_k$, chosen uniformly at random among all such paths.

I would appreciate your assistance in implementing this in Mathematica!

I found a question related to mine (how to find all shortest paths) here: Finding all shortest paths between two vertices, but I am not sure how to utilize the answer there to select, uniformly at random, a path among all paths generated by the algorithm there.

$\endgroup$
  • $\begingroup$ I'm a Mathematica newbie, so I guess I am stuck "everywhere". In particular I have a problem generating all relevant shortest paths and choosing from them at random. $\endgroup$ – mich May 9 '17 at 22:15
  • $\begingroup$ Your question is unclear. To "replace" the sub-path means replacing vertexes and edges, but the sub-path already exists. Draw by hand (if necessary) exactly what you're seeking. $\endgroup$ – David G. Stork May 9 '17 at 23:42
  • $\begingroup$ I have a walk $v_1 \ldots v_i v_{i+1} \ldots v_j \ldots v_n$. I want to generate a new walk, $v_1 \ldots v_i u_{i+1} u_{i+2} \ldots u_{j-1} v_j \ldots v_n$, where $u_{i+1} \ldots u_{j-1}$ is the shortest path from $v_i$ to $v_j$, chosen uniformly at random among all such shortest paths. $\endgroup$ – mich May 10 '17 at 7:33
  • $\begingroup$ I suggest to rewrite your question and focus on the main issue: How to find all shortest paths between two vertices? Show an example graph with multiple shortest paths between the same two vertices (but something more complex than CycleGraph[4]) $\endgroup$ – Szabolcs May 10 '17 at 8:36
  • $\begingroup$ Dear @Szabolcs, I don't think that is the main issue; you can find an algorithm for all shortest paths here mathematica.stackexchange.com/questions/4128/…. The issue I am struggling with is integration, since I am not familiar withe Mathematica's syntax. I am not sure how to utilize the algorithm in e.g. the linked answer to randomly choose one of these paths! (In retrospect I will edit my post to include this helpful link.) $\endgroup$ – mich May 10 '17 at 8:38
4
$\begingroup$

Perhaps this will be easier to follow.

This function finds all shortest paths in graph g between vertices s and t, and returns them in a list.

findAllShortestPaths[g_, s_, t_] := 
 FindPath[g, s, t, {GraphDistance[g, s, t]}, All]

This function takes a graph, a walk, and two indices into the walk array: k and l. Then it replaces the section between the kth and lth elements of the walk, in the manner you described.

replacePath[g_, walk_, {k_, l_}] :=
 Join[
   Take[walk, k-1],
   RandomChoice@findAllShortestPaths[g, walk[[k]], walk[[l]] ],
   Take[walk, {l+1, -1}]
 ]

Example:

SeedRandom[42];
g = RandomGraph[{10, 20}, VertexLabels -> "Name"]

findAllShortestPaths[g, 1, 2]
(* {{1, 10, 2}, {1, 6, 2}} *)

walk = {7, 1, 10, 2};

HighlightGraph[g, PathGraph[walk]]

replacePath[g, walk, {2, 4}]
(* {7, 1, 6, 2} *)
$\endgroup$
1
$\begingroup$

Here is a graph:

g = RandomGraph[{20, 50}];

Here is the path between $\nu_l = 5$ and $\nu_n = 9$ (chosen arbitrarily):

mypathlist = FindPath[g, 5, 9][[1]]

(* {5, 2, 3, 6, 4, 1, 18, 10, 7, 9} *)

Here are two points along that path chosen arbitrarily:

myvertexes = RandomSample[mypathlist, 2]

(* {2, 7} *)

Here is the shortest path in $g$ between these vertexes:

mynewpathsegment = 
 FindShortestPath[g, myvertexes[[1]], myvertexes[[2]]]

(* {2,7} *)

If you want to get all such shortest paths:

myshortestlist = FindPath[gg, myvertexes[[1]], myvertexes[[2]], {GraphDistance[g, myvertexes[[1]], myvertexes[[2]]]}, All]

Then choose one of these shortest paths randomly:

myfinalshortpath = RandomChoice[myshortestlist]

Here is the original path with the new shortest path replacing the existing path segment:

mypathlist /. 
{x__, PatternSequence[myvertexes[[1]], __, myvertexes[[2]]], z__} -> 
{x, Sequence[myvertexes[[1]], myvertexes[[2]]], z}

(* {5, 2, 7, 9} *)


Note that this code automatically selects one of the shortest paths, if there are indeed multiple shortest paths. You can verify this with this simple example:

gg = Graph[{1 -> 2, 1 -> 3, 3 -> 4, 2 -> 4}]

FindShortestPath[gg, 1, 4]

(* {1, 2, 4} *)

(but not {1,3,4}).

$\endgroup$
  • $\begingroup$ Hi David, thank you for your help. Your answer almost achieves what I'm trying to do, but instead of "mynewpathsegment = FindShortestPath[g, myvertexes[[1]], myvertexes[[2]]]", I want to generate a list of all shortest paths from $v_i$ and $v_j$, then choose one shortest path among those, at random .Do you have any idea how I might accomplish that? $\endgroup$ – mich May 10 '17 at 7:31
  • $\begingroup$ @mich My code performs precisely what you seek. Please see addendum to solution. $\endgroup$ – David G. Stork May 10 '17 at 15:52
  • $\begingroup$ "Note that this code automatically and randomly selects one of the shortest paths," @David, it selects one of the shortest paths, but not randomly. Each time you run this code on the same graph and same starting and ending vertices, it returns the same shortest path. That is the problem the OP was referring to. Identifying multiple shortest paths between the same points in important in many applications, e.g. in betweenness calculations. $\endgroup$ – Szabolcs May 10 '17 at 15:59
  • $\begingroup$ mich and @Szabolcs: OK. Now fixed. $\endgroup$ – David G. Stork May 10 '17 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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