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.1-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9fbb57d950fb9ba37367a7251956400f8ec0b63ce29a03f32610238c1106ff24 |
|
MD5 | 6a8caa5e01cb47155023fdb03dfd4071 |
|
BLAKE2b-256 | 4280352d99ce49fe2e68aa1a260ad47528b4d92230f67f05f825a3c5227b8489 |
Hashes for higra-0.6.1-cp38-cp38-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0a6ee776a1ed2fd483b09f205c023d79f014d358a7836bb485003d07f8c22659 |
|
MD5 | 1d4fa8ab379ea8136996bd5d76e7d806 |
|
BLAKE2b-256 | 81793a6c98a460eafd35ef0b96aaeca4415848f99964b44c3dcd46952d1897c0 |
Hashes for higra-0.6.1-cp38-cp38-macosx_10_13_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2d54b423f1294c00c9094fa6e0b13ee3af28a9e4ee39e73686955fbcda09fbca |
|
MD5 | 8cf82f77e36fa4b8d510b3241c01932e |
|
BLAKE2b-256 | 6fb8689fd22432d809b2582e193362c775662f330fb4ac4a09aecd86a2e0d313 |
Hashes for higra-0.6.1-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6853d10f31c239bdc66bf2eb99f1dd12eebb73204374beb7e7ab888aba99083a |
|
MD5 | 967f68feb6ad8e7a0d42dee137eeaabe |
|
BLAKE2b-256 | 18f98e682807179d90855ff00df94068e8557cc8f961de67be51d3b78d0f9511 |
Hashes for higra-0.6.1-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5c96533886fb044aa2a6460da0f9b60e3ab82c56fbe558555dbb6475e80cec2a |
|
MD5 | bd8c790692b5fd8f31f1037b94362a5b |
|
BLAKE2b-256 | 9014855da71882c8217c186a961f75e5a55cbe5cfd740be125b2744db8e5fdd1 |
Hashes for higra-0.6.1-cp37-cp37m-macosx_10_13_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d9c68223469ca20b7d901b71957324a828f931acc67f68acfc2a679735d6de00 |
|
MD5 | a56e54eb5f3fc570aa79ca8e5ae0b370 |
|
BLAKE2b-256 | 8c89a670c3c6dbf87bba0f7093b1ded7e0b92c3ba0df41cc286c161886f2e0b9 |
Hashes for higra-0.6.1-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7cc149ef8be7a8b76a7db35b84f8deac0cb22685e09ed3dd548587ea78a2897c |
|
MD5 | f039d5cf6ca41cd99b97577bb68cbfa1 |
|
BLAKE2b-256 | a0dccd47a00de3faf9cf454e7bd279c0d2ce7e3888caf514e7df68e65ec3a751 |
Hashes for higra-0.6.1-cp36-cp36m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7d1ecd94716ee6fd56699c193122ee9b016ee830cc7cc869b7e2be2b8f08b892 |
|
MD5 | 27e6f8f4c4335c7c2f655cc607986a8a |
|
BLAKE2b-256 | c24220967c4a19870597305fc7ec34cb9a0c39b6eb4d062acd58fc976b6399a6 |
Hashes for higra-0.6.1-cp36-cp36m-macosx_10_13_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d5d0703c7f9ac9caea905d682fe11109eb1af1e38eb430efeb7b8e54364c2991 |
|
MD5 | de8314819b2c5e50d487eae3f50cdf6e |
|
BLAKE2b-256 | 84490c33cfe6faa953d6144ac3e94f302b18a6ba36a0f60edf0bc981b0058cc6 |
Hashes for higra-0.6.1-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 97616f77fc78a5c2d77c2fc828732bc8289b7683cf4e2bee26560e0997019fb5 |
|
MD5 | f7728cc27d7f15a8ec0022409d3b895f |
|
BLAKE2b-256 | 2b8bf6fcc1cedd00a2cfb4576d9c9c26c5ecd53ee34a0279720f8ce9fa3f5bfe |