|
What does edge_values for an UndirectedGraph mean? how is it different from the edge_weights? I am asking this in context of making a weighting function for a binary partition tree |
Replies: 7 comments
|
Both are synonyms. Normally, I prefer "edge_weights" over "edge_values", sorry the documentation of binary_partition_tree is not very consistent on this point. |
|
My bad : I think that you were indeed talking about the example about average linkage given in the documentation: things are a bit confusing here. In this context, imagine that we are merging clusters A and B giving the new cluster C. Then we want to compute the weight of the edge between the new cluster C and another neighboring cluster D. For average linkage this edge weight is defined as the average weights of all edges linking a vertex in C to a vertex in D. For efficiency reasons we cannot use this formula as this would require to find all such edges. Instead we want to deduce it from the weights of the edges A<->D and B<->D, but in order to do this we need another information: how many edges link A to D (denoted n_AB) and how many link B to D (denoted n_BD). Then the weight of the edge C<->D is (w(A<->D) * n_AD + w(B<->D) * n_BD) / ( n_AD + n_BD ) (weighted average...). In the example edge weights are stored in the array "edge_values" and number of edges are stored in the array "edge_weights" : hence the confusion. |
|
Thanks for the clarification @PerretB. I ended up using binary_partition_tree_complete_linkage. I have another query, first I constructed a 4-adjacency graph using hg.get_4_adjacency_graph() and constructed the binary partition tree with complete linkage distance. I got a rather conspicuous tree, one of the children of the tree was a leaf. Do you think this is normal behaviour for a BPT? If not, what can be the issue? |
|
In Higra, the leaves of a hierarchy corresponds to the vertices of the graph it was built from. So if you start from a graph with n vertices, a binary partition tree will have 2 *n -1 nodes and the first n nodes are leaves which correspond to the n vertices of the graph. |
|
I am sorry, i wanted to say one of the children of the root of the tree was a leaf, any views on that? |
|
It is possible if e.g. the minimum of the weights of the edges attached to this vertex is larger than the weight of any other edges in the graph. From my experience, this is not an uncommon situation if you compute, for example, a naive RGB gradient on an image. |
|
I understand your point, thank you so much for the clarification! |
My bad : I think that you were indeed talking about the example about average linkage given in the documentation: things are a bit confusing here.
In this context, imagine that we are merging clusters A and B giving the new cluster C. Then we want to compute the weight of the edge between the new cluster C and another neighboring cluster D.
For average linkage this edge weight is defined as the average weights of all edges linking a vertex in C to a vertex in D. For efficiency reasons we cannot use this formula as this would require to find all such edges. Instead we want to deduce it from the weights of the edges A<->D and B<->D, but in order to do this we need another information: how m…