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.7, 3.8, 3.9, 3.10, 3.11 (amd64)
- 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.6-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3222d0c713d93ae13adb28c48263d59fc6f7d2cbb966d7a63aac30e53b3b8b04 |
|
MD5 | ab5d70cc173d6a99fce8980119e4faf7 |
|
BLAKE2b-256 | 020b482f2ddd364aaa5692adbda38bbd390188fcd688dfc738d7ad628015dbaf |
Hashes for higra-0.6.6-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6b892fcf04d6e8204f6bb79e620097ab2c528e632e383b09adc8a383d91bc117 |
|
MD5 | 593197cc4fb508f3cfffc958e41cc759 |
|
BLAKE2b-256 | 0278bb1bfc9cc1c66b5961b3b1413e0fda65bad0421c89bf0341629ae9ffaa40 |
Hashes for higra-0.6.6-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e09038ff7b3fba8fa49948c7246e696f4c82e071dcedc3c704dad19d0b7b9b75 |
|
MD5 | 466355f17a81533d0599bfc16b545824 |
|
BLAKE2b-256 | d2dc5263390ac80f5751b8786f74a80c111468c66087eeaaf7cd4231489c248f |
Hashes for higra-0.6.6-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b408bce14fc6682da3a97d02a2ca85b656e528bff913cbee0dee57e036cf8442 |
|
MD5 | 0b640e87c6b1da48829b939c0ad26af8 |
|
BLAKE2b-256 | 3210c8699a6cb78b6221375ee958aa82d8f24cab923dff8622349b7f4d7e8c65 |
Hashes for higra-0.6.6-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 43f29e2087e5d0bd7d446280b5f49b50d079da02595c86421afc25f8f6e9767e |
|
MD5 | ad95e8fdc2ca6d1a8ace5e6e7738a592 |
|
BLAKE2b-256 | 34be7eb424e803571616f5ccaa5fdc396ba18f4be66f35f3b39be7d39da32f5d |
Hashes for higra-0.6.6-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9e505c8e9dc89d4ef25ef548e2addeee19dcc9ea76a312a635ac8717d72e1d7f |
|
MD5 | 9f2a4bdff3d7b0feab5127bf4f48dc8a |
|
BLAKE2b-256 | 8857154237e95851cb67247878545654db27a8c45b6af553067bb0806bbe6a80 |
Hashes for higra-0.6.6-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ae09f941dbedbf365ee29f486c6fceab01f603431aa6c5802c23ace5b7659c72 |
|
MD5 | 633b083c9c9927c87341b7cd73621783 |
|
BLAKE2b-256 | 5c1847d7887393a7ca60cf7f58b18f7ec23e8800a98cf8cd339b8126acc6f1f2 |
Hashes for higra-0.6.6-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 785ac84d70550c44217824169f15c0211feacb0c9929c73b370c78712e73473d |
|
MD5 | 8dca4a25f82f5e6eab3bd09fc63a0eaa |
|
BLAKE2b-256 | 9ccc3b9f6016754bbc2176a6b278162a73a79189a33c806f7f28fa81ae54b4de |
Hashes for higra-0.6.6-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e68922a576b261899e2ecd4d0b1c818ab65b39f34205eda1038eab0769d4561f |
|
MD5 | f09a2cb1751baade010ea25a1b5af5c1 |
|
BLAKE2b-256 | 77a7833fb8d55f8faf1adea5011e0ae528dae160eb3d72f4ed2366c6d5688058 |
Hashes for higra-0.6.6-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a77b5bd8c21743b3facff7a1455a31c1289da185e82a2a4dc06a5a30ca66c528 |
|
MD5 | 936429e46287feb79978240cab5798f8 |
|
BLAKE2b-256 | e52b138b11c31eaf4c0316d21020e9f74eb376bf9761e10cc151e8ee47749c12 |
Hashes for higra-0.6.6-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8b916f90dc7b4d53f8395b6512128664d771342cd6acafcff32303b511977152 |
|
MD5 | 4cfe91d1e158e10a67f1a1252a8bc5aa |
|
BLAKE2b-256 | a96137a9aa39294b273d1eddc3850f1557207b1232b7f0083ea62f0b3f40e9c4 |
Hashes for higra-0.6.6-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a95b37141963da876f833e449053a3d7c5646b26dbebb5dfb3a309582be426d5 |
|
MD5 | 8065d22719902035f7691531dfaef7be |
|
BLAKE2b-256 | 7376fec085009cb2c90293513c06c489f0ef979a0534eb54f6c7a397f5c27429 |
Hashes for higra-0.6.6-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 882a1794b18ebb58e1c4cda13e4d0532ba3dce299f21712f23f916ab5091da5d |
|
MD5 | fe1a26f5ef3e9410c4f56519c4bf8901 |
|
BLAKE2b-256 | 5736c17e150e570a77b137eba8077fb7bdc85fff98215f761940787eed0b5989 |
Hashes for higra-0.6.6-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4283ece4bdecc49e6f8057dbd905064bf844ccf958a1b70412614e2a4cf84668 |
|
MD5 | 05d884a2a104e7909f3efcc2549acdc6 |
|
BLAKE2b-256 | 4a0449a624014fd220e3e26bbc2b1f9b73b500587f17eecbc27b48d116a140bf |
Hashes for higra-0.6.6-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | afe026609230a979c0cf2ab79054f3b4f20c3ac966242a73a91b3ae3bd09a1bd |
|
MD5 | d7ebc5ee4cd23eab60a33c8f45a1e86b |
|
BLAKE2b-256 | 566fec8848ddb5b347b4d9f5d55440f25fa2d834d9e9eb86b57b3e192f482937 |