Metadata-Version: 2.1
Name: higra
Version: 0.6.11
Summary: Hierarchical Graph Analysis
Home-page: https://github.com/higra/Higra
Author: Benjamin Perret
Author-email: benjamin.perret@esiee.fr
License: CeCILL-B
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=1.26.0



# Higra: Hierarchical Graph Analysis

[![Build Status](https://perretb.visualstudio.com/AzurePipelines/_apis/build/status/higra.Higra?branchName=master)](https://perretb.visualstudio.com/AzurePipelines/_build/latest?definitionId=2&branchName=master)
[![Build status](https://ci.appveyor.com/api/projects/status/oo0v2uepcxihvwno?svg=true)](https://ci.appveyor.com/project/PerretB/higra-21ed3)
[![codecov](https://codecov.io/gh/higra/Higra/branch/master/graph/badge.svg)](https://codecov.io/gh/higra/Higra)
[![Documentation Status](https://readthedocs.org/projects/higra/badge/?version=latest)](https://higra.readthedocs.io/en/stable/?badge=stable)

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](https://github.com/QuantStack/xtensor) arrays in C++ and [numpy](https://github.com/numpy/numpy) arrays in Python).

## Installation

The Python package can be installed with Pypi:

```bash
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](https://support.microsoft.com/en-us/help/2977003/the-latest-supported-visual-c-downloads))

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

## Documentation

[https://higra.readthedocs.io/](https://higra.readthedocs.io/)

### Demonstration and tutorials

A collection of demonstration notebooks is available in the [documentation](https://higra.readthedocs.io/en/stable/notebooks.html). 
Notebooks are stored in a dedicated repository [Higra-Notebooks](https://github.com/higra/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](doc/source/fig/example_graph_filtering.png)](https://github.com/higra/Higra-Notebooks/blob/master/Illustrations%20of%20SoftwareX%202019%20article.ipynb)

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

[![Example on image filtering](doc/source/fig/example_image_filtering.png)](https://github.com/higra/Higra-Notebooks/blob/master/Illustrations%20of%20SoftwareX%202019%20article.ipynb)

## 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](https://github.com/higra/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](http://www.cecill.info/licences/Licence_CeCILL-B_V1-en.txt) 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](http://www.sciencedirect.com/science/article/pii/S235271101930247X), SoftwareX, Volume 10, 2019. DOI: 10.1016/j.softx.2019.100335

<details> 
 <summary><b>Bibtex</b></summary>
 
    @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",
     }
        
</details>


 
## Third-party libraries

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

- [pybind11](https://github.com/pybind/pybind11) helps to create Python bindings of c++ methods and classes - [BSD-style license](https://github.com/pybind/pybind11/blob/master/LICENSE)
- [xtensor](https://github.com/QuantStack/xtensor) (with [xtl](https://github.com/QuantStack/xtl), [xsimd](https://github.com/QuantStack/xsimd), and [xtensor-python](https://github.com/QuantStack/xtensor-python) provides `numpy` like arrays for c++ with seamless integration with Python - all under the [BSD-3-Clause license](https://github.com/QuantStack/xtensor/blob/master/LICENSE)
- [Catch2](https://github.com/catchorg/Catch2) is a unit test framework - [Boost Software License 1.0](https://github.com/catchorg/Catch2/blob/master/LICENSE.txt)


