Do we have anything like that? All I can find is the minimum spanning tree function, which roots it wherever it wants.
I need this for the minimum cycle basis PR.
Thank you!
The minimum spanning tree function creates a new igraph_t object. Creating new graphs should not be necessary to find a cycle basis.
You will need to do a breadth first search. I expect igraph_bfs not to be a perfect fit for this use case, so I would write an appropriate version from scratch.
Just to confirm. We don’t have any function that finds a shortest path tree rooted at a specific vertex right?
I’m not sure what you mean by “should not be necessary”: nothing is necessary in life except oxygen and food, but tools help keep the house tidy. Are you familiar with the algorithm I’m trying to implement?
No, there is no function that constructs a new graph (tree) which is a shortest path tree.
It will be inefficient to construct a new graph. I would not prefer an implementation that does that.
Thank you.
I agree it would be best to avoid that, however the algorithm is not trivial, not just one bfs.
If you are concerned it’d be great if you could have a look at the PR and comment or, even better, implement some of those functions. I’m sure you could do some of that better than myself 
To be clear, the signature for finding the minimum spanning tree function is
int igraph_minimum_spanning_tree(const igraph_t* graph,
igraph_vector_t* res, const igraph_vector_t* weights)
In other words, it does not construct a new graph.
In fact, I don’t understand why the function igraph_minimum_spanning_tree_prim is there, which has the signature
int igraph_minimum_spanning_tree_prim(const igraph_t *graph, igraph_t *mst,
const igraph_vector_t *weights)
and which does not do much more than calling igraph_minimum_spanning_tree and then using the returned edges to build a new graph. This is trivial, and can be left to a user of igraph. Moreover, the naming is rather unclear, because igraph_minimum_spanning_tree_prim suggests it simply uses a specific algorithm, but does the same, while in reality, it does something else, namely creating a subgraph. I propose we remove igraph_minimum_spanning_tree_prim.
Moreover, it seems that @iosonofabio needs rooted trees that represent the shortest distance to vertices from a given vertex. In directed graphs, such trees depend on the vertex that is used as a root. To me, it would make sense to have an implementation of igraph_minimum_spanning_tree that allows you to indicate a root vertex (or vertices in the case of multiple components) and that works on directed graphs. Since @iosonofabio is working on that, wouldn’t it make sense to also include that as a public function, instead of just an internal function?
Yes in fact I have added my first try for that function to the cycle basis PR, it just swaps vertex indices to enforce a root, happy to move it to the other file and expose it as API if you guys think it work as expected!
1 Like