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.7, 3.8, 3.9, 3.10
• Linux 64 bits, macOS, Windows 64 bits (requires Visual C++ Redistributable for Visual Studio 2015)

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

Bibtex

@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",
 }

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