Welcome to Higra’s documentation!¶
Changelog¶
0.6.4¶
Add function to compute the line graph of a graph
line_graph()
#239Add function to extract a subtree from a tree
sub_tree()
#238Add new fast lowest common ancestor algorithm
lowest_common_ancestor_preprocess()
with \(O(n)\) time preprocessing and average \(O(1)\) time query (based on sparse table with blocks). The expected speedup is comprised between 1.2 and 1.8 compared to the previous method (parse table without block wich is still available). #237Add options to set a global thread number limit
set_num_threads()
#234
0.6.2¶
Add support for Python 3.9, remove support of Python 3.5` #233
0.6.1¶
Breaking changes¶
C++ only: the children relation of trees is not computed automatically anymore, a call to the member function
compute_children
is required before accessing to any children information of a tree, see documentation Children relation #228
Other changes¶
Function
bpt_canonical()
can now process a graph given as a edge list (arrays of source and target vertices) #230Add functions
sources()
andtargets()
to the classesUndirectedGraph
andTree
which will returns views whenever possible #230Add options for memory preallocation in
UndirectedGraph
constructor #232Improve performance of regular grid graphs #231
Improve memory usage of marginal accumulators #228
Remove the need of the children relation anymore of trees in several functions #228
Bugfix: Regular grid graph will now always fulfils the
CptGridGraph
concept #229
0.6.0¶
Breaking changes¶
The functions
filter_non_relevant_node_from_tree()
,filter_small_nodes_from_tree()
, andfilter_weak_frontier_nodes_from_tree()
now return canonized tree by default (old behaviour is obtained with the argumentcanonize_tree=False
) #221C++ only: the function
bpt_canonical
does not compute an explicit representation of the minimum spanning tree. The mst can still be reconstructed with the fieldmst_edge_map
in the result using the new functionsubgraph_spanning
f50ebc8C++ only: fields of the class
regular_graph
are now private with public const accessors #211
Other changes¶
Major Python classes (Trees, graphs, …) are now pickable #212 and #214
Python classes now support dynamic attributes and higra attributes are now stored directly in the objects dictionaries with a direct access as class members. #209 and #210
Function
bpt_canonical()
now supports: construction of the tree based on an arbitrary given ordering, avoid the explicit computation of the minimum spanning tree, multidimentional edge weights (with lexicographic sorting). The documentation has also been improved. #222Fast lowest ancestor computation is now better integrated to the
Tree
class. Callinglowest_common_ancestor_preprocess()
will now make any call tolowest_common_ancestor()
to use the preprocessing #216Add parallel sorting functions
sort()
andarg_sort()
(also support lexicographic ordering). #219Add function
subgraph()
to extract the subgraph induced by a set of edges from an undirected graph 4cfa9acFunctions for watershed hierarchies in Python can now return the non canonized tree (option
canonize_tree=False
) #220Function
canonize_hierarchy()
can now return thenode_map
which associates any node of the canonized tree to a node of the original tree. 5701d29Fix bug in
filter_small_nodes_from_tree()
when the base graph is a region adjacency graph #215
0.5.3¶
Fix bug in
watershed_hierarchy_by_attribute()
: on some conditions a large minima could be split in two or more regions. #205
0.5.2¶
Add function
tree_monotonic_regression()
: perform regression on a tree with an increasingness constraint #198Add attribute
attribute_moment_of_inertia()
: first Hu moment on hierarchies constructed on 2d pixel graphs. #197Add attribute
attribute_topological_height()
: number of edges on the longest path from a node to the leaf. #194Improve support for regular graphs: add functions
as_explicit_graph()
(convert an implicit graph to an explicit graph),mask_2_neighbours()
(create an neighbour list from an adjacency mask),get_nd_regular_graph()
andget_nd_regular_implicit_graph()
(create a regular implicit or explicit regular graph) #204Improve conversions functions between adjacency matrices and undirected graphs: improve functions
adjacency_matrix_2_undirected_graph()
andundirected_graph_2_adjacency_matrix()
(support for Scipy sparse matrix), andmake_graph_from_points()
(add symmetrization strategies). #201Improve documentation of
binary_partition_tree()
, fix typos in Trees, add section Troubleshooting. #199 #196Add altitudes increasingness assertions in several functions #193
Fix incorrect overload resolution in
as_explicit_graph()
when seeds are not of typenp.int64
#203Fix incorrect number of regions computation in fragmentation curves when groundtruth labels are not contiguous Hierarchy fragmentation curve #200
Fix
delinearize_vertex_weights()
not supporting Numpy arrays as shapes. #188Fix
save_tree()
incorrectly failing with no tree attributes. #181
0.5.1¶
Decrease ABI compatibility of linux wheels to 8 (G++ 4.9) #177
0.5.0¶
Breaking change¶
Removed overload of function
weight_graph()
taking a custom weighting function. An equivalent, and much efficient, behavior can be achieved be applying a vectorized function on the edge list (seeedge_list()
) 5914574Removed support for Python 3.4 #174
Other changes¶
Add support for Python 3.8 #174
Fix and add more efficient implementation of seeded watershed labelisation
labelisation_seeded_watershed()
#173Parallelize several algorithms with Intel TBB (parallel sort, hierarchy construction, fast LCA, graph weighting) #168 #169
Add support for Intel Threading Building Blocks (TBB), see usage in Installation #168 #175
Update third party libs #170
Fix agglomerative clustering when the input graph has duplicated edges Binary partition hierarchy #167
Fix missing overloads for unsigned types in
weight_graph()
#166Fix a bug in hierarchical watershed when leaves had non zero values Watershed hierarchy #165
0.4.5¶
Add new notebook: *Visualizing hierarchical image segmentations* #159
Add hierarchical cost function
tree_sampling_divergence()
#158Add attribute
attribute_tree_sampling_probability()
9faf740Add attribute
attribute_children_pair_sum_product()
0c6c958Improvements in documentation #157
Add hierarchy algorithm
component_tree_multivariate_tree_of_shapes_image2d()
#156Fix return policy in
parents()
, now returns a non writable reference e3eb5aaAdd option to deactivate immersion in tree of shapes 9efb6b6
Add algorithm
tree_fusion_depth_map()
11e4f53
0.4.4¶
Fix codecov incorrectly including third party libs #152
Add hierarchical cost
dasgupta_cost()
#151Add new attribute
attribute_child_number()
#149Fix bug in
simplify_tree()
#148 and #150Add argmin and argmax accumulators #146
Add new notebooks: PRL article illustrations and Astromical object detection with the MaxTree #145 and #155
Update third party libs #141
0.4.2¶
Breaking change¶
Rename function attribute_mean_weights into
attribute_mean_vertex_weights()
#136
Other changes¶
Add SoftwareX illustrations notebook #140
Replace specialized C++ bindings for hierarchical watershed by a generic calls to
watershed_hierarchy_by_attribute()
#139Fix inconsistency between Python and C++ definitions of
attribute_volume()
#138Separate code and documentation on graph and tree attributes #137
Fix bug in
attribute_mean_vertex_weights()
#136
0.4.1¶
Add function
accumulate_on_contours()
. #134Better handling of null perimeter in
attribute_contour_strength()
. #133Add links to Python notebooks in the documentation. #132
Fix bug in
common_type()
support for bool type was missing. #131Fix bug in
attribute_contour_length()
with tree of shapes when interpolated are removed. #129
0.4.0¶
Breaking change¶
Refactor attributes related to perimeter: there is now a single homogeneous function
attribute_contour_length()
that replaces attribute_perimeter_length, attribute_perimeter_length_component_tree, and attribute_perimeter_length_partition_tree #121 and #124Add decorator
auto_cache()
for autocaching of function results which replaces the decorator data_provider. #122 and #127
Other changes¶
Add a Cookiecutter project for c++ higra extension development Higracppextensioncookiecutter
Add more documentation for installation and compiling #123
Fix bug with integer data in
attribute_gaussian_region_weights_model()
#126Fix bug in graph associated to the
component_tree_tree_of_shapes_image2d()
#120Improve algorithm for
attribute_extrema()
#119Moved repository to higra Github organization #118
0.3.8¶
Add attributes:
attribute_height()
,attribute_extrema()
,attribute_extinction_value()
, andattribute_dynamics()
#110Fix tree category propagation #109
0.3.7¶
Hardening: add range checks in various Python bindings #107
Bundle
Higra
and third party libraries into pip wheel for easy C++ extension development:get_include()
,get_lib_include()
,get_lib_cmake()
#106Make
deleted_nodes
parameter ofreconstruct_leaf_data()
optional #105
0.3.6¶
Add
plot_graph
andplot_partition_tree()
#104Add
num_children()
overload that returns the number of children of every non leaf nodes #101
0.3.5¶
Breaking change¶
Rename
quasi_flat_zones_hierarchy
toquasi_flat_zone_hierarchy()
https://github.com/PerretB/Higra/commit/8aa95694fc7b8b59fd61ffe264943586e935a686
Other changes¶
Add
exponentiallinkage
for agglomerative clusteringbinary_partition_tree_exponential_linkage()
https://github.com/PerretB/Higra/commit/a523d8cc484576907e356113dde23adf832eb13bAdd
canonize_hierarchy()
https://github.com/PerretB/Higra/commit/9a2c8d9e103fc3444f733e0c5a83b2bd775fdea8
0.3.4¶
Add
filter_non_relevant_node_from_tree()
,filter_small_nodes_from_tree()
, andfilter_weak_frontier_nodes_from_tree()
https://github.com/PerretB/Higra/commit/521f2416b9b649ace76168728c6d5c06edfde8c6Add
labelisation_horizontal_cut_from_num_regions()
https://github.com/PerretB/Higra/commit/cb9cc0d6ebeaa97f76c60ae1b879f2bfb777c01bAdd
at_least
andat_most
parameters forhorizontal_cut_from_num_regions()
https://github.com/PerretB/Higra/commit/7b5d00422562840de93df9fcef247b27a2d7365dOptimize Horizontal cut explorer construction https://github.com/PerretB/Higra/commit/68128b9f0201360888d7409dad397ceba23b100d
Add
child()
overload that returns the ith child of every non leaf nodes https://github.com/PerretB/Higra/commit/6d47a21e942debfdebb633d6e7b7de88238c30ba
0.3.3¶
Add
accumulate_at()
https://github.com/PerretB/Higra/commit/4dadfad522aa6f8d59fa185507a0941c6fc0d0b0Add
altitude_correction
parameter to Ward linkagebinary_partition_tree_ward_linkage()
https://github.com/PerretB/Higra/commit/196386fe7e96aa9c8d97dd269b40ca022bb5dfbbMake
edge_weights
parameter ofundirected_graph_2_adjacency_matrix()
optional https://github.com/PerretB/Higra/commit/ca195a9d26ef7eaeb24afc7df5db9b90ba8e5ee7
0.3.2¶
Add
dendrogram_purity()
https://github.com/PerretB/Higra/commit/fb84d6fbc908d2bc1971cf6fc840f3da8c23c5bbAdd
random_binary_partition_tree()
https://github.com/PerretB/Higra/commit/46ff1e54d65b658c8d90682761fd77606b764e3cFix altitudes increasingness in Ward linkage
binary_partition_tree_ward_linkage()
https://github.com/PerretB/Higra/commit/82ba29f940a85c328df76bf9642cfc85f0b94dc7
0.3.1¶
Code cleanup #95
Add Ward linkage
binary_partition_tree_ward_linkage()
#94Add
make_lca_fast()
for fast lca result caching #93
0.3.0¶
Breaking change¶
Refactor Python concepts #88
Other changes¶
Fix bug with
saliency()
working on rags #92Fix bug in wheels generation (test result were ignored) #90
Fix bug in
linearize_vertex_weights()
#89Update
xtensor
#86Add
attribute_perimeter_length_component_tree()
#84Add Tree of shapes
component_tree_tree_of_shapes_image2d()
#82
Installation¶
Prebuild binaries¶
The Python package can be installed with Pypi:
pip install higra
Supported systems:
Python 3.5, 3.6, 3.7, 3.8
Linux 64 bits, macOS, Windows 64 bits
Manual build¶
Higra can be build from source directly with cmake or through
a wrapper setuptools
setup.py
script. The latter is especially useful to create wheels (pip installable packages).
Building Higra from source requires:
a c++ 14 compiler (tested with GCC, Clang, Visual Studio 2019)
cmake (2.8+)
Python (3.5+) with Numpy (1.17.3+)
With cmake¶
The following commands will download and build Higra from source.
The python package will be in the directory build/higra/
.
Note that the python package must be findable by Python in order to be used
(e.g. by setting your PYTHONPATH
environment variable).
git clone https://github.com/higra/Higra.git
mkdir build
cd build
cmake DDO_AUTO_TEST=ON DHG_USE_TBB=OFF ../Higra/
make
Sometimes, cmake gets confused when several Python versions are installed on the system.
You can specify which version to use with DPYTHON_EXECUTABLE:FILEPATH=/PATHTOPYTHON/python
, e.g.
cmake DDO_AUTO_TEST=ON DHG_USE_TBB=OFF DPYTHON_EXECUTABLE:FILEPATH=/anaconda3/bin/python ../Higra/
Cmake options:¶
USE_SIMD
(boolean, defaultON
): Use SIMD instructionsDO_CPP_TEST
(boolean, defaultON
): Build the c++ test suitDO_AUTO_TEST
(boolean, defaultOFF
): Execute test suit automatically at the end of the buildHG_USE_TBB
(boolean, defaultOFF
): Use Intel Threading Building Blocks (TBB)
If HG_USE_TBB
is equal to ON
, cmake will try to locate TBB automatically.
TBB path can however be specified manually with the following parameters:
TBB_INCLUDE_DIR
(path): path to TBB include (path containing a folder called tbb that contains TBB header files)TBB_LIBRARY
(path): path to TBB library (path containing tbb.so on Unix or tbb.lib on Windows)
With setuptools¶
The file setup.py
is a thin wrapper around the cmake script.
The following commands will download the library, create a binary wheel and install it with pip.
git clone https://github.com/higra/Higra.git
cd Higra
python setup.py bdist_wheel
cd dist
pip install higra*.whl
In order to activate TBB, one must define the following environment variable before calling setup.py
HG_USE_TBB
(any value): will activate use of TBBTBB_INCLUDE_DIR
(optional, path): path to TBB include (path containing a folder called tbb that contains TBB header files)TBB_LIBRARY
(optional, path): path to TBB library (path containing tbb.so on Unix or tbb.lib on Windows)TBB_DLL
(mandatory on Windows, filepath): path to TBB DLL
Developing c++ extensions¶
While Higra provides many vectorized operators to implement algorithms efficiently in Python, it is possible that some operations cannot be done efficiently in Python.
In such case, the Higracppextensioncookiecutter enables to easily setup and generate c++ extension using Higra with Python bindings.
Python notebooks¶
The following python notebooks contain examples demonstrating Higra usage.
Hierarchy filtering 

Watershed hierarchies 

Connected image filtering with component trees 

Computing a saliency map with the shaping framework 

Filtering with nonincreasing criterion  The shaping framework 

Visualizing hierarchical image segmentation 

Illustrations of SoftwareX 2019 article 

Illustrations of Pattern Recognition Letters 2019 article 

Multiscale Hierarchy Alignment and Combination 

Region Adjacency Graph 

Interactive object segmentation 

Fuzzymarkerbased interactive object segmentation  DGMM 2021 

Astronomical object detection with the MaxTree 

Contour Simplification 
Troubleshooting¶
Error “ImportError: DLL load failed: The specified module could not be found.” on Windows
Make sure that the latest version of Visual C++ Redistributable for Visual Studio 2015 is installed on your computer.
Graphs¶
Important
#include "higra/graph.hpp
Graphs come in three flavours in Higra:
ugraph
represents general undirected graphs (adjacency list).tree
represents undirected connected acyclic rooted graphs (parent array).regular_graph
represents implicit graphs: in such graphs edges are computed on the fly (not stored). For example, they can be used to represent pixel adjacencies in images.
This page presents common functions for the manipulation of graphs.
A dedicated page for the tree
structure, see Trees.
All functions acting on graphs have the same name in C++ and in Python, except for iterators to avoid name collisions with the Boost Graph Library (BGL).
In c++, graph related methods are free functions (as in BGL), while in Python they are member functions.
For example, the function num_vertices
that returns the number of vertices in a graph, will be called:
Important
In c++, one must call the function compute_children
on a tree before using it as a graph.
1  n = graph.num_vertices()

1  auto n = num_vertices(graph);

Vertices¶
Graph vertices are represented by positive integers (index_t
in c++), suitable for array indexing.
Note that the constructor of the ugraph class accepts a single parameter: the initial number of vertices in the graph.
Function 
Returns 
Description 
Available 


new vertex 
add a new vertex to the graph 


void 
add a given number of new vertices to the graph 


positive integer 
Number of vertices in the graph 

Example:
1 2 3 4 5 6 7 8 9  import higra as hg
g = hg.UndirectedGraph()
g.add_vertex()
g.add_vertex()
g.add_vertices(3)
nv = g.num_vertices() # 5

1 2 3 4 5 6 7 8 9 10  #include "higra/graph.hpp"
using namespace hg;
ugraph g;
add_vertex(g);
add_vertex(g);
add_vertices(3, g);
auto nv = num_vertices(g); // 5

Iterating on vertices¶
Function 
Returns 
Description 
Available 


a range of iterators 
iterator on all graph vertices 


a range of iterators 
iterator on all vertices adjacent to the given vertex 

1 2 3 4 5 6 7 8  g = hg.UndirectedGraph()
...
for v in g.vertices():
... # all vertices of g
for v in g.adjacent_vertices(1):
... # all vertices adjacent to vertex 1 in g

1 2 3 4 5 6 7 8 9 10  ugraph g;
...
for(auto v: vertex_iterator(g)){
... // all vertices of g
}
for(auto v: adjacent_vertex_iterator(1, g)){
... // all vertices adjacent to vertex 1 in g
}

Edges¶
Graph edges are composed of a source vertex, a target vertex, and, optionally, an index.
Graphs which have indexed edges provide the following guaranties:
edge indices of a graph
g
are integers (typeindex_t
) comprised between 0 (included) andnum_edges(g)
(excluded);the index of a given edge will never change during the object lifetime.
However, note that in an undirected graph, the edges (x, y)
and (y, x)
have the same index.
All operations are done in constant time.
Function 
Returns 
Description 
Available 


void 
add a new edge to the graph 


void 
add all edges given as a pair of arrays (sources, targets) to the graph 


positive integer 
number of edges in the graph 


vertex index 
source vertex of an edge 


vertex index 
target vertex of an edge 


edge index 
the index of the given edge in the current graph 


edge 
the edge with given index (in an undirected graph, always returns the edge whose source vertex is smaller than the target vertex) 


a pair of arrays (sources, targets) defining all the edges of the graph 
void 

Note that python’s edges are simply tuples whose first value is the source vertex, second value is the target vertex, and third (optional) value is the index.
Example:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  import higra as hg
# create a graph with 4 vertices and no edge
g = hg.UndirectedGraph(4)
# add an edge, between vertex 0 and 1
g.add_edge(0, 1)
# add an edge, between vertex 0 and 1
e = g.add_edge(1, 2)
s = g.source(e) # 1 or equivalently e[0]
t = g.target(e) # 2 or equivalently e[1]
ei = g.index(e) # 1 or equivalently e[2]
# add the two edges (3, 0) and (3, 1)
g.add_edges((3, 3), (0, 1));
ne = g.num_edges() # 4
sources, targets = g.edge_list() # sources = [0, 1, 0, 1], targets = [1, 2, 3, 3]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21  #include "higra/graph.hpp"
using namespace hg;
// create a graph with 4 vertices and no edge
ugraph g(4);
// add an edge, between vertex 0 and 1
add_edge(0, 1, g);
// add an edge, between vertex 0 and 1
auto e = add_edge(1, 2, g);
auto s = source(e, g); // 1
auto t = target(e, g); // 2
auto ei = index(e, g); // 1
// add the two edges (3, 0) and (3, 1)
add_edges({3, 3}, {0, 1}, g);
auto ne = num_edges(g); // 4
auto edges = edge_list(g); // edges.first = {0, 1, 0, 1}, edges.second = {1, 2, 3, 3}

Iterating on edges¶
Function 
Returns 
Description 
Available 


a range of iterators 
iterator on graph edges 


a range of iterators 
iterators on all edges whose target is the given vertex 


a range of iterators 
iterators on all edges whose source is the given vertex 

1 2 3 4 5 6 7 8 9 10 11  g = hg.UndirectedGraph()
...
for e in g.edges():
print(g.source(e), g.target(e))
for e in g.in_edges(1):
... # all edges e such that g.target(e) == 1
for e in g.out_edges(1):
... # all edges e such that g.source(e) == 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14  ugraph g;
...
for(auto e: edge_iterator(g)){
std::cout << source(e, g) << " " << target(e, g) << std::endl;
}
for(auto e: in_edge_iterator(1, g)){
... // all edges e such that target(e, g) == 1
}
for(auto e: out_edge_iterator(1, g)){
... // all edges e such that source(e, g) == 1
}

Degrees¶
Currently, all the graphs are undirected, meaning that the degree, the outdegree and the indegree of a vertex are all equal.
Operations are done in constant time in ugraph
, tree
. Operations are done in time proportional to \(E/V\) in regular_graph
.
Function 
Returns 
Description 
Available 


a positive integer 
number of edges containing the given vertex as either the source or the target 


a positive integer 
number of edges containing the given vertex as the target 


a positive integer 
number of edges containing the given vertex as either the source or the target 

1 2 3 4 5 6 7 8 9 10 11  g = hg.UndirectedGraph()
...
# degree of vertex 1
d1 = g.degree(1)
# in degree of vertex 2
d2 = g.in_degree(2)
# out degree of vertex 3
d3 = g.out_degree(3)

1 2 3 4 5 6 7 8 9 10 11  ugraph g;
...
// degree of vertex 1
auto d1 = degree(1, g);
// in degree of vertex 2
auto d2 = in_degree(2, g);
// out degree of vertex 3
auto d3 = out_degree(3, g);

Weighted graph¶
Higra enforces a strong separation between graphs and weights (on vertices or edges): a graph never stores weights.
Vertex indices and edge indices (except for regular_graph
) enables to have an immediate mapping between vertices
or edges and values stored in an array. The preferred storage for weights are xtensor
containers in c++ and numpy
arrays in python.
1 2 3 4 5  def sum_adjacent_vertices_weights(graph, vertex_weights, vertex):
result = 0
for v in g.adjacent_vertices(vertex);
result += vertex_weights[v]
return result

1 2 3 4 5 6 7 8 9 10  // compute the sum of vertex weights adjacent to given vertex
auto sum_adjacent_vertices_weights(const ugraph &g,
const array_1d<double> &vertex_weights,
index_t vertex){
double result = 0;
for(auto v: adjacent_vertex_iterator(vertex, g)){
result += vertex_weights[v];
}
return result
}

Trees¶
Important
#include "higra/graph.hpp
The tree class is the fundamental structure of many hierarchical representations of graphs. In Higra, a tree is an undirected acyclic rooted graph (see Graphs), augmented with specific functions matching the usual semantic of trees.
As with any graph in Higra, the vertices of a tree (also called nodes) are represented by positive integers suitable for array indexing. Higra’s trees ensure that vertices are are topologically sorted, i.e. that for any vertices \(v1\) and \(v2\), if \(v2\) is an ancestor of \(v1\), then \(v1\le v2\). Moreover, whenever a tree \(t\) is a hierarchical representation of a graph \((V, E)\), then the leaves of \(t\) are equal to \(V\): i.e. there is a direct mapping between the leaves of the tree and the vertices of the graph represented by this tree.
The base of the tree data structure is the parent array: i.e. an array that indicates for each vertex the index of its parent (for convenience, the root of the tree is its own parent). For example, the following tree (leaves are represented by squares, inner nodes by circles, and vertex indices are indicated inside the nodes):
is represented by the following parent array:
node 
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
parent 
7 
7 
8 
8 
8 
9 
9 
11 
10 
10 
11 
11 
Constructor¶
The tree
class has a single constructor that takes a single parameter: the parent array.
Example:
1 2 3 4  import higra as hg
# creates the tree shown in the figure above
g = hg.Tree((7, 7, 8, 8, 8, 9, 9, 11, 10, 10, 11, 11))

1 2 3 4 5  #include "higra/graph.hpp"
using namespace hg;
// creates the tree shown in the figure above
tree t({7, 7, 8, 8, 8, 9, 9, 11, 10, 10, 11, 11});

Basic functions¶
Function 
Returns 
Description 


positive integer 
Number of leaves in the tree 

vertex 
Root node (last node of the parent array) 

vertex 
Parent(s) of the given node(s) 

array of vertices 
The parent array 

boolean 
True if given node(s) is a leaf, False otherwise 
Example:
1 2 3 4 5 6 7 8 9 10 11 12 13  # creates the tree shown in the figure above
t = hg.Tree((7, 7, 8, 8, 8, 9, 9, 11, 10, 10, 11, 11))
t.num_leaves() # 7
t.root() # 11
t.parent(2) # 8
t.parent((0, 11, 8)) # array {7, 11, 10}
t.parents() # array {7, 7, 8, 8, 8, 9, 9, 11, 10, 10, 11, 11}
t.is_leaf(4) # True
t.is_leaf(5) # False
t.is_leaf((0, 11, 8)) # array {True, False, False}

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17  // creates the tree shown in the figure above
tree t({7, 7, 8, 8, 8, 9, 9, 11, 10, 10, 11, 11});
// two set of vertices
array_1d<index_t> vertices{0, 11, 8};
array_1d<index_t> vertices2{8, 11, 7};
num_leaves(t); // 7
root(t); // 11
parent(2, t); // 8
parent(vertices, t); // array {7, 11, 10}
parents(t); // array {7, 7, 8, 8, 8, 9, 9, 11, 10, 10, 11, 11}
is_leaf(4, t); // true
is_leaf(5, t); // false
is_leaf(vertices, t); // array {true, false, false}

Iterators¶
Function 
Returns 
Description 


a range of iterators 
iterator on the leaves of the tree 

a range of iterators (cpp), a list (python) 
iterator from a given node to the root of the tree (both included) 

a range of iterators 
iterator on the nodes of the tree in a topological order 

a range of iterators 
iterator on the nodes of the tree in a reverse topological order 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28  # creates the tree shown in the figure above
t = hg.Tree((7, 7, 8, 8, 8, 9, 9, 11, 10, 10, 11, 11))
for n in t.leaves():
... # 0, 1, 2, ..., 6
for n in t.ancestors(8):
... # 8, 10, 11
for n in t.leaves_to_root_iterator(
include_leaves = True, # optional: include (default) or exclude leaves from the iterator
include_root = True): # optional: include (default) or exclude root from the iterator
... // 0, 1, 2, ..., 11
for n in t.leaves_to_root_iterator(
include_leaves = False,
include_root = False):
... // 7, 8, 9, 10
for n in t.root_to_leaves_iterator(
include_leaves = True, # optional: include (default) or exclude leaves from the iterator
include_root = True): # optional: include (default) or exclude root from the iterator
... // 11, 10, 9, ..., 0
for n in t.root_to_leaves_iterator(
include_leaves = False,
include_root = False):
... // 10, 9, 8, 7

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34  // creates the tree shown in the figure above
tree t({7, 7, 8, 8, 8, 9, 9, 11, 10, 10, 11, 11});
for(auto n: leaves_iterator(t)){
... // 0, 1, 2, ..., 6
}
for(auto n: ancestors_iterator(8, t)){
... // 8, 10, 11
}
for(auto n: leaves_to_root_iterator(t,
leaves_it::include /* optional: include (default) or exclude leaves from the iterator*/,
root_it::include /* optional: include (default) or exclude root from the iterator*/)){
... // 0, 1, 2, ..., 11
}
for(auto n: leaves_to_root_iterator(t,
leaves_it::exclude,
root_it::exclude)){
... // 7, 8, 9, 10
}
for(auto n: root_to_leaves_iterator(t,
leaves_it::include /* optional: include (default) or exclude leaves from the iterator*/,
root_it::include /* optional: include (default) or exclude root from the iterator*/)){
... // 11, 10, 9, ..., 0
}
for(auto n: root_to_leaves_iterator(t,
leaves_it::exclude,
root_it::exclude)){
... // 10, 9, 8, 7
}

Children relation¶
Important
In C++ the children relation is only available on request: one must call the function compute_children
prior
to calling any of the following functions (otherwise the behaviour is undefined). Computing the children relation
is a linear time operation that will require in the order of \(n + 3m\) words of memory where \(n\) is the number
of nodes in the tree and \(m\) is the number of nonleaf nodes (1 word is equal to 64bits on a x64 platform).
The children relation can be cleared to save space with the function clear_children
and the status of the relation
can be checked with the function children_computed
.
In Python the relation is automatically computed when needed, the relation can be cleared with the function clear_children
.
Function 
Returns 
Description 


positive integer 
Number(s) of children of the given node(s) 

vertex 
ith child of the given node(s) 

a range of iterators (cpp), a list (python) 
iterator on the children of the given node 

initialize the children relation (can be called several time safely) 





free up the space used to store the children relation 
1 2 3 4 5 6 7 8 9 10 11  # creates the tree shown in the figure above
t = hg.Tree((7, 7, 8, 8, 8, 9, 9, 11, 10, 10, 11, 11))
t.num_children(8) # 3
t.num_children((0, 11, 8)) # array {0, 2, 3}
t.child(1, 11) # 10
t.child(0, (8, 11, 7)) # array {2, 7, 0}
for n in t.children(8):
... # 2, 3, 4

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24  // creates the tree shown in the figure above
tree t({7, 7, 8, 8, 8, 9, 9, 11, 10, 10, 11, 11});
// IMPORTANT: compute the children relation first
t.compute_children();
t.children_computed(); // true
// two set of vertices
array_1d<index_t> vertices{0, 11, 8};
array_1d<index_t> vertices2{8, 11, 7};
num_children(8, t); // 3
num_children(vertices, t); // array {0, 2, 3}
child(1, 11, t); // 10
child(0, vertices2, t); // array {2, 7, 0}
for(auto n: children_iterator(t, 8)){
... // 2, 3, 4
}
// only if you lack memory and if you are sure that the children relation is not needed anymore
t.clear_children();

Finding nodes¶
Common operations requires to find internal nodes corresponding to particular leaves of the tree. Higra tree offers two helper methods for this:
lowest_common_ancestor
finds the lowest common ancestor between two nodesn_1
andn_2
, i.e. the smallest node of the tree that contains bothn_1
andn_2
; and
find_regions
finds the highest node containing a noden_1
and whose altitude is strictly lower than a given value.
Both functions can operate on scalars or arrays. Both functions have a linear time complexity.
In case of lower common ancestor the helper class lca_fast/LCAFast
(cpp/python) can provide a constant query time in exchange of a
linearithmic time preprocessing.
Function 
Returns 
Description 


node index 
lowest common ancestor(s) of the given pair(s) of nodes 

node index 
highest region(s) containing the given node(s) whose altitude if lower than the given altitude(s) 
1 2 3 4 5 6 7 8  # tree node altitudes
altitudes = numpy.asarray((0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 5))
lca = t.lowest_common_ancestor(2, 5) # 10
lcas = t.lowest_common_ancestor((2, 8, 0), (5, 6, 11)) # (10, 10, 11)
// vertices and altitudes
auto r = t.find_region((2, 8, 0), (1, 6, 2), altitudes) # (2, 11, 7)

1 2 3 4 5 6 7 8 9 10 11 12 13 14  // tree node altitudes
array_1d<double> altitudes{0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 5};
// two set of vertices
array_1d<index_t> vertices1{2, 8, 0};
array_1d<index_t> vertices2{5, 6, 11};
auto lca = lowest_common_ancestor(2, 5, t); // 10
auto lcas = lowest_common_ancestor(vertices1, vertices2, t); // {10, 10, 11}
// vertices and altitudes
array_1d<index_t> vertices3{2, 8, 0};
array_1d<double> alts{1, 6, 2};
auto r = find_region(vertices, alts, altitudes, t); // {2, 11, 7}

Accumulators¶
Tree accumulators enables to efficiently accumulates values from the children of a node and move the accumulated value to this node. They are especially important for writing efficient algorithms in Python by avoiding to use the tree iterators in many common scenarii. Using them in C++ can also be beneficial as they are written to natively and efficiently handle ndimensional data.
Each tree accumulator function has an accumulator
parameter.
Currently, the following accumulators are defined:
mean
: computes the average of the provided value (default value: 0)minimum
: computes the minimum of the provided value (default value: maximal representable value for the specific data type)maximum
: computes the maximum of the provided value (default value: minimal representable value for the specific data type)counter
: computes the number of provided value (default value: 0)sum
: computes the sum of the provided value (default value: 0)prod
: computes the product of the provided value (default value: 1)
Default values and results of the accumulators have the same shape/dimension of the input values, except for the counter accumulator which is always a scalar integer.
Accumulators are wrapped into factories in C++ while the Python interface only exposes an enumeration (real accumulator types are currently not exported in Python).
1  acc = hg.Accumulators.sum

1  auto acc = accumulator_sum();

Parallel accumulator¶
The parallel accumulator defines the new value of a node as the accumulation of the values of its children. This process is done in parallel on the whole tree.
The parallel accumulator pseudocode could be:
1 2 3 4 5 6 7 8 9 10  # input: a tree t
# input: an attribute att on the nodes of t
# input: an accumulator acc
output = empty_like(input)
for each node n of t:
output[n] = acc(input[t.children(n)])
return output

The following example demonstrates the application of a parallel sum accumulator on a simple tree:
1 2 3 4 5 6 7  # tree in the above example
t = hg.Tree((5, 5, 6, 6, 6, 7, 7, 7))
input = numpy.ones((t.num_vertices(),))
result = hg.accumulate_parallel(t, input, hg.Accumulators.sum)
# result = (0, 0, 0, 0, 0, 2, 3, 2)

1 2 3 4 5 6 7  // tree in the above example
tree t({5, 5, 6, 6, 6, 7, 7, 7});
array_1d<index_t> input = xt::ones({num_vertices(t)});
auto result = accumulate_parallel(t, input, hg::accumulator_sum());
// result = {0, 0, 0, 0, 0, 2, 3, 2};

Sequential accumulator¶
The sequential accumulator defines the new value of a node as the accumulation of the accumulated values of its children. This process is thus done sequentially from the leaves to the root of the tree.
The sequential accumulator pseudocode could be:
1 2 3 4 5 6 7 8 9 10 11  # input: a tree t
# input: an attribute att on the leaves of t
# input: an accumulator acc
output = empty(t.num_vertices())
output[0:t.num_leaves()] = input
for each nonleaf node n of t from the leaves to the root:
output[n] = acc(output[t.children(n)])
return output

The following example demonstrates the application of a sequential sum accumulator on a simple tree:
1 2 3 4 5 6 7  # tree in the above example
t = hg.Tree((5, 5, 6, 6, 6, 7, 7, 7))
input = numpy.ones((t.num_leaves(),))
result = hg.accumulate_sequential(t, input, hg.Accumulators.sum)
# result = (1, 1, 1, 1, 1, 2, 3, 5)

1 2 3 4 5 6 7  // tree in the above example
tree t({5, 5, 6, 6, 6, 7, 7, 7});
array_1d<index_t> input = xt::ones({num_leaves(t)});
auto result = accumulate_sequential(t, input, hg::accumulator_sum());
// result = {1, 1, 1, 1, 1, 2, 3, 5};

Sequential and combine accumulator¶
The sequential and combine accumulator defines the new value of a node as the accumulation of the accumulated values of its children combined with another node dependent value. This process is thus done sequentially from the leaves to the root of the tree.
The sequential accumulator pseudocode could be:
1 2 3 4 5 6 7 8 9 10 11 12 13  # input: a tree t
# input: an attribute att1 on the leaves of t
# input: an attribute att2 on the nodes of t
# input: an accumulator acc
# input: a function combine
output = empty(t.num_vertices())
output[0:t.num_leaves()] = att1
for each nonleaf node n of t from the leaves to the root:
output[n] = combine(acc(output[t.children(n)]), att2[n])
return output

The following example demonstrates the application of sequential max accumulator with a sum combiner on a simple tree:
1 2 3 4 5 6 7 8  # tree in the above example
t = hg.Tree((5, 5, 6, 6, 6, 7, 7, 7))
leaf_attribute = numpy.ones((t.num_leaves(),))
tree_attribute = numpy.ones((t.num_vertices(),))
result = hg.accumulate_and_add_sequential(t, tree_attribute, leaf_attribute, hg.Accumulators.max)
# result = (1, 1, 1, 1, 1, 2, 2, 3)

1 2 3 4 5 6 7 8 9 10 11 12  // tree in the above example
tree t({5, 5, 6, 6, 6, 7, 7, 7});
array_1d<index_t> leaf_attribute = xt::ones({num_leaves(t)});
array_1d<index_t> tree_attribute = xt::ones({num_vertices(t)});
auto result = accumulate_and_combine_sequential(t,
tree_attribute,
leaf_attribute,
hg::accumulator_max(),
std::plus<index_t>());
// result = {1, 1, 1, 1, 1, 2, 2, 3};

Note that currently, to ease the binding of this accumulator to Python, the combining function cannot be specified at runtime and the library offers several statically bound functions:
accumulate_and_add_sequential
accumulate_and_sum_sequential
accumulate_and_multiply_sequential
accumulate_and_min_sequential
accumulate_and_max_sequential
Propagators¶
A propagator efficiently move values from a node to its children (it can be seen as the inverse of the accumulators). They are especially important for writing efficient algorithms in Python by avoiding to use the tree iterators in many common scenarii. Using them in C++ can also be beneficial as they are written to natively and efficiently handle ndimensional data.
Conditional parallel propagator¶
The conditional parallel propagator defines the new value of a node as its parent value if the condition is true and keeps its value otherwise. This process is done in parallel on the whole tree. The default condition (if the user does not provide one) is true for all nodes: each node takes the value of its parent.
The conditional parallel propagator pseudocode could be:
1 2 3 4 5 6 7 8 9 10 11  # input: a tree t
# input: an attribute att on the nodes of t
# input: a condition cond on the nodes of t
output = copy(input)
for each node n of t:
if(cond(n)):
output[n] = input[t.parent(n)]
return output

The following example demonstrates the application of a conditional parallel propagation:
1 2 3 4 5 6 7 8  # tree in the above example
t = hg.Tree((5, 5, 6, 6, 6, 7, 7, 7))
input = numpy.asarray((1, 2, 3, 4, 5, 6, 7, 8))
condition = numpy.asarray((True, False, True, False, True, True, False, False))
result = hg.propagate_parallel(t, input, condition)
# result = (6, 2, 7, 4, 7, 8, 7, 8)

1 2 3 4 5 6 7 8  // tree in the above example
tree t({5, 5, 6, 6, 6, 7, 7, 7});
array_1d<index_t> input{1, 2, 3, 4, 5, 6, 7, 8};
array_1d<bool> condition{true, false, true, false, true, true, false, false};
auto result = propagate_parallel(t, input, condition);
// result = {6, 2, 7, 4, 7, 8, 7, 8};

Conditional sequential propagator¶
The conditional sequential propagator defines the new value of a node as its parent propagated value if the condition is true and keeps its value otherwise. This process is thus done from the root to the leaves of the tree.
The conditional sequential propagator pseudocode could be:
1 2 3 4 5 6 7 8 9 10 11  # input: a tree t
# input: an attribute att on the nodes of t
# input: a condition cond on the nodes of t
output = copy(input)
for each node n of t:
if(cond(n)):
output[n] = output[t.parent(n)]
return output

The following example demonstrates the application of a conditional sequential propagation:
1 2 3 4 5 6 7 8  # tree in the above example
t = hg.Tree((5, 5, 6, 6, 6, 7, 7, 7))
input = numpy.asarray((1, 2, 3, 4, 5, 6, 7, 8))
condition = numpy.asarray((True, False, True, False, True, True, False, False))
result = hg.propagate_sequential(t, input, condition)
# result = (8, 2, 7, 4, 7, 8, 7, 8)

1 2 3 4 5 6 7 8  // tree in the above example
tree t({5, 5, 6, 6, 6, 7, 7, 7});
array_1d<index_t> input{1, 2, 3, 4, 5, 6, 7, 8};
array_1d<bool> condition{true, false, true, false, true, true, false, false};
auto result = propagate_sequential(t, input, condition);
// result = {8, 2, 7, 4, 7, 8, 7, 8};

Sequential propagate and accumulate¶
The sequential propagate and accumulate defines the new value of a node as its parent value accumulated with its current value. This process is done from the root to the leaves of the tree.
The propagate and accumulate pseudocode could be:
1 2 3 4 5 6 7 8 9 10  # input: a tree t
# input: an attribute att on the nodes of t
# input: an accumulator acc
output[t.root] = acc(input[t.root])
for each node n of t from the root (excluded) to the leaves:
output[n] = acc(output[t.parent(n)], input[n])
return output

The following example demonstrates the application of a propagate and accumulate with a sum accumulator:
1 2 3 4 5 6 7  # tree in the above example
t = hg.Tree((5, 5, 6, 6, 6, 7, 7, 7))
input = numpy.asarray((1, 2, 3, 4, 5, 6, 7, 8))
result = hg.propagate_sequential_and_accumulate(t, input, condition)
# result = (15, 16, 18, 19, 20, 14, 15, 8)

1 2 3 4 5 6 7  // tree in the above example
tree t({5, 5, 6, 6, 6, 7, 7, 7});
array_1d<index_t> input{1, 2, 3, 4, 5, 6, 7, 8};
auto result = propagate_sequential_and_accumulate(t, input, hg.Accumulators.sum);
// result = {15, 16, 18, 19, 20, 14, 15, 8};

Core hierarchy algorithm¶

Computes the canonical binary partition tree, also called binary partition tree by altitude ordering or connectivity constrained single min/linkage clustering of the given graph. 

The saliency map of the input hierarchy \((tree, altitudes)\) for the leaf graph \(g\) is an array of edge weights \(sm\) for \(g\) such that for each pair of adjacent vertices \((i,j)\) in \(g\), \(sm(i,j)\) is equal to the ultrametric distance between \(i\) and \(j\) corresponding to the hierarchy. 

Computes the quasi flat zone hierarchy of the given weighted graph. 

Creates a copy of the given tree and deletes the vertices \(i\) of the tree such that \(deletedVertices[i]\) is 

Removes consecutive tree nodes with equal altitudes. 

Transforms a tree into a binary tree. 

bpt_canonical
(graph, edge_weights=None, sorted_edge_indices=None, return_altitudes=True, compute_mst=True)[source]¶ Computes the canonical binary partition tree, also called binary partition tree by altitude ordering or connectivity constrained single min/linkage clustering of the given graph.
 Definition
The following definition is adapted from:
Cousty, Jean, Laurent Najman, Yukiko Kenmochi, and Silvio Guimarães. “Hierarchical segmentations with graphs: quasiflat zones, minimum spanning trees, and saliency maps.” Journal of Mathematical Imaging and Vision 60, no. 4 (2018): 479502.
Let \(G=(V,E)\) be an undirected graph, let \(\prec\) be a total order on \(E\), and let \(e_k\) be the edge in \(E\) that has exactly \(k\) smaller edges according to \(\prec\): we then say that \(k\) is the rank of \(e_k\) (for \(\prec\)). The canonical binary partition hierarchy of \(G\) for \(\prec\) is defined as the sequence of nested partitions:
\(P_0 = \{\{v\}, v\in V\}\), the finest partion is composed of every singleton of \(V\); and
\(P_n = (P_{n1} \backslash \{P_{n1}^x, P_{n1}^y\}) \cup (P_{n1}^x \cup P_{n1}^y)\) where \(e_n=\{x,y\}\) and \(P_{n1}^x\) and \(P_{n1}^y\) are the regions of \(P_{n1}\) that contain \(x\) and \(y\) respectively.
At the step \(n\), we remove the regions at the two extremities of the \(n\)th smallest edge and we add their union. Note that we may have \(P_n = P_{n1}\) if both extremities of the edge \(e_n\) were in a same region of \(P_{n1}\). Otherwise, \(P_n\) is obtained by merging two regions of \(P_{n1}\).
The canonical binary partition tree is then the tree representing the merging steps in this sequence, it is thus binary. Each merging step, and thus each non leaf node of the tree, is furthermore associated to a specific edge of the graph, called a building edge that led to this merge. It can be shown that the set of all building edges associated to a canonical binary partition tree is a minimum spanning tree of the graph for the given edge ordering \(\prec\).
The map that associates every non leaf node of the canonical binary partition tree to its building edge is called the mst_edge_map. In practice this map is represented by an array of size \(tree.num\_vertices()  tree.num\_leaves()\) and, for any internal node \(i\) of the tree, \(mst\_edge\_map[i  tree.num\_leaves()]\) is equal to the index of the building edge in \(G\) associated to \(i\).
The ordering \(\prec\) can be specified explicitly by providing the array of indices
sorted_edge_indices
that sort the edges, or implicitly by providing the array of edge weightsedge_weights
. In this case,sorted_edge_indices
is set equal tohg.arg_sort(edge_weights, stable=True)
. Ifedge_weights
is an array with more than 1 dimension, a lexicographic ordering is used.If requested, altitudes associated to the nodes of the canonical binary partition tree are computed as follows:
if
edge_weights
are provided, the altitude of a nonleaf node is equal to the edge weight of its building edge; andotherwise, the altitude of a nonleaf node is equal to the rank of its building edge.
The altitude of a leaf node is always equal to 0.
 Example
The above figure corresponds to the following code (note that vertex indices start at 0 in the code):
>>> g = hg.UndirectedGraph(5) >>> g.add_edges((0, 0, 1, 1, 1, 2, 3), >>> (1, 2, 2, 3, 4, 4, 4)) >>> edge_weights = np.asarray((4, 6, 3, 7, 11, 8, 5)) >>> tree, altitudes = hg.bpt_canonical(g, edge_weights) >>> tree.parents() array([6, 5, 5, 7, 7, 6, 8, 8, 8]) >>> altitudes array([0, 0, 0, 0, 0, 3, 4, 5, 7]) >>> tree.mst_edge_map array([2, 0, 6, 3]) >>> tree.mst.edge_list() (array([1, 0, 3, 1]), array([2, 1, 4, 3]))
An object of type UnidrectedGraph is not necessary:
>>> edge_weights = np.asarray((4, 6, 3, 7, 11, 8, 5)) >>> sources = (0, 0, 1, 1, 1, 2, 3) >>> targets = (1, 2, 2, 3, 4, 4, 4) >>> tree, altitudes = hg.bpt_canonical((sources, targets, 5), edge_weights) >>> tree.parents() array([6, 5, 5, 7, 7, 6, 8, 8, 8]) >>> altitudes array([0, 0, 0, 0, 0, 3, 4, 5, 7]) >>> tree.mst_edge_map array([2, 0, 6, 3])
 Complexity
The algorithm used is based on Kruskal’s minimum spanning tree algorithm and is described in:
Laurent Najman, Jean Cousty, Benjamin Perret. Playing with Kruskal: Algorithms for Morphological Trees in EdgeWeighted Graphs. ISMM 2013: 135146.
If
sorted_edge_indices
is provided the algorithm runs in quasi linear \(\mathcal{O}(n \alpha(n))\), with \(n\) the number of elements in the graph and with :math`alpha` the inverse of the Ackermann function. Otherwise, the computation time is dominated by the sorting of the edge weights which is performed in linearithmic \(\mathcal{O}(n \log(n))\) time. Parameters
graph – input graph or triplet of two arrays and an integer (sources, targets, num_vertices) defining all the edges of the graph and its number of vertices.
edge_weights – edge weights of the input graph (may be omitted if
sorted_edge_indices
is given).sorted_edge_indices – array of indices that sort the edges of the input graph by increasing weight (may be omitted if
edge_weights
is given).return_altitudes – if
True
an array representing the altitudes of the tree vertices is returned. (default:True
).compute_mst – if
True
and if the input is a graph object computes an explicit undirected graph representing the minimum spanning tree associated to the hierarchy, accessible through theCptBinaryHierarchy
Concept (e.g. withtree.mst
). (default:True
).
 Returns
a tree (Concept
CptBinaryHierarchy
if the input is a graph object), and, ifreturn_altitudes
isTrue
, its node altitudes

canonize_hierarchy
(tree, altitudes, return_node_map=False)[source]¶ Removes consecutive tree nodes with equal altitudes.
The new tree is composed of the inner nodes \(n\) of the input tree such that \(altitudes[n] \neq altitudes[tree.parent(n)]\) or \(n = tree.root(n)\).
For example, applying this function to the result of
bpt_canonical()
on an edge weighted graph is the same as computing thequasi_flat_zone_hierarchy()
of the same edge weighted graph.If
return_node_map
isTrue
, an extra array that maps any vertex index \(i\) of the new tree, to the index of the corresponding vertex in the original tree is returned. Parameters
tree – input tree
altitudes – altitudes of the vertices of the tree
return_node_map – if
True
, also return the node map.
 Returns
a tree (Concept
CptHierarchy
if input tree already satisfied this concept) its node altitudes, and, if requested, its node map.

quasi_flat_zone_hierarchy
(graph, edge_weights)[source]¶ Computes the quasi flat zone hierarchy of the given weighted graph. The nodes of the quasi flat zone hierarchy corresponds to the connected components of all the possible thresholds of the edge weights.
 Parameters
graph – input graph
edge_weights – edge weights of the input graph
 Returns
a tree (Concept
CptHierarchy
) and its node altitudes

simplify_tree
(tree, deleted_vertices, process_leaves=False)[source]¶ Creates a copy of the given tree and deletes the vertices \(i\) of the tree such that \(deletedVertices[i]\) is
True
.The returned
node_map
is an array that maps any node index \(i\) of the new tree, to the index of the corresponding node in the original tree. Parameters
tree – input tree
deleted_vertices – boolean valuation of the input tree nodes
process_leaves – If
False
, a leaf vertex \(v\) will never be removed disregarding the value of \(deletedVertices[v]\). IfTrue
, leaves node may be removed. Note that in this case, a reordering of the nodes may be necessary, which is a more complex and slower operation.
 Returns
a tree (Concept
CptHierarchy
if input tree already satisfied this concept) and the node map

tree_2_binary_tree
(tree)[source]¶ Transforms a tree into a binary tree.
Each nonleaf node of the input tree must have at least 2 children!
Whenever a nonleaf node \(n\) with \(k > 2\) children is found:
an extra node \(m\) is created;
the first 2 children of \(n\) become children of the new node \(m\); and
the new node \(m\) becomes the first child of \(n\).
The number of children of \(n\) is thus reduced by 1. This operation is repeated \(k2\) times, i.e. until \(n\) has only 2 children.
The returned
node_map
is an array that maps any node index \(i\) of the new tree, to the index of the corresponding node in the original tree. Complexity
This algorithms runs in linear time \(O(tree.num\_vertices())\).
 Examples
Compute the watershed hierarchy by area of an edge weighted graph and get the corresponding binary hierarchy. The returned
node_map
enables to recover the altitudes of the new hierarchy from the altitudes of the input hierarchy.tree, altitudes = watershed_hierarchy_by_area(graph, edge_weights) new_tree, node_map = tree_2_binary_tree(tree) new_altitudes = altitudes[node_map]
 Parameters
tree – Input tree
 Returns
a tree (Concept
CptHierarchy
if input tree already satisfied this concept) and the node map

saliency
(tree, altitudes, leaf_graph, handle_rag=True)[source]¶ The saliency map of the input hierarchy \((tree, altitudes)\) for the leaf graph \(g\) is an array of edge weights \(sm\) for \(g\) such that for each pair of adjacent vertices \((i,j)\) in \(g\), \(sm(i,j)\) is equal to the ultrametric distance between \(i\) and \(j\) corresponding to the hierarchy.
Formally, this is computed using the following property: \(sm(i,j) = altitudes(lowest\_common\_ancestor_{tree}(i,j))\).
Complexity: \(\mathcal{O}(n\log(n) + m)\) with \(n\) the number of vertices in the tree and \(m\) the number of edges in the graph.
 Parameters
tree – input tree (Concept
CptHierarchy
)altitudes – altitudes of the vertices of the tree
leaf_graph – graph whose vertex set is equal to the leaves of the input tree (deduced from
CptHierarchy
)handle_rag – if tree has been constructed on a rag, then saliency values will be propagated to the original graph, hence leading to a saliency on the original graph and not on the rag
 Returns
1d array of edge weights
Hierarchy construction algorithms¶
Binary partition hierarchy¶

Binary partition tree of the graph with a user provided cluster distance. 

Alias for 
Binary partition tree with complete linkage distance. 


Binary partition tree with average linkage distance. 
Binary partition tree with exponential linkage distance. 


Binary partition tree with the Ward linkage rule. 
Binary partition tree according to the MumfordShah energy with a constant piecewise model. 

binary_partition_tree_single_linkage
(graph, edge_weights)[source]¶ Alias for
bpt_canonical()
.Given a graph \(G=(V, E)\), with initial edge weights \(w\), the distance \(d(X,Y)\) between any two clusters \(X\) and \(Y\) is
\[d(X,Y) = \min \{w(\{x,y\})  x \in X, y \in Y, \{x,y\} \in E \}\]Regions are then iteratively merged following the above distance (closest first) until a single region remains.
 Parameters
edge_weights – edge weights of the input graph (Concept
CptEdgeWeightedGraph
)graph – input graph (deduced from
CptEdgeWeightedGraph
)
 Returns
a tree (Concept
CptHierarchy
) and its node altitudes (ConceptCptValuedHierarchy
)

binary_partition_tree_complete_linkage
(graph, edge_weights)[source]¶ Binary partition tree with complete linkage distance.
Given a graph \(G=(V, E)\), with initial edge weights \(w\), the distance \(d(X,Y)\) between any two clusters \(X\) and \(Y\) is
\[d(X,Y) = \max \{w(\{x,y\})  x \in X, y \in Y, \{x,y\} \in E \}\]Regions are then iteratively merged following the above distance (closest first) until a single region remains
 Parameters
graph – input graph
edge_weights – edge weights of the input graph
 Returns
a tree (Concept
CptHierarchy
) and its node altitudes

binary_partition_tree_average_linkage
(graph, edge_weights, edge_weight_weights=None)[source]¶ Binary partition tree with average linkage distance.
Given a graph \(G=(V, E)\), with initial edge weights \(w\) with associated weights \(w_2\), the distance \(d(X,Y)\) between any two clusters \(X\) and \(Y\) is
\[d(X,Y) = \frac{1}{Z} \sum_{x \in X, y \in Y, \{x,y\} \in E} w(\{x,y\}) \times w_2(\{x,y\})\]with \(Z = \sum_{x \in X, y \in Y, \{x,y\} \in E} w_2({x,y})\).
 Parameters
graph – input graph
edge_weights – edge weights of the input graph
edge_weight_weights – weighting of edge weights of the input graph (default to an array of ones)
 Returns
a tree (Concept
CptHierarchy
) and its node altitudes

binary_partition_tree_exponential_linkage
(graph, edge_weights, alpha, edge_weight_weights=None)[source]¶ Binary partition tree with exponential linkage distance.
Given a graph \(G=(V, E)\), with initial edge weights \(w\) with associated weights \(w_2\), the distance \(d(X,Y)\) between any two clusters \(X\) and \(Y\) is
\[d(X,Y) = \frac{1}{Z} \sum_{x \in X, y \in Y, \{x,y\} in E} w_2(\{x,y\}) \times \exp(\alpha * w(\{x,y\})) \times w(\{x,y\})\]with \(Z = \sum_{x \in X, y \in Y, \{x,y\} \in E} w_2(\{x,y\}) \times \exp(\alpha * w(\{x,y\}))\).
 See
Nishant Yadav, Ari Kobren, Nicholas Monath, Andrew Mccallum. Supervised Hierarchical Clustering with Exponential Linkage Proceedings of the 36th International Conference on Machine Learning, PMLR 97:69736983, 2019.
 Parameters
graph – input graph
edge_weights – edge weights of the input graph
alpha – exponential parameter
edge_weight_weights – weighting of edge weights of the input graph (default to an array of ones)
 Returns
a tree (Concept
CptHierarchy
) and its node altitudes

binary_partition_tree_ward_linkage
(graph, vertex_centroids, vertex_sizes=None, altitude_correction='max')[source]¶ Binary partition tree with the Ward linkage rule.
Given a graph \(G=(V, E)\), with initial edge weights \(w\) with associated weights \(w'\), the distance \(d(X,Y)\) between any two clusters \(X\) and \(Y\) is
\[d(X,Y) = \frac{ X \times Y }{ X + Y } \ \vec{X}  \vec{Y} \^2\]where \(\vec{X}\) and \(\vec{Y}\) are the centroids of \(X\) and \(Y\).
Regions are then iteratively merged following the above distance (closest first) until a single region remains
Note that the Ward distance is not necessarily strictly increasing when processing a non complete graph. This can be corrected afterward with an altitude correction strategy. Valid values for
altitude correction
are:"none"
: nothing is done and the altitude of a node is equal to the Ward distance between its 2 children; this may not be nondecreasing"max"
: the altitude of a node \(n\) is defined as the maximum of the the Ward distance associated to each node in the subtree rooted in \(n\).
 Parameters
graph – input graph
vertex_centroids – Centroids of the graph vertices (must be a 2d array)
vertex_sizes – Size (number of elements) of the graph vertices (default to an array of ones)
altitude_correction – can be
"none"
or"max"
(default)
 Returns
a tree (Concept
CptHierarchy
) and its node altitudes

binary_partition_tree_MumfordShah_energy
(graph, vertex_values, vertex_area=None, vertex_perimeter=None, edge_length=None, squared_vertex_values=None)[source]¶ Binary partition tree according to the MumfordShah energy with a constant piecewise model.
The distance between two regions is equal to the apparition scale of the merged region.
See:
Laurent Guigues, Jean Pierre Cocquerez, Hervé Le Men. Scalesets Image Analysis. International Journal of Computer Vision, Springer Verlag, 2006, 68 (3), pp.289317
 Parameters
graph – input graph
vertex_values – Sum of values inside each vertex of the input graph (1d array for scalar value or 2d array for vectorial values, e.g. RGB pixel values)
vertex_area – area of the vertices of the input graph (provided by
attribute_vertex_area()
on graph)vertex_perimeter – perimeter of the vertices of the input graph (provided by
attribute_vertex_perimeter()
on graph)edge_length – length of the frontier represented by the edges of the input graph (provided by
attribute_edge_length()
on graph)squared_vertex_values – Sum of squared values inside each vertex of the input graph (1d array for scalar value or 2d array for vectorial values, e.g. RGB pixel values). If this argument is not provided, it will default to vertex_values * vertex_values which is only correct if a vertex contains a single value.
 Returns
a tree (Concept
CptHierarchy
) and its node altitudes

binary_partition_tree
(graph, weight_function, edge_weights)[source]¶ Binary partition tree of the graph with a user provided cluster distance.
At each step:
the algorithm finds the edge of smallest weight;
the two vertices linked by this edge are merged: the new vertex is the parent of the two merged vertices and its altitude is equal to the weight of the fusion edge;
the weight of the edges linking the new vertex to the remaining vertices of the graph are updated according to the user provided function (
weight_function
);repeat until a single vertex remains
The initial weight of the edges (
edge_weights
) and the callback (weight_function
) determine the shape of the hierarchy. Note that the altitudes of the constructed hierarchy are not necessarily increasing; if needed this can be enforced as a post processing with the functiontree_monotonic_regression()
.Classical linkage functions are already implemented:
single/min linkage
binary_partition_tree_single_linkage()
complete/max linkage
binary_partition_tree_complete_linkage()
average linkage
binary_partition_tree_average_linkage()
Ward linkage
binary_partition_tree_ward_linkage()
.
Those functions are implemented in c++ and should be faster than a user defined weighting function written in Python.
 Weight function
The
weight_function
callback can be anything defining the operator()
and should follow the following pattern:def weight_function(graph, # the current state of the graph fusion_edge_index, # the edge between the two vertices being merged new_region, # the new vertex in the graph merged_region1, # the first vertex merged merged_region2, # the second vertex merged new_neighbours): # list of edges to be weighted (see below) ... for n in new_neighbours: ... n.set_new_edge_weight(new_edge_value) # define the weight of this edge }
Each element in the parameter
new_neighbours
represent an edge between the new vertex and another vertex of the graph. For each element of the list, the following methods are available:neighbour_vertex()
: the other vertexnum_edges()
: returns 2 if both the two merged vertices had an edge linking themselves withneighbour_vertex()
and 1 otherwisefirst_edge_index()
: the index of the edge linking one of the merged region toneighbour_vertex()
second_edge_index()
: the index of the edge linking the other merged region toneighbour_vertex()
(only ifnum_edges()==2
)set_new_edge_weight(value)
: weight of the new edge. This has to be defined in the weighting function.new_edge_index()
: the index of the new edge as the weighting function will probably have to track new weight values
 Example
The following example shows how to define a weighting function for average linkage assuming that:
edge_weights
is an array containing the weight of each edge, andedge_counts
is an array containing the number of edges present between two clusters: initially 1 for each edge but this will increase when clusters are merged.
When a merge happens, there are two possibilities. Consider that we have three clusters \(A\), \(B\), and \(C\) and we are merging \(A\) and \(B\) to obtain the new cluster \(D\).
If there is an edge of weight \(w_{AC}\) and multiplicity \(c_{AC}\) between \(A\) and \(C\) but there is no edge between \(B\) and \(C\). Then, the new graph will contain an edge between \(D\) and \(C\) such that \(w_{DC}=w_{AC}\) and \(c_{DC}=c_{AC}\). (The situation is similar if the edge were between \(B\) and \(C\)).
If there is an edge between \(A\) and \(C\) and between \(B\) and \(C\). Then, the new graph will contain an edge between \(D\) and \(C\) such that \(w_{DC} = \frac{w_{AC}*c_{AC} + w_{BC}*c_{BC}}{c_{AC} + c_{BC}}\) and \(c_{DC}=c_{AC} + c_{BC}\).
def weighting_function_average_linkage(graph, fusion_edge_index, new_region, merged_region1, merged_region2, new_neighbours): for n in new_neighbours: if n.num_edges() > 1: new_count = edge_counts[n.first_edge_index()] + edge_counts[n.second_edge_index()] new_weight = (edge_weights[n.first_edge_index()] * edge_counts[n.first_edge_index()] \ + edge_weights[n.second_edge_index()] * edge_counts[n.second_edge_index()]) \ / new_weight else: new_count = edge_counts[n.first_edge_index()] new_weight = edge_weights[n.first_edge_index()] n.set_new_edge_weight(new_weight) edge_weights[n.new_edge_index()] = new_weight edge_counts[n.new_edge_index()] = new_count
 Complexity
The worst case time complexity is in \(\mathcal{O}(n^2\log(n))\) with \(n\) the number of vertices in the graph. The runtime complexity on a sparse graph with well structured data (far different from noise) can be much better in practice.
Warning
This function uses a Python callback (the
weight_function
) that is called frequently by the algorithm: performances will be far from optimal. Please consider a C++ implementation if it is too slow (see this helper project ). Parameters
graph – input graph
weight_function – see detailed description above
edge_weights – edge weights of the input graph
 Returns
a tree (Concept
CptHierarchy
) and its node altitudes
Component tree¶

Min Tree hierarchy from the input vertex weighted graph. 

Max Tree hierarchy from the input vertex weighted graph. 

component_tree_min_tree
(graph, vertex_weights)[source]¶ Min Tree hierarchy from the input vertex weighted graph.
The Min/Max Tree structure were proposed in 1, 2. The algorithm used in this implementation was first described in 3.
 1(1,2)
Ph. Salembier, A. Oliveras, and L. Garrido, “Antiextensive connected operators for image and sequence processing,” IEEE Trans. Image Process., vol. 7, no. 4, pp. 555570, Apr. 1998.
 2(1,2)
Ro. Jones, “Connected filtering and segmentation using component trees,” Comput. Vis. Image Understand., vol. 75, no. 3, pp. 215228, Sep. 1999.
 3(1,2)
Ch. Berger, T. Geraud, R. Levillain, N. Widynski, A. Baillard, and E. Bertin, “Effective Component Tree Computation with Application to Pattern Recognition in Astronomical Imaging,” IEEE ICIP 2007.
 Parameters
graph – input graph
vertex_weights – vertex weights of the input graph
 Returns
a tree (Concept
CptHierarchy
) and its node altitudes

component_tree_max_tree
(graph, vertex_weights)[source]¶ Max Tree hierarchy from the input vertex weighted graph.
The Min/Max Tree structure were proposed in 1, 2. The algorithm used in this implementation was first described in 3.
 Parameters
graph – input graph
vertex_weights – vertex weights of the input graph
 Returns
a tree (Concept
CptHierarchy
) and its node altitudes
Constrained connectivity hierarchy¶
Alphaomega constrained connectivity hierarchy based on the given vertex weighted graph. 

Strongly constrained connectivity hierarchy based on the given edge weighted graph. 

constrained_connectivity_hierarchy_alpha_omega
(graph, vertex_weights)[source]¶ Alphaomega constrained connectivity hierarchy based on the given vertex weighted graph.
For \((i,j)\) be an edge of the graph, we define \(w(i,j)=w(i)  w(j)\), the weight of this edge. Let \(X\) be a set of vertices, the range of \(X\) is the maximal absolute difference between the weights of any two vertices in \(X\): \(R(X) = \max\{w(i)  w(j), (i,j)\in X^2\}\)
Let \(\alpha\) be a positive real number, a set of vertices \(X\) is \(\alpha\)connected, if for any two vertices \(i\) and \(j\) in \(X\), there exists a path from \(i\) to \(j\) in \(X\) composed of edges of weights lower than or equal to \(\alpha\).
Let \(\alpha\) and \(\omega\) be a two positive real numbers, the \(\alpha\omega\)connected components of the graph are the maximal \(\alpha'\)connected sets of vertices with a range lower than or equal to \(\omega\), with \(\alpha'\leq\alpha\).
Finally, the alphaomega constrained connectivity hierarchy is defined as the hierarchy composed of all the \(kk\)connected components for all positive \(k\).
The definition used follows the one given in:
P. Soille, “Constrained connectivity for hierarchical image partitioning and simplification,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, no. 7, pp. 11321145, July 2008. doi: 10.1109/TPAMI.2007.70817
The algorithm runs in time \(\mathcal{O}(n\log(n))\) and proceeds by filtering a quasiflat zone hierarchy (see
quasi_flat_zones_hierarchy()
) Parameters
graph – input graph
vertex_weights – edge_weights: edge weights of the input graph
 Returns
a tree (Concept
CptHierarchy
) and its node altitudes

constrained_connectivity_hierarchy_strong_connection
(graph, edge_weights)[source]¶ Strongly constrained connectivity hierarchy based on the given edge weighted graph.
Let \(X\) be a set of vertices, the range of \(X\) is the maximal weight of the edges linking two vertices inside \(X\).
Let \(\alpha\) be a positive real number, a set of vertices \(X\) is \(\alpha\)connected, if for any two vertices \(i\) and \(j\) in \(X\), there exists a path from \(i\) to \(j\) in \(X\) composed of edges of weights lower than or equal to \(\alpha\).
Let \(\alpha\) be a positive real numbers, the \(\alpha\)strongly connected components of the graph are the maximal \(\alpha'\)connected sets of vertices with a range lower than or equal to \(\alpha\) with \(\alpha'\leq\alpha\).
Finally, the strongly constrained connectivity hierarchy is defined as the hierarchy composed of all the \(\alpha\) strongly connected components for all positive \(\alpha\).
The definition used follows the one given in:
P. Soille, “Constrained connectivity for hierarchical image partitioning and simplification,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, no. 7, pp. 11321145, July 2008. doi: 10.1109/TPAMI.2007.70817
The algorithm runs in time \(\mathcal{O}(n\log(n))\) and proceeds by filtering a quasiflat zone hierarchy (see
quasi_flat_zones_hierarchy()
) Parameters
graph – input graph
edge_weights – edge_weights: edge weights of the input graph
 Returns
a tree (Concept
CptHierarchy
) and its node altitudes
Random hierarchy¶

Random binary partition tree with a controlled amount of asymmetry/unbalancedness. 

random_binary_partition_tree
(num_leaves, asymmetry_probability)[source]¶ Random binary partition tree with a controlled amount of asymmetry/unbalancedness.
The tree is grown from the root to the leaves. At each step, the algorithm randomly select one of the growable leaf node of the current tree. Two children are added to the selected node; the number of leaf nodes is hence increased by one. Then,
with probability \(1asymmetry\_probability\), both new children are marked as growable
with probability \(asymmetry\_probability\), only one of the children is marked as growable
The altitudes of the returned hierarchy are obtained with
attribute_regular_altitudes()
: The regular altitudes is comprised between 0 and 1 and is inversely proportional to the depth of a node.A valid minimal connected graph (a tree) is associated to the leaves of the tree.
 Parameters
num_leaves – expected number of leaves in the generated tree
asymmetry_probability – real value between 0 and 1. At 0 the tree is perfectly unbalanced, at 1 it is perfectly balanced (if
num_leaves
is a power of 2)
 Returns
a tree (Concept
CptBinaryHierarchy
) and its node altitudes
Watershed hierarchy¶

Watershed hierarchy by a user defined attributes. 
Watershed hierarchy for the given minima ordering. 


Watershed hierarchy by area. 

Watershed hierarchy by volume. 

Watershed hierarchy by dynamics. 
Watershed hierarchy by number of parents. 

watershed_hierarchy_by_attribute
(graph, edge_weights, attribute_functor, canonize_tree=True)[source]¶ Watershed hierarchy by a user defined attributes.
The definition of hierarchical watershed follows the one given in:
J. Cousty, L. Najman. Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts. ISMM 2011: 272283.
The algorithm used is described in:
Laurent Najman, Jean Cousty, Benjamin Perret. Playing with Kruskal: Algorithms for Morphological Trees in EdgeWeighted Graphs. ISMM 2013: 135146.
The attribute functor is a function that takes a binary partition tree and an array of altitudes as argument and returns an array with the node attribute values for the given tree.
Example:
Calling watershed_hierarchy_by_area is equivalent to:
tree = watershed_hierarchy_by_attribute(graph, edge_weights, lambda tree, _: hg.attribute_area(tree))
 Parameters
graph – input graph
edge_weights – edge weights of the input graph
attribute_functor – function computing the regional attribute
canonize_tree – if
True
(default), the resulting hierarchy is canonized (see functioncanonize_hierarchy()
), otherwise the returned hierarchy is a binary tree
 Returns
a tree (Concept
CptHierarchy
isTrue
andCptBinaryHierarchy
otherwise) and its node altitudes

watershed_hierarchy_by_minima_ordering
(graph, edge_weights, minima_ranks, minima_altitudes=None, canonize_tree=True)[source]¶ Watershed hierarchy for the given minima ordering.
The definition used follows the one given in:
J. Cousty, L. Najman. Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts. ISMM 2011: 272283.
and in,
J. Cousty, L. Najman, B. Perret. Constructive links between some morphological hierarchies on edgeweighted graphs.. ISMM 2013: 8697.
The algorithm used is adapted from the algorithm described in:
Laurent Najman, Jean Cousty, Benjamin Perret. Playing with Kruskal: Algorithms for Morphological Trees in EdgeWeighted Graphs. ISMM 2013: 135146.
The ranking ranking of the minima of the given edge weighted graph \((G,w)\) is given as vertex weights with values in \(\{0, \ldots, n\}\) with \(n\) the number of minima of \((G,w)\). It must satisfy the following preconditions:
each minimum of \((G,w)\) contains at least one non zero vertex,
all non zero vertices in a minimum have the same weight,
there is no non zero value vertex outside minima, and
no two minima contain non zero vertices with the same weight.
minima_altitudes
is an optional non decreasing 1d array of size \(n + 1\) with non negative values such that \(minima\_altitudes[i]\) indicates the altitude of the minima of rank \(i\). Note that the first entry of the minima altitudes array, ie. the value at index 0, does not represent a minimum and its value should be 0.The altitude of a node of the computed watershed corresponds to the altitude (respectively the rank) of the minima it is associated to if
minima_altitudes
is provided (respectively not provided). Parameters
graph – input graph
edge_weights – edge weights of the input graph
minima_ranks – input graph vertex weights containing the rank of each minima of the input edge weighted graph
minima_altitudes – array mapping each minima rank to its altitude (optional)
canonize_tree – if
True
(default), the resulting hierarchy is canonized (see functioncanonize_hierarchy()
), otherwise the returned hierarchy is a binary tree
 Returns
a tree (Concept
CptHierarchy
isTrue
andCptBinaryHierarchy
otherwise) and its node altitudes

watershed_hierarchy_by_area
(graph, edge_weights, vertex_area=None, canonize_tree=True)[source]¶ Watershed hierarchy by area.
The definition of hierarchical watershed follows the one given in:
J. Cousty, L. Najman. Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts. ISMM 2011: 272283.
The algorithm used is described in:
Laurent Najman, Jean Cousty, Benjamin Perret. Playing with Kruskal: Algorithms for Morphological Trees in EdgeWeighted Graphs. ISMM 2013: 135146.
 Parameters
graph – input graph
edge_weights – input graph edge weights
vertex_area – area of the input graph vertices (provided by
attribute_vertex_area()
)canonize_tree – if
True
(default), the resulting hierarchy is canonized (see functioncanonize_hierarchy()
), otherwise the returned hierarchy is a binary tree
 Returns
a tree (Concept
CptHierarchy
isTrue
andCptBinaryHierarchy
otherwise) and its node altitudes

watershed_hierarchy_by_volume
(graph, edge_weights, vertex_area=None, canonize_tree=True)[source]¶ Watershed hierarchy by volume.
The definition of hierarchical watershed follows the one given in:
J. Cousty, L. Najman. Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts. ISMM 2011: 272283.
The algorithm used is described in:
Laurent Najman, Jean Cousty, Benjamin Perret. Playing with Kruskal: Algorithms for Morphological Trees in EdgeWeighted Graphs. ISMM 2013: 135146.
 Parameters
graph – input graph
edge_weights – input graph edge weights
vertex_area – area of the input graph vertices (provided by
attribute_vertex_area()
)canonize_tree – if
True
(default), the resulting hierarchy is canonized (see functioncanonize_hierarchy()
), otherwise the returned hierarchy is a binary tree
 Returns
a tree (Concept
CptHierarchy
isTrue
andCptBinaryHierarchy
otherwise) and its node altitudes

watershed_hierarchy_by_dynamics
(graph, edge_weights, canonize_tree=True)[source]¶ Watershed hierarchy by dynamics.
The definition of hierarchical watershed follows the one given in:
J. Cousty, L. Najman. Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts. ISMM 2011: 272283.
The algorithm used is described in:
Laurent Najman, Jean Cousty, Benjamin Perret. Playing with Kruskal: Algorithms for Morphological Trees in EdgeWeighted Graphs. ISMM 2013: 135146.
 Parameters
graph – input graph
edge_weights – input graph edge weights
canonize_tree – if
True
(default), the resulting hierarchy is canonized (see functioncanonize_hierarchy()
), otherwise the returned hierarchy is a binary tree
 Returns
a tree (Concept
CptHierarchy
isTrue
andCptBinaryHierarchy
otherwise) and its node altitudes

watershed_hierarchy_by_number_of_parents
(graph, edge_weights, canonize_tree=True)[source]¶ Watershed hierarchy by number of parents.
The definition of number of parents was proposed in:
B. Perret, J. Cousty, S. J. F. Guimarães and D. S. Maia, Evaluation of Hierarchical Watersheds , in IEEE Transactions on Image Processing, vol. 27, no. 4, pp. 16761688, April 2018. doi: 10.1109/TIP.2017.2779604
The definition of hierarchical watershed follows the one given in:
J. Cousty, L. Najman. Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts. ISMM 2011: 272283.
The algorithm used is described in:
Laurent Najman, Jean Cousty, Benjamin Perret. Playing with Kruskal: Algorithms for Morphological Trees in EdgeWeighted Graphs. ISMM 2013: 135146.
 Parameters
graph – input graph
edge_weights – edge weights of the input graph
canonize_tree – if
True
(default), the resulting hierarchy is canonized (see functioncanonize_hierarchy()
), otherwise the returned hierarchy is a binary tree
 Returns
a tree (Concept
CptHierarchy
isTrue
andCptBinaryHierarchy
otherwise) and its node altitudes
Hierarchy processing algorithms¶
Algorithm for alignment problems¶

Align hierarchies boundaries on the boundaries of the provided supervertex decomposition of a graph 

Find for each region of the fine rag, the region of the coarse rag that maximises the intersection with the “fine” region. 
Find for each label (ie region) of the fine labelisation, the label of the region in the coarse labelisation that maximises the intersection with the fine region. 

align_hierarchies
(graph, vertex_labels, other_hierarchies)[source]¶ Align hierarchies boundaries on the boundaries of the provided supervertex decomposition of a graph
Given:
a graph \(G=(V,E)\)
a fine labelisation \(l_1\) of the vertices of \(G\);
a tree \(T\) on \(G\) whose supervertices corresponds to the coarse labelisation \(l_2\) of the vertices of \(G\); and
the altitudes \(a\) of the nodes of \(T\).
Let us denote:
given a vertex \(x\) of \(G\) and a labelisation \(l\), \(l(x)\) is the region of \(l\) that contains \(x\)
given a region \(r\) of \(l_1\), \(s(r, l_2)\) is the region \(R\) of \(l_2\) that has the largest intersection with \(r\), ie, \(s(r, l_2) = \arg \max_{R \in l_2}  R \cap r \)
The projection of \(T\) onto \(l_1\) is a hierarchy given by the saliency map \(sm\) on \(G\) defined by:
\[\forall e_{xy} \in E, sm(e_{xy}) = a(lca_T(s(l_1(x), l_2), s(l_1(y), l_2)))\]where \(lca_T(x, y)\) is the lowest common ancestor of nodes \(x\) and \(y\) in \(T\).
 Parameters
graph – the domain graph
vertex_labels – 1d array of positive integers, labeling of the graph vertices into supervertices
other_hierarchies – a hierarchy or a list of hierarchies: hierarchies can be given either as valued trees (pairs (tree, altitudes) ) or as saliency maps (pairs (graph, edge_weights)), defined on the pixel graph or on a region adjacency graph (Concept
CptRegionAdjacencyGraph
).
 Returns
a hierarchy or a list of hierarchies as saliency maps

project_fine_to_coarse_rag
(fine_rag, coarse_rag)[source]¶ Find for each region of the fine rag, the region of the coarse rag that maximises the intersection with the “fine” region.
See:
project_fine_to_coarse_labelisation()
 Parameters
fine_rag – reference region adjacency graph (Concept
CptRegionAdjacencyGraph
)coarse_rag – region adjacency graph to align (Concept
CptRegionAdjacencyGraph
)
 Returns
a 1d array of size
fine_rag.num_vertices()

project_fine_to_coarse_labelisation
(labelisation_fine, labelisation_coarse, num_regions_fine=0, num_regions_coarse=0)[source]¶ Find for each label (ie region) of the fine labelisation, the label of the region in the coarse labelisation that maximises the intersection with the fine region.
Precondition:
\(range(labelisation\_fine) = [0, \ldots, num\_regions\_fine[\)
\(range(labelisation\_coarse) = [0, \ldots, num\_regions\_coarse[\)
Then, for all label \(i \in [0, \ldots, num\_regions\_fine[\),
\[result(i) = \arg \max_{j \in [0, \ldots, num\_regions\_coarse[}  (fine\_labelisation == i) \cap (coarse\_labelisation == j) \]If
num_regions_fine
ornum_regions_coarse
are not provided, they will be determined as \(max(labelisation\_fine) + 1\) and \(max(labelisation\_coarse) + 1\) Parameters
labelisation_fine – 1d array of positive integers
labelisation_coarse – 1d array of positive integers (same length as
labelisation_fine
)num_regions_fine – optional, number of different labels in
labelisation_fine
num_regions_coarse – optional, number of different labels in
labelisation_coarse
 Returns
a 1d array mapping fine labels to coarse labels
Horizontal Cut¶
This module offers two classes to ease the navigation through the horizontal cuts of a hierarchy.
This class helps to explore and to browse the horizontal cuts of a valued hierarchy. 

Represents an horizontal cut in a hierarchy as a set of nodes. 

Labelize tree leaves according to an horizontal cut of the tree given by its number of regions. 

Labelize tree leaves according to an horizontal cut of the tree given by its altitude. 

labelisation_horizontal_cut_from_num_regions
(tree, altitudes, num_regions, mode='at_least', leaf_graph=None)[source]¶ Labelize tree leaves according to an horizontal cut of the tree given by its number of regions.
If
mode
is"at_least"
(default), the the smallest horizontal cut having at least the given number of regions is considered. Ifmode
is"at_most"
, the the largest horizontal cut having at most the given number of regions is considered.Consider using the class
HorizontalCutExplorer
if you plan to compute several horizontal cuts from a same hierarchy. Parameters
tree – input tree (deduced from
CptHierarchy
)altitudes – node altitudes of the input tree
num_regions – a number of regions
mode –
"at_least"
or"at_most"
leaf_graph – graph of the tree leaves (optional, deduced from
CptHierarchy
)
 Returns
Leaf labels

labelisation_horizontal_cut_from_threshold
(tree, altitudes, threshold, leaf_graph=None)[source]¶ Labelize tree leaves according to an horizontal cut of the tree given by its altitude.
Two leaves are in the same region (ie. have the same label) if the altitude of their lowest common ancestor is strictly greater than the specified threshold.
Consider using the class
HorizontalCutExplorer
if you plan to compute several horizontal cuts from a same hierarchy. Parameters
tree – input tree (deduced from
CptHierarchy
)altitudes – node altitudes of the input tree
threshold – a threshold level
leaf_graph – graph of the tree leaves (optional, deduced from
CptHierarchy
)
 Returns
Leaf labels

class
HorizontalCutExplorer
¶ This class helps to explore and to browse the horizontal cuts of a valued hierarchy. Construction of the HorizontalCutExplorer if performed in linear time \(\mathcal{O}(n)\) w.r.t. the number of nodes in the tree. Each cut of the hierarchy can be accessed through:
its index (the first single region cut has index 0). This operations runs in \(\mathcal{O}(k)\), with \(k\) the number of regions in the retrieved cut ;
the number of regions in the cut (the smallest partition having at least the given number of regions if found). This operations runs in \(\mathcal{O}(k*\log(n))\), with \(k\) the number of regions in the retrieved cut;
the altitude of the cut. This operations runs in \(\mathcal{O}(k*\log(n))\), with \(k\) the number of regions in the retrieved cut.

__new__
(tree, altitudes)¶ Creates an horizontal cut explorer for the given valued hierarchy.
Altitudes must be increasing
 Parameters
tree – input tree
altitudes – tree nodes altitudes
 Returns
an
HorizontalCutExplorer

altitude_cut
(self: higra.higram.HorizontalCutExplorer, cut_index: int) → float¶ Altitude of the ith cut of the hierarchy (cut numbering start at 0 with the cut with a single region).

altitude_cuts
(self: higra.higram.HorizontalCutExplorer) → List[float]¶ Altitude of each cut of the hierarchy.

horizontal_cut_from_altitude
(self: higra.higram.HorizontalCutExplorer, threshold: float) → higra.higram.HorizontalCutNodes¶ Retrieve the horizontal cut for given threshold level.

horizontal_cut_from_index
(self: higra.higram.HorizontalCutExplorer, i: int) → higra.higram.HorizontalCutNodes¶ Retrieve the ith horizontal cut of tree (cut numbering start at 0 with the cut with a single region).

horizontal_cut_from_num_regions
(self: higra.higram.HorizontalCutExplorer, num_regions: int, at_least: bool = True) → higra.higram.HorizontalCutNodes¶ Horizontal cut with a given number of regions.
If
at_least
isTrue
(default), the the smallest horizontal cut having at least the given number of regions is returned. Ifat_least
isFalse
, the the largest horizontal cut having at most the given number of regions is returned.

num_cuts
(self: higra.higram.HorizontalCutExplorer) → int¶ Number of horizontal cuts in the hierarchy.

num_regions_cut
(self: higra.higram.HorizontalCutExplorer, i: int) → int¶ Number of regions in the ith cut of the hierarchy (cut numbering start at 0 with the cut with a single region).

num_regions_cuts
(self: higra.higram.HorizontalCutExplorer) → List[int]¶ Number of regions in each cut of the hierarchy.

class
HorizontalCutNodes
¶ Represents an horizontal cut in a hierarchy as a set of nodes.

__init__
()¶ Initialize self. See help(type(self)) for accurate signature.

altitude
(self: higra.higram.HorizontalCutNodes) → float¶ Altitude of the cut.

graph_cut
(tree, leaf_graph, handle_rag=True)¶ Graph cut corresponding to the tree cut. The edge (i, j) has a non zero value if the closest ancestors of i and j in the cut are different.
 Parameters
tree – input tree (Concept
CptHierarchy
)leaf_graph – graph on the tree leaves (deduced from
CptHierarchy
)handle_rag – if True and if leaf_graph is a region adjacency graph then the cut is given for the original graph (the pregraph of the region adjacency graph).
 Returns
a graph cut

labelisation_leaves
(tree, leaf_graph, handle_rag=True)¶ Labelize tree leaves according to the horizontal cut. Two leaves are in the same region (ie. have the same label) if their lowest common ancestor is a subset or equal to one the node of the cut.,
 Parameters
tree – input tree (Concept
CptHierarchy
)leaf_graph – graph on the tree leaves (deduced from
CptHierarchy
)handle_rag – if True and if leaf_graph is a region adjacency graph then the labels are given for the original graph (the pregraph of the region adjacency graph).
 Returns
a 1d array

nodes
(self: higra.higram.HorizontalCutNodes) → xt::xtensor¶ Array containing the indices of the nodes of the cut.

reconstruct_leaf_data
(tree, altitudes, leaf_graph, handle_rag=True)¶ Reconstruct the cut at leaf level of the provided tree. A leaf of the tree is valued by the altitude of the single cut node which is an ancestor of the leaf.
 Parameters
tree – input tree (Concept
CptHierarchy
)altitudes – node altitudes of the input tree
leaf_graph – graph on the tree leaves (deduced from
CptHierarchy
)handle_rag – if True and if leaf_graph is a region adjacency graph then the cut is given for the original graph (the pregraph of the region adjacency graph).
 Returns
leaf weights

Utility functions move and accumulates values along trees¶

Propagates parent values to children: for each node \(i\), if \(condition(i)\) then \(output(i) = node\_weights(tree.parent(i))\) otherwise \(output(i) = node\_weights(i)\). 

Sequentially propagates parent values to children: for each node \(i\) from the root to the leaves, if \(i\) is not the root and if \(condition(i)\) then \(output(i) = output(tree.parent(i))\) otherwise \(output(i) = node\_weights(i)\). 

Sequentially propagates parent values to children and accumulates with current value: for each node \(i\) from the root to the leaves, \(output(i) = accumulator(node\_weights(i), output(parent(i)))\). 

Accumulates values of the children of every node \(i\) in the \(node\_weights\) array and puts the result in output: \(output(i) = accumulator(node\_weights(children(i)))\) 

Sequential accumulation of node values from the leaves to the root. 

Accumulates node values from the leaves to the root and add the result with the input array. 

Accumulates node values from the leaves to the root and multiply the result with the input array. 

Accumulates node values from the leaves to the root and takes the maximum of result and the input array. 

Accumulates node values from the leaves to the root and takes the minimum of result and the input array. 

For each edge of the leaf graph, accumulates the weights of the nodes whose contour pass by this edge. 

propagate_parallel
(tree, node_weights, condition=None)[source]¶ Propagates parent values to children: for each node \(i\), if \(condition(i)\) then \(output(i) = node\_weights(tree.parent(i))\) otherwise \(output(i) = node\_weights(i)\).
The conditional parallel propagator pseudocode could be:
# input: a tree t # input: an attribute att on the nodes of t # input: a condition cond on the nodes of t output = copy(input) for each node n of t: if(cond(n)): output[n] = input[t.parent(n)] return output
 Parameters
tree – input tree
node_weights – Weights on the nodes of the tree
condition – Boolean array on the nodes of the tree
 Returns
returns new tree node weights

propagate_sequential
(tree, node_weights, condition)[source]¶ Sequentially propagates parent values to children: for each node \(i\) from the root to the leaves, if \(i\) is not the root and if \(condition(i)\) then \(output(i) = output(tree.parent(i))\) otherwise \(output(i) = node\_weights(i)\).
 Parameters
tree – input tree
node_weights – Weights on the nodes of the tree
condition – Boolean array on the nodes of the tree
 Returns
returns new tree node weights

propagate_sequential_and_accumulate
(tree, node_weights, accumulator)[source]¶ Sequentially propagates parent values to children and accumulates with current value: for each node \(i\) from the root to the leaves, \(output(i) = accumulator(node\_weights(i), output(parent(i)))\).
 Parameters
tree – input tree
node_weights – Weights on the nodes of the tree
accumulator – see
Accumulators
 Returns
returns new tree node weights

accumulate_parallel
(tree, node_weights, accumulator)[source]¶ Accumulates values of the children of every node \(i\) in the \(node\_weights\) array and puts the result in output: \(output(i) = accumulator(node\_weights(children(i)))\)
 Parameters
tree – input tree
node_weights – Weights on the nodes of the tree
accumulator – see
Accumulators
 Returns
returns new tree node weights

accumulate_sequential
(tree, leaf_data, accumulator, leaf_graph=None)[source]¶ Sequential accumulation of node values from the leaves to the root. For each leaf node \(i\), \(output(i) = leaf_data(i)\). For each node \(i\) from the leaves (excluded) to the root, \(output(i) = accumulator(output(children(i)))\)
 Parameters
tree – input tree (Concept
CptHierarchy
)leaf_data – array of weights on the leaves of the tree
accumulator – see
Accumulators
leaf_graph – graph of the tree leaves (optional, deduced from
CptHierarchy
)
 Returns
returns new tree node weights

accumulate_and_add_sequential
(tree, node_weights, leaf_data, accumulator, leaf_graph=None)[source]¶ Accumulates node values from the leaves to the root and add the result with the input array.
For each leaf node \(i\), output(i) = \(leaf\_data(i)\). For each node \(i\) from the leaves (excluded) to the root, \(output(i) = input(i) + accumulator(output(children(i)))\)
 Parameters
tree – input tree (Concept
CptHierarchy
)node_weights – Weights on the nodes of the tree
leaf_data – Weights on the leaves of the tree
accumulator – see
Accumulators
leaf_graph – graph of the tree leaves (optional, deduced from
CptHierarchy
)
 Returns
returns new tree node weights

accumulate_and_multiply_sequential
(tree, node_weights, leaf_data, accumulator, leaf_graph=None)[source]¶ Accumulates node values from the leaves to the root and multiply the result with the input array.
For each leaf node \(i\), \(output(i) = leaf_data(i)\). For each node \(i\) from the leaves (excluded) to the root, \(output(i) = input(i) + accumulator(output(children(i)))\)
 Parameters
tree – input tree (Concept
CptHierarchy
)node_weights – Weights on the nodes of the tree
leaf_data – Weights on the leaves of the tree
accumulator – see
Accumulators
leaf_graph – graph of the tree leaves (optional (optional, deduced from
CptHierarchy
))
 Returns
returns new tree node weights

accumulate_and_max_sequential
(tree, node_weights, leaf_data, accumulator, leaf_graph=None)[source]¶ Accumulates node values from the leaves to the root and takes the maximum of result and the input array.
For each leaf node \(i\), \(output(i) = leaf_data(i)\). For each node \(i\) from the leaves (excluded) to the root, \(output(i) = \max(input(i), accumulator(output(children(i)))\)
 Parameters
tree – input tree (Concept
CptHierarchy
)node_weights – Weights on the nodes of the tree
leaf_data – Weights on the leaves of the tree
accumulator – see
Accumulators
leaf_graph – graph of the tree leaves (optional, deduced from
CptHierarchy
)
 Returns
returns new tree node weights

accumulate_and_min_sequential
(tree, node_weights, leaf_data, accumulator, leaf_graph=None)[source]¶ Accumulates node values from the leaves to the root and takes the minimum of result and the input array.
For each leaf node \(i\), \(output(i) = leaf_data(i)\). For each node \(i\) from the leaves (excluded) to the root, \(output(i) = \min(input(i), accumulator(output(children(i)))\)
 Parameters
tree – input tree (Concept
CptHierarchy
)node_weights – Weights on the nodes of the tree
leaf_data – Weights on the leaves of the tree
accumulator – see
Accumulators
leaf_graph – graph of the tree leaves (optional, deduced from
CptHierarchy
)
 Returns
returns new tree node weights

accumulate_on_contours
(tree, node_weights, accumulator, leaf_graph)[source]¶ For each edge of the leaf graph, accumulates the weights of the nodes whose contour pass by this edge.
For any edge \(\{x,y\}\), let \(R_{\{x,y\}}\) be the set of regions of the input tree \(T\) having \(\{x,y\}\) in its contour:
\[R_{\{x,y\}} = \{n \in T \, \, \{x,y\} \cap n = 1 \}\]The output value for the edge \(\{x,y\}\) is then the accumulated weights of the nodes in \(R_{\{x,y\}}\).
 Runtime complexity
This algorithm runs in \(\mathcal{O}(n*k)\) with \(n\) the number of edges in the leaf graph and \(k\) the maximal depth of the tree (i.e. the number of edges on the longest downward path between the root and a leaf).
 Parameters
tree – input tree (Concept
CptHierarchy
)node_weights – weights on the nodes of the tree
accumulator – see
Accumulators
leaf_graph – graph of the tree leaves (deduced from
CptHierarchy
)
 Returns
returns leaf graph edge weights
Algorithm for trees¶

Given two binary markers \(o\) (object) and \(b\) (background) (given by their indicator functions) on the leaves of a tree \(T\), the corresponding binary labelization of the leaves of \(T\) is defined as the union of all the nodes intersecting \(o\) but not \(b\): 

Filter the given tree according to a functor telling if nodes are relevant or not. 

Filter the given tree according to node size: 

Filter the given tree according to the frontier strength. 

Labelize the tree leaves into supervertices. 

Each leaf of the tree takes the altitude of its closest non deleted ancestor. 

Sort the nodes of a tree according to their altitudes. 

Test if the altitudes of the given tree are increasing; i.e. 

Test if 2 trees \(t_1\) and \(t_2\) are isomorph assuming that they share the same leaves. 

Depth map associated to the fusion of the given list of trees. 

Monotonic regression on the given tree altitudes. 

binary_labelisation_from_markers
(tree, object_marker, background_marker, leaf_graph=None)[source]¶ Given two binary markers \(o\) (object) and \(b\) (background) (given by their indicator functions) on the leaves of a tree \(T\), the corresponding binary labelization of the leaves of \(T\) is defined as the union of all the nodes intersecting \(o\) but not \(b\):
\[res = \bigcup \{R \in T \mid R \cap o \neq \emptyset, \textrm{ and } R \cap b = \emptyset\}\] Parameters
tree – input tree (Concept
CptHierarchy
)object_marker – indicator function of the object marker: 1d array of size tree.num_leaves() where non zero values correspond to the object marker
background_marker – indicator function of the background marker: 1d array of size tree.num_leaves() where non zero values correspond to the background marker
leaf_graph – graph on the leaves of the input tree (optional, deduced from
CptHierarchy
)
 Returns
Leaf labels

filter_non_relevant_node_from_tree
(tree, altitudes, non_relevant_functor, leaf_graph, canonize_tree=True)[source]¶ Filter the given tree according to a functor telling if nodes are relevant or not.
In a binary a tree, each inner node (non leaf node) is associated to the frontier separating its two children. If a the frontier associated to a node is considered as non relevant (for example because on of the two children of the node is too small) then the corresponding frontier is removed effectively merging its two children.
This function returns a binary partition tree such that:
the frontiers associated to nodes marked nonrelevant do not exist anymore;
the regions of the new tree are either regions of the initial tree or regions obtained by merging adjacent regions of the initial tree.
If
tree
does not satisfy the conceptCptBinaryHierarchy
, the given tree is first transformed into a binary tree (arbitrary choices are made).non_relevant_functor
must be a function that accepts two arguments, a binary tree and its node altitudes, and must return a boolean node attribute for the given tree (ie a 1d array of booleanish values of sizetree.num_vertices()
. A value ofTrue
is interpreted as this node is not relevant and its associated frontier must be removed. See
filter_small_nodes_from_tree()
filter_weak_frontier_nodes_from_tree()
 Parameters
tree – input tree (Concept
CptHierarchy
)altitudes – node altitudes of the input tree
non_relevant_functor – a function that computes an attribute on a binary tree
leaf_graph – graph of the tree leaves (deduced from
CptHierarchy
)canonize_tree – if
True
(default), the resulting hierarchy is canonized (see functioncanonize_hierarchy()
), otherwise the returned hierarchy is a binary tree
 Returns
a tree (Concept
CptHierarchy
isTrue
andCptBinaryHierarchy
otherwise) and its node altitudes

filter_small_nodes_from_tree
(tree, altitudes, size_threshold, leaf_graph, canonize_tree=True)[source]¶ Filter the given tree according to node size:
This function returns a binary partition tree such that:
it does not contain any region whose size is below the given threshold;
the regions of the new tree are either regions of the initial tree or regions obtained by merging adjacent regions of the initial tree.
 See
 Parameters
tree – input tree (Concept
CptHierarchy
)altitudes – node altitudes of the input tree
size_threshold – regions whose size is smaller than this threshold will be removed (see
attribute_area()
)leaf_graph – graph of the tree leaves (deduced from
CptHierarchy
)canonize_tree – if
True
(default), the resulting hierarchy is canonized (see functioncanonize_hierarchy()
), otherwise the returned hierarchy is a binary tree
 Returns
a tree (Concept
CptHierarchy
isTrue
andCptBinaryHierarchy
otherwise) and its node altitudes

filter_weak_frontier_nodes_from_tree
(tree, altitudes, edge_weights, strength_threshold, leaf_graph, canonize_tree=True)[source]¶ Filter the given tree according to the frontier strength.
The strength of a frontier is defined as the mean weights of the edges crossing the frontier (see
attribute_frontier_strength()
).This function returns a binary partition tree such that:
it does not contain any contour whose strength is lower than the given threshold;
the regions of the new tree are either regions of the initial tree or regions obtained by merging adjacent regions of the initial tree.
 See
 Parameters
tree – input tree (Concept
CptHierarchy
)altitudes – node altitudes of the input tree
leaf_graph – graph of the tree leaves (deduced from
CptHierarchy
)edge_weights – edge weights of the leaf graph
strength_threshold – regions whose associated frontier strength is smaller than the given threshold are removed (see
attribute_frontier_strength()
)canonize_tree – if
True
(default), the resulting hierarchy is canonized (see functioncanonize_hierarchy()
), otherwise the returned hierarchy is a binary tree
 Returns
a tree (Concept
CptHierarchy
isTrue
andCptBinaryHierarchy
otherwise) and its node altitudes

labelisation_hierarchy_supervertices
(tree, altitudes, leaf_graph=None, handle_rag=True)[source]¶ Labelize the tree leaves into supervertices. The altitudes must be increasing, i.e. for any nodes \(i, j\) such that \(j\) is an ancestor of \(i\), then \(altitudes[i] \leq altitudes[j]\). Two leaves are in the same supervertex if they have a common ancestor at altitude 0.
If we consider that the pair \((tree, altitudes)\) represents a dendrogram, i.e. that it defines a pseudoultrametric on the set of leaves, a supervertex is a maximal cluster such that the distance between any pair of points in the cluster is equal to 0.
This functions guaranties that the labels are in the range \([0, num\_supervertices1]\).
 Parameters
tree – input tree (Concept
CptHierarchy
)altitudes – node altitudes of the input tree
leaf_graph – graph of the tree leaves (optional, deduced from
CptHierarchy
)handle_rag – if True and the provided tree has been built on a region adjacency graph, then the labelisation corresponding to the rag regions is returned.
 Returns
Leaf labels

reconstruct_leaf_data
(tree, altitudes, deleted_nodes=None, leaf_graph=None)[source]¶ Each leaf of the tree takes the altitude of its closest non deleted ancestor.
The root node is never deleted. In a component tree, leaves are always deleted.
If
deleted_nodes
isNone
then its default value is set to np.zeros((tree.numvertices(),) (no nodes are deleted). Parameters
tree – input tree (Concept
CptHierarchy
)altitudes – node altitudes of the input tree
deleted_nodes – binary node weights indicating which nodes are deleted (optional)
leaf_graph – graph of the tree leaves (optional, deduced from
CptHierarchy
)
 Returns
Leaf weights

sort_hierarchy_with_altitudes
(tree, altitudes)[source]¶ Sort the nodes of a tree according to their altitudes. The altitudes must be increasing, i.e. for any nodes \(i, j\) such that \(j\) is an ancestor of \(i\), then \(altitudes[i] \leq altitudes[j]\).
The result is a new tree and a node map, isomorph to the input tree such that for any nodes \(i\) and \(j\), \(i<j \Rightarrow altitudes[node\_map[i]] \leq altitudes[node\_map[j]]\)
The latter condition is stronger than the original condition on the altitudes as \(j\) is an ancestor of \(i\) implies \(i<j\) while the converse is not true.
The returned “node_map” is an array that maps any node index \(i\) of the new tree, to the index of this node in the original tree.
 Parameters
tree – input tree
altitudes – node altitudes of the input tree
 Returns
the sorted tree (Concept
CptHierarchy
), its node altitudes, and the node map

test_altitudes_increasingness
(tree, altitudes)[source]¶ Test if the altitudes of the given tree are increasing; i.e. if for any nodes \(i, j\) such that \(j\) is an ancestor of \(i\), then \(altitudes[i] \leq altitudes[j]\).
 Parameters
tree – input tree
altitudes – node altitudes of the input tree
 Returns
True
ifaltitudes
are increasing fortree
,False
otherwise.

test_tree_isomorphism
(tree1: hg::tree_internal::tree, tree2: hg::tree_internal::tree) → bool¶ Test if 2 trees \(t_1\) and \(t_2\) are isomorph assuming that they share the same leaves.
By this definition \(t_1\) is isomorph to \(t_2\) if there exists a bijection \(f\) from the nodes of \(t_1\) to the nodes of \(t_2\) such that:
for any leaf node \(n\) of \(t_1\), \(f(n) = n\), and
for any node \(n\) of \(t_1\), \(f(t_1.parent(n)) = t_2.parent(f(n))\)
Note that the root node of \(r\) a tree \(t\) is defined by \(t.parent(r) = r\), thus 2) becomes for the root node \(r_1\) of \(t_1\), \(f(r_1) = t_2.parent(f(r_1))\), i.e. \(f(r_1)\) is the root node of \(t_2\)

tree_fusion_depth_map
(*trees)[source]¶ Depth map associated to the fusion of the given list of trees. This depth map can be used to compute a new tree representing the fusion of the input trees, eg. with
component_tree_max_tree()
.The method is described in:
E. Carlinet. A Tree of shapes for multivariate images. PhD Thesis, Université ParisEst, 2015.
All trees must be defined over the same domain, i.e. have the same number of leaves. Given a set of trees \((T_1, T_2, T_3,... T_n)\) composed of the set of nodes \((N_1, N_2, N_3, ... N_n)\). We define the fusion graph as the graph induced the inclusion relation \(\subseteq\) on the union of all the tree nodes \(\bigcup\{N_1, N_2, N_3, ... N_n\}\).
The result is a directed acyclic graph with a single root (corresponding to the roots of the input trees). The depth of a node in this graph is defined as the length of the longest path from the root this node. This function returns the depth of the leaves of this graph (which are the same as the leaves of the input trees).
 See
A multivariate tree of shapes of a colour 2d can be computed with
component_tree_multivariate_tree_of_shapes_image2d()
. Complexity
The worst case runtime complexity of this method is \(\mathcal{O}(N^2D^2)\) with \(N\) the number of leaves and \(D\) the number of trees. If we denote by \(K\) the depth of the deepest tree to merge, one can rewrite the runtime complexity as \(\mathcal{O}(NKD^2)\).
 Parameters
trees – at least two trees defined over the same domain
 Returns
a depth map representing the fusion of the input trees

tree_monotonic_regression
(tree, altitudes, mode, weights=None)[source]¶ Monotonic regression on the given tree altitudes. Computes new altitudes
naltitudes
that are close to the givenaltitudes
and that are increasing for the giventree
: i.e. for any nodes \(i, j\) such that \(j\) is an ancestor of \(i\), then \(naltitudes[i] \leq naltitudes[j]\).The definition of close depends of the value of
mode
:If
mode
is equal to"min"
thennaltitudes
is the largest increasing function belowaltitudes
.If
mode
is equal to"max"
thennaltitudes
is the smallest increasing function abovealtitudes
.If
mode
is equal to"least_square"
thennaltitudes
minizes the following minization problem:
\[naltitudes = \arg \min_x \sum_i (weights[i] * (altitudes[i]  x[i])^2)\]such that
naltitudes
is increasing fortree
. Complexity
With \(n\) the number of nodes in the
tree
:For the modes
"min"
and"max"
, the runtime complexity is linear \(\mathcal{O}(n)\).For the mode
"least_square"
, the runtime complexity is linearithmic \(\mathcal{O}(n\log(n))\) and the space complexity is linear \(\mathcal{O}(n)\). The algorithm used is described in:P. Pardalos and G. Xue ‘Algorithms for a Class of Isotonic Regression Problems.’ Algorithmica (1999) 23: 211. doi:10.1007/PL00009258
 Parameters
tree – input tree
altitudes – node altitudes of the input tree
mode – the regression mode :
"min"
,"max"
, or"least_square"
weights – node weights of the input tree (default to an array of 1s). This parameter is ignored if
mode
is not"least_square"
.
 Returns
a 1d array
Tree attributes¶

Area of each node the given tree. 

Given a node \(n\) whose parent is \(p\), the attribute value of \(n\) is the rank of \(n\) in the list of children of \(p\). 

Length of the contour (perimeter) of each node of the given tree. 

Strength of the contour of each node of the given tree. 

The compactness of a node is defined as its area divided by the square of its perimeter length. 

The depth of a node \(n\) of the tree \(T\) is equal to the number of ancestors of \(n\) in \(T\). 

Given a node \(n\) of the tree \(T\), the dynamics of \(n\) is the difference between the altitude of the deepest minima of the subtree rooted in \(n\) and the altitude of the closest ancestor of \(n\) that has a deeper minima in its subtree. 

The extinction value of a node \(n\) of the input tree \(T\) with increasing altitudes \(alt\) for the increasing attribute \(att\) is the equal to the threshold \(k\) such that the node \(n\) is still in an minima of \(t\) when all nodes having an attribute value smaller than \(k\) are removed. 

Identify nodes in a hierarchy that represent extrema (minima or maxima). 

Length of the frontier represented by each node the given partition tree. 

Mean edge weight along the frontier represented by each node the given partition tree. 
Estimates a gaussian model (mean, (co)variance) for leaf weights inside a node. 


In a tree \(T\), given that the altitudes of the nodes vary monotically from the leaves to the root, the height of a node \(n\) of \(T\) is equal to the difference between the altitude of the parent of \(n\) and the altitude of the deepest nonleaf node in the subtree of \(T\) rooted in \(n\). 

Lowest common ancestor of i and j for each edge \((i, j)\) of the leaf graph of the given tree. 

Mean vertex weights of the leaf graph vertices inside each node of the given tree. 

Moment of inertia (first Hu moment) of each node of the given tree. 

Given a tree \(T\) with node weights \(w\): the children pair sum product for a node \(n\) sums for every pairs \((c_i, c_j)\) of children of \(n\), the product of the node weights of \(c_i\) and \(c_j\). 
Piecewise constant MumfordShah energy of each node of the input tree. 


Regular altitudes is comprised between 0 and 1 and is inversely proportional to the depth of a node 

Sibling index of each node of the given tree. 
Given a node \(n\) of 


Given a tree \(T\), estimate the probability that a node \(n\) of the tree represents the smallest cluster containing a pair of vertices \(\{a, b\}\) of the graph \(G=(V, E)\) with edge weights \(w\). 

Volume of each node the given tree. 

attribute_area
(tree, vertex_area=None, leaf_graph=None)[source]¶ Area of each node the given tree. The area of a node is equal to the sum of the area of the leaves of the subtree rooted in the node.
 Parameters
tree – input tree (Concept
CptHierarchy
)vertex_area – area of the vertices of the leaf graph of the tree (provided by
attribute_vertex_area()
on leaf_graph )leaf_graph – (deduced from
CptHierarchy
)
 Returns
a 1d array
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_child_number
(tree)[source]¶ Given a node \(n\) whose parent is \(p\), the attribute value of \(n\) is the rank of \(n\) in the list of children of \(p\). In other \(attribute(n)=i\) means that \(n\) is the \(i\)th child of \(p\).
The root of the tree, who has no parent, take the value 1.
 Parameters
tree – Input tree
 Returns
a 1d array
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_contour_length
(tree, vertex_perimeter=None, edge_length=None, leaf_graph=None)[source]¶ Length of the contour (perimeter) of each node of the given tree.
 Parameters
tree – input tree (Concept
CptHierarchy
)vertex_perimeter – perimeter of each vertex of the leaf graph (provided by
attribute_vertex_perimeter()
on leaf_graph)edge_length – length of each edge of the leaf graph (provided by
attribute_edge_length()
on leaf_graph)leaf_graph – (deduced from
CptHierarchy
)
 Returns
a 1d array
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_contour_strength
(tree, edge_weights, vertex_perimeter=None, edge_length=None, leaf_graph=None)[source]¶ Strength of the contour of each node of the given tree. The strength of the contour of a node is defined as the mean edge weights on the contour.
 Parameters
tree – input tree (Concept
CptHierarchy
)edge_weights – edge_weights of the leaf graph
vertex_perimeter – perimeter of each vertex of the leaf graph (provided by
attribute_vertex_perimeter()
on leaf_graph)edge_length – length of each edge of the leaf graph (provided by
attribute_edge_length()
on leaf_graph)leaf_graph – (deduced from
CptHierarchy
)
 Returns
a 1d array
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_compactness
(tree, area=None, contour_length=None, normalize=True, leaf_graph=None)[source]¶ The compactness of a node is defined as its area divided by the square of its perimeter length.
 Parameters
tree – input tree (Concept
CptHierarchy
)area – node area of the input tree (provided by
attribute_area()
on tree)contour_length – node contour length of the input tree (provided by
attribute_perimeter_length()
on tree)normalize – if True the result is divided by the maximal compactness value in the tree
leaf_graph – (deduced from
CptHierarchy
)
 Returns
a 1d array
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_depth
(tree)[source]¶ The depth of a node \(n\) of the tree \(T\) is equal to the number of ancestors of \(n\) in \(T\).
The depth of the root node is equal to 0.
 Parameters
tree – Input tree
 Returns
a nd array
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_dynamics
(tree, altitudes, increasing_altitudes='auto')[source]¶ Given a node \(n\) of the tree \(T\), the dynamics of \(n\) is the difference between the altitude of the deepest minima of the subtree rooted in \(n\) and the altitude of the closest ancestor of \(n\) that has a deeper minima in its subtree. If no such ancestor exists then, the dynamics of \(n\) is equal to the difference between the altitude of the highest node of the tree (the root) and the depth of the deepest minima.
The dynamics is the extinction values (
attribute_extinction_value()
) for the attribute height (attribute_height()
).Possible values of
increasing_altitude
are:'auto'
: the function will automatically determine ifaltitudes
are increasing or decreasing (this has small computational cost but does not impact the runtime complexity).True
or'increasing'
: this means that altitudes are increasing from the leaves to the root (ie. for any node \(n\), \(altitudes(n) \leq altitudes(parent(n))\).False
or'decreasing'
: this means that altitudes are decreasing from the leaves to the root (ie. for any node \(n\), \(altitude(n) \geq altitude(parent(n))\).
 Parameters
tree – Input tree
altitudes – Tree node altitudes
increasing_altitudes – possible values ‘auto’, True, False, ‘increasing’, and ‘decreasing’
 Returns
a 1d array like
altitudes
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_extinction_value
(tree, altitudes, attribute, increasing_altitudes='auto')[source]¶ The extinction value of a node \(n\) of the input tree \(T\) with increasing altitudes \(alt\) for the increasing attribute \(att\) is the equal to the threshold \(k\) such that the node \(n\) is still in an minima of \(t\) when all nodes having an attribute value smaller than \(k\) are removed.
Formally, let \(\{M_i\}\) be the set of minima of the hierarchy \(T\) with altitudes \(alt\). Let \(prec\) be a total ordering of \(\{M_i\}\) such that \(M_i \prec M_j \Rightarrow alt(M_i) \leq alt(M_j)\). Let \(r(M_i)\) be the smallest node of \(t\) containing \(M_i\) and another minima \(M_j\) such that \(M_j \prec M_i\). The extinction value of \(M_i\) is then defined as \(alt(r(M_i))  alt(M_i)\).
Extinction values of minima are then extended to other nodes in the tree with the following rules:
the extinction value of a nonleaf node \(n\) which is not a minimum is defined as the largest extinction values among all the minima contained in \(n\) (and 0 if \(n\) does not contain any minima); and
the extinction value of a leaf node \(n\) belonging to a minima \(M_i\) is equal to the extinction value of \(M_i\). I \(n\) does not belong to any minima its extinction value is 0.
The function can also handle decreasing altitudes, in which case minima should be replaced by maxima in the description above. Possible values of
increasing_altitude
are:'auto'
: the function will automatically determine ifaltitudes
are increasing or decreasing (this has small computational cost but does not impact the runtime complexity).True
or'increasing'
: this means that altitudes are increasing from the leaves to the root (ie. for any node \(n\), \(altitudes(n) \leq altitudes(parent(n))\).False
or'decreasing'
: this means that altitudes are decreasing from the leaves to the root (ie. for any node \(n\), \(altitude(n) \geq altitude(parent(n))\).
 Parameters
tree – Input tree
altitudes – Tree node altitudes
attribute – Tree node attribute
increasing_altitudes – possible values ‘auto’, True, False, ‘increasing’, and ‘decreasing’
 Returns
a 1d array like
attribute

attribute_extrema
(tree, altitudes)[source]¶ Identify nodes in a hierarchy that represent extrema (minima or maxima).
An extremum (minimum or maximum) of the hierarchy \(T\) with altitudes \(alt\) is a node \(n\) of \(T\) such that the altitude of any non leaf node included in \(n\) is equal to the altitude of \(n\) and the altitude of the parent of \(n\) is different from the altitude of \(n\).
The result is a boolean array such that \(result(n)\) is
True
if the node \(n\) is an extremum andFalse
otherwise. Parameters
tree – Input tree
altitudes – Tree node altitudes
 Returns
a 1d boolean array
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_frontier_length
(tree, edge_length=None, leaf_graph=None)[source]¶ Length of the frontier represented by each node the given partition tree.
In a partition tree, each node represent the merging of 2 or more regions. The frontier of a node is then defined as the common contour between the merged regions. This function compute the length of these common contours as the sum of the length of edges going from one of the merged region to the other one.
The result has the same dtype as the edge_length array.
 Parameters
tree – input tree
edge_length – length of the edges of the leaf graph (provided by
attribute_edge_length()
on leaf_graph)leaf_graph – graph on the leaves of the input tree (deduced from
CptHierarchy
)
 Returns
a 1d array
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_frontier_strength
(tree, edge_weights, leaf_graph)[source]¶ Mean edge weight along the frontier represented by each node the given partition tree.
In a partition tree, each node represent the merging of 2 or more regions. The frontier of a node is then defined as the common contour between the merged regions. This function compute the strength of a common contour as the sum of the weights of edges going from one of the merged region to the other one divided by the length of the contour.
The result has the same dtype as the edge_weights array.
 Parameters
tree – input tree
edge_weights – weight of the edges of the leaf graph (if leaf_graph is a region adjacency graph, edge_weights might be weights on the edges of the pregraph of the rag).
leaf_graph – graph on the leaves of the input tree (deduced from
CptHierarchy
)
 Returns
a 1d array
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_gaussian_region_weights_model
(tree, vertex_weights, leaf_graph=None)[source]¶ Estimates a gaussian model (mean, (co)variance) for leaf weights inside a node.
The result is composed of two arrays:
the first one contains the mean value inside each node, scalar if vertex weights are scalar and vectorial otherwise,
the second one contains the variance of the values inside each node, scalar if vertex weights are scalar and a (biased) covariance matrix otherwise.
Vertex weights must be scalar or 1 dimensional.
 Parameters
tree – input tree (Concept
CptHierarchy
)vertex_weights – vertex weights of the leaf graph of the input tree
leaf_graph – leaf graph of the input tree (deduced from
CptHierarchy
)
 Returns
two arrays mean and variance
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_height
(tree, altitudes, increasing_altitudes='auto')[source]¶ In a tree \(T\), given that the altitudes of the nodes vary monotically from the leaves to the root, the height of a node \(n\) of \(T\) is equal to the difference between the altitude of the parent of \(n\) and the altitude of the deepest nonleaf node in the subtree of \(T\) rooted in \(n\).
Possible values of
increasing_altitude
are:'auto'
: the function will automatically determine ifaltitudes
are increasing or decreasing (this has small computational cost but does not impact the runtime complexity).True
or'increasing'
: this means that altitudes are increasing from the leaves to the root (ie. for any node \(n\), \(altitudes(n) \leq altitudes(parent(n))\).False
or'decreasing'
: this means that altitudes are decreasing from the leaves to the root (ie. for any node \(n\), \(altitude(n) \geq altitude(parent(n))\).
 Parameters
tree – Input tree
altitudes – Tree node altitudes
increasing_altitudes – possible values ‘auto’, True, False, ‘increasing’, and ‘decreasing’
 Returns
a 1d array like
altitudes
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_lca_map
(tree, leaf_graph)[source]¶ Lowest common ancestor of i and j for each edge \((i, j)\) of the leaf graph of the given tree.
Complexity: \(\mathcal{O}(n\log(n)) + \mathcal{O}(m)\) where \(n\) is the number of nodes in tree and \(m\) is the number of edges in
leaf_graph
. Parameters
tree – input tree (Concept
CptHierarchy
)leaf_graph – graph on the leaves of the input tree (deduced from
CptHierarchy
on tree)
 Returns
a 1d array
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_mean_vertex_weights
(tree, vertex_weights, area=None, leaf_graph=None)[source]¶ Mean vertex weights of the leaf graph vertices inside each node of the given tree.
For any node \(n\), the mean vertex weights \(a(n)\) of \(n\) is
\[a(n) = \frac{\sum_{x\in n} vertex\_weights(x)}{area(n)}\] Parameters
tree – input tree (Concept
CptHierarchy
)vertex_weights – vertex weights of the leaf graph of the input tree
area – area of the tree nodes (provided by
attribute_area()
)leaf_graph – leaf graph of the input tree (deduced from
CptHierarchy
)
 Returns
a nd array
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_moment_of_inertia
(tree, leaf_graph)[source]¶ Moment of inertia (first Hu moment) of each node of the given tree. This function works only if
leaf_graph
is a 2D grid graph. The moment of inertia is a translation, scale and rotation invariant characterization of the shape of the nodes.Given a node \(X\) of
tree
, the raw moments \(M_{ij}\) are defined as:\[M_{ij} = \sum_{x}\sum_{y} x^i y^j\]where \((x,y)\) are the coordinates of every vertex in \(X\). Then, the centroid \(\{\overline{x},\overline{y}\}\) of \(X\) is given by
\[\overline{x} = \frac{M_{10}}{M_{00}} \textrm{ and } \overline{y} = \frac{M_{01}}{M_{00}}\]Some central moments of \(X\) are then:
\(\mu_{00} = M_{00}\)
\(\mu_{20} = M_{20}  \overline{x} \times M_{10}\)
\(\mu_{02} = M_{02}  \overline{y} \times M_{01}\)
The moment of inertia \(I_1\) of \(X\) if finally defined as
\[I_1 = \eta_{20} + \eta_{02}\]where \(\eta_{ij}\) are given by:
\(\eta_{ij} = \frac{\mu_{ij}}{\mu_{00}^{1+\frac{i+j}{2}}}\)
 Parameters
tree – input tree (Concept
CptHierarchy
)leaf_graph – graph on the leaves of the input tree (deduced from
CptHierarchy
on tree)
 Returns
a 1d array
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_children_pair_sum_product
(tree, node_weights)[source]¶ Given a tree \(T\) with node weights \(w\): the children pair sum product for a node \(n\) sums for every pairs \((c_i, c_j)\) of children of \(n\), the product of the node weights of \(c_i\) and \(c_j\). Formally:
\[res(n) = \sum_{i=0}^{i<numc(n)} \sum_{j=0}^{j<i} w(child(i, n)) * w(child(j, n))\]where \(numc(n)\) is the number of children of \(n\) and \(child(i, n)\) is the \(i\)th child of the node \(n\).
The result is thus an array with the same shape as
node_weights
 Parameters
tree – Input tree
node_weights – node weights of the input tree
 Returns
an array with the same shape as
node_weights

attribute_piecewise_constant_Mumford_Shah_energy
(tree, vertex_weights, gamma, leaf_graph)[source]¶ Piecewise constant MumfordShah energy of each node of the input tree. The energy of a node is equal to its data fidelity energy plus gamma times its regularization energy.
For the piecewise constant MumfordShah model:
the data fidelity energy assumes a piecewise constant model in each node and is given by the variance of the vertex values inside the node (see function
attribute_gaussian_region_weights_model()
) multiplied by its area,the regularity energy is given by the length of the contour of the node (see function
attribute_contour_length()
).
 Parameters
tree – input tree (Concept
CptHierarchy
)vertex_weights – vertex weights of the leaf graph of the input tree
gamma – weighting of the regularization term (should be a positive value)
leaf_graph – leaf graph of the input tree (deduced from
CptHierarchy
)
 Returns
a 1d array measuring the energy of each node the input tree

attribute_regular_altitudes
(tree, depth=None)[source]¶ Regular altitudes is comprised between 0 and 1 and is inversely proportional to the depth of a node
 Parameters
tree – input tree
depth – depth of the tree node (provided by
attribute_depth()
)
 Returns
a nd array
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_sibling
(tree, skip=1)[source]¶ Sibling index of each node of the given tree.
For each node \(n\) which is the \(k\)th child of its parent node \(p\) among \(N\) children, the attribute sibling of \(n\) is the index of the \((k + skip) % N\)th child of \(p\).
The sibling of the root node is itself.
The sibling attribute enables to easily emulates a (doubly) linked list among brothers.
In a binary tree, the sibling attribute of a node is effectively its only brother (with skip equals to 1).
 Parameters
tree – Input tree
skip – Number of skipped element in the children list (including yourself)
 Returns
a nd array
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_topological_height
(tree)[source]¶ Given a node \(n\) of
tree
, the topological height of \(n\) is the number of edges on the longest path from the node \(n\) to a leaf oftree
.The topological height of the leaves is equal to 0.
 Parameters
tree – Input tree
 Returns
a 1d array
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_tree_sampling_probability
(tree, leaf_graph, leaf_graph_edge_weights, model='edge')[source]¶ Given a tree \(T\), estimate the probability that a node \(n\) of the tree represents the smallest cluster containing a pair of vertices \(\{a, b\}\) of the graph \(G=(V, E)\) with edge weights \(w\).
This method is defined in 1.
We define the probability \(P(\{a,b\})\) of a pair of vertices \(\{a,b\}\) as \(w(\{a,b\}) / Z\) with \(Z=\sum_{e\in E}w(E)\) if \(\{a,b\}\) is an edge of \(G\) and 0 otherwise. Then the probability \(P(a)\) of a vertex \(b\) is defined as \(\sum_{b\in V}P(\{a, b\})\)
Two sampling strategies are proposed for sampling pairs of vertices to compute the probability of a node of the tree:
edge: the probability of sampling the pair \(\{a, b\}\) is given by \(P(\{a, b\})\); and
null: the probability of sampling the pair \(\{a, b\}\) is given by the product of the probabilities of \(a\) and \(b\): \(P(a)*P(b)\).
Assuming that the edge weights on the leaf graph of a hierarchy represents similarities:
We expect these distributions to differ significantly if the tree indeed represents the hierarchical structure of the graph. Specifically, we expect [the edge distribution] to be mostly concentrated on deep nodes of the tree (far from the root), as two nodes \(u\), \(v\) connected with high weight \(w(\{u, v\})\) in the graph typically belong to a small cluster, representative of the clustering structure of the graph; on the contrary, we expect [the null distribution] to be concentrated over shallow nodes (close to the root) as two nodes \(w(\{u, v\})\) sampled independently at random typically belong to large clusters, less representative of the clustering structure of the graph. 1
 1(1,2)
Charpentier, B. & Bonald, T. (2019). “Tree Sampling Divergence: An InformationTheoretic Metric for Hierarchical Graph Clustering.” Proceedings of IJCAI.
 Complexity
The tree sampling divergence runtime complexity depends of the sampling model:
edge: \(\mathcal{O}(N\log(N) + M)\) with \(N\) the number of nodes in the tree and \(M\) the number of edges in the leaf graph.
null: \(\mathcal{O}(N\times C^2)\) with \(N\) the number of nodes in the tree and \(C\) the maximal number of children of a node in the tree.
 See
The
tree_sampling_divergence()
is a non supervised hierarchical cost function defined as the KullbackLeibler divergence between the edge sampling model and the independent (null) sampling model. Parameters
tree – Input tree
leaf_graph – Graph defined on the leaves of the input tree
leaf_graph_edge_weights – Edge weights of the leaf graphs (similarities)
model – defines the edge sampling strategy, either “edge” or “null”
 Returns
a 1d array

attribute_volume
(tree, altitudes, area=None)[source]¶ Volume of each node the given tree. The volume \(V(n)\) of a node \(n\) is defined recursively as:
\[V(n) = area(n) *  altitude(n)  altitude(parent(n))  + \sum_{c \in children(n)} V(c)\] Parameters
tree – input tree
altitudes – node altitudes of the input tree
area – area of the nodes of the input hierarchy (provided by
attribute_area()
on tree)
 Returns
a 1d array
Autocache: This function is decorated with the
auto_cache()
decorator.
Tree energy optimization¶

Labelisation of the input tree leaves corresponding to the optimal cut according to the given energy attribute. 
Transforms the given hierarchy into its optimal energy cut hierarchy for the given energy terms. 

Transform the given hierarchy into an optimal energy cut hierarchy using the piecewise constant MumfordShah energy (see function 

labelisation_optimal_cut_from_energy
(tree, energy_attribute, accumulator=<Accumulators.sum: 6>, leaf_graph=None)[source]¶ Labelisation of the input tree leaves corresponding to the optimal cut according to the given energy attribute.
Given a node \(i\), the value \(energy(i)\) represents the energy fo the partial partition composed of the single region \(i\). Given a node \(i\), the energy of the partial partition composed of the children of \(i\) is given by \(accumulator(energy(children(i)))\) This function computes the partition (ie. a set of node forming a cut of the tree) that has a minimal energy according to the definition above.
Supported accumulators are hg.Accumulators.sum, hg.Accumulators.min, and hg.Accumulators.max.
The algorithm used is based on dynamic programming and runs in linear time \(\mathcal{O}(n)\) w.r.t. to the number of nodes in the tree.
See:
Laurent Guigues, Jean Pierre Cocquerez, Hervé Le Men. Scalesets Image Analysis. International Journal of Computer Vision, Springer Verlag, 2006, 68 (3), pp.289317
and
Bangalore Ravi Kiran, Jean Serra. Globallocal optimizations by hierarchical cuts and climbing energies. Pattern Recognition Letters, Elsevier, 2014, 47 (1), pp.1224.
 Parameters
tree – input tree (Concept
CptHierarchy
)energy_attribute – energy value of each node of the input tree
accumulator – see
Accumulators
leaf_graph – leaf graph of the input tree (deduced from
CptHierarchy
)
 Returns
a labelisation of the leaves of the tree

hierarchy_to_optimal_energy_cut_hierarchy
(tree, data_fidelity_attribute, regularization_attribute, approximation_piecewise_linear_function=10)[source]¶ Transforms the given hierarchy into its optimal energy cut hierarchy for the given energy terms. In the optimal energy cut hierarchy, any horizontal cut corresponds to an optimal energy cut in the original hierarchy.
Each node \(i\) of the tree is associated to a data fidelity energy \(D(i)\) and a regularization energy \(R(i)\). The algorithm construct a new hierarchy with associated altitudes such that the horizontal cut of level lambda is the optimal cut for the energy attribute \(D + \lambda * R\) of the input tree (see function
labelisation_optimal_cut_from_energy()
). In other words, the horizontal cut of level \(\lambda\) in the result is the cut of the input composed of the nodes \(N\) such that \(\sum_{r \in N} D(r) + \lambda * R(r)\) is minimal.PRECONDITION: the regularization energy \(R\) must be sub additive: for each node \(i\): \(R(i) \leq \sum_{c\in Children(i)}R(c)\)
The algorithm runs in linear time \(\mathcal{O}(n)\)
See:
Laurent Guigues, Jean Pierre Cocquerez, Hervé Le Men. Scalesets Image Analysis. International Journal of Computer Vision, Springer Verlag, 2006, 68 (3), pp.289317
 Parameters
tree – input tree
data_fidelity_attribute – 1d array representing the data fidelity energy of each node of the input tree
regularization_attribute – 1d array representing the regularization energy of each node of the input tree
approximation_piecewise_linear_function – Maximum number of pieces used in the approximated piecewise linear model for the energy function (default 10).
 Returns
a tree (Concept
CptHierarchy
) and its node altitudes

hierarchy_to_optimal_MumfordShah_energy_cut_hierarchy
(tree, vertex_weights, leaf_graph, approximation_piecewise_linear_function=10)[source]¶ Transform the given hierarchy into an optimal energy cut hierarchy using the piecewise constant MumfordShah energy (see function
hierarchy_to_optimal_energy_cut_hierarchy()
).In this context:
the data fidelity energy assumes a piecewise constant model in each node and is given by the variance of the vertex values inside the node (see function
attribute_gaussian_region_weights_model()
) multiplied by its area,the regularity energy is given by the length of the contour of the node (see function
attribute_contour_length()
).
 Parameters
tree – input tree (Concept
CptHierarchy
)vertex_weights – vertex weights of the leaf graph of the input tree
leaf_graph – leaf graph of the input tree (deduced from
CptHierarchy
)approximation_piecewise_linear_function – Maximum number of pieces used in the approximated piecewise linear model for the energy function (default 10).
 Returns
a tree (Concept
CptHierarchy
) and its node altitudes
Assessment¶
Hierarchical cost¶

Dasgupta’s cost is an unsupervised measure of the quality of a hierarchical clustering of an edge weighted graph. 

Weighted average of the purity of each node of the tree with respect to a ground truth labelization of the tree leaves. 

Tree sampling divergence is an unsupervised measure of the quality of a hierarchical clustering of an edge weighted graph. 

dasgupta_cost
(tree, edge_weights, leaf_graph)[source]¶ Dasgupta’s cost is an unsupervised measure of the quality of a hierarchical clustering of an edge weighted graph.
Let \(T\) be a tree representing a hierarchical clustering of the graph \(G=(V, E)\). Let \(w\) be a dissimilarity function on the edges \(E\) of the graph.
The Dasgupta’s cost is define as:
\[dasgupta(T, V, E, w) = \sum_{\{x,y\}\in E} \frac{area(lca_T(x,y))}{w(\{x,y\})}\] See
S. Dasgupta. “A cost function for similaritybased hierarchical clustering .” In Proc. STOC, pages 118–127, Cambridge, MA, USA, 2016
 Complexity
The runtime complexity is \(\mathcal{O}(n\log(n) + m)\) with \(n\) the number of nodes in \(T\) and \(m\) the number of edges in \(E\).
 Parameters
tree – Input tree
edge_weights – Edge weights on the leaf graph (dissimilarities)
leaf_graph – Leaf graph of the input tree (deduced from
CptHierarchy
)
 Returns
a real number

dendrogram_purity
(tree, leaf_labels)[source]¶ Weighted average of the purity of each node of the tree with respect to a ground truth labelization of the tree leaves.
Let \(T\) be a tree with leaves \(V=\{1, \ldots, n\}\). Let \(C=\{C_1, \ldots, C_K\}\) be a partition of \(V\) into \(k\) (label) sets.
The purity of a subset \(X\) of \(V\) with respect to class \(C_\ell\in C\) is the fraction of elements of \(X\) that belongs to class \(C_\ell\):
\[pur(X, C_\ell) = \frac{ X \cap C_\ell }{ X }.\]The purity of \(T\) is the defined as:
\[pur(T) = \frac{1}{Z}\sum_{k=1}^{K}\sum_{x,y\in C_k, x\neq y} pur(lca_T(x,y), C_k)\]with \(Z= \{\{x,y\} \subseteq V \mid x\neq y, \exists k, \{x,y\}\subseteq C_k\} \).
 See
Heller, Katherine A., and Zoubin Ghahramani. “Bayesian hierarchical clustering .” Proc. ICML. ACM, 2005.
 Complexity
The dendrogram purity is computed in \(\mathcal{O}(N\times K \times C^2)\) with \(N\) the number of nodes in the tree, \(K\) the number of classes, and \(C\) the maximal number of children of a node in the tree.
 Parameters
tree – input tree
leaf_labels – a 1d integral array of length tree.num_leaves()
 Returns
a score between 0 and 1 (higher is better)

tree_sampling_divergence
(tree, edge_weights, leaf_graph)[source]¶ Tree sampling divergence is an unsupervised measure of the quality of a hierarchical clustering of an edge weighted graph. It measures how well the given edge weighted graph can be reconstructed from the tree alone. It is equal to 0 if and only if the given graph can be fully recovered from the tree.
It is defined as the KullbackLeibler divergence between the edge sampling model \(p\) and the independent (null) sampling model \(q\) of the nodes of a tree (see
attribute_tree_sampling_probability()
).The tree sampling divergence on a tree \(T\) is then
\[TSD(T) = \sum_{x \in T} p(x) \log\frac{p(x)}{q(x)}\]The definition of the tree sampling divergence was proposed in:
Charpentier, B. & Bonald, T. (2019). “Tree Sampling Divergence: An InformationTheoretic Metric for Hierarchical Graph Clustering.” Proceedings of IJCAI.
 Complexity
The tree sampling divergence is computed in \(\mathcal{O}(N (\log(N) + C^2) + M)\) with \(N\) the number of nodes in the tree, \(M\) the number of edges in the leaf graph, and \(C\) the maximal number of children of a node in the tree.
 Parameters
tree – Input tree
edge_weights – Edge weights on the leaf graph (similarities)
leaf_graph – Leaf graph of the input tree (deduced from
CptHierarchy
)
 Returns
a real number
Hierarchy fragmentation curve¶
This class represents a fragmentation curve, ie the evolution of the scores of the partitions of a hierarchy with respect to the number of regions in those partitions. 

Quality measures usable with optimal cut assessment 


Fragmentation curve of the horizontal cuts in a hierarchy w.r.t. 

Fragmentation curve of the optimal cuts in a hierarchy w.r.t. 
Creates an assesser for hierarchy optimal cuts w.r.t. 


class
FragmentationCurve
¶ This class represents a fragmentation curve, ie the evolution of the scores of the partitions of a hierarchy with respect to the number of regions in those partitions.
Example
plt.plot(x=fg.num_regions(), y=fg.scores())

__init__
()¶ Initialize self. See help(type(self)) for accurate signature.

num_regions
(self: higra.higram.FragmentationCurve) → xt::xtensor¶ Array of number of regions in the different cuts

num_regions_ground_truth
(self: higra.higram.FragmentationCurve) → int¶ Array of number of regions in the different cuts

num_regions_normalized
(self: higra.higram.FragmentationCurve) → xt::xtensor¶ Array of number of regions in the different cuts divided by the number of regions in the groundtruth

scores
(self: higra.higram.FragmentationCurve) → xt::xtensor¶ Array of scores of the different cuts


class
OptimalCutMeasure
¶ Quality measures usable with optimal cut assessment
Members:
BCE
DHamming
DCovering

BCE
= <OptimalCutMeasure.BCE: 0>¶

DCovering
= <OptimalCutMeasure.DCovering: 2>¶

DHamming
= <OptimalCutMeasure.DHamming: 1>¶

__eq__
(self: object, other: object) → bool¶

__getstate__
(self: object) → int¶

__hash__
(self: object) → int¶

__init__
(self: higra.higram.OptimalCutMeasure, value: int) → None¶

__int__
(self: higra.higram.OptimalCutMeasure) → int¶

__members__
= {'BCE': <OptimalCutMeasure.BCE: 0>, 'DCovering': <OptimalCutMeasure.DCovering: 2>, 'DHamming': <OptimalCutMeasure.DHamming: 1>}¶

__module__
= 'higra.higram'¶

__ne__
(self: object, other: object) → bool¶

__repr__
(self: object) → str¶

__setstate__
(self: higra.higram.OptimalCutMeasure, state: int) → None¶

__str__
()¶ name(self: handle) > str

property
name
¶


assess_fragmentation_horizontal_cut
(tree, altitudes, ground_truth, measure, max_regions=200, vertex_map=None)[source]¶ Fragmentation curve of the horizontal cuts in a hierarchy w.r.t. a given measure.
The base graph of the hierarchy is:
the leaf graph of the hierarchy if it is not a region adjacency graph
the original graph of the leaf graph of the hierarchy if it is a region adjacency graph
 Parameters
tree – input hierarchy (Concept
CptHierarchy
)altitudes – altitudes of the nodes of the input hierarchy
ground_truth – labelisation of base graph vertices
measure – evaluation measure to use (see enumeration
PartitionMeasure
)max_regions – maximum number of regions in the cuts
vertex_map – optional, vertex mapping if the hierarchy is build on a region adjacency graph (deduced from
CptRegionAdjacencyGraph
on the leaf graph of tree)
 Returns
an object of type
FragmentationCurve

assess_fragmentation_optimal_cut
(tree, ground_truth, measure, max_regions=200, vertex_map=None)[source]¶ Fragmentation curve of the optimal cuts in a hierarchy w.r.t. a given measure.
The base graph of the hierarchy is:
the leaf graph of the hierarchy if it is not a region adjacency graph
the original graph of the leaf graph of the hierarchy if it is a region adjacency graph
 Parameters
tree – input hierarchy (Concept
CptHierarchy
)ground_truth – labelisation of base graph vertices
measure – evaluation measure to use (see enumeration
OptimalCutMeasure
)max_regions – maximum number of regions in the cuts
vertex_map – optional, vertex mapping if the hierarchy is build on a region adjacency graph (deduced from
CptRegionAdjacencyGraph
on the leaf graph of tree)
 Returns
an object of type
FragmentationCurve

make_assesser_fragmentation_optimal_cut
(tree, ground_truth, measure, max_regions=200, vertex_map=None)[source]¶ Creates an assesser for hierarchy optimal cuts w.r.t. a given groundtruth partition of the base graph vertices and the given optimal cut measure (see
OptimalCutMeasure
). The algorithms will explore optimal cuts containing at most max_regions regions.The base graph of the hierarchy is:
the leaf graph of the hierarchy if it is not a region adjacency graph
the original graph of the leaf graph of the hierarchy if it is a region adjacency graph
 Parameters
tree – input hierarchy (Concept
CptHierarchy
)ground_truth – labelisation of base graph vertices
measure – evaluation measure to use (see enumeration
OptimalCutMeasure
)max_regions – maximum number of regions in the cuts
vertex_map – optional, vertex mapping if the hierarchy is build on a region adjacency graph (deduced from
CptRegionAdjacencyGraph
on the leaf graph of tree)
 Returns
an object of type
AssesserFragmentationOptimalCut

class
AssesserFragmentationOptimalCut
¶ 
fragmentation_curve
(self: higra.higram.AssesserFragmentationOptimalCut) → higra.higram.FragmentationCurve¶ Fragmentation curve, i.e. for each number of region k between 1 and max_regions, the score of the optimal cut with k regions.

optimal_number_of_regions
(self: higra.higram.AssesserFragmentationOptimalCut) → int¶ Number of regions in the optimal cut.

optimal_partition
(self: higra.higram.AssesserFragmentationOptimalCut, num_regions: int = 0) → xt::xtensor¶ Labelisation of the tree vertices that corresponds to the optimal cut withthe given number of regions. If the number of regions is equal to 0 (default), the global optimal cut it returned (it will contain get_optimal_number_of_regions regions).

optimal_score
(self: higra.higram.AssesserFragmentationOptimalCut) → float¶ Score of the optimal cut.

Partition score¶
Quality measures usable with partition assessment 


Overloaded function. 

class
PartitionMeasure
¶ Quality measures usable with partition assessment
Members:
BCE
DHamming
DCovering

BCE
= <PartitionMeasure.BCE: 0>¶

DCovering
= <PartitionMeasure.DCovering: 2>¶

DHamming
= <PartitionMeasure.DHamming: 1>¶

property
name
¶


assess_partition
(*args, **kwargs)¶ Overloaded function.
assess_partition(candidate: numpy.ndarray[numpy.int8], ground_truth: numpy.ndarray[numpy.int8], partition_measure: higra.higram.PartitionMeasure) > float
Assess a given candidate partition with a groundtruth segmentation and an evaluation measure (see enumeration PartitionMeasure). The candidate and groundtruth partitions must be given as labelisations with integers values between 0 (included) and the number of regions in the partition (excluded).
assess_partition(candidate: numpy.ndarray[numpy.uint8], ground_truth: numpy.ndarray[numpy.uint8], partition_measure: higra.higram.PartitionMeasure) > float
assess_partition(candidate: numpy.ndarray[numpy.int16], ground_truth: numpy.ndarray[numpy.int16], partition_measure: higra.higram.PartitionMeasure) > float
assess_partition(candidate: numpy.ndarray[numpy.uint16], ground_truth: numpy.ndarray[numpy.uint16], partition_measure: higra.higram.PartitionMeasure) > float
assess_partition(candidate: numpy.ndarray[numpy.int32], ground_truth: numpy.ndarray[numpy.int32], partition_measure: higra.higram.PartitionMeasure) > float
assess_partition(candidate: numpy.ndarray[numpy.uint32], ground_truth: numpy.ndarray[numpy.uint32], partition_measure: higra.higram.PartitionMeasure) > float
assess_partition(candidate: numpy.ndarray[numpy.int64], ground_truth: numpy.ndarray[numpy.int64], partition_measure: higra.higram.PartitionMeasure) > float
assess_partition(candidate: numpy.ndarray[numpy.uint64], ground_truth: numpy.ndarray[numpy.uint64], partition_measure: higra.higram.PartitionMeasure) > float
Graph processing algorithms¶
Graph accumulators¶

Accumulates edge weights of the out edges of each vertex \(i\): ie \(output(i) = accumulator(edge\_weights(out\_edges(i)))\). 

Accumulates vertex weights of the adjacent vertices of each vertex \(i\): ie \(output(i) = accumulator(vertex\_weights(adjacent\_vertices(i)))\). 

accumulate_graph_edges
(graph, edge_weights, accumulator)[source]¶ Accumulates edge weights of the out edges of each vertex \(i\): ie \(output(i) = accumulator(edge\_weights(out\_edges(i)))\).
 Parameters
graph – input graph
edge_weights – Weights on the edges of the graph
accumulator – see
Accumulators
 Returns
returns new graph vertex weights

accumulate_graph_vertices
(graph, vertex_weights, accumulator)[source]¶ Accumulates vertex weights of the adjacent vertices of each vertex \(i\): ie \(output(i) = accumulator(vertex\_weights(adjacent\_vertices(i)))\).
 Parameters
graph – input graph
vertex_weights – Weights on the vertices of the graph
accumulator – see
Accumulators
 Returns
returns new graph vertex weights
Graph attributes¶

Edge length of the given graph. 

Vertex area of the given graph. 

Coordinates of the vertices of the given grid graph. 

List of leaf nodes inside the subtree rooted in a node. 

Vertex perimeter of the given graph. 

attribute_edge_length
(graph)[source]¶ Edge length of the given graph.
In general the length of an edge if simply equal to 1. But, if the graph is a region adjacency graph then the length of an edge is equal to the sum of length of the corresponding edges in the original graph (obtained with a recursive call to
attribute_edge_length
on the original graph). Parameters
graph – input graph
 Returns
a nd array
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_vertex_area
(graph)[source]¶ Vertex area of the given graph.
In general the area of a vertex if simply equal to 1. But, if the graph is a region adjacency graph then the area of a region is equal to the sum of the area of the vertices inside the region (obtained with a recursive call to
attribute_vertex_area
on the original graph). Parameters
graph – input graph
 Returns
a 1d array
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_vertex_coordinates
(graph, shape)[source]¶ Coordinates of the vertices of the given grid graph.
Example
>>> g = hg.get_4_adjacency_graph((2, 3)) >>> c = hg.attribute_vertex_coordinates(g) (((0, 0), (0, 1), (0, 2)), ((1, 0), (1, 1), (1, 2)))
 Parameters
graph – Input graph (Concept
CptGridGraph
)shape – (deduced from
CptGridGraph
)
 Returns
a nd array
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_vertex_list
(tree)[source]¶ List of leaf nodes inside the subtree rooted in a node.
WARNING: This function is slow and will use O(n²) space, with n the number of leaf nodes !
SHOULD ONLY BE USED FOR DEBUGGING AND TESTING
 Parameters
tree – input tree
 Returns
a list of lists
Autocache: This function is decorated with the
auto_cache()
decorator.

attribute_vertex_perimeter
(graph, edge_length=None)[source]¶ Vertex perimeter of the given graph. The perimeter of a vertex is defined as the sum of the length of outedges of the vertex.
If the input graph has an attribute value no_border_vertex_out_degree, then each vertex perimeter is assumed to be equal to this attribute value. This is a convenient method to handle image type graphs where an outer border has to be considered.
 Parameters
graph – input graph
edge_length – length of the edges of the input graph (provided by
attribute_edge_length()
on graph)
 Returns
a nd array
Autocache: This function is decorated with the
auto_cache()
decorator.
Algorithms for graphs¶
Undirected edgeweighted graph corresponding to an adjacency matrix. 


Labelises graph vertices according to the given graph cut. 

Determines the graph cut that corresponds to a given labeling of the graph vertices. 

Compute the line graph of an undirected graph. 

Creates a graph from vertex coordinates. 

Computes the minimum spanning tree of the given edge weighted graph with Kruskal’s algorithm. 

Extract a subgraph of the input graph. 

Subdominant ultrametric of the given edge weighted graph. 

Adjacency matrix corresponding to an undirected edgeweighted graph (the result is thus symmetric). 

adjacency_matrix_2_undirected_graph
(adjacency_matrix, non_edge_value=0)[source]¶ Undirected edgeweighted graph corresponding to an adjacency matrix.
Adjacency matrix entries which are equal to
non_edge_value
are not considered to be part of the graph. Parameters
adjacency_matrix – Input adjacency matrix (A 2d symmetric square matrix)
non_edge_value – Value used to represent non existing edges in the adjacency matrix
 Returns
a pair (UndirectedGraph, ndarray) representing the graph and its edge_weights (Concept
CptEdgeWeightedGraph
)

graph_cut_2_labelisation
(graph, edge_weights)[source]¶ Labelises graph vertices according to the given graph cut.
Each edge having a non zero value in the given edge_weights are assumed to be part of the cut.
 Parameters
graph – Input graph
edge_weights – Weights on the edges of the graph
 Returns
A labelisation of the graph vertices

labelisation_2_graph_cut
(graph, vertex_labels)[source]¶ Determines the graph cut that corresponds to a given labeling of the graph vertices.
The result is a weighting of the graph edges where edges with a non zero weight are part of the cut.
 Parameters
graph – input graph
vertex_labels – Weights on the vertices of the graph
 Returns
graph edgeweights representing the equivalent cut

line_graph
(graph)[source]¶ Compute the line graph of an undirected graph.
The line graph \(LG\) of an undirected graph \(G\) is a graph such that:
each vertex of \(LG\) represents an edge of \(G\): the \(i\)th vertex of \(LG\) corresponds to the \(i\)th edge of \(G\); and
two vertices \(x\) and \(y\) of \(LG\) are adjacent if their corresponding edges in \(G\) share a common extremity. Formally, if \(x\) represents the edge \(\{i, j \}\) and if \(y\) represents the edge \(\{k, j \}\), then the edge \(\{x, y\}\) belongs to \(LG\) if \(\{i, j \} \cap \{k, j \} \neq \emptyset\).
The line graph is also known as: the covering graph, the derivative, the edgetovertex dual, the conjugate, the representative graph, the edge graph, the interchange graph, the adjoint graph, or the derived graph.
 Parameters
graph – input graph
 Returns
the line graph of the input graph

make_graph_from_points
(X, graph_type='knn+mst', symmetrization='max', **kwargs)[source]¶ Creates a graph from vertex coordinates.
The argument
graph_type
selects the graph creation methods. Possible values are:"complete"
: creates the complete graph"knn"
: creates a \(k\)nearest neighbor graph, the parameter \(k\) can be controlled with the extra parameter ‘n_neighbors’ (default value 5). The resulting graph may have several connected components."knn+mst"
(default): creates a \(k\)nearest neighbor graph and add the edges of an mst of the complete graph. This method ensures that the resulting graph is connected. The parameter \(k\) can be controlled with the extra parameter ‘n_neighbors’ (default value 5)."delaunay"
: creates a graph corresponding to the Delaunay triangulation of the points (only works in low dimensions).
The weight of an edge \(\{x,y\}\) is equal to the Euclidean distance between \(x\) and \(y\): \(w(\{x,y\})=\X[x, :]  X[y, :]\\).
\(K\)nearest neighbor based graphs are naturally directed, the argument
symmetrization
enables to chose a symmetrization strategy. Possible values are:"min"
: an edge \(\{x,y\}\) is created if there both arcs \((x,y)\) and \((y,x)\) exist. Its weight is given by the minimum weight of the two arcs."max"
: an edge \(\{x,y\}\) is created if there is any of the two arcs \((x,y)\) and \((y,x)\) exists. Its weight is given by the weight of the existing arcs (if both arcs exists they necessarily have the same weight).
This method is not suited for large set of points.
 Parameters
X – A 2d array of vertex coordinates
graph_type –
"complete"
,"knn"
,"knn+mst"
(default), or"delaunay"
symmetrization – “min”` or
"max"
kwargs – extra args depends of chosen graph type
 Returns
a graph and its edge weights

minimum_spanning_tree
(graph, edge_weights)[source]¶ Computes the minimum spanning tree of the given edge weighted graph with Kruskal’s algorithm.
If the input graph is not connected, the result is indeed a minimum spanning forest.
Complexity: \(\mathcal{O}(n*log(n))\) with \(n\) the number of edges in the graph
 Parameters
graph – Input graph
edge_weights – Graph edge weights
 Returns
a minimum spanning tree of the input edge weighted graph (Concept
CptMinimumSpanningTree
)

subgraph
(graph, edge_indices, spanning=True, return_vertex_map=False)[source]¶ Extract a subgraph of the input graph. Let \(G=(V,E)\) be the graph
graph
and let \(E^*\) be a subset of \(E\). The subgraph of \(G\) induced by \(E^*\) is equal to:\((V, E^*)\) is
spanning
isTrue
; and\((\bigcup E^*, E^*)\) otherwise (the set of vertices of the subgraph is equal to the set of vertices present at an extremity of an edge in \(E^*\)).
The array
edge_indices
contains the indices of the edges in the set \(E^*\). The edges in the subgraph are in the same order as the edges in the arrayedge_indices
.If
spanning
isFalse
, the subgraph may contain less vertices than the input graph. In such case, the optional array result \(vertex\_map\) (returned ifreturn_vertex_map
isTrue
) indicates for each vertex \(i\) of the subgraph, its corresponding index in the input graph. Example
>>> # linear graph with 6 vertices >>> graph = hg.UndirectedGraph(6) >>> graph.add_edges(np.arange(5), np.arange(1, 6)) >>> >>> # select edges (4, 5), (0, 1), and (3, 4), note that vertex 2 is not in any edge >>> edge_indices = np.asarray((4, 0, 3)) >>> subgraph, vertex_map = hg.subgraph(graph, edge_indices, spanning=False, return_vertex_map=True) >>> >>> subgraph.num_vertices() 5 >>> vertex_map [0 1 3 4 5] >>> subgraph.edge_list() ([3 0 2], [4 1 3]) >>> vertex_map [0 1 3 4 5]
 Parameters
graph – input graph.
edge_indices – an array of edge indices of the input graph.
spanning – if
True
, the subgraph has the same vertex set as the input graph.return_vertex_map – if
True
, also returns an array mapping each vertex of the current to its corresponding vertex in the input graph.
 Returns
a subgraph and, if
return_vertex_map
isTrue
, a vertex map

undirected_graph_2_adjacency_matrix
(graph, edge_weights=None, non_edge_value=0, sparse=True)[source]¶ Adjacency matrix corresponding to an undirected edgeweighted graph (the result is thus symmetric).
As the given graph is not necessarily complete, nonexisting edges will receive the value
non_edge_value
in the adjacency matrix. Parameters
graph – Input graph
edge_weights – Graph edge weights (default to
np.ones(graph.num_edges())
ifNone
)non_edge_value – Value used to represent edges that are not in the input graph (must be 0 if
sparse
isTrue
)sparse – if
True
the result will be a sparse matrix in the csr format (requires Scipy to be installed)
 Returns
A 2d symmetric square matrix

ultrametric_open
(graph, edge_weights)[source]¶ Subdominant ultrametric of the given edge weighted graph.
The subdominant ultrametric relative to a given dissimilarity measure (here the graph edge weights) is defined as the largest ultrametric smaller than the dissimilarity measure.
In the case of an edge weighted undirected graph, the value of the subdominant ultrametric on the edge \(e_{xy}\) is given by the minmax distance between \(x\) and \(y\).
Complexity: \(\mathcal{O}(n*log(n))\) with \(n\) the number of edges in the graph
 Parameters
graph – Input graph
edge_weights – Graph edge weights
 Returns
edge weights corresponding to the subdominant ultrametric
Utility functions to weight the edges of a graph¶
Members: 


Compute the edge weights of a graph using source and target vertices values and specified weighting function (see 

class
WeightFunction
¶ Members:
mean
min
max
L0
L1
L2
L_infinity
L2_squared
source
target

L0
= <WeightFunction.L0: 3>¶

L1
= <WeightFunction.L1: 4>¶

L2
= <WeightFunction.L2: 5>¶

L2_squared
= <WeightFunction.L2_squared: 7>¶

L_infinity
= <WeightFunction.L_infinity: 6>¶

max
= <WeightFunction.max: 2>¶

mean
= <WeightFunction.mean: 0>¶

min
= <WeightFunction.min: 1>¶

property
name
¶

source
= <WeightFunction.source: 8>¶

target
= <WeightFunction.target: 9>¶


weight_graph
(graph, vertex_weights, weight_function)[source]¶ Compute the edge weights of a graph using source and target vertices values and specified weighting function (see
WeightFunction
enumeration). Parameters
graph – input graph
vertex_weights – vertex weights of the input graph
weight_function – see
WeightFunction
 Returns
edge weights of the graph
Region adjacency graph¶
Create a region adjacency graph (rag) of a vertex labelled graph. 

Create a region adjacency graph (rag) from a graph cut. 


Projects rag vertex weights onto original graph vertices. 

Projects rag edge weights onto original graph edges. 

Weights rag vertices by accumulating values from the vertex weights of the original graph. 

Weights rag edges by accumulating values from the edge weights of the original graph. 

make_region_adjacency_graph_from_labelisation
(graph, vertex_labels)[source]¶ Create a region adjacency graph (rag) of a vertex labelled graph. Each maximal connected set of vertices having the same label is a region. Each region is represented by a vertex in the rag. There is an edge between two regions of labels \(l_1\) and \(l_2\) in the rag iff there exists an edge linking two vertices of labels \(l_1\) and \(l_2\) int he original graph.
 Parameters
graph – input graph
vertex_labels – vertex labels on the input graph
 Returns
a region adjacency graph (Concept
CptRegionAdjacencyGraph
)

make_region_adjacency_graph_from_graph_cut
(graph, edge_weights)[source]¶ Create a region adjacency graph (rag) from a graph cut. Two vertices \(v_1\), \(v_2\) are in the same region if there exists a \(v_1v_2\)path composed of edges weighted 0. Each region is represented by a vertex in the rag. There is an edge between two regions of labels \(l_1\) and \(l_2\) in the rag iff there exists an edge linking two vertices of labels \(l_1\) and \(l_2\) int he original graph.
 Parameters
graph – input graph
edge_weights – edge weights on the input graph, non zero weights are part of the cut
 Returns
a region adjacency graph (Concept
CptRegionAdjacencyGraph
)

rag_back_project_vertex_weights
(graph, vertex_weights)[source]¶ Projects rag vertex weights onto original graph vertices. The result is an array weighting the vertices of the original graph of the rag such that: for any vertex \(v\) of the original graph, its weight is equal to the weight of the vertex of the rag that represents the region that contains \(v\).
For any vertex index \(i\), \(result[i] = rag\_vertex\_weight[rag\_vertex_map[i]]\)
 Parameters
graph – input region adjacency graph
vertex_weights – vertex weights on the input region adjacency graph
 Returns
vertex weights on the original graph

rag_back_project_edge_weights
(graph, edge_weights)[source]¶ Projects rag edge weights onto original graph edges. The result is an array weighting the edges of the original graph of the rag such that: for any edge \(e\) of the original graph, its weight is equal to the weight of the edge of the rag that represents that links the two regions containing the extremities of \(e\). If no such edge exists (if the extremities of \(e\) are in the same region), its value is 0.
For any edge index \(ei\), \(result[ei] = rag\_edge\_weight[rag\_edge\_map[ei]]\) if \(rag\_edge\_map[ei] != 1\) and 0 otherwise.
 Parameters
graph – input region adjacency graph
edge_weights – edge weights on the input region adjacency graph
 Returns
edge weights on the original graph

rag_accumulate_on_vertices
(rag, accumulator, vertex_weights)[source]¶ Weights rag vertices by accumulating values from the vertex weights of the original graph.
For any vertex index \(i\) of the rag, \(result[i] = accumulator(\{vertex\_weights[j]  rag\_vertex\_map[j] == i\})\)
 Parameters
rag – input region adjacency graph (Concept
RegionAdjacencyGraph
)vertex_weights – vertex weights on the original graph
accumulator – see
Accumulators
 Returns
vertex weights on the region adjacency graph

rag_accumulate_on_edges
(rag, accumulator, edge_weights)[source]¶ Weights rag edges by accumulating values from the edge weights of the original graph.
For any edge index \(ei\) of the rag, \(result[ei] = accumulate(\{edge\_weights[j]  rag\_edge\_map[j] == ei\})\)
 Parameters
rag – input region adjacency graph (Concept
RegionAdjacencyGraph
)edge_weights – edge weights on the original graph
accumulator – see
Accumulators
 Returns
edge weights on the region adjacency graph
Labelisation watershed¶

Watershed cut of the given edge weighted graph. 

Seeded watershed cut on an edge weighted graph. 

labelisation_watershed
(graph, edge_weights)[source]¶ Watershed cut of the given edge weighted graph.
The definition and algorithm used are described in:
J. Cousty, G. Bertrand, L. Najman and M. Couprie. Watershed cuts: minimum spanning forests, and the drop of water principle. IEEE Trans. on Pattern Analysis and Machine Intelligence, 31(8): 13621374, 2009.
The watershed cut is represented by a labelisation of the graph vertices.
 Complexity
This algorithm has a linear runtime complexity \(\mathcal{O}(n)\) with \(n\) the number of edges in the graph.
 Parameters
graph – input graph
edge_weights – Weights on the edges of the graph
 Returns
A labelisation of the graph vertices

labelisation_seeded_watershed
(graph, edge_weights, vertex_seeds, background_label=0)[source]¶ Seeded watershed cut on an edge weighted graph. Seeds and associated labels are given in
vertex_seeds
. A vertex \(v\), such that \(vertex\_seeds(v)\neq background\_label\) is a seed with associated label \(vertex\_seeds(v)\).The label of a vertex of the graph is then defined equal to the label of the closest seed in the edge weighted graph for the minmax distance. If several such seeds exist (eg. on a plateus between two seeds), an arbitrary and consistent choice is made ensuring that:
each flat zone of level \(k\) of the final labelling contains at least one seed with the label \(k\); and
each seed is contained in a flat zone whose level is equal to the seed label.
 Complexity
This algorithm has a runtime complexity in \(\mathcal{O}(n \log n)\) with \(n\) the number of edges in the graph.
 Parameters
graph – Input graph
edge_weights – Weights on the edges of the graph
vertex_seeds – Seeds with integer label values on the vertices of the graph
background_label – Vertices whose values are equal to
background_label
(default 0) invertex_seeds
are not considered as seeds
 Returns
A labelisation of the graph vertices
Data Structures¶
Accumulators¶
The Accumulators class enumerates the various way of combining a list of values into a single value that are used in various algorithms. 


Accumulate the given weights located at given indices. 

class
Accumulators
¶ The Accumulators class enumerates the various way of combining a list of values into a single value that are used in various algorithms.
Members:
min
max
mean
counter
sum
prod
first
last
argmin
argmax

argmax
= <Accumulators.argmax: 9>¶

argmin
= <Accumulators.argmin: 8>¶

counter
= <Accumulators.counter: 5>¶

first
= <Accumulators.first: 0>¶

last
= <Accumulators.last: 1>¶

max
= <Accumulators.max: 4>¶

mean
= <Accumulators.mean: 2>¶

min
= <Accumulators.min: 3>¶

property
name
¶

prod
= <Accumulators.prod: 7>¶

sum
= <Accumulators.sum: 6>¶


accumulate_at
(indices, weights, accumulator)[source]¶ Accumulate the given weights located at given indices.
Let \(M = max(indices)\). For all \(i \in \{0, \ldots, M\}\)
\[result[i] = accumulator(\{weights[j, :] \mid indices[j] = i \})\] Parameters
indices – a 1d array of indices (entry equals to \(1\) are ignored)
weights – a ndarray of shape \((s_1, \ldots, s_n)\) such that \(s_1=indices.size\)
accumulator – see
Accumulators
 Returns
a ndarray of size \((M, s_2, \ldots, s_n)\)
Concepts¶

Concept Name: Abstract Concept 

Concept Name: grid_graph 

Concept Name: region_adjacency_graph 

Concept Name: hierarchy 

Concept Name: binary_hierarchy 

Concept Name: minimum_spanning_tree 

class
Concept
(**kw_args)[source]¶ Concept Name: Abstract Concept
Description: A concept describes how a set of data elements can be considered as a coherent notion of higher semantic level. One of the data elements of the concept is the canonical element of the association that can be used to materialize the concept, ie, to assemble all the data elements associated to the canonical element in order to build a representation of the higher semantic object described by the concept. Concepts are conceptually close to Classes in object oriented programming where data elements correspond to attributes. However with concepts, one never creates or manipulates actual objects: objects exist only from the relation between their data elements.
Canonical data element: The canonical element of a concept is the data that serves as a reference to retrieve all the data elements of the Concept. The canonical element is usually chosen such that there is a natural n to 1 association between the canonical element and its data elements.
Data elements:

classmethod
construct
(canonical_element, strict=True, data_cache=None)[source]¶ Tries to construct a dictionary holding all the data elements of the concept associated to the given canonical element.
 Parameters
canonical_element – an object
strict – if True an exception is raised if all the data elements of the Concept cannot be recovered from the given canonical element, otherwise the missing data element is simply not included in the result.
data_cache – specify a data cache where to search for data elements. If None, the default Higra global data cache is used.
 Returns
a dictionary

classmethod

class
CptGridGraph
(**kwargs)[source]¶ Concept Name: grid_graph
Description: A graph whose vertices correspond to points on a regular grid.
Canonical data element: graph
Data elements:
graph (canonical): a graph g
shape (attribute name: ‘shape’): the shape of the underlying grid (a 1d array of positive integers such that np.prod(shape) = g.num_vertices())

class
CptRegionAdjacencyGraph
(**kwargs)[source]¶ Concept Name: region_adjacency_graph
Description: A graph whose vertices represented supervertices of another graph.
Canonical data element: rag
Data elements:
rag (canonical): the region adjacency graph
pre_graph (attribute name: ‘pre_graph’): the base graph
vertex_map (attribute name: ‘vertex_map’): a map giving for each vertex of pre_graph the corresponding vertex of rag
edge_map (attribute name: ‘edge_map’): a map giving for each edge of pre_graph the corresponding edge of rag (and 1 if not such edge exists)

class
CptHierarchy
(**kwargs)[source]¶ Concept Name: hierarchy
Description: A tree representing a hierarchy over a base graph.
Canonical data element: tree
Data elements:
tree (canonical): a tree t
leaf_graph (attribute name: ‘leaf_graph’): the graph associated to the leaves of the tree

class
CptBinaryHierarchy
(**kwargs)[source]¶ Concept Name: binary_hierarchy
Description: A binary tree representing a hierarchy with an associated minimum spanning tree on the hierarchy leaf graph.
Canonical data element: tree
Data elements:
tree (canonical): a hierarchy h
mst (attribute name: ‘mst’): a minimum spanning tree of the leaf graph of the hierarchy
mst_edge_map (attribute name: ‘mst_edge_map’): Map each internal vertex i of the tree to the edge ‘mst_edge_map[i  tree.num_leaves()]’ of theleaf graph of the hierarchy corresponding to a minimum spanning tree edge.
leaf_graph (attribute name: ‘leaf_graph’): the graph associated to the leaves of the tree (inherited from
CptHierarchy
)

class
CptMinimumSpanningTree
(**kwargs)[source]¶ Concept Name: minimum_spanning_tree
Description: A minimum spanning tree and its base graph.
Canonical data element: mst
Data elements:
base_graph (attribute name: ‘base_graph’): a base graph
mst (canonical): a minimum spanning tree of the base graph
mst_edge_map (attribute name: ‘mst_edge_map’): For each edge index i of the mst, gives the corresponding edge index in the base graph
Embedding Grid¶
Grid embeddings are utility classes to ease the manipulation of point coordinates in the ddimensional integer grid. An embedding has a shape (height and width in 2 dimensions).
For a given dimension \(N\in\{1,2,3,4,5\}\), there is a specific grid embedding class called EmbeddingGridNd
.
All the specific grid embedding classes implement the same interface.

class
EmbeddingGrid2d
¶ 
__init__
(self: higra.higram.EmbeddingGrid2d, shape: numpy.ndarray[numpy.int64]) → None¶ Create a new grid embedding. Shape must be a 1d array with striclty positive values.

contains
(*args, **kwargs)¶ Overloaded function.
contains(self: higra.higram.EmbeddingGrid2d, coordinates: List[int]) > bool
Takes a list or tuple representing the coordinates of a point and returns true if the point is contained in the embedding.
contains(self: higra.higram.EmbeddingGrid2d, points: numpy.ndarray[numpy.int8]) > xt::xtensor
Takes a n1 x n2 x … nk array, with nk = self.dimension(), and returns a boolean array of dimension n1 x n2 x … n(k1) indicating if each point is contained in the embedding.
contains(self: higra.higram.EmbeddingGrid2d, points: numpy.ndarray[numpy.int16]) > xt::xtensor
contains(self: higra.higram.EmbeddingGrid2d, points: numpy.ndarray[numpy.int32]) > xt::xtensor
contains(self: higra.higram.EmbeddingGrid2d, points: numpy.ndarray[numpy.int64]) > xt::xtensor

dimension
(self: higra.higram.EmbeddingGrid2d) → int¶ Get the dimension of the embedding (aka self.shape().size()).

grid2lin
(*args, **kwargs)¶ Overloaded function.
grid2lin(self: higra.higram.EmbeddingGrid2d, coordinates: List[int]) > int
Compute the linear coordinate of a point given its nd coordinates.
grid2lin(self: higra.higram.EmbeddingGrid2d, points: numpy.ndarray[numpy.int8]) > xt::xtensor
Takes a n1 x n2 x … nk array, with nk = self.dimension(), and returns a uint64 array of dimension n1 x n2 x … n(k1) giving the linear coordinate of each point.
grid2lin(self: higra.higram.EmbeddingGrid2d, points: numpy.ndarray[numpy.int16]) > xt::xtensor
grid2lin(self: higra.higram.EmbeddingGrid2d, points: numpy.ndarray[numpy.int32]) > xt::xtensor
grid2lin(self: higra.higram.EmbeddingGrid2d, points: numpy.ndarray[numpy.int64]) > xt::xtensor

lin2grid
(*args, **kwargs)¶ Overloaded function.
lin2grid(self: higra.higram.EmbeddingGrid2d, index: int) > numpy.ndarray[numpy.int64]
Compute the nd coordinates of a point given its linear coordinate.
lin2grid(self: higra.higram.EmbeddingGrid2d, points: numpy.ndarray[numpy.int8]) > xt::xtensor
Takes a n1 x n2 x … nk array, and returns an array of dimension n1 x n2 x … nk x self.dimension() where each value, seen as the linear coordinates of a point, has been replaced by the corresponding nd coordinates.
lin2grid(self: higra.higram.EmbeddingGrid2d, points: numpy.ndarray[numpy.int16]) > xt::xtensor
lin2grid(self: higra.higram.EmbeddingGrid2d, points: numpy.ndarray[numpy.int32]) > xt::xtensor
lin2grid(self: higra.higram.EmbeddingGrid2d, points: numpy.ndarray[numpy.int64]) > xt::xtensor

shape
(self: higra.higram.EmbeddingGrid2d) → numpy.ndarray[numpy.int64]¶ Get the shape/dimensions of the grid embedding

size
(self: higra.higram.EmbeddingGrid2d) → int¶ Get the total number of points contained in the embedding.

LCAFast¶
LCAFast
is a utility class to perform fast computation of lowest common ancestors in a tree.
In exchange of a \(n\log(n)\) preprocessing it offers a constant time query for any pairs of vertices.

Deprecated: please use 
alias of 

make_lca_fast
(tree)[source]¶ Deprecated: please use
lowest_common_ancestor_preprocess()
 Parameters
tree – input tree
 Returns

LCAFast
¶ alias of
higra.higram.LCA_rmq_sparse_table_block
Regular graph¶
Regular graphs are translation invariant graphs in the ddimensional integer grid. Regular graphs do not explicitly store edges: they are thus not suited to represent edge weighted graphs.
For a given dimension \(N\in\{1,2,3,4,5\}\), there is a specific regular graph class called RegularGraphNd
.
All the specific regular graph classes implement the same interface.

class
RegularGraph2d
(shape, neighbour_list)¶ 
__init__
(shape, neighbour_list)¶ Creates a new regular grid graph
Example:
>>> # construct implicit 6 adj 3D graph >>> adj_6 = (( 0, 0, 1), >>> ( 0, 0, 1), >>> ( 0, 1, 0), >>> ( 0, 1, 0), >>> (1, 0, 0), >>> ( 1, 0, 0)) >>> >>> shape = (100, 100, 100) >>> >>> g = hg.RegularGraph3d(shape, adj_6)
 Parameters
shape – list of int or embedding of the right dimension
neighbour_list – a list of points coordinates
 Returns
a regular graph instance

adjacent_vertices
(self: higra.higram.RegularGraph2d, vertex: int) → Iterator¶ Iterator over all vertices adjacent to the given vertex.

as_explicit_graph
()¶ Converts the current regular graph instance to an equivalent explicit undirected graph.
 Returns
An
UndirectedGraph
equivalent to the current graph

degree
(*args, **kwargs)¶ Overloaded function.
degree(self: higra.higram.RegularGraph2d, vertex: int) > int
Return the degree of the given vertex.
degree(self: higra.higram.RegularGraph2d, vertices_array: numpy.ndarray[numpy.int32]) > xt::xtensor
Return the degree of the given vertices.
degree(self: higra.higram.RegularGraph2d, vertices_array: numpy.ndarray[numpy.uint32]) > xt::xtensor
degree(self: higra.higram.RegularGraph2d, vertices_array: numpy.ndarray[numpy.int64]) > xt::xtensor
degree(self: higra.higram.RegularGraph2d, vertices_array: numpy.ndarray[numpy.uint64]) > xt::xtensor

in_degree
(*args, **kwargs)¶ Overloaded function.
in_degree(self: higra.higram.RegularGraph2d, vertex: int) > int
Return the in degree of the given vertex.
in_degree(self: higra.higram.RegularGraph2d, vertices_array: numpy.ndarray[numpy.int32]) > xt::xtensor
Return the in degree of the given vertices.
in_degree(self: higra.higram.RegularGraph2d, vertices_array: numpy.ndarray[numpy.uint32]) > xt::xtensor
in_degree(self: higra.higram.RegularGraph2d, vertices_array: numpy.ndarray[numpy.int64]) > xt::xtensor
in_degree(self: higra.higram.RegularGraph2d, vertices_array: numpy.ndarray[numpy.uint64]) > xt::xtensor

in_edges
(self: higra.higram.RegularGraph2d, vertex: int) → Iterator¶ Iterator over all in edges from ‘vertex’. An in edge is a tuple ‘(adjacent_vertex, vertex)’.

neighbour_list
(self: higra.higram.RegularGraph2d) → numpy.ndarray[numpy.int64]¶ Get the neighbour list defining the regular graph.

num_vertices
(self: higra.higram.RegularGraph2d) → int¶ Return the number of vertices in the graph

out_degree
(*args, **kwargs)¶ Overloaded function.
out_degree(self: higra.higram.RegularGraph2d, vertex: int) > int
Return the out degree of the given vertex.
out_degree(self: higra.higram.RegularGraph2d, vertices_array: numpy.ndarray[numpy.int32]) > xt::xtensor
Return the out degree of the given vertices.
out_degree(self: higra.higram.RegularGraph2d, vertices_array: numpy.ndarray[numpy.uint32]) > xt::xtensor
out_degree(self: higra.higram.RegularGraph2d, vertices_array: numpy.ndarray[numpy.int64]) > xt::xtensor
out_degree(self: higra.higram.RegularGraph2d, vertices_array: numpy.ndarray[numpy.uint64]) > xt::xtensor

out_edges
(self: higra.higram.RegularGraph2d, vertex: int) → Iterator¶ Iterator over all out edges from ‘vertex’. An out edge is a tuple ‘(vertex, adjacent_vertex)’.

shape
(self: higra.higram.RegularGraph2d) → numpy.ndarray[numpy.int64]¶ Get the shape of the grid graph.

source
(self: higra.higram.RegularGraph2d, edge: tuple) → detail::accessor<detail::accessor_policies::tuple_item>¶ Get the source vertex of an edge.

target
(self: higra.higram.RegularGraph2d, edge: tuple) → detail::accessor<detail::accessor_policies::tuple_item>¶ Get the target vertex of an edge.

vertices
(self: higra.higram.RegularGraph2d) → Iterator¶ Iterator over all vertices of the graph.

Tree Graph¶
Tree graphs represent trees as undirected rooted graphs.
Category of hierarchies. 

An optimized static tree structure with nodes stored linearly in topological order (from leaves to root). 

class
TreeCategory
¶ Category of hierarchies.
Members:
ComponentTree
PartitionTree

ComponentTree
= <TreeCategory.ComponentTree: 0>¶

PartitionTree
= <TreeCategory.PartitionTree: 1>¶

property
name
¶


class
Tree
¶ An optimized static tree structure with nodes stored linearly in topological order (from leaves to root).

__init__
(*args, **kwargs)¶ Overloaded function.
__init__(self: higra.higram.Tree, parent_relation: numpy.ndarray[numpy.int8], category: higra.higram.TreeCategory = <TreeCategory.PartitionTree: 1>) > None
Create a tree from the given parent relation.
__init__(self: higra.higram.Tree, parent_relation: numpy.ndarray[numpy.uint8], category: higra.higram.TreeCategory = <TreeCategory.PartitionTree: 1>) > None
__init__(self: higra.higram.Tree, parent_relation: numpy.ndarray[numpy.int16], category: higra.higram.TreeCategory = <TreeCategory.PartitionTree: 1>) > None
__init__(self: higra.higram.Tree, parent_relation: numpy.ndarray[numpy.uint16], category: higra.higram.TreeCategory = <TreeCategory.PartitionTree: 1>) > None
__init__(self: higra.higram.Tree, parent_relation: numpy.ndarray[numpy.int32], category: higra.higram.TreeCategory = <TreeCategory.PartitionTree: 1>) > None
__init__(self: higra.higram.Tree, parent_relation: numpy.ndarray[numpy.uint32], category: higra.higram.TreeCategory = <TreeCategory.PartitionTree: 1>) > None
__init__(self: higra.higram.Tree, parent_relation: numpy.ndarray[numpy.int64], category: higra.higram.TreeCategory = <TreeCategory.PartitionTree: 1>) > None
__init__(self: higra.higram.Tree, parent_relation: numpy.ndarray[numpy.uint64], category: higra.higram.TreeCategory = <TreeCategory.PartitionTree: 1>) > None

adjacent_vertices
(self: higra.higram.Tree, vertex: int) → Iterator¶ Iterator over all vertices adjacent to the given vertex.

ancestors
(self: higra.higram.Tree, node: int) → xt::xtensor¶ Get the list of ancestors of the given node in topological order (starting from the given node included).

category
(self: higra.higram.Tree) → higra.higram.TreeCategory¶ Get the tree category (see enumeration TreeCategory)

child
(index, vertex=None)¶ Get the
index
th (starting at 0) child of the given vertex/array of vertices.If
vertex
isNone
, the function will return theindex
th child of every non leaf node of the tree. Parameters
index – positive integer
vertex – a vertex index or a 1d array of vertex indices (default to
np.arange(self.num_leaves(), self.num_vertices()
)
 Returns
a vertex index or a 1d array of vertex indices

children
(self: higra.higram.Tree, node: int) → xt::xtensor¶ Get a copy of the list of children of the given node.

clear_children
(self: higra.higram.Tree) → None¶ Remove the children relation if it has already been computed. May free memory but only useful if you are sure that this relation won’t be required by further processing).

degree
(*args, **kwargs)¶ Overloaded function.
degree(self: higra.higram.Tree, vertex: int) > int
Return the degree of the given vertex.
degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.int32]) > xt::xtensor
Return the degree of the given vertices.
degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.uint32]) > xt::xtensor
degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.int64]) > xt::xtensor
degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.uint64]) > xt::xtensor

edge_from_index
(self: higra.higram.Tree, edge_index: int) → tuple¶ Get an edge from its index.

edge_list
()¶ Returns a tuple of two arrays (sources, targets) defining all the edges of the graph.
 Example
>>> t = Tree((5, 5, 6, 6, 6, 7, 7, 7)) >>> t.edge_list() (array([0, 1, 2, 3, 4, 5, 6]), array([5, 5, 6, 6, 6, 7, 7]))
 Returns
pair of two 1d arrays

edges
(self: higra.higram.Tree) → Iterator¶ Iterator over all edges of the graph.

find_region
(vertex, level, altitudes)¶ Searches for the largest node of altitude lower than the given level and containing the given vertex. If no such node exists the given vertex is returned.
 Parameters
vertex – a vertex or a 1d array of vertices
level – a level or a 1d array of levels (should have the same dtype as altitudes)
altitudes – altitudes of the nodes of the tree
 Returns
a vertex or a 1d array of vertices

in_degree
(*args, **kwargs)¶ Overloaded function.
in_degree(self: higra.higram.Tree, vertex: int) > int
Return the in degree of the given vertex.
in_degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.int32]) > xt::xtensor
Return the in degree of the given vertices.
in_degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.uint32]) > xt::xtensor
in_degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.int64]) > xt::xtensor
in_degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.uint64]) > xt::xtensor

in_edges
(self: higra.higram.Tree, vertex: int) → Iterator¶ Iterator over all in edges from ‘vertex’. An in edge is a tuple ‘(adjacent_vertex, vertex)’.

index
(self: higra.higram.Tree, edge: tuple) → detail::accessor<detail::accessor_policies::tuple_item>¶ Get the index of an edge.

is_leaf
(*args, **kwargs)¶ Overloaded function.
is_leaf(self: higra.higram.Tree, vertex: int) > bool
Returns true if the given node is a leaf of true and false otherwise.
is_leaf(self: higra.higram.Tree, vertices: numpy.ndarray[numpy.int32]) > xt::xtensor
Indicates if each vertex in the given array is a leaf or not.
is_leaf(self: higra.higram.Tree, vertices: numpy.ndarray[numpy.uint32]) > xt::xtensor
is_leaf(self: higra.higram.Tree, vertices: numpy.ndarray[numpy.int64]) > xt::xtensor
is_leaf(self: higra.higram.Tree, vertices: numpy.ndarray[numpy.uint64]) > xt::xtensor

leaves
(self: higra.higram.Tree) → Iterator¶ Returns an iterator on leaves of the tree.

leaves_to_root_iterator
(self: higra.higram.Tree, include_leaves: bool = True, include_root: bool = True) → Iterator¶ Returns an iterator on the node indices going from the leaves to the root of the tree.

lowest_common_ancestor
(vertices1, vertices2)¶ Compute the lowest common ancestor between pairs of vertices defined by
vertices1
andvertices2
.vertices1
andvertices2
must be either:two positive integers strictly smaller than the number of vertices in the tree;
two 1d arrays of positive integers strictly smaller than the number of vertices in the tree and of the same size.
 Complexity
The worst case time complexity is \(\mathcal{O}(qn)\) with \(q\) the number of lowest ancestors to compute and \(n\) the number of vertices in the tree.
If many lowest ancestors are needed, this time complexity can be reduced to \(\mathcal{O}(q)\) at the cost of a linearithmic time \(\mathcal{O}(n\log(n))\) preprocessing by calling the function
lowest_common_ancestor_preprocess()
. Parameters
vertices1 – a vertex index or an array of vertex indices
vertices2 – a vertex index or an array of vertex indices
 Returns
the lowest common ancestor(s) of every pair of input vertices (a single index or an array of indices)

lowest_common_ancestor_preprocess
(algorithm='sparse_table_block', block_size=1024, force_recompute=False)¶ Preprocess the tree to obtain a fast constant time \(\mathcal{O}(1)\) lowest common ancestor query. Once this function has been called on a given tree instance, every following calls to the function
lowest_common_ancestor()
will use this preprocessing. Calling twice this function does nothing except ifforce_recompute
isTrue
.Two algorithms are available:
sparse_table
has a preprocessing time and space complexity in \(\mathcal{O}(n\log(n))\) with \(n\) the number of vertices in the tree and performs every query in constant time \(\mathcal{O}(1)\).sparse_table_block
(default) has a linear preprocessing time and space complexity in \(\mathcal{O}(n)\) and performs queries in averagecase constant time \(\mathcal{O}(1)\). With this algorithm the user can specify the block size to be used, the general rule of thumb being that larger block size will decrease the preprocessing time but increase the query time.
 Parameters
algorithm – specify the algorithm to be used, can be either
sparse_table
orsparse_table_block
.block_size – if
algorithm
issparse_table_block
, specify the block size to be used (default 1024)force_recompute – if
False
(default) calling this function twice won’t repreprocess the tree, even if the specified algorithm or algorithm parameter have changed.
 Returns
An object of type
LCA_rmq_sparse_table_block
orLCA_rmq_sparse_table

num_children
(vertex=None)¶ Get the the number of children of the given vertices.
If
vertex
isNone
, the function will return the number of children of every non leaf node of the tree. Parameters
vertex – a vertex index or a 1d array of vertex indices (default to
np.arange(self.num_leaves(), self.num_vertices()
) Returns
an integer or a 1d array of integers

num_edges
(self: higra.higram.Tree) → int¶ Return the number of edges in the graph

num_leaves
(self: higra.higram.Tree) → int¶ Get the number of leaves nodes.

num_vertices
(self: higra.higram.Tree) → int¶ Return the number of vertices in the graph

out_degree
(*args, **kwargs)¶ Overloaded function.
out_degree(self: higra.higram.Tree, vertex: int) > int
Return the out degree of the given vertex.
out_degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.int32]) > xt::xtensor
Return the out degree of the given vertices.
out_degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.uint32]) > xt::xtensor
out_degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.int64]) > xt::xtensor
out_degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.uint64]) > xt::xtensor

out_edges
(self: higra.higram.Tree, vertex: int) → Iterator¶ Iterator over all out edges from ‘vertex’. An out edge is a tuple ‘(vertex, adjacent_vertex)’.

parent
(*args, **kwargs)¶ Overloaded function.
parent(self: higra.higram.Tree, node: int) > int
Get the parent of the given node.
parent(self: higra.higram.Tree, vertices: numpy.ndarray[numpy.int32]) > xt::xtensor
Get the parent of each vertex in the given array.
parent(self: higra.higram.Tree, vertices: numpy.ndarray[numpy.uint32]) > xt::xtensor
parent(self: higra.higram.Tree, vertices: numpy.ndarray[numpy.int64]) > xt::xtensor
parent(self: higra.higram.Tree, vertices: numpy.ndarray[numpy.uint64]) > xt::xtensor

parents
(self: higra.higram.Tree) → xt::xtensor¶ Get the parents array representing the tree.

root
(self: higra.higram.Tree) → int¶ Get the index of the root node (i.e. self.num_vertices()  1)

root_to_leaves_iterator
(self: higra.higram.Tree, include_leaves: bool = True, include_root: bool = True) → Iterator¶ Returns an iterator on the node indices going from the root to the leaves of the tree.

source
(self: higra.higram.Tree, edge: tuple) → detail::accessor<detail::accessor_policies::tuple_item>¶ Get the source vertex of an edge.

sources
()¶ Source vertex of every edge of the graph.
 Example
>>> t = Tree((5, 5, 6, 6, 6, 7, 7, 7)) >>> t.sources() array([0, 1, 2, 3, 4, 5, 6])
 Returns
a 1d array of size
self.num_edges()

sub_tree
(root_node)¶ Extract the sub tree rooted in the given node of the current tree.
The result is a new tree \(st\) and a node map \(nm\) such that:
the node map associates each node of the sub tree \(st\) to its corresponding node in the original tree
the order of the nodes of the original tree is preserved in the sub tree: for any vertices \(x\) and \(y\) of \(st\) such that \(x < y\) then \(nm[x] < nm[y]\)
 Complexity
The tree is constructed in linearithmic time \(\mathcal{O}(n\log(n))\) with \(n\) the number of vertices in the sub tree.
 Example
>>> t = Tree((5, 5, 6, 6, 6, 7, 7, 7)) >>> sub_tree, node_map = t.sub_tree(6) >>> sub_tree.parents() array([3, 3, 3, 3]) >>> node_map array([2, 3, 4, 6])
 Parameters
root_node – a vertex of the current tree
 Returns
the sub tree rooted in
root
and the node map

target
(self: higra.higram.Tree, edge: tuple) → detail::accessor<detail::accessor_policies::tuple_item>¶ Get the target vertex of an edge.

targets
()¶ Target vertex of every edge of the graph.
 Example
>>> t = Tree((5, 5, 6, 6, 6, 7, 7, 7)) >>> t.targets() array([5, 5, 6, 6, 6, 7, 7])
 Returns
a 1d array of size
self.num_edges()

vertices
(self: higra.higram.Tree) → Iterator¶ Iterator over all vertices of the graph.

Undirected graph¶
The UndirectedGraph
class is suited to represent general undirected graphs.

class
UndirectedGraph
¶ A class to represent sparse undirected graph as adjacency lists.

__init__
(self: higra.higram.UndirectedGraph, number_of_vertices: int = 0, reserved_edges: int = 0, reserved_edge_per_vertex: int = 0) → None¶ Create a new graph with no edge.
 Parameters
number_of_vertices – initial number of vertices in the graph
reserved_edges – preallocate space for the given number of edges
reserved_edge_per_vertex – preallocate space for the given number of edge per vertex

add_edge
(self: higra.higram.UndirectedGraph, source: int, target: int) → tuple¶ Add an (undirected) edge between ‘vertex1’ and ‘vertex2’. Returns the new edge.

add_edges
(*args, **kwargs)¶ Overloaded function.
add_edges(self: higra.higram.UndirectedGraph, sources: numpy.ndarray[numpy.int32], targets: numpy.ndarray[numpy.int32]) > None
Add all edges given as a pair of arrays (sources, targets) to the graph.
add_edges(self: higra.higram.UndirectedGraph, sources: numpy.ndarray[numpy.uint32], targets: numpy.ndarray[numpy.uint32]) > None
add_edges(self: higra.higram.UndirectedGraph, sources: numpy.ndarray[numpy.int64], targets: numpy.ndarray[numpy.int64]) > None
add_edges(self: higra.higram.UndirectedGraph, sources: numpy.ndarray[numpy.uint64], targets: numpy.ndarray[numpy.uint64]) > None

add_vertex
(self: higra.higram.UndirectedGraph) → int¶ Add a vertex to the graph, the index of the new vertex is returned

add_vertices
(self: higra.higram.UndirectedGraph, num: int) → None¶ Add the given number of vertices to the graph.

adjacent_vertices
(self: higra.higram.UndirectedGraph, vertex: int) → Iterator¶ Iterator over all vertices adjacent to the given vertex.

degree
(*args, **kwargs)¶ Overloaded function.
degree(self: higra.higram.UndirectedGraph, vertex: int) > int
Return the degree of the given vertex.
degree(self: higra.higram.UndirectedGraph, vertices_array: numpy.ndarray[numpy.int32]) > xt::xtensor
Return the degree of the given vertices.
degree(self: higra.higram.UndirectedGraph, vertices_array: numpy.ndarray[numpy.uint32]) > xt::xtensor
degree(self: higra.higram.UndirectedGraph, vertices_array: numpy.ndarray[numpy.int64]) > xt::xtensor
degree(self: higra.higram.UndirectedGraph, vertices_array: numpy.ndarray[numpy.uint64]) > xt::xtensor

edge_from_index
(self: higra.higram.UndirectedGraph, edge_index: int) → tuple¶ Get an edge from its index.

edge_list
()¶ Returns a tuple of two arrays (sources, targets) defining all the edges of the graph.
 Example
>>> g = UndirectedGraph(3) >>> g.add_edges((0, 1, 0), (1, 2, 2)) >>> g.edge_list() (array([0, 1, 0]), array([1, 2, 2]))
 Returns
pair of two 1d arrays

edges
(self: higra.higram.UndirectedGraph) → Iterator¶ Iterator over all edges of the graph.

in_degree
(*args, **kwargs)¶ Overloaded function.
in_degree(self: higra.higram.UndirectedGraph, vertex: int) > int
Return the in degree of the given vertex.
in_degree(self: higra.higram.UndirectedGraph, vertices_array: numpy.ndarray[numpy.int32]) > xt::xtensor
Return the in degree of the given vertices.
in_degree(self: higra.higram.UndirectedGraph, vertices_array: numpy.ndarray[numpy.uint32]) > xt::xtensor
in_degree(self: higra.higram.UndirectedGraph, vertices_array: numpy.ndarray[numpy.int64]) > xt::xtensor
in_degree(self: higra.higram.UndirectedGraph, vertices_array: numpy.ndarray[numpy.uint64]) > xt::xtensor

in_edges
(self: higra.higram.UndirectedGraph, vertex: int) → Iterator¶ Iterator over all in edges from ‘vertex’. An in edge is a tuple ‘(adjacent_vertex, vertex)’.

index
(self: higra.higram.UndirectedGraph, edge: tuple) → detail::accessor<detail::accessor_policies::tuple_item>¶ Get the index of an edge.

num_edges
(self: higra.higram.UndirectedGraph) → int¶ Return the number of edges in the graph

num_vertices
(self: higra.higram.UndirectedGraph) → int¶ Return the number of vertices in the graph

out_degree
(*args, **kwargs)¶ Overloaded function.
out_degree(self: higra.higram.UndirectedGraph, vertex: int) > int
Return the out degree of the given vertex.
out_degree(self: higra.higram.UndirectedGraph, vertices_array: numpy.ndarray[numpy.int32]) > xt::xtensor
Return the out degree of the given vertices.
out_degree(self: higra.higram.UndirectedGraph, vertices_array: numpy.ndarray[numpy.uint32]) > xt::xtensor
out_degree(self: higra.higram.UndirectedGraph, vertices_array: numpy.ndarray[numpy.int64]) > xt::xtensor
out_degree(self: higra.higram.UndirectedGraph, vertices_array: numpy.ndarray[numpy.uint64]) > xt::xtensor

out_edges
(self: higra.higram.UndirectedGraph, vertex: int) → Iterator¶ Iterator over all out edges from ‘vertex’. An out edge is a tuple ‘(vertex, adjacent_vertex)’.

remove_edge
(self: higra.higram.UndirectedGraph, edge_index: int) → None¶ Remove the given edge from the graph (the edge is not really removed: its source and target are attached to a virtual node of index 1).

set_edge
(self: higra.higram.UndirectedGraph, edge_index: int, source: int, target: int) → None¶ Modify the source and the target of the given edge.

source
(self: higra.higram.UndirectedGraph, edge: tuple) → detail::accessor<detail::accessor_policies::tuple_item>¶ Get the source vertex of an edge.

sources
()¶ Source vertex of every edge of the graph.
 Example
>>> g = UndirectedGraph(3) >>> g.add_edges((0, 1, 0), (1, 2, 2)) >>> g.sources() array([0, 1, 0])
 Returns
a 1d array of size
self.num_edges()

target
(self: higra.higram.UndirectedGraph, edge: tuple) → detail::accessor<detail::accessor_policies::tuple_item>¶ Get the target vertex of an edge.

targets
()¶ Target vertex of every edge of the graph.
 Example
>>> g = UndirectedGraph(3) >>> g.add_edges((0, 1, 0), (1, 2, 2)) >>> g.targets() array([1, 2, 2])
 Returns
a 1d array of size
self.num_edges()

vertices
(self: higra.higram.UndirectedGraph) → Iterator¶ Iterator over all vertices of the graph.

Interoperability¶
Scipy Interoperability functions¶
Converts an Higra binary hierarchy to a SciPy linkage matrix. 

Converts a SciPy linkage matrix to an Higra binary hierarchy. 

binary_hierarchy_to_scipy_linkage_matrix
(tree, altitudes=None, area=None)[source]¶ Converts an Higra binary hierarchy to a SciPy linkage matrix.
From SciPy documentation:
An \(n1\) by 4 matrix \(Z\) is returned. At the \(i\)th iteration, clusters with indices \(Z[i, 0]\) and \(Z[i, 1]\) are combined to form cluster \(n+i\). A cluster with an index less than \(n\) corresponds to one of the \(n\) original observations. The distance between clusters \(Z[i, 0]\) and \(Z[i, 1]\) is given by \(Z[i, 2]\). The fourth value \(Z[i, 3]\) represents the number of original observations in the newly formed cluster.
If
altitudes
is not specified, the value provided byattribute_regular_altitudes()
ontree
is used.If
area
is not specified, the value provided byattribute_area()
ontree
is used. Parameters
tree – Input tree
altitudes – Tree nodes altitudes (should be increasing w.r.t tree)
area – Tree nodes area (should be increasing w.r.t tree)
 Returns
A linkage matrix

scipy_linkage_matrix_to_binary_hierarchy
(linkage_matrix)[source]¶ Converts a SciPy linkage matrix to an Higra binary hierarchy.
The result is composed of
a tree
an array containing the altitudes of the tree nodes
an array containing the area of the tree nodes
 Parameters
linkage_matrix – a 2d array as produced by the linkage method of SciPy
 Returns
a tuple (tree, altitudes, area)
Image applications¶
2D contours representation and simplification¶

Overloaded function. 
A contour2d is a set of polyline contours. 

A polyline contour is an ordered list of contour segment that form a continuous piece of frontier between 2 regions. 

A contour segment is an ordered list of contour elements that are considered to form a straight line segment.A contour element is a pair (edge_index, coordinates) where coordinates is a 2d point. 

fit_contour_2d
(*args, **kwargs)¶ Overloaded function.
fit_contour_2d(graph: hg::undirected_graph_internal::undirected_graph<hg::undirected_graph_internal::vecS>, shape: List[int], edgeWeights: numpy.ndarray[numpy.int8]) > higra.higram.Contour2d
Construct a contour_2d object from a graph cut of a 2d image with a 4 adjacency (non zero edges are part of the cut).
fit_contour_2d(graph: hg::undirected_graph_internal::undirected_graph<hg::undirected_graph_internal::vecS>, shape: List[int], edgeWeights: numpy.ndarray[numpy.uint8]) > higra.higram.Contour2d
fit_contour_2d(graph: hg::undirected_graph_internal::undirected_graph<hg::undirected_graph_internal::vecS>, shape: List[int], edgeWeights: numpy.ndarray[numpy.int16]) > higra.higram.Contour2d
fit_contour_2d(graph: hg::undirected_graph_internal::undirected_graph<hg::undirected_graph_internal::vecS>, shape: List[int], edgeWeights: numpy.ndarray[numpy.uint16]) > higra.higram.Contour2d
fit_contour_2d(graph: hg::undirected_graph_internal::undirected_graph<hg::undirected_graph_internal::vecS>, shape: List[int], edgeWeights: numpy.ndarray[numpy.int32]) > higra.higram.Contour2d
fit_contour_2d(graph: hg::undirected_graph_internal::undirected_graph<hg::undirected_graph_internal::vecS>, shape: List[int], edgeWeights: numpy.ndarray[numpy.uint32]) > higra.higram.Contour2d
fit_contour_2d(graph: hg::undirected_graph_internal::undirected_graph<hg::undirected_graph_internal::vecS>, shape: List[int], edgeWeights: numpy.ndarray[numpy.int64]) > higra.higram.Contour2d
fit_contour_2d(graph: hg::undirected_graph_internal::undirected_graph<hg::undirected_graph_internal::vecS>, shape: List[int], edgeWeights: numpy.ndarray[numpy.uint64]) > higra.higram.Contour2d
fit_contour_2d(graph: hg::undirected_graph_internal::undirected_graph<hg::undirected_graph_internal::vecS>, shape: List[int], edgeWeights: numpy.ndarray[numpy.float32]) > higra.higram.Contour2d
fit_contour_2d(graph: hg::undirected_graph_internal::undirected_graph<hg::undirected_graph_internal::vecS>, shape: List[int], edgeWeights: numpy.ndarray[numpy.float64]) > higra.higram.Contour2d

class
Contour2d
¶ A contour2d is a set of polyline contours. Each polyline contour represent a continuous piece of contour between two regions.

__getitem__
(self: higra.higram.Contour2d, arg0: int) → higra.higram.PolylineContour2d¶

__init__
()¶ Initialize self. See help(type(self)) for accurate signature.

__iter__
(self: higra.higram.Contour2d) → Iterator¶ Iterator on the polyline contours.

__len__
(self: higra.higram.Contour2d) → int¶ Number of polyline contours.

subdivide
(self: higra.higram.Contour2d, epsilon: float = 0.1, relative_epsilon: bool = True, min_size: int = 2) → None¶ Subdivide each segment of the contour such that: For each segment, the distance between the line joining the extremities of the segment and each of its elements is lower than the given threshold (Ramer–Douglas–Peucker algorithm) or smaller than the minimal specified size The threshold is equal to  epsilon if relative_epsilon is false  epsilon times the distance between the segment extremities if relative_epsilon is true
Implementation note: simply call subdivide on each polyline of the contour.


class
PolylineContour2d
¶ A polyline contour is an ordered list of contour segment that form a continuous piece of frontier between 2 regions. Note that consecutive segments share their extremities: given two consecutive contour segments s1 and s2, the last element of s1 is equal to the first element of s2.

__getitem__
(self: higra.higram.PolylineContour2d, arg0: int) → higra.higram.ContourSegment2d¶

__init__
()¶ Initialize self. See help(type(self)) for accurate signature.

__iter__
(self: higra.higram.PolylineContour2d) → Iterator¶ Iterator on the contour segments of the polyline contour.

__len__
(self: higra.higram.PolylineContour2d) → int¶ Number of segments in the polyline contour.

subdivide
(self: higra.higram.PolylineContour2d, epsilon: float = 0.1, relative_epsilon: bool = True, min_size: int = 2) → None¶ Subdivide the line such that the distance between the line joining the extremities of the contour segment and each of its elements is lower than the threshold ( Ramer–Douglas–Peucker algorithm) or smaller than the minimal specified size
The threshold is equal to  epsilon if relative_epsilon is false  epsilon times the distance between the segment extremities if relative_epsilon is true


class
ContourSegment2d
¶ A contour segment is an ordered list of contour elements that are considered to form a straight line segment.A contour element is a pair (edge_index, coordinates) where coordinates is a 2d point.

__getitem__
(self: higra.higram.ContourSegment2d, arg0: int) → Tuple[int, Tuple[float, float]]¶

__init__
()¶ Initialize self. See help(type(self)) for accurate signature.

__iter__
(self: higra.higram.ContourSegment2d) → Iterator¶ Iterator on the contour elements of the contour segment.

__len__
(self: higra.higram.ContourSegment2d) → int¶ Number of elements in the contour segment.

angle
(self: higra.higram.ContourSegment2d) → float¶ Angle of the vector (last()first()) in [pi; pi].

distance_to_point
(self: higra.higram.ContourSegment2d, point: xt::xfixed_container<double, xt::fixed_shape<2ul>, (xt::layout_type)1, true, xt::xtensor_expression_tag>) → float¶ Distance between the given point and the line defined by the fist and last element of the contour segment.

norm
(self: higra.higram.ContourSegment2d) → float¶ Distance between first and last elements of the contour segment.

Utility functions for graph and images¶

Create a contour image in the Khalimsky grid from a 4 adjacency edgeweighted graph. 

Create a 4 adjacency edgeweighted graph from a contour image in the Khalimsky grid. 

Create an explicit undirected 4 adjacency graph of the given shape. 

Create an explicit undirected 8 adjacency graph of the given shape. 
Create an implicit undirected 4 adjacency graph of the given shape (edges are not stored). 

Create an implicit undirected 8 adjacency graph of the given shape (edges are not stored). 


Creates a regular graph of the given 

Creates an implicit regular graph of the given 

Converts as a neighbouring mask as a neighbour list. 

graph_4_adjacency_2_khalimsky
(graph, edge_weights, shape, add_extra_border=False)[source]¶ Create a contour image in the Khalimsky grid from a 4 adjacency edgeweighted graph.
 Parameters
graph – must be a 4 adjacency 2d graph (Concept
CptGridGraph
)edge_weights – edge weights of the graph
shape – shape of the graph (deduced from
CptGridGraph
)add_extra_border – if False result size is 2 * shape  1 and 2 * shape + 1 otherwise
 Returns
a 2d array

khalimsky_2_graph_4_adjacency
(khalimsky, extra_border=False)[source]¶ Create a 4 adjacency edgeweighted graph from a contour image in the Khalimsky grid.
 Parameters
khalimsky – a 2d array
extra_border – if False the shape of the Khalimsky image is 2 * shape  1 and 2 * shape + 1 otherwise, where shape is the shape of the resulting grid graph
 Returns
a graph (Concept
CptGridGraph
) and its edge weights

get_4_adjacency_graph
(shape)[source]¶ Create an explicit undirected 4 adjacency graph of the given shape.
 Parameters
shape – a pair (height, width)
 Returns
a graph (Concept
CptGridGraph
)

get_8_adjacency_graph
(shape)[source]¶ Create an explicit undirected 8 adjacency graph of the given shape.
 Parameters
shape – a pair (height, width)
 Returns
a graph (Concept
CptGridGraph
)

get_4_adjacency_implicit_graph
(shape)[source]¶ Create an implicit undirected 4 adjacency graph of the given shape (edges are not stored).
 Parameters
shape – a pair (height, width)
 Returns
a graph (Concept
CptGridGraph
)

get_8_adjacency_implicit_graph
(shape)[source]¶ Create an implicit undirected 8 adjacency graph of the given shape (edges are not stored).
 Parameters
shape – a pair (height, width)
 Returns
a graph (Concept
CptGridGraph
)

get_nd_regular_graph
(shape, neighbour_list)[source]¶ Creates a regular graph of the given
shape
with the adjacency given as aneighbour_list
.See the helper function
mask_2_neighbours()
to create a suitableneighbour_list
. Example
Create a 2d 4adjacency implicit graph of size
(13, 24)
:>>> graph = get_nd_regular_graph((13, 24), ((1, 0), (0, 1), (0, 1), (1, 0)))
Create a 3d 6adjacency implicit graph of size
(10, 13, 24)
:>>> mask = [[[0, 0, 0], [0, 1, 0], [0, 0, 0]], >>> [[0, 1, 0], [1, 0, 1], [0, 1, 0]], >>> [[0, 0, 0], [0, 1, 0], [0, 0, 0]]] >>> neighbours = mask_2_neighbours(mask) >>> graph = get_nd_regular_graph((10, 13, 24), neighbours)
 Parameters
shape – a tuple of \(n\) elements representing the dimension of the graph vertices.
neighbour_list – a 2d array of \(k\) \(n\)d integer vectors
 Returns
a regular graph

get_nd_regular_implicit_graph
(shape, neighbour_list)[source]¶ Creates an implicit regular graph of the given
shape
with the adjacency given as aneighbour_list
.See the helper function
mask_2_neighbours()
to create a suitableneighbour_list
. Example
Create a 2d 4adjacency implicit graph of size
(13, 24)
:>>> graph = get_nd_regular_implicit_graph((13, 24), ((1, 0), (0, 1), (0, 1), (1, 0)))
Create a 3d 6adjacency implicit graph of size
(10, 13, 24)
:>>> mask = [[[0, 0, 0], [0, 1, 0], [0, 0, 0]], >>> [[0, 1, 0], [1, 0, 1], [0, 1, 0]], >>> [[0, 0, 0], [0, 1, 0], [0, 0, 0]]] >>> neighbours = mask_2_neighbours(mask) >>> graph = get_nd_regular_implicit_graph((10, 13, 24), neighbours)
 Parameters
shape – a tuple of \(n\) elements representing the dimension of the graph vertices.
neighbour_list – a 2d array of \(k\) \(n\)d integer vectors
 Returns
an implicit regular graph

mask_2_neighbours
(mask, center=None)[source]¶ Converts as a neighbouring mask as a neighbour list. A neighbouring
mask
is a \(n\)d matrix where each strictly positive value represent a neighbour of thecenter
point. The neighbour list is obtained by offsetting the coordinates of those positive values by the coordinates of the center.The default center is the center of the
mask
matrix: i.e.mask.shape // 2
. Example
>>> mask = [[0, 1, 0], [1, 0, 1], [0, 1, 0]] >>> hg.mask_2_neighbours(mask) array([[1, 0], [0, 1], [0, 1], [1, 0]])
>>> mask = [[0, 1, 0], [1, 0, 1], [0, 1, 0]] >>> center = [2, 1] >>> hg.mask_2_neighbours(mask) array([[2, 0], [1, 1], [1, 1], [0, 0]])
>>> mask = [[[0, 0, 0], [0, 1, 0], [0, 0, 0]], >>> [[0, 1, 0], [1, 0, 1], [0, 1, 0]], >>> [[0, 0, 0], [0, 1, 0], [0, 0, 0]]] >>> hg.mask_2_neighbours(mask) array([[1, 0, 0], [1, 0, 0], [0, 1, 0], [0, 1, 0], [0, 0, 1], [0, 0, 1]])
 Parameters
mask – a \(n\)d matrix
center – a 1d array of size \(n\) (optional)
 Returns
a list of point coordinates
Mean probability boundary hierarchy¶

Creates a region adjacency graph (rag) with the oriented watershed transform. 

Mean probability boundary hierarchy. 

Multiscale mean probability boundary hierarchy. 

oriented_watershed
(graph, edge_weights, shape, edge_orientations=None)[source]¶ Creates a region adjacency graph (rag) with the oriented watershed transform.
The method is described in:
P. Arbelaez, M. Maire, C. Fowlkes and J. Malik, “Contour Detection and Hierarchical Image Segmentation,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 5, pp. 898916, May 2011. doi: 10.1109/TPAMI.2010.161
If no edge orientations are provided, then the weight of a rag edge between region i and j is the mean weight of the edges linking a vertex of i to a vertex of j.
This does not include gradient estimation.
 Parameters
graph – must be a 4 adjacency graph (Concept
CptGridGraph
)edge_weights – gradient value on edges
shape – shape of the graph, i.e. a pair (height, width) (deduced from
CptGridGraph
)edge_orientations – estimated orientation of the gradient on edges (optional)
 Returns
a pair (rag, rag_edge_weights): the region adjacency graph (Concept
CptRegionAdjacencyGraph
) and its estimated edge_weights

mean_pb_hierarchy
(graph, edge_weights, shape, edge_orientations=None)[source]¶ Mean probability boundary hierarchy.
The method is described in:
P. Arbelaez, M. Maire, C. Fowlkes and J. Malik, “Contour Detection and Hierarchical Image Segmentation,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 5, pp. 898916, May 2011. doi: 10.1109/TPAMI.2010.161
This does not include gradient estimation.
The returned hierarchy is defined on the gradient watershed superpixels.
The final sigmoid scaling of the hierarchy altitude is not performed.
 Parameters
graph – must be a 4 adjacency graph (Concept
CptGridGraph
)edge_weights – gradient value on edges
shape – shape of the graph, i.e. a pair (height, width) (deduced from
CptGridGraph
)edge_orientations – estimated orientation of the gradient on edges (optional)
 Returns
a tree (Concept
CptHierarchy
) and its node altitudes

multiscale_mean_pb_hierarchy
(graph, fine_edge_weights, others_edge_weights, shape, edge_orientations=None)[source]¶ Multiscale mean probability boundary hierarchy.
The method is described in:
J. PontTuset, P. Arbeláez, J. Barron, F. Marques, and J. Malik Multiscale Combinatorial Grouping for Image Segmentation and Object Proposal Generation IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), vol. 39, no. 1, pp. 128  140, 2017.
and in:
K.K. Maninis, J. PontTuset, P. Arbeláez and L. Van Gool Convolutional Oriented Boundaries: From Image Segmentation to HighLevel Tasks IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), vol. 40, no. 4, pp. 819  833, 2018.
This does not include gradient estimation.
The returned hierarchy is defined on the gradient watershed superpixels.
The final sigmoid scaling of the hierarchy altitude is not performed.
 Parameters
graph – must be a 4 adjacency graph (Concept
CptGridGraph
)fine_edge_weights – edge weights of the finest gradient
others_edge_weights – tuple of gradient value on edges
shape – shape of the graph, i.e. a pair (height, width) (deduced from
CptGridGraph
)edge_orientations – estimated orientation of the gradient on edges (optional)
 Returns
a tree (Concept
CptHierarchy
) and its node altitudes
Tree of shapes¶
Tree of shapes of a 2d image. 

Multivariate tree of shapes for a 2d multiband image. 

component_tree_tree_of_shapes_image2d
(image, padding='mean', original_size=True, immersion=True, exterior_vertex=0)[source]¶ Tree of shapes of a 2d image.
The Tree of Shapes was described in 1. The algorithm used in this implementation was first described in 2.
The tree is computed in the interpolated multivalued Khalimsky space to provide a continuous and autodual representation of input image.
Possible values of padding are ‘none’, ‘mean’, and ‘zero’. If padding is different from ‘none’, an extra border of pixels is added to the input image before anything else. This will ensure the existence of a shape encompassing all the shapes inside the input image (if exterior_vertex is inside the extra border): this shape will be the root of the tree. The padding value can be:
0 if
padding
is equal to"zero"
;the mean value of the boundary pixels of the input image if
padding
is equal to"mean"
.
If
original_size
isTrue
, all the nodes corresponding to pixels not belonging to the input image are removed (except for the root node). Iforiginal_size
isFalse
, the returned tree is the tree constructed in the interpolated/padded space. In practice if the size of the input image is \((h, w)\), the leaves of the returned tree will correspond to an image of size:\((h, w)\) if
original_size
isTrue
;\((h * 2  1, w * 2  1)\) is
original_size
isFalse
andpadding
is"none"
; and\(((h + 2) * 2  1, (w + 2) * 2  1)\) otherwise.
 Advanced options
immersion
defines if the initial image should be first converted as an equivalent continuous representation called a plain map. Ifimmersion
is set toFalse
the level lines of the shapes of the image may intersect (if the image is not well composed) and the result of the algorithm is undefined (the algorithm will arbitrarily break level lines to get a set of shapes forming a tree). Ifimmersion
isFalse
, the result size will be:\((h, w)\) if
original_size
isTrue
or ifpadding
is"none"
;\((h + 2, w + 2)\) otherwise.
Exterior_vertex
defines the linear coordinates of the pixel corresponding to the exterior (interior and exterior of a shape is defined with respect to this point). The coordinate of this point must be given in the padded/interpolated space. 1
Pa. Monasse, and F. Guichard, “Fast computation of a contrastinvariant image representation,” Image Processing, IEEE Transactions on, vol.9, no.5, pp.860872, May 2000
 2
Th. Géraud, E. Carlinet, S. Crozet, and L. Najman, “A Quasilinear Algorithm to Compute the Tree of Shapes of nD Images”, ISMM 2013.
 Parameters
image – must be a 2d array
padding – possible values are ‘none’, ‘zero’, and ‘mean’ (default = ‘mean’)
original_size – remove all nodes corresponding to interpolated/padded pixels (default = True)
immersion – performs a plain map continuous immersion fo the original image (default = True)
exterior_vertex – linear coordinate of the exterior point
 Returns
a tree (Concept
CptHierarchy
) and its node altitudes

component_tree_multivariate_tree_of_shapes_image2d
(image, padding='mean', original_size=True, immersion=True)[source]¶ Multivariate tree of shapes for a 2d multiband image. This tree is defined as a fusion of the marginal trees of shapes. The method is described in:
E. Carlinet. A Tree of shapes for multivariate images. PhD Thesis, Université ParisEst, 2015.
The input
image
must be a 3d array of shape \((height, width, channel)\).Note that the constructed hierarchy doesn’t have natural altitudes associated to its node: as a node is generally a fusion of several marginal nodes, we can’t associate a single canonical value from the original image to this node.
The parameters
padding
,original_size
, andimmersion
are forwarded to the functioncomponent_tree_tree_of_shapes_image2d()
: please look at this function documentation for more details. Complexity
The worst case runtime complexity of this method is \(\mathcal{O}(N^2D^2)\) with \(N\) the number of pixels and \(D\) the number of bands. If the image pixel values are quantized on \(K<<N\) different values (eg. with a color image in \([0..255]^D\)), then the worst case runtime complexity can be tightened to \(\mathcal{O}(NKD^2)\).
 See
This function relies on
tree_fusion_depth_map()
to compute the fusion of the marinal trees. Parameters
image – input color 2d image
padding – possible values are ‘none’, ‘zero’, and ‘mean’ (default = ‘mean’)
original_size – remove all nodes corresponding to interpolated/padded pixels (default = True)
immersion – performs a plain map continuous immersion fo the original image (default = True)
 Returns
a tree (Concept
CptHierarchy
)
IO¶
Pink Graph IO¶

Read a graph file stored in pink ascii format 

Save a (vertex/edge weighted) graph in the pink ascii file format. 

read_graph_pink
(filename)[source]¶ Read a graph file stored in pink ascii format
 Parameters
filename – path to the graph file
 Returns
a tuple (graph, vertex_weights, edge_weights)

save_graph_pink
(filename, graph, vertex_weights=None, edge_weights=None, shape=None)[source]¶ Save a (vertex/edge weighted) graph in the pink ascii file format.
 Parameters
filename – path to the graph file (will be overwritten if the file already exists!)
graph – graph to save (Concept
CptGridGraph
)edge_weights – edge weights of the graph (optional)
vertex_weights – vertex weights of the graph (optional)
shape – shape of the graph (optional) (deduced from
CptGridGraph
)
 Returns
nothing
Tree IO¶
Tree IO allows de/serialization of a tree and associated attributes in a custom simple format.

Print a partition tree in ASCII format. 

Read a tree stored in mixed ascii/binary format. 

Save a tree and scalar attributes to mixed ascii/binary format. 

print_partition_tree
(tree, *, altitudes=None, attribute=None, float_size=4, ordering='area', scale='linear', return_string=False)[source]¶ Print a partition tree in ASCII format.
The tree is represented as a dendrogram oriented horizontally with the leaves on the left and the root on the right. Node positions are proportional to their altitudes.
This function can be used for debugging and illustrations: it is not meant to handle large trees.
 Parameters
tree – Input tree
altitudes – Tree node altitudes (will default to
attribute_regular_altitudes(tree)()
ifNone
)attribute – Optional tree node attributes. If provided, the node attribute value will be printed instead of its altitude.
float_size – Number of characters reserved for number printing.
ordering – determine how the children of a node are ordered. Possible values are ‘altitudes’, ‘area’, ‘none’, ‘leaves’
scale – scale of the x axis: ‘linear’ (default) or ‘log’
return_string – if
True
, the string is returned instead of being printed (defaultFalse
)
 Returns
A string if
return_string
isTrue
,None
otherwise

read_tree
(filename)[source]¶ Read a tree stored in mixed ascii/binary format.
Attributes are also registered as tree object attributes.
 Parameters
filename – path to the tree file
 Returns
a pair (tree, attribute_map)

save_tree
(filename: str, tree: higra.higram.Tree, attributes: Dict[str, numpy.ndarray[numpy.float64]] = {}) → None¶ Save a tree and scalar attributes to mixed ascii/binary format. Attributes must be numpy 1d arrays stored in a dictionary with string keys (attribute names).
Simple graph and tree plotting¶

Plot the given graph. 

Plot the given tree as a dendrogram. 

Print a partition tree in ASCII format. 

plot_graph
(graph, *, vertex_positions, vertex_labels=None)[source]¶ Plot the given graph.
Requires the
matplotlib
library. Parameters
graph – Input graph
vertex_positions – 2d array containing the coordinates of each vertex of the graph
labels – Optional: vertex labels
 Returns
None

plot_partition_tree
(tree, *, altitudes=None, n_clusters=0, lastp=30)[source]¶ Plot the given tree as a dendrogram.
Requires the
matplotlib
and thescipy
libraries. Parameters
tree – Input tree
altitudes – Tree node altitudes (will default to
attribute_regular_altitudes(tree)()
ifNone
)n_clusters – Colorize the
n_clusters
largest clusters of the dendrogram with different colorslastp – Collapse subtrees containing less than
lastp
leaves.
 Returns
void
Misc functions¶
Data cache¶

List all Higra attributes of the object 

Get the Higra attributes named 

Set the Higra attributes named 

Function decorator that provides automatic caching of function results. 

Globally activates or deactivates the caching of 
Returns the current state of the caching policy for of 


Cleanup the result cache for the specified elements 

list_attributes
(key)[source]¶ List all Higra attributes of the object
key
.See functions
get_attribute()
andset_attribute()
. Parameters
key – an object
 Returns
a list of strings

get_attribute
(key, attribute_name)[source]¶ Get the Higra attributes named
attribute_name
of the objectkey
.See functions
list_attributes()
andset_attribute()
. Parameters
key – an object
attribute_name – a string
 Returns
the attribute value associated to the given name (
None
if no such attribute exists)

set_attribute
(key, attribute_name, attribute, insert_dynamic=True)[source]¶ Set the Higra attributes named
attribute_name
of the objectkey
to the valueattribute
.See functions
list_attributes()
andget_attribute()
. Parameters
key – an object
attribute_name – a string
attribute – a value
insert_dynamic – if
True
and ifkey
supports dynamic attributes, a new object attribute with the given name and values will be added to the given object
 Returns
None

@
auto_cache
[source]¶ Function decorator that provides automatic caching of function results.
The basic idea is that two successive calls with the same arguments to an auto_cache decorated function will indeed produce a single function call. The second time, the result of the first call will be returned.
Auto cache is useful for expensive functions that might be called in unrelated locations (where manual reuse of function result would be difficult).
Auto cache can only decorates functions with only positional and named arguments. The first argument of the function must support weak references.
 Special parameters
All functions decorated by
autocache
support the following named arguments:no_cache
(boolean value). IfTrue
, auto caching is disabled for this function call: no cached data will be used or stored.force_recompute
(boolean value). IfTrue
, no cache result will be used for this function call but the result of the function call will be cached for future use.
 Caveats
A function call is identified by a hash of its arguments. This hash is computed in such a way that non hashable objects (except from dictionaries) are indeed identified by their unique object identifier. This means that calling the same autocached function with the same mutated arguments can potentially lead to unexpected results.
>>> @hg.auto_cache >>> def cached_sum(a): >>> return sum(a) >>> >>> a = numpy.zeros(10) >>> cached_sum(a) 0 >>> a[0] = 1 # mutate a >>> cached_sum(a) # auto cache cannot detect mutation of a and returns the cached result 0
This problem can be solved by using
no_cache
,force_recompute
(see above) or by globally disabling function caching (seeset_auto_cache_state()
).>>> cached_sum(a, no_cache=True) # or force_recompute=True 1
If you are really unlucky, it might also appends that two unrelated set of arguments get the same hash. In such case the auto cache decorator will consider that they are the same. This is however extremely unlikely to happen.
 Life Time
The data stored in the cache are associated to the first argument of the function called the reference object. All data related to a reference object is cleared when it gets garbage collected.
The cache data associated to a particular function or object can be manually cleared with
clear_auto_cache()
. Global setting
Auto caching can be globally disabled, see:
 Returns

set_auto_cache_state
(boolean)[source]¶ Globally activates or deactivates the caching of
auto_cache()
decorated functions.If set to
True
(default), an auto cached function will save its results in the object cache of its first argument. Any other call to this function with the same arguments will return the result stored in the cache instead of recomputing a new result (except if this behaviour is locally overridden with the name arguments “force_recompute=True” or “no_cache=True”).If set to
False
, autocached functions will behave as normal function: they won’t try to cache results. See
get_auto_cache_state()
: get current state of the automatic caching. Parameters
boolean –
True
to globally activate caching,False
to deactivate it Returns
nothing

get_auto_cache_state
()[source]¶ Returns the current state of the caching policy for of
auto_cache()
decorated functions. See
set_auto_cache_state()
: modify the state of the automatic caching. Returns
True if autocaching is globally active, False otherwise

clear_auto_cache
(*, function=None, reference_object=None, data_cache=None)[source]¶ Cleanup the result cache for the specified elements
 Parameters
function – function or name of a
auto_cache()
decorated function to clear (ifNone
all functions are cleared)reference_object – reference object whose cached data have to be cleared (if
None
cache data of all objects are cleared)data_cache – data cache to work on (will default to the global Higra cache)
 Returns
nothing
Utility functions¶

Returns the indices that would sort an array. 

Sort the given array inplace. 

Set the maximum number of threads usable in parallel computing. 

Test if the given object is iterable 

Decorator: add the decorated function to the specified class. 

This function ensure that the given shape will be easily convertible in a c++ callback (ie that it won’t interfere badly in pybind11 overload resolution algorithm) 

Linearize the given ndarray according to the given shape. 

DeLinearize the given ndarray according to the given shape. 

Test if the given object has method member called 

Test if a bijection exists between the elements of 

Compute the element wise mean of two arrays of angles (radian) handling a modulo \(\pi\) wrapping. 

Returns a 

Find a common type to a list of numpy arrays. 

Find a common type to a list of numpy arrays, cast all arrays that need to be cast to this type and returns the list of arrays (with some of them casted). 

Cast the given numpy array to the given dtype and returns the result. 
Return the path to higra include files. 

Return the path to higra lib include files. 

Return the path to higra lib cmake files. 

arg_sort
(array, stable=False)[source]¶ Returns the indices that would sort an array. A parallel algorithm is used if possible.
If
stable
isTrue
, the relative order of equivalent elements is maintained (otherwise the ordering of equivalent elements may be arbitrary or even non deterministic).If the array has 2 dimensions, a lexicographic sort is used.
 Example
>>> a = np.asarray((5, 2, 1, 4, 9)) >>> hg.arg_sort(a) (2 1 3 0 4)
>>> a = np.asarray(((2, 2, 1, 1, 3), >>> (2, 2, 2, 1, 0))).T >>> hg.arg_sort(a, stable=True) (3 2 0 1 4)
 Parameters
array – input array (1d or 2d)
stable – if
True
, a stable sort is performed.
 Returns
A 1d array of indices that would sort the input array

sort
(array, stable=False)[source]¶ Sort the given array inplace. A parallel algorithm is used if possible.
If
stable
isTrue
, the relative order of equivalent elements is maintained (otherwise the ordering of equivalent elements may be arbitrary or even non deterministic). Example
>>> a = np.asarray((5, 2, 1, 4, 9)) >>> hg.sort(a) >>> a [1 2 4 5 9]
 Parameters
array – input array (1d or 2d)
stable – if
True
, a stable sort is performed.
 Returns
nothing

set_num_threads
(num_threads: int) → None¶ Set the maximum number of threads usable in parallel computing. If
num_threads
is equal to 0, the maximum number of threads resets to its default value (number of logical cores available on the machine).

is_iterable
(obj)[source]¶ Test if the given object is iterable
 Parameters
obj – an object
 Returns
True if obj is iterable, False otherwise

extend_class
(cls, method_name=None)[source]¶ Decorator: add the decorated function to the specified class. If no name is specified the name of the function is used.
 Example
>>> class A: >>> pass >>> >>> @extend_class(A, "shiny_method") >>> def hello(self, name): >>> print("Hello", name) >>> >>> a = A() >>> a.shiny_method("foo")
:param cls The class to extend :param method_name The name that the new method will take (If None, it will be determined from the decorated function)

normalize_shape
(shape)[source]¶ This function ensure that the given shape will be easily convertible in a c++ callback (ie that it won’t interfere badly in pybind11 overload resolution algorithm)
 Example
>>> normalize_shape([4, 5]) (4, 5)
 Parameters
shape – an iterable of integers
 Returns
the equivalent normalized shape

linearize_vertex_weights
(vertex_weights, graph=None, shape=None)[source]¶ Linearize the given ndarray according to the given shape.
If
shape
isNone
, the input array is returned.Else if
shape
is a prefix ofvertex_weights.shape
then thelen(shape)
first dimensions ofvertex_weights
are collapsed (linearized).Else if
vertex_weights.shape[0]
is equal to the product of the elements inshape
then the input array is returned (array was already linearized).Else: an exception is raised.
Note that this function tries its best to guess what should be done but some ambiguity might always exist.
 Examples
>>> r = hg.linearize_vertex_weights(np.ones((4, 5)), shape=(4, 5)) >>> r.shape (20,)
>>> r = hg.linearize_vertex_weights(np.ones((4, 5, 10, 12)), shape=(4, 5)) >>> r.shape (20, 10, 12)
>>> r = hg.linearize_vertex_weights(np.ones((20,)), shape=(4, 5)) >>> r.shape (20,)
>>> r = hg.linearize_vertex_weights(np.ones((20, 4, 5, 2, 3)), shape=(4, 5)) >>> r.shape (20, 4, 5, 2, 3)
 Raises
ValueError – if
vertex_weights.shape
andshape
are incompatible. See
 Parameters
vertex_weights – an ndarray representing vertex weights on a square ndgrid
graph – a graph (optional, Concept
CptGridGraph
)shape – a list of integers (optional, deduced from Concept
CptGridGraph
)
 Returns
maybe reshaped vertex_weights

delinearize_vertex_weights
(vertex_weights, graph=None, shape=None)[source]¶ DeLinearize the given ndarray according to the given shape.
If
shape
isNone
, the input array is returned.Else if
shape
is a prefix ofvertex_weights.shape
then the input array is returned.Else if
vertex_weights.shape[0]
is equal to the product of the elements inshape
then the first dimension ofvertex_weights
is expanded (delinearized) into the sequence of dimensions given byshape
Else: an exception is raised.
Note that this function tries its best to guess what should be done but some ambiguity might always exist.
 Examples
>>> r = hg.delinearize_vertex_weights(np.ones((20,)), shape=(4, 5)) >>> r.shape (4, 5)
>>> r = hg.delinearize_vertex_weights(np.ones((20, 4, 5, 2, 3)), shape=(4, 5)) >>> r.shape (4, 5, 4, 5, 2, 3)
>>> r = hg.delinearize_vertex_weights(np.ones((4, 5)), shape=(4, 5)) >>> r.shape (4, 5)
>>> r = hg.delinearize_vertex_weights(np.ones((4, 5, 10, 12)), shape=(4, 5)) >>> r.shape (4, 5, 10, 12)
 Raises
ValueError – if
vertex_weights.shape
andshape
are incompatible. See
 Parameters
vertex_weights – an ndarray representing vertex weights on a square ndgrid
graph – a graph (optional, Concept
CptGridGraph
)shape – a list of integers (optional, deduced from Concept
CptGridGraph
)
 Returns
maybe reshaped vertex_weights

has_method
(obj, method_name)[source]¶ Test if the given object has method member called
method_name
. Parameters
obj – an object
method_name – a string
 Returns
True
ifobject.method_name
is a valid callable expression,False
otherwise

is_in_bijection
(a, b)[source]¶ Test if a bijection exists between the elements of
a
and the elements ofb
.Given two numpy arrays
a
andb
returnsTrue
ifa
andb
have same sizethere exists a bijective function \(f\) such that, for all \(i\), \(a(i) = f(b(i))\)
Note that input arrays are flattened.
 Parameters
a – an nd array
b – an nd array
 Returns
True
if a bijection exists andFalse
otherwise

mean_angle_mod_pi
(angles1, angles2)[source]¶ Compute the element wise mean of two arrays of angles (radian) handling a modulo \(\pi\) wrapping.
eg: the modulo \(\pi\) mean angle between 0 and 3.0 is roughly 3.07
 Parameters
angles1 – must be in \([0; \pi]\)
angles2 – must be in \([0; \pi]\)
 Returns
average of angles1 and angles2 with correct wrapping in \([0; \pi]\)

dtype_info
(dtype)[source]¶ Returns a
numpy.iinfo
object if givendtype
is an integral type, and anumpy.finfo
if givendtype
is a float type. Raises
ValueError – if
dtype
is a more complex type. Parameters
dtype – a numpy dtype
 Returns
an info object on given
dtype

common_type
(*arrays, safety_level='minimum')[source]¶ Find a common type to a list of numpy arrays.
If safety level is equal to ‘minimum’, then the result type is the smallest that ensures that all values in all arrays can be represented exactly in the given type (except for np.uint64 which is allowed to fit in a np.int64!) In this case the function also guaranties that the result type is integral if all the arrays have integral types.
If safety level is equal to ‘overflow’, the result type ensures a to have a type suitable to contain the result of common operations involving the input arrays (additions, divisions…). This relies on
numpy.common_type
: The return type will always be an inexact (i.e. floating point) scalar type, even if all the arrays are integer arrays. If one of the inputs is an integer array, the minimum precision type that is returned is a 64bit floating point dtype.All input arrays except
int64
anduint64
can be safely cast to the returneddtype
without loss of information. Parameters
arrays – a sequence of numpy arrays
safety_level – either ‘minimum’ or ‘overflow’
 Returns
a numpy dtype

cast_to_common_type
(*arrays, safety_level='minimum')[source]¶ Find a common type to a list of numpy arrays, cast all arrays that need to be cast to this type and returns the list of arrays (with some of them casted).
If safety level is equal to ‘minimum’, then the result type is the smallest that ensures that all values in all arrays can be represented exactly in the given type (except for np.uint64 which is allowed to fit in a np.int64!) In this case the function also guaranties that the result type is integral if all the arrays have integral types.
If safety level is equal to ‘overflow’, the result type ensures a to have a type suitable to contain the result of common operations involving the input arrays (additions, divisions…). This relies on numpy.common_type: The return type will always be an inexact (i.e. floating point) scalar type, even if all the arrays are integer arrays. If one of the inputs is an integer array, the minimum precision type that is returned is a 64bit floating point dtype.
All input arrays except int64 and uint64 can be safely cast to the returned dtype without loss of information.
 See
 Parameters
arrays – a sequence of numpy arrays
safety_level – either ‘minimum’ or ‘overflow’
 Returns
a list of arrays

cast_to_dtype
(array, dtype)[source]¶ Cast the given numpy array to the given dtype and returns the result. If the input array dtype is already equal to the given dtype, the input array is returned.
 Parameters
array – a numpy array
dtype – a numpy dtype
 Returns
a numpy array

get_include
()[source]¶ Return the path to higra include files. To be used for c++ extension writing.
 Returns
Arrays¶
Important
#include "higra/structure/array.hpp
The preferred way to represent homogeneous tabular data in higra is through the use of xtensor multidimentional arrays. Xtensor aims at providing numpy like arrays in C++: take a look at the numpy>xtensor cheat sheet .
Higra defines some commodity types (aliases) that map to particular xtensor types. There are 3 categories of types:
points, ie. 1 dimensional arrays of fixed size: they do not require heap allocated memory and benefit from a lot of compile time optimization;
fixed dimension arrays of variable size: they require heap allocated memory but, thanks to their fixed dimension, they also benefit from compile time optimization;
variable dimension arrays of variable size: they require heap allocated memory.
Therefore, using the most specific type compatible with your needs will provide better performances.
Typename 
Template 
Description 
Base type 



An n dimensional point 


A two dimentional point with real coordinates ( 



A two dimentional point with integral coordinates ( 



A three dimentional point with real coordinates ( 



A three dimentional point with integral coordinates ( 



A four dimentional point with real coordinates ( 



A four dimentional point with integral coordinates ( 




A one dimentional array 



A two dimentional array 



A three dimentional array 



A four dimentional array 



A ndimentional array (n being defined at runtime) 

Quick start¶
Creating arrays¶
From scratch:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  // explicit initialization
array_2d<int> a1 {{1, 2, 3},
{4, 5, 6}};
// empty (non initialized) array of given shape
array_2d<int> a2 = array_1d<int>::from_shape({2, 3});
// array of given shapes initialized with given value
array_2d<int> a3({2, 3}, 5);
// array of given shapes initialized with 0
array_2d<int> a4 = xt::zeros<int>({2, 3});
// array of given shapes initialized with 1
array_2d<int> a5 = xt::ones<int>({2, 3});

From an existing array:
1 2 3 4 5 6 7 8 9 10 11 12 13 14  array_2d<int> a1 {{1, 2, 3},
{4, 5, 6}};
// same shape and value type, noninitialized
auto a2 = xt::empty_like(a1);
// same shape and value type, initialized to 0
auto a3 = xt::zeros_like(a1);
// same shape and value type, initialized to 1
auto a4 = xt::ones_like(a1);
// same shape and value type, initialized to given value
auto a5 = xt::full_like(a1, 5);

Properties¶
1 2 3 4 5 6 7 8 9 10 11 12 13  array_2d<int> a1 {{1, 2, 3},
{4, 5, 6}};
// dimension
auto d = a1.dimension(); // 2
// size
auto s = a1.size(); // 6
// shape
auto sh = a1.shape();
sh[0]; // 2
sh[1]; // 3

Element access¶
1 2 3 4 5 6 7 8 9 10  array_2d<int> a1 {{1, 2, 3},
{4, 5, 6}};
// modify and read element at line 1, column 2
a1(1, 2) = 7;
int v = a1(1, 2);
// Same thing with the [] operator
a1[{1, 2}] = 7;
int v = a1[{1, 2}];

Display¶
1 2 3 4 5 6 7 8  #include <iostream>
#include <xtensor/xio.hpp>
using namespace std;
array_2d<int> a1 {{1, 2, 3},
{4, 5, 6}};
cout << a1 << "\n";

Lazy Evaluation¶
Most xtensor operations are lazily evaluated. In the following situation:
1 2 3 4  array_1d<int> a1{1, 2, 3};
array_1d<int> a2{4, 5, 6};
auto r = a2 * (a1 + a2);

r does only store the expression, i.e. the symbolic operation, but no actual results. The result will be computed when elements are accessed:
1  auto v = r(1); // performs 5 * (2 + 5)

If an expression is evaluated several times at the same position, the same result will be computed several times.
An expression can be fully evaluated by assigning it to an actual array or by using the eval function:
1 2  array_1d<int> ar1 = r; // evaluates the expression r and assigns the result to ar1
auto ar2 = xt::eval(r); // evaluates r and assigns it to an array called ar2

Attention
Returning a non evaluated expression that refers to local variable will lead to undefined behaviors:
1 2 3 4 5 6  auto function(){
array_1d<int> a1{1, 2, 3};
array_1d<int> a2{4, 5, 6};
//return a1 + a2; => ERROR depends of local variables that are destructed at the end of the function
return xt::eval(a1 + a2); // OK
}

Namespace hg¶
Warning
The cpp documentation is in progress, so here is a raw dump of the whole hg
namespace: enjoy!

enum
hg
::
accumulators
¶ Values:

enumerator
first
¶

enumerator
last
¶

enumerator
mean
¶

enumerator
min
¶

enumerator
max
¶

enumerator
counter
¶

enumerator
sum
¶

enumerator
prod
¶

enumerator
argmin
¶

enumerator
argmax
¶

enumerator

enum
hg
::
weight_functions
¶ Predefined edgeweighting functions (see weight_graph function)
Values:

enumerator
mean
¶

enumerator
min
¶

enumerator
max
¶

enumerator
L0
¶

enumerator
L1
¶

enumerator
L2
¶

enumerator
L_infinity
¶

enumerator
L2_squared
¶

enumerator
source
¶

enumerator
target
¶

enumerator

enum
hg
::
tos_padding
¶ Padding mode for the function component_tree_tree_of_shapes.
Values:

enumerator
none
¶

enumerator
mean
¶

enumerator
mean

enumerator
mean

enumerator
zero
¶

enumerator

enum
hg
::
leaves_it
¶ Enum used in tree node iterator (leaves_to_root_iterator and root_to_leaves_iterator) to include or exclude leaves from the iterator.
Values:

enumerator
include
¶

enumerator
exclude
¶

enumerator

enum
hg
::
root_it
¶ Enum used in tree node iterator (leaves_to_root_iterator and root_to_leaves_iterator) to include or exclude the root from the iterator.
Values:

enumerator
include
¶

enumerator
exclude
¶

enumerator

using
hg
::
contour_2d
= contour_2d_internal::contour_2d<point_2d_f>¶

using
hg
::
polyline_contour_2d
= contour_2d_internal::polyline_contour_2d<point_2d_f>¶

using
hg
::
contour_segment_2d
= contour_2d_internal::contour_segment_2d<point_2d_f>¶

using
hg
::
array_1d
= xt::xtensor<value_t, 1>¶

using
hg
::
array_2d
= xt::xtensor<value_t, 2>¶

using
hg
::
array_3d
= xt::xtensor<value_t, 3>¶

using
hg
::
array_4d
= xt::xtensor<value_t, 4>¶

using
hg
::
array_nd
= xt::xarray<value_t>¶

using
hg
::
fibonacci_heap
= fibonacci_heap_internal::fibonacci_heap<value_type>¶

using
hg
::
lca_sparse_table_block
= lca_internal::lca_rmq<tree, range_minimum_query_internal::rmq_sparse_table_block<index_t>>¶

using
hg
::
lca_sparse_table
= lca_internal::lca_rmq<tree, range_minimum_query_internal::rmq_sparse_table<index_t>>¶

using
hg
::
lca_fast
= lca_sparse_table_block¶

using
hg
::
point
= xt::xtensor_fixed<value_t, xt::xshape<dim>>¶

using
hg
::
regular_graph
= regular_graph_internal::regular_graph<embedding_t>¶

using
hg
::
regular_grid_graph_1d
= regular_graph<hg::embedding_grid_1d>¶

using
hg
::
regular_grid_graph_2d
= regular_graph<hg::embedding_grid_2d>¶

using
hg
::
regular_grid_graph_3d
= regular_graph<hg::embedding_grid_3d>¶

using
hg
::
regular_grid_graph_4d
= regular_graph<hg::embedding_grid_4d>¶

using
hg
::
regular_graph_out_edge_iterator
= typename regular_graph_internal::regular_graph<embedding_t>::out_edge_iterator¶

using
hg
::
regular_graph_adjacent_vertex_iterator
= typename regular_graph_internal::regular_graph<embedding_t>::adjacency_iterator¶

using
hg
::
tree
= tree_internal::tree¶

using
hg
::
vecS
= undirected_graph_internal::vecS¶

using
hg
::
hash_setS
= undirected_graph_internal::hash_setS¶

using
hg
::
undirected_graph
= undirected_graph_internal::undirected_graph<storage_type>¶

using
hg
::
ugraph
= undirected_graph_internal::undirected_graph<>¶

using
hg
::
union_find
= union_find_internal::union_find<>¶

using
hg
::
index_t
= int64_t¶ Preferred type to represent an index.

using
hg
::
size_t
= std::size_t¶ Preferred type to represent a size.

using
hg
::
stackv
= std::stack<T, std::vector<T>>¶

const index_t
hg
::
invalid_index
= 1¶ Constant used to represent an invalid index (eg.
not initialized)

template<typename
T
, typenameaccumulator_t
, typenameoutput_t
= typename T::value_type>
autohg
::
accumulate_at
(const array_1d<index_t> &indices, const xt::xexpression<T> &xweights, const accumulator_t &accumulator)¶ )
 Template Parameters
T –
accumulator_t –
output_t –
 Parameters
indices – a 1d array of indices (entry equals to :math:
1
are ignored)xweights – a ndarray of shape :math:
(s_1, \ldots, s_n)
such that :math:s_1=indices.size()
accumulator –
 Returns
a ndarray of size :math:
(M, s_2, \ldots, s_n)

template<typename
graph_t
, typenameT
, typenameaccumulator_t
, typenameoutput_t
= typename T::value_type>
autohg
::
accumulate_graph_edges
(const graph_t &graph, const xt::xexpression<T> &xedge_weights, const accumulator_t &accumulator)¶

template<typename
graph_t
, typenameT
, typenameaccumulator_t
, typenameoutput_t
= typename T::value_type>
autohg
::
accumulate_graph_vertices
(const graph_t &graph, const xt::xexpression<T> &xvertex_weights, const accumulator_t &accumulator)¶

template<typename
tree_t
, typenameT
, typenameaccumulator_t
, typenameoutput_t
= typename T::value_type>
autohg
::
accumulate_parallel
(const tree_t &tree, const xt::xexpression<T> &xinput, const accumulator_t &accumulator)¶

template<typename
tree_t
, typenameT
, typenameaccumulator_t
, typenameoutput_t
= typename T::value_type>
autohg
::
accumulate_sequential
(const tree_t &tree, const xt::xexpression<T> &xvertex_data, const accumulator_t &accumulator)¶