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.1-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 81e4dc1cd42bb7255b303c85e0b21073ccbaa0783f06ddac002b468810b6c2dd |
|
MD5 | e77a384b8f085b07c149caa3124a8197 |
|
BLAKE2b-256 | 40137873d0e8a1575ddeb550448e74849d4a7cdbfc2b039148ac41c1c6be3286 |
Hashes for higra-0.5.1-cp38-cp38-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e7c12eb89dd2e7e8f17aea4727e7d4f62409df98c513b4bd91831ce8324b2459 |
|
MD5 | dfa2ae37bc15dc28175a76bb7448abb7 |
|
BLAKE2b-256 | b7ed7ea995329ff762172f0b50763b9f0671576c2c51f160180f8773629dcc30 |
Hashes for higra-0.5.1-cp38-cp38-macosx_10_13_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8a80d099fd8639738175f2510739ded8e50679a12123a64b3a648b60bbfc3ef7 |
|
MD5 | fed4a0b872d85926eb2287a445217cb0 |
|
BLAKE2b-256 | ec61faafc0ef4f68ca56551fe6e5113b55d1319a9c8bc250ecb683a1b75ec493 |
Hashes for higra-0.5.1-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8ec65ccc49beac8a8db1bd488303f70903a7303d82d0d17067ecaa2b7187ffe6 |
|
MD5 | abf76aa8f6e0bad5503dc21671fde93d |
|
BLAKE2b-256 | 72355ee20e284fec105b5b02c5a48af533704534f7c51c325d62ae554dd8db4c |
Hashes for higra-0.5.1-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 61d947855cda3f5b0ff30381bf2b3fff5ac2824694c882890ca4d8ee7a7544e5 |
|
MD5 | 258f7eff8d14435ec69c7ed62c4bd478 |
|
BLAKE2b-256 | f54328bf02a1fd802e2119fddb8392e190e37387bf982453e71881ff36db77d4 |
Hashes for higra-0.5.1-cp37-cp37m-macosx_10_13_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6dd561c2588c1f399623c218bb17d6b218a0724956bfdae61e8e8980b3c72cb5 |
|
MD5 | 8d0888dd68edc884ab0674efba266fb1 |
|
BLAKE2b-256 | f395542942fb23801a843c62b164ab0870a36ba7c8978ae38a8b2b55c65a1429 |
Hashes for higra-0.5.1-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1bb5b47e5c01d06da2137a10b770759f177a73d7c60082161f4c466567c33278 |
|
MD5 | 97f622dd5711e4e3d55b0efae776ba3c |
|
BLAKE2b-256 | fb65ca2288db7b3050e88dd29a476da9b53e5838921737c804b3a64dce215074 |
Hashes for higra-0.5.1-cp36-cp36m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 359a92faee1e877433d5cbd9ebba08c30d8820b4ddf4482ea7929437eb9e2900 |
|
MD5 | 48eb863dd8585edc16f299179e3a2a61 |
|
BLAKE2b-256 | 5422e938a122eb79a0b9e0703018daa098e3ae36d83a222d251b74d1b12b9f51 |
Hashes for higra-0.5.1-cp36-cp36m-macosx_10_13_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c2bcd795ee4947062148b7c477a47987a5fd7df767f16619e349e6361d7729a7 |
|
MD5 | b303a47efe15fb660f118510a92ef2b7 |
|
BLAKE2b-256 | fdd54800fd88bd639da7525c96e21940b38ba626f804349d0477f176b899cbff |
Hashes for higra-0.5.1-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4fee3a04f55afdab25dd9ef7756ec3c80e60ccdc941caf73396163215258692f |
|
MD5 | 11025e163eb0a793bf98d232bb5b26d4 |
|
BLAKE2b-256 | a2502e9018a0e74838af07ec7428ac7913fd9f3b246f4a280fdf8f9faa9b3ef5 |
Hashes for higra-0.5.1-cp35-cp35m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 11fd9a1bd345462e0cb18c8f952f4adb7c54a47afc2c9b5140f36e21a9dd4554 |
|
MD5 | 1f2d232a2b561ef05e4206f545e38b06 |
|
BLAKE2b-256 | bf438c62fbb2dffabfa5d23af1fce4cdc2f91675ec5c6a59c7f173fe91527094 |
Hashes for higra-0.5.1-cp35-cp35m-macosx_10_13_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0d1b7fc2a35ac833696945318132f835c9f9c5a3cc4d664acc23a1166c594e53 |
|
MD5 | 3e5bdf843f3d88bd87ab3148bc473569 |
|
BLAKE2b-256 | fefa810b1ee3da70d2afc615259e1ed6695ae836698af472374238874ce2191d |