Higra: Hierarchical Graph Analysis

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).

Installation

The Python package can be installed with Pypi:

pip install higra

Supported systems:

• Python 3.8, 3.9, 3.10, 3.11, 3.12 (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

Documentation

https://higra.readthedocs.io/

Demonstration and tutorials

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

Code samples

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.

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

License and how-to cite

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

Third-party libraries

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