1
$\begingroup$

I would like to use edge-direction to distinguish between parents and children in a given spanning tree. When choice of root-node is not unique FindSpanningTree returns the trees as undirected graphs, but my algorithms would be easier to implement if the edge-directions of the spanning-tree graph imposed a unique tree structure.

$\endgroup$

2 Answers 2

1
$\begingroup$

My IGraph/M package has a function specifically for orienting trees away from your chosen root. As you say, this can be very useful to distinguish between "parents" and "children" in rooted trees, and this is exactly why I implemented the function.

Here's an example:

IGOrientTree[IGTreeGame[5], 3,
 VertexLabels -> "Name", GraphLayout -> "LayeredDigraphEmbedding"]

enter image description here

IGTreeGame[5] generates a random 5-vertex tree and IGOrientTree[..., 3] orients edges way from vertex 3 (essentially making 3 the root of the tree).


Some warnings to those who would use @thorimur's solution of starting with a directed graph:

  • The directed spanning tree problem is quite different form the undirected one, and is often solved using Edmond's algorithm. Be aware that by giving a directed input to FindSpanningTree, you are forcing Mathematica to use an entirely different algorithm.

  • This algorithm can also be chosen explicitly in FindSpanningTree using Method -> "MinimumCostArborescence". However, in Mathematica 12.1 and prior versions it is broken and will return incorrect result. In Mathematica 12.2 it was fixed.

  • As OP's followup question shows, the function is still broken for negative weights in Mathematica 12.3.1.

Overall, if you are looking for spanning trees in undirected graphs, I suggest not using directed graphs at all. Just orient the edge after the spanning tree was found.

$\endgroup$
1
$\begingroup$

If you don't need to specify the root, simply convert to a directed graph first:

FindSpanningTree @ DirectedGraph @ g

(This will replace each undirected edge with two antiparallel directed edges, and so the resulting tree will be directed.)

If you do want to specify that the root is v:

FindSpanningTree[{DirectedGraph[g], v}]
$\endgroup$
2
  • 1
    $\begingroup$ I actually tried this beforehand but was getting inconsistent behavior. The easiest way to reproduce it is by: FindSpanningTree[ Graph[{1 \[DirectedEdge] 2, 2 \[DirectedEdge] 1, 2 \[DirectedEdge] 3, 3 \[DirectedEdge] 2, 1 \[DirectedEdge] 3, 3 \[DirectedEdge] 1}, EdgeWeight -> {-1, -1, -2, -2, -3, -3}]] Apparently FindSpanningTree does not like the combination of directed graphs and negative weights. $\endgroup$ Aug 2, 2021 at 5:43
  • 1
    $\begingroup$ @user3257842 oo, wasn't aware of this, yikes! it's a bit of a hack, but i suppose one could Rescale the edgeweights first—though I imagine @Szabolcs solution is computationally superior, given their description of what happens :) $\endgroup$
    – thorimur
    Aug 2, 2021 at 23:47

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.