Skip to content

higra/Higra

Repository files navigation

Higra: Hierarchical Graph Analysis

Build Status Build status codecov Documentation Status

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:

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.

Example on clustering

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

Example on 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):