Hello,
I was wondering if in igraph, we have a funcion to compute the spanning tree of a graph with the root as parameter?
I saw unfold_tree but it adds vertex. Is it not possible to have the equivalent without the added vertex?
Regards,
You can get a spanning tree using spanning_tree.
You can always consider any tree as rooted in a particular vertex. So the question is what are you trying to do exactly?
Or perhaps you were simply looking for a breadth first search? You can do that using bfs. You can indicate a root vertex that is used to start the BFS from.
@vtraag Actually, it might not be a bad idea to add a “root” parameter to start computing the tree from. This way, one could easily and quickly compute a spanning tree of the connected component that contains a certain vertex. This is how igraph_random_spanning_tree (which I contributed) works. Of course, the same result is already achievable with only slightly more trouble. This would only add a minor convenience.
@ElemenT5ven Can you clarify what you are looking for? As @vtraag said, any vertex of an undirected tree can be considered to be its root.
It would be good to have the same interface as for igraph_random_spanning_tree indeed.
Hello,
We are trying to generate the spanning tree of our graph by a BFS with the root vertex as parameter.
So we did a loop on the list of parents to build the edges of the tree
But it was really slow
We were wondering if we had a better way to do that in python
By the way,
We can t understand why we get an unknown vertex in the list of the start indices of the layers, here in the exemple it’s 8
@ElemenT5ven Can you explain in more detail what you mean when you say that you want to be able to choose the root? It’s still not clear to me if you want specifically a BFS tree (you did not say this in the original message). Otherwise, any vertex can be considered the root. Trees don’t naturally have roots.
I cannot tell if you started using bfs because that’s what you wanted from the start or because of the comments we made above.
I am not that familiar with the Python interface specifically, but given parents=[2, 0, 2, 0, 3, 7, 5, 1] from your example, you can do something like g = Graph(zip(range(7), parents)).simplify().
The simplify() was needed because the parent of the root vertex is marked as itself.
There may be a better way that I am not aware of.
Personally, I was quite confused by the description “The start indices of the layers in the vertex list”. I was not sure what it was. @tamas perhaps the docs can be improved a bit?
After staring at it for a while, I can see that the differences of consecutive items in the list are the number of vertices in each layer of the BFS tree. These are not vertex indices. That the last two elements are 7 and 8 means that the last layer has 8-7 = 1 element.
In other words, if b is the vector of vertex IDs in the order that they were visited in, the last layer is b[7:8]. The number 7 is the index within b where the last layer starts.