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.4, 3.5, 3.6, 3.7
- 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.4.4-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2aeb653fbb2ec6aa107a80295e51a192821ee3643addb32b808574550ab6ffad |
|
MD5 | a73243497cfe3768dc00160209a74b15 |
|
BLAKE2b-256 | c763aaf56fadd84c8e0a283e0ddf5f09a7bb07543904862376f4633b28b9f701 |
Hashes for higra-0.4.4-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 054c8cc511bb890b7634c68ad328b29e66f1f97b4d69c11ae464b1f80d101616 |
|
MD5 | 2ab5ac756aee29a53d274180ca1c4c0b |
|
BLAKE2b-256 | d82b52255ef05af37160f744add346363c8357f4628c9f9e5ece7712c6179891 |
Hashes for higra-0.4.4-cp37-cp37m-macosx_10_6_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 634569077b3f5cf3d76ccc3e39ba013d6f58abd5396e03a44123efdaffc3654e |
|
MD5 | b5fc908a0f35d0af89835dcb4bddcc48 |
|
BLAKE2b-256 | 3a2e15be5b85929cf1d60e085610bfbeb1a30b1b89729ee2f9860a75a4ed18d7 |
Hashes for higra-0.4.4-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 62b520d21cd3e932f24c4c4a5ae7a1301f1bd4578cbd2e15ac1010e0e903abe8 |
|
MD5 | 1929209008a29c42906cfad06932a1c0 |
|
BLAKE2b-256 | d0fa17f14d4c950205ca7b0f3f0e3bf97634c40be015293a2087ce82791e0c21 |
Hashes for higra-0.4.4-cp36-cp36m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3b7d51b915e0035233288924ce8bfc05bf39db45c33b8bdb114473059c9e5e14 |
|
MD5 | e9b0acb521428cfb8136d0b0ceb36c14 |
|
BLAKE2b-256 | 6600ee7d4b1a54eb6c77121dfb8f605ad23930085ea5177961de0eee47e5382c |
Hashes for higra-0.4.4-cp36-cp36m-macosx_10_6_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ec09d5de2b99ce438afedf59c9aa6523339ebf4ed9c674ec41836d56a1f01fe0 |
|
MD5 | d14f973119d3b997dc602af09c759401 |
|
BLAKE2b-256 | f77fee8fa20740e0d594221852740e47d44e8a5c34b98ea65df79b00d9af1fea |
Hashes for higra-0.4.4-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 99b8e7ab8bee0b76c921480b91fc63bba24e0c225197977d1c350695d371b49b |
|
MD5 | ce5e7deceb4f30779865d2b6df7f70b3 |
|
BLAKE2b-256 | 5313766e03087fd94a79fbfd6b75f8974f96ee670fab96b525db7e092e921133 |
Hashes for higra-0.4.4-cp35-cp35m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6c51ccb5b6772eebfc77c6d24a98213300629e9083781e71ad421ce2327d6861 |
|
MD5 | 36d015bc090d9008b096a9ad83a2af22 |
|
BLAKE2b-256 | 777a5348b272173e45d5e26562b35dbef3dfcf0227def1032dd1f87a61c495bd |
Hashes for higra-0.4.4-cp35-cp35m-macosx_10_6_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cbf8519238e68247acc33d0904198aacf3ba3df7342c46a720d2dd8c155a6628 |
|
MD5 | a42b1051164812074102583f6a7f2320 |
|
BLAKE2b-256 | 55c9ba9fe4e90e8cd5f80d4c715b06f3e60975f4889f0cdfc113c4565931a7ff |
Hashes for higra-0.4.4-cp34-cp34m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c755ca5f31ab680796f93c00cbb1c1eea1774fb9fe6a5698dd4219b7cb4c2483 |
|
MD5 | 71595602a1ac7a3ef5d117cb9788f647 |
|
BLAKE2b-256 | bd05b87f4f08f5f39920cc8d29c056a3506a2fda3fc965f7961072567e990a76 |
Hashes for higra-0.4.4-cp34-cp34m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5c913adf6e684347aa94e4b9b8f8c41ada0a37dfdbfa21a470eb87386c258ffe |
|
MD5 | e4cfa7d597219544f15f015137983a0b |
|
BLAKE2b-256 | e3cc06775a7ef67d02717d0e45b8ab1b5247f33a641f7b95ed0d943e08fc8fb1 |
Hashes for higra-0.4.4-cp34-cp34m-macosx_10_6_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bc1fd34343dfbcebdaae70900d3a4e7c93291191ef793f5869c9ce5b079fa520 |
|
MD5 | 56103421e6a47313b38f34da430d2eab |
|
BLAKE2b-256 | e56ab73985edf7beb2213cfc6e5b06282977606379c2e6230d18231e7c9728cd |