I am in a situation where I’m using mst() (in igraph R) but on directed graphs. I know that this is not formally correct, and that e.g., networkx can find arborescences which might be more ‘correct’. However the minimum directed tree in this case would not necessarily admit directed paths between all vertices, and while my source graph is not symmetrical (A→B has a different cost than B→A) an approximation based on treating a directed graph as undirected is good enough for my purposes.
What is unclear to me is how exactly igraph treats a directed graph as undirected in this case. The R documentation doesn’t even mention this. The C source code has in comments that “Directed graphs are treated as undirected for this computation.” but I am not familiar enough with the code to parse out exactly how that is happening. Does it take the lower cost connection between A→B and B→A, the first one it comes across (basically the upper or lower triangle of the adjacency matrix), some average of the two possible costs, or something else?
I’d like to be able to be precise about this in a paper I’m writing up where we’ve used igraph this way.
During spanning tree computations (both minimum spanning tree and other algorithms), edge directions are simply ignored in directed graphs. Imagine drawing the graph and simply omitting arrowheads. The algorithm works with what you’d get this way.
The directed version of minimum spanning trees, often called a minimum spanning arborescence, are not currently implemented in igraph. I’d love to see these implemented (see Edmonds’s algorithm), but I certainly don’t have the capacity at this moment. This concept is sufficiently different from undirected spanning trees that it would be exposed as a different function (notmst()).
Side note: I see that the forum software flagged several of your posts as spam. I tried to approve these, but something seems wrong: I still can’t see them appearing. I’ll look into fixing this as soon as I get to it.
Concerning MSTs, I suppose that means that if there is a directed link in each direction between two vertices (e_ij and e_ji) then the algorithm will land on whichever one is the lower cost in arriving at the MST.
Concerning minimum cost arborescences networkx has an implementation, which may help in developing one for igraph.