Hierarchical Graph Analysis
Project description
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.5, 3.6, 3.7, 3.8
- Linux 64 bits, macOS, Windows 64 bits (requires Visual C++ Redistributable for Visual Studio 2015)
Documentation
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
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distributions
Built Distributions
Hashes for higra-0.5.3-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1815207875065c19749374a2a193da29c672d1bf678a77afd941ac0e21a39055 |
|
MD5 | 1066381897f3c0eb7501eb9219fccbde |
|
BLAKE2b-256 | 630f87bbf1f9acf8c06458af365a8ab4266ec1f8a5f7108e5b2acd40e02419bf |
Hashes for higra-0.5.3-cp38-cp38-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5c7c06ca6ae92e483b7003d2e9a887846c9b452814f161b8799e1092d053be95 |
|
MD5 | f96a176087c95f36b30f59ee7316448f |
|
BLAKE2b-256 | 409250d7a69b0e434c41ffa817cd7637864f156cb7cd8bdcf5a4ac120ee9c2a7 |
Hashes for higra-0.5.3-cp38-cp38-macosx_10_13_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9bcdca0ad7cd7d420d3975a263879c408cc1fb4d5569decffd5c2d264e2b60dd |
|
MD5 | 1754e989eee01f3b1670e20496d77ef0 |
|
BLAKE2b-256 | 7a1efd7927c1e66750268b2b0309747e9b7518f7def78b6b699626dd6828ab75 |
Hashes for higra-0.5.3-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6aebd72c5310746ca5823efe63ddfa4ebe49cb17f749b3bafd2a42b1977550cd |
|
MD5 | 9ccd7794a2a6e5f3878dafc25a0e2865 |
|
BLAKE2b-256 | 65aaa90e7ab50e629aa4314b38e61b0ee5fc7fa8a58e9ae0b755b8cb09d2b690 |
Hashes for higra-0.5.3-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7b5431150751c9781b5cef1c17902d153715e844ae276c60e9361e6258762988 |
|
MD5 | 81b3b42277f8efce0abce5cbf5a33fa5 |
|
BLAKE2b-256 | 3fbf39debb069e4756064608c2d3836a1491e137b59b7fcd1dec899110b011d4 |
Hashes for higra-0.5.3-cp37-cp37m-macosx_10_13_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e9e1e9ee40a9b5232d162912732a8ddf8a590c4ba2885745809bd4b6ea6d8901 |
|
MD5 | 5d47ce8490bd52ec55bed8e96e9404d7 |
|
BLAKE2b-256 | df680da46abc81c53620471deb1f3daee6459c299c4be18ac5aa470081cea411 |
Hashes for higra-0.5.3-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 32d8b35d633f728b89ad4304a255ca1b00d589b4fdefad6755377c745dfaa84b |
|
MD5 | 4d84d4dd44f3cab439cb43e4059ca3c1 |
|
BLAKE2b-256 | 924b6866e9938623fd767566550a03f6a3526166ad5ca091ed6683e927abdfeb |
Hashes for higra-0.5.3-cp36-cp36m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d01b7957fe8867d2ff5be855c6f03047e124fd8ff203eb092d644219ab2571c4 |
|
MD5 | af4527f7322463d860c1c14294afc168 |
|
BLAKE2b-256 | 39c2d962550e67c95d99582953fe69a9acfc0fcae664f3b6cef6741bbf64964f |
Hashes for higra-0.5.3-cp36-cp36m-macosx_10_13_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cd5692a4265c1c85dfc54528a0aff20d299cd4d4d8bb9a97264198775a5d4786 |
|
MD5 | 2f520da704e1df0986fe9b67adb3dd27 |
|
BLAKE2b-256 | 21a278072dcc23810a13bd27dd5c835cf3566fb528519f8561928018058acc5e |
Hashes for higra-0.5.3-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 72e20b3d964cecfa6e9d86d96fa9cc95aec01ef288c312dadd29a9431f5cce6b |
|
MD5 | bde3164d55ac66e39cd4653797ee148e |
|
BLAKE2b-256 | 36c86298f14a73481a1304ef0c56beb3a92920db99d68c9ef03b496fa302d21c |
Hashes for higra-0.5.3-cp35-cp35m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ee9296664b809e75d82d8d4e376ec1cf3d8a08def23ba2333c28eebdf1fd3d7a |
|
MD5 | ff68f9cc5e81555d844bd032bfbbf7de |
|
BLAKE2b-256 | e25b04a9ad95a7b8496e0d0e9638e4bb5940d668a2f3e16c6afac6ff5e5e356a |
Hashes for higra-0.5.3-cp35-cp35m-macosx_10_13_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bd0d02d8cdb19f8afb67524d59b86cc21d19829571b7cce475e2f72e399116f8 |
|
MD5 | a0aa60e569c5515b00db14862c676d42 |
|
BLAKE2b-256 | bff95f105bcce5b050f12be65f50e817a08f58552d1ec3540bde55f00c644546 |