Higra is a C++/Python library for efficient sparse graph analysis with a special focus on hierarchical methods. Some of the main features are:

• efficient methods and data structures to handle the dual representations of hierarchical clustering: trees (dendrograms) and saliency maps (ultrametric distances);
• hierarchical clusterings: quasi-flat zone hierarchy, hierarchical watersheds, agglomerative clustering (single-linkage, average-linkage, complete-linkage, exponential-linkage, Ward, or user provided linkage rule), constrained connectivity hierarchy;
• component trees: min and max trees;
• manipulate and explore hierarchies: simplification, accumulators, cluster extraction, various attributes (size, volume, dynamics, perimeter, compactness, moments, etc.), horizontal and non-horizontal cuts, hierarchies alignment;
• optimization on hierarchies: optimal cuts, energy hierarchies;
• algorithms on graphs: accumulators, vertices and clusters dissimilarities, region adjacency graphs, minimum spanning trees and forests, watershed cuts;
• assessment: supervised assessment of graph clusterings and hierarchical clusterings;
• image toolbox: special methods for grid graphs, tree of shapes, hierarchical clustering methods dedicated to image analysis, optimization of Mumford-Shah energy.

Higra is thought for modularity, performance and seamless integration with classical data analysis pipelines. The data structures (graphs and trees) are decoupled from data (vertex and edge weights ) which are simply arrays (xtensor arrays in C++ and numpy arrays in Python).

The Python package can be installed with Pypi:

pip install higra

Supported systems:

• Python 3.9, 3.10, 3.11, 3.12, 3.13 (amd64)
• Linux 64 bits, macOS, Windows 64 bits (requires Visual C++ Redistributable for Visual Studio 2015)

macOS ARM64 is currently only supported through conda conda install higra -c conda-forge

https://higra.readthedocs.io/

A collection of demonstration notebooks is available in the documentation. Notebooks are stored in a dedicated repository Higra-Notebooks.

This example demonstrates the construction of a single-linkage hierarchical clustering and its simplification by a cluster size criterion.

This example demonstrates the use of hierarchical clustering for image filtering.

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 Higra-cppextension-cookiecutter enables to easily setup and generate c++ extension using Higra with Python bindings.

The license Cecill-B is fully compatible with BSD-like licenses (BSD, X11, MIT) with an attribution requirement.

The recommended way to give attribution is by citing the following presentation article:

B. Perret, G. Chierchia, J. Cousty, S.J. F. Guimarães, Y. Kenmochi, L. Najman, Higra: Hierarchical Graph Analysis, SoftwareX, Volume 10, 2019. DOI: 10.1016/j.softx.2019.100335

@article{PCCGKN:softwarex2019,
     title = "Higra: Hierarchical Graph Analysis",
     journal = "SoftwareX",
     volume = "10",
     pages = "1--6",
     year = "2019",
     issn = "2352-7110",
     doi = "10.1016/j.softx.2019.100335",
     author = "B. Perret and G. Chierchia and J. Cousty and S.J. F. Guimar\~{a}es and Y. Kenmochi and L. Najman",
 }

Higra bundles several third-party libraries (inside the lib folder):

• pybind11 helps to create Python bindings of c++ methods and classes - BSD-style license
• xtensor (with xtl, xsimd, and xtensor-python provides numpy like arrays for c++ with seamless integration with Python - all under the BSD-3-Clause license
• Catch2 is a unit test framework - Boost Software License 1.0