6
$\begingroup$

The on-line documentation for FindShortestPathTree (part of the Combinatorica package) says:

"ShortestPathSpanningTree has been superseded by FindSpanningTree"

I don't understand how to use FindSpanningTree to construct the tree of shortest paths from a given vertex in a directed graph.

Consider the small exanple:

smallgraph = 
 Graph[{DirectedEdge[1, 2], 
        DirectedEdge[2, 3], 
        DirectedEdge[1, 4], 
        DirectedEdge[4, 3]}, 
        EdgeWeight -> {1, 1, 2, 1}, 
        VertexLabels -> "Name", EdgeLabels -> "EdgeWeight"]

The tree of shortest paths from vertex 1 in this graph is

 Graph[{DirectedEdge[1, 2], 
        DirectedEdge[2, 3], 
        DirectedEdge[1, 4]}, 
        EdgeWeight -> {1, 1, 2}, 
        VertexLabels -> "Name", EdgeLabels -> "EdgeWeight"]

That's not what FindSpanningTree produces.

FindSpanningTree[{smallgraph,1},EdgeWeight -> {1, 1, 2, 1}]

yields

fstree = 
   Graph[{DirectedEdge[1, 2], 
          DirectedEdge[1, 4], 
          DirectedEdge[4, 3]}, 
          EdgeWeight -> {1, 1, 2, 1}, 
          VertexLabels -> "Name", EdgeLabels -> "EdgeWeight"]

How to use FindSpanningTree to construct a tree of shortest paths? Is ShortestPathSpanningTree truly superseded by FindSpanningTree?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ In your code you never use FindSpanningTree. The graph produces by FindSpanningTree[smallgraph] has the same total weight as the one that you propose. $\endgroup$
    – Bob Hanlon
    Commented Jul 23, 2022 at 19:34
  • $\begingroup$ Thanks for the comment. You are absolutely correct that the two graphs have the same total weight. The key difference here, apparently lost in the transition from the Combinatorica package, is that FindSpanningTree is only concerned with the total weight of edges. ShortestPathSpanningTree imposes different criteria: It insists that the path to each vertex be a shortest path. My apologies, I mistyped the name of the procedure producing fstree. It should have been FindSpanningTree. I've corrected that. $\endgroup$
    – user46831
    Commented Jul 25, 2022 at 18:10

2 Answers 2

Reset to default
9
$\begingroup$

My IGraph/M package provides replacements for most of the graph theory functions of Combinatorica.

It includes IGShortestPathTree:

Example use on a weighted graph, rooting the tree in vertex 1:

gr = IGDistanceWeighted@IGDelaunayGraph@RandomPoint[Disk[], 40];

HighlightGraph[
 gr,
 {IGShortestPathTree[gr, 1], {1}},
 GraphHighlightStyle -> "DehighlightFade"
 ]

enter image description here

This function produces a tree with the same directedness as the original graph. If you want a directed graph with edges oriented away from the root, post-process it with IGOrientTree[].

Indeed, the weighted shortest path tree is not the same as the minimum spanning tree, as you can see with

HighlightGraph[gr, IGSpanningTree[gr]]
Improve this answer
$\endgroup$
6
$\begingroup$

Thanks for that. Impressive. An alternative that might be better reflected in the documentation is to use FindShortestPath.

(* FindShortestPath returns a procedure *)
With[{pathfunc=FindShortestPath[smallgraph, 1, All],
     (* Construct weight rules for the graph *)
      edgeweights =Thread[Rule[EdgeList[smallgraph],
                               PropertyValue[smallgraph,EdgeWeight]]]},
     (* For each vertex, recover the path and its length *)
     Map[With[{path=EdgeList[PathGraph[pathfunc[#],
                                     DirectedEdges->True]]},
                {# , path, Plus@@path/.edgeweights}]&,
         VertexList[smallgraph]]]

Alternatively, just return the edges of the tree...

Added in response to User293787's good suggestion:


ClearAll[myShortestPathTree];
(* Given a graph and a vertex in the graph, 
   Return a graph consisting of the edges of a shortest path tree from that vertex
   The optional value DirectEdges determines whether the tree is directed or not *) 
myShortestPathTree[graph_,root_,OptionsPattern[{DirectEdges->True}]]:=
With[(*FindShortestPath returns a procedure that, given a vertex, returns a shortest path to it *)
     {pathfunc=FindShortestPath[graph,root,All],
      directedges = OptionValue[DirectEdges]},
     (* FindShortestPath returns a list of vertices, not the edges of the path, 
        that leaves ambiguity as to whether the edges of the path are directed or not.
        In a multigraph, the list of vertices does not uniquely identify the edges 
        The option DirectEdges, with default value of True, allows the user produce either a directed spanning tree (DirectEdges -> True) or an undirected one*)
    Graph[DeleteDuplicates[
             Flatten[
                   Map[EdgeList[PathGraph[pathfunc[#], DirectedEdges->directedges]]&,
                       VertexList[graph]]]], 
          VertexLabels->"Name"]]
```
Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ (+1) but it would be more useful for other people if you rewrote this as a function myShortestPathSpanningTree[graph_] := .... Ideally that function would return a Graph object. $\endgroup$
    – user293787
    Commented Jul 24, 2022 at 7:09
  • 1
    $\begingroup$ Good suggestion. There is some ambiguity in translating the list of vertices from FindShortestPath into a list of edges. The simple code added above dodges that issue $\endgroup$
    – user46831
    Commented Jul 25, 2022 at 17:45

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.