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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\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}]
Improve this answer
$\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$ Commented 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$ Commented Aug 2, 2021 at 23:47

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.