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.6.0-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 80887bee6af9904cf18b37bd9140b2704450edd5c42e5a03a9a0b05f6a8f3629 |
|
MD5 | 2bf5111a8a6cabe6344dc0e7ac184545 |
|
BLAKE2b-256 | 0e0e81d4ec2457bf301656327d87f1f81648fc394cc4eb049bf812cff0acd734 |
Hashes for higra-0.6.0-cp38-cp38-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 51726c5e0c066fb636019c93b443cf4699d9e30adb62c9cb04bf9feca19a0463 |
|
MD5 | 637244a43c167f96e9ba5a2c432b488d |
|
BLAKE2b-256 | a654212d23a43e7df61f34e179ddecde23fd8e60a594a5a83970f0af432f268e |
Hashes for higra-0.6.0-cp38-cp38-macosx_10_13_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 984c396b09a106b14464f0e85b60f37bd2020a6b6aa7b5bf0ffd728689520d79 |
|
MD5 | 49e0f8b7b29211eaa65cb6422bf68ac0 |
|
BLAKE2b-256 | 8a16ed76e2be1f96a99546d59670e1d021236d683ea797fd572b50dd34e4c81a |
Hashes for higra-0.6.0-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0d415f3a4be0685edb19896a8f647d350b55aa6406a96c2f982d2ae692532c45 |
|
MD5 | 6f80c9a2f6f9d0a4a4670af944a9a760 |
|
BLAKE2b-256 | f7b4c16ba864338cda9ea1d5ebcfbfbb350daf9e49b7f2914dcf5989394872f8 |
Hashes for higra-0.6.0-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dddb80f411e4173beeac523b070a4c0f535ed064cd285e4ddf4ada6bff261f83 |
|
MD5 | 1a875d86651b91af110c706936ca2e9a |
|
BLAKE2b-256 | 34db8a7fb2eb0f51182e43dbec00948f2cf8d218ceeb4378f419d3a72a7023b4 |
Hashes for higra-0.6.0-cp37-cp37m-macosx_10_13_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 523d6dba961e4500d0303955fd66b0c943ffbed73cb469144f571c143fc1f6ef |
|
MD5 | d138286c2e77c1f92e0daacd10a118fb |
|
BLAKE2b-256 | 3a6799d07a475a7e6e664820c95fb96615410ed3b9595b7e09b50be51ad3c804 |
Hashes for higra-0.6.0-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 36b7295c782ca0f9b6b2ef1da951c31be8be65adf9d56f58c046032061062962 |
|
MD5 | a4b925a265a43c61eb974a6054db46e1 |
|
BLAKE2b-256 | ada17ffeb425e0a334ad4c6d72d2553329b036bac74067d7dcd904031a2144bc |
Hashes for higra-0.6.0-cp36-cp36m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4f9bbe8b5fffafdbf118f37758cb8c0a20bc58ba30a8a548fd0524f1f4b96d13 |
|
MD5 | 572839a1f348c10cbb5081a276f96b96 |
|
BLAKE2b-256 | 9f833e9cf25c40d6803897e7e0722f3bf73986e7e30a0aa1a4fe84d56b3ec5c3 |
Hashes for higra-0.6.0-cp36-cp36m-macosx_10_13_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8dd84e64d49d7d047b2155763f6da450f378699afbb1298ec40733a811d98aec |
|
MD5 | 27e6e435aeb29300f2ddb5a90b61fd09 |
|
BLAKE2b-256 | 6f22280d3e88dc38ab929df4013f84be1f93b8115b74f58bd4c7753599a58296 |
Hashes for higra-0.6.0-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3096e4b196e1079e55e12794d058543afbaa5ed23f36d39d981101e89e8ed85e |
|
MD5 | 1c9dfecf126e7471efeccf7891de5624 |
|
BLAKE2b-256 | 14a273dc92b2f7a1332fb74001fd90872a5294c5d5fddc806a9bcb8a34bb3f5a |
Hashes for higra-0.6.0-cp35-cp35m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 046be74386f70aa0867ddfe79bf0a3debb56a6b8490f5b1c168b3944d3e008f8 |
|
MD5 | 9d2f7f6286434471a1f667372e810db7 |
|
BLAKE2b-256 | a79a151647298347d84f99a8d84727fda974a6ba1d738f8b27760994b27343a5 |
Hashes for higra-0.6.0-cp35-cp35m-macosx_10_13_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3a0374126ac266ec9215e81c403e861f322839bbbc7050d78ce3ba148755593a |
|
MD5 | 99f76090a1f0be44b7ef5fd27aaf59b3 |
|
BLAKE2b-256 | 282891841c8c9b81fe9443814746fff2105be4b23ee5baf912f7acd7fdbf24b3 |