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$
5
  • $\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$
    – aellab
    May 9, 2017 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$ May 9, 2017 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$
    – aellab
    May 10, 2017 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, 2017 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$
    – aellab
    May 10, 2017 at 8:38

2 Answers 2

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$
4
  • $\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$
    – aellab
    May 10, 2017 at 7:31
  • $\begingroup$ @mich My code performs precisely what you seek. Please see addendum to solution. $\endgroup$ May 10, 2017 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, 2017 at 15:59
  • $\begingroup$ mich and @Szabolcs: OK. Now fixed. $\endgroup$ May 10, 2017 at 16:09

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.