HorizontalCutExplorer issue using binary_partition_tree_MumfordShah_energy

[lefevrej]

There is an issue when trying to instanciate HorizontalCutExplorer with tree and altitudes obtained with binary_partition_tree_MumfordShah_energy. It happened using version 0.5.1.

The code that can be used to reproduce this issue is :

grad = np.load("./pred_x_mala.npy")
grad = grad[0:100,  0:100]

size = grad.shape
graph = hg.get_4_adjacency_graph(size)
edge_weights = hg.weight_graph(graph, grad, hg.WeightFunction.mean)

tree, altitudes = hg.binary_partition_tree_MumfordShah_energy(graph, grad)

explorer = hg.HorizontalCutExplorer(tree, altitudes)

RuntimeError Traceback (most recent call last)

[<ipython-input-22-6a83b33a3683>](https://localhost:8080/#) in <module>()  ----> 1  
[data.zip](https://github.com/higra/Higra/files/4545966/data.zip)

explorer  =  hg.HorizontalCutExplorer(tree,  altitudes)  

RuntimeError: tree in file /tmp/pip-req-build-sigqrb0e/include/higra/algo/../structure/tree_graph.hpp(line:122): nodes are not in a topological order (last node is not a root)

The data I used : data.zip

[PerretB]

I confirm that I can reproduce the bug, I will investigate.

[PerretB]

Ok, in fact it is not really a bug but there are some missing precondition checks.

Indeed, binary_partition_tree_MumfordShah_energy cannot ensure that the altitudes of the produced tree will be increasing : there may be a node n such that altitudes[n] > altitudes[tree.parent(n)] (the Mumford-Shah energy is not increasing).

But HorizontalCutExplorer expect increasing altitudes: otherwise we cannot speak of "a cut at a given altitude". Your options are:

1) You can ignore the altitudes returned by "binary_partition_tree_MumfordShah_energy" and create your own increasing altitudes. For example you can use the topological_height:

new_altitudes = hg.accumulate_and_add_sequential(tree, np.ones(tree.num_vertices()), np.zeros(tree.num_leaves()), hg.Accumulators.max)

2) You can try to make the altitudes increasing. For example the smallest increasing altitudes which are larger than your non increasing altitudes are:

new_altitudes = hg.accumulate_and_max_sequential(tree, altitudes, altitudes[:tree.num_leaves()], hg.Accumulators.max)

3) You can remove the nodes where the increasingness is violated : this is bit more involving.

[lefevrej]

Thanks for your answer and your solutions !