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
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.0-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 14888e3f6c3f3c6714440fb60fdab5e8c462e210a13632d8bc24774c05c09026 |
|
MD5 | 1a68fc106c77973664aefd4ea63f5241 |
|
BLAKE2b-256 | b2139d8b4a403b10edb75ce3adbe08bc5c4e5b8100ccaef978cf1cc1dc4e6758 |
Hashes for higra-0.5.0-cp38-cp38-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 77e6ef67a979869153c60d74587cf18fb9c1cb5f86af0cd07de17501e1a106e0 |
|
MD5 | 1e5ac2747b7cc0a9cfef5242662cf0b2 |
|
BLAKE2b-256 | 10af09616bb05be30b837ec05d36b52ad62589fb04f9d5c57efacd15d3a5b81c |
Hashes for higra-0.5.0-cp38-cp38-macosx_10_13_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f64e659c2f6babd5bd1b4b7be44e96cd02a42425bb19cbea7a178411824a0a01 |
|
MD5 | 654f10a4e7350ba32d231e46a9847ab3 |
|
BLAKE2b-256 | 841bab6bc5932831225adc95575f2087eefbb16c6343e989a940e51d4ad7756c |
Hashes for higra-0.5.0-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a2cf06bce158f27ac380770267f148d1374e743ee9caa0a839c5b5d05a76c703 |
|
MD5 | e402204a05a8a76e518067ad25a61030 |
|
BLAKE2b-256 | 94731fd7f77afb05ec27bac7db76a7313480ff8490d372b5f329dff2b9aa7ed5 |
Hashes for higra-0.5.0-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1f8fe7eef62631ab86a96529daf2490aa81a067ac0e31bfaeddc989cf3584f6a |
|
MD5 | 1d92e94f06c5be36b0258a58bd796552 |
|
BLAKE2b-256 | 61169f0e7cf16fae7d8570aabe743a0a7f0e9ec3e6493cc04987680bd62176e1 |
Hashes for higra-0.5.0-cp37-cp37m-macosx_10_13_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 11ee0d31db94dfe08d1f9a5ebe207e245268e0009625648631df374ae50f7c2a |
|
MD5 | 4a040a14e9c8b737b15c11bad3c46401 |
|
BLAKE2b-256 | 692677396a90cb6442bba0d2493dbf18f5868645fc4b3e4bcfcc8dee424b5cec |
Hashes for higra-0.5.0-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b39183b40ed9924fa0d4b8a0c3b4ad36bd42cc3f6b47d1bbb262afbcfbbd0dc7 |
|
MD5 | 0e6fb8097c956ee9e7a0daaa829ff3b9 |
|
BLAKE2b-256 | 77e36252ebfbfde6a9e2fb679e0fdd831248c964ea62bfd5de56d2246f938f7a |
Hashes for higra-0.5.0-cp36-cp36m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2bff9192dcae9f6c494e02c0199b6cee3b7662fa082dcfb3a55cf92eef0d46ac |
|
MD5 | d15a455b3f8b04b8802386bba648d240 |
|
BLAKE2b-256 | 4851cf8d984b813de8ca6545d235f7916b9be2ec8ba456bde00189c3284374d4 |
Hashes for higra-0.5.0-cp36-cp36m-macosx_10_13_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 119101ca7e75e2e912055f3a050233402dd29daff80dee5c51c8cb9d530ecb38 |
|
MD5 | 778158823bfb8a730326739c1d7ae4a6 |
|
BLAKE2b-256 | bf2cb23d72cc9cad2804a989a7f87f4f4de84ce83ea4addc9d67583d23f357b2 |
Hashes for higra-0.5.0-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 12904f8482ba35c5eac4f44febb4cd0fbeb0a378214bd230a7becaa739bb4883 |
|
MD5 | 730478c39585920e6343b005db09cd5b |
|
BLAKE2b-256 | 871d9893b819fdb8997c8f9f07598185c3fe0a7729f4f17d45fa7c587881fb4b |
Hashes for higra-0.5.0-cp35-cp35m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6d87ba240627763027e994cee78be36fb98fa115e1e552dc8c7fb14b6bac6f54 |
|
MD5 | fa5cdc7a8cc196f1f306a503af107ff5 |
|
BLAKE2b-256 | 39a75cbed1828f81c9793b776ffadc60afba3fbaae42f43af7041c5c78752c40 |
Hashes for higra-0.5.0-cp35-cp35m-macosx_10_13_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6c31bc5332ad97a20737f5043d5539556a1826160f1dfeb395cae69e1c813064 |
|
MD5 | e02df4b0e0e6eef0c18d3c9b7d3f37ec |
|
BLAKE2b-256 | 962b1b3b5cba168ea5949af81e2e5e63dd04cd1909b3c15b454b1fff3239fcb9 |