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.6, 3.7, 3.8, 3.9
- 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.4-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 80029a58b37dbd8337ed59094de96b69a60a25b17b71a89a70ec39ce5c4a968f |
|
MD5 | 52525673aa8ec205fa5f8a969627face |
|
BLAKE2b-256 | d7e283a4ed38a5631b6fa636b1cfe82ec83104e212338e7efb5dd4381cb1c5b6 |
Hashes for higra-0.6.4-cp39-cp39-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dcea5b1df961cd1b29e55a721fab2158b0ab641cb7253db42592ff36a6a4f62d |
|
MD5 | 3461d9dfd27848d4b63fb8a55c625488 |
|
BLAKE2b-256 | 3687d38ee6735e527917097b089f87031851cd8053e018618966a0912f6825f3 |
Hashes for higra-0.6.4-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 13f028eb8735d6ea594929ad7b35bb8a63bcc798b2f1f31408a7cd9d76c6d796 |
|
MD5 | b4ffaba4f7e02b39796fd182e41ba8d2 |
|
BLAKE2b-256 | 1efd6ec6cd94a1ee67c567fbfd45a2c96491183023e570cabf637effcc728c87 |
Hashes for higra-0.6.4-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 534409fada1edfb728fa65571e48e769eb15b857c594335bb5b6e1d28eba3346 |
|
MD5 | 1749dfcac65f249559951c0ff21f260f |
|
BLAKE2b-256 | 90dec5af45c52346e7b069d141552a75820db266b309bd3f3d739498c7220852 |
Hashes for higra-0.6.4-cp38-cp38-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7affc903714b55fac6f20ee425e9c770c39010a712da14ec59ef593a65b8cfba |
|
MD5 | 40a3bde5dded5875497849df6c75a4d6 |
|
BLAKE2b-256 | 27a703561f6c8df3bb3d2556fda7ba8cc10e70a3551c6695adf01114adfbeb66 |
Hashes for higra-0.6.4-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ae48208c66d0ab3bb6eab79e48a235a8a5af648d1be0f7bb2ac85cc0425f97ca |
|
MD5 | 39585040d9ed2fb54700c9cbd7368a18 |
|
BLAKE2b-256 | ddc30d98689b9033ba45a1a62e17d7190fe7e3e17df0c48f2db8d2dc083fbba4 |
Hashes for higra-0.6.4-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3d1b9ea510614d9e7f2a20532b532af000ffeb6bfb8611c78d4c09f612714816 |
|
MD5 | 4f7c45b9676b18fdd7a1fe806716949e |
|
BLAKE2b-256 | 0e1dd0353bee6b364d94eee3296abb36dae3e5c53a167d84dc4f544a7572edc9 |
Hashes for higra-0.6.4-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 975b3d2a81f514a193a71e4cf61dbc49e7a8515f0175fd63c50bc29789cdbf9d |
|
MD5 | 98ce7f2234b4d278528e0f8a2dc08709 |
|
BLAKE2b-256 | 1973e4f6faf16ff11bcb3ef20662d98df59786c329662a087c3293d223d1c384 |
Hashes for higra-0.6.4-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5142a29e80ffcb77e19340187001f94b1834adbc71448aa3f7f6c085f340051a |
|
MD5 | d2a6050869c4205f814b405e88d3ade9 |
|
BLAKE2b-256 | 799ce3df4903891922612be759543efc7fb673283ea5258e53cfccc25c730332 |
Hashes for higra-0.6.4-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 34b4d92552bd9487d9d2cf8401207ea6b28429f34a2871ce241a0b55c64603e2 |
|
MD5 | f6e017675e7719e343022daf45aaf953 |
|
BLAKE2b-256 | 2b2e94e04d0dcd748b8da9bd7b830834320859dee04d174e41862a00e92350b0 |
Hashes for higra-0.6.4-cp36-cp36m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 07f63b6f239c8f9f7f64d7a10bc72eeb23055b600fb72953a16009fdd5cd313e |
|
MD5 | 781891aa24d4dbc8b8831f43ac148438 |
|
BLAKE2b-256 | 947d1e1283d9caf4ce37216e0d034e66e88abc15367303bc0b0b5ebe2cedf50a |
Hashes for higra-0.6.4-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fee05b02a89ed724773f0e606a2d368884235baf8fb22b4e71fde8118d41bd75 |
|
MD5 | 9aad2f97708884ce9c322fb0ffe9c58e |
|
BLAKE2b-256 | f1418fbf6da5fac2edbed2aee6233601b35e2d11e2923cf90f7c17731f6b2ed2 |