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 (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.5.2-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ed19924f8a4de3e9428212ae09766cf395fad97008621817ba4845f8d02954cd |
|
MD5 | c4a8f94e3be91b5dca0d7c175607f11f |
|
BLAKE2b-256 | 2a974a5a1656f5799937912b7e4a0215062da4521045536e66c6084b7b38638b |
Hashes for higra-0.5.2-cp38-cp38-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0db2d116f13bfa90fcf0a3f6df3f6478e8b7fdbbc139878fa76d0799c183d35f |
|
MD5 | a2362f7c79469f1b92b9246ec6776fc1 |
|
BLAKE2b-256 | a2d2d0b9dceaafda1e6fcadbb534c2c03c5d1fc4437589e37f58c1624f053cb2 |
Hashes for higra-0.5.2-cp38-cp38-macosx_10_13_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 59f1455e45a8638a0a73d53b89becabeca3a55b6cf5082279bbf56af08c87926 |
|
MD5 | 8b9e2fa6993e038566321f9db0958663 |
|
BLAKE2b-256 | 137193ddc9abd24c63e34489cdef8475d58f4a60e351289266da39a057bc0559 |
Hashes for higra-0.5.2-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1d1199879163ab8e12ed234a828f6a7d786e7086dafd594d6866010a93336f22 |
|
MD5 | 9ec37d0256f6fb0b0c5e38b327716abe |
|
BLAKE2b-256 | f32efe5da0460effa4159cc30c9640d0429d5c6cf366597e8a7652a72b0fb4f2 |
Hashes for higra-0.5.2-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0f3ecd8bba70f6556c01404eafb2868c46ba69a16e7065f5dd853cfbce6ac13f |
|
MD5 | 6bb48c36d61da5226cccb263e89fd2f2 |
|
BLAKE2b-256 | e31ad995e28eadc0884c8dcc109eb8f33ca83a345374c2e185f1356f32fc4de6 |
Hashes for higra-0.5.2-cp37-cp37m-macosx_10_13_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 213a5d06306602e3dbcc82dd2f84148be58fa2b5e27a2b7dece93c2a70091097 |
|
MD5 | d991462cf4a65823dfd92a8324854949 |
|
BLAKE2b-256 | 073709c21b0214ebf3a2fa461857ccf713ed7349d14f997c20e09fc2c0c408c2 |
Hashes for higra-0.5.2-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7007b30a70926d99f11558ef5e85bc536d7e06b9eebcd8fdaeff949410ec4c0a |
|
MD5 | c98f4681f6f12c9f0646446feb47c2b3 |
|
BLAKE2b-256 | 2c046dea8a58184a0e9dc7c90175241d58c2ecf8fdd1abd02f30ab8254dee767 |
Hashes for higra-0.5.2-cp36-cp36m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 19bf640376104c618e2de882220a43adec80dfa2c72cc901925d1a12cacf110d |
|
MD5 | c6c86183d503fa7ca84a4c0297519478 |
|
BLAKE2b-256 | ace7df2d6f73db692f33c32e1127a635259cb2cde415b8de9fe27e0238dff5ab |
Hashes for higra-0.5.2-cp36-cp36m-macosx_10_13_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 901a623d830423994cf7292dc5732831c324953d81349130f869ea3629f1cfc5 |
|
MD5 | 1d76504a43434f44eba448f3ae043fd5 |
|
BLAKE2b-256 | d7c8f363979a0190d9ac7a285cdf3b76b734eaa9fc7d545f2578c7a4dab06d76 |
Hashes for higra-0.5.2-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 01a38673f38cf7cd06af5bd3996a9bcf5d76249be3d8f75aa786ac6907fcc15e |
|
MD5 | 2b6d004348853996c414724ef03076cc |
|
BLAKE2b-256 | ae5402943efd4bbbe6ec1a59f2e496101f4baef2ff90c224ca28907a3e353112 |
Hashes for higra-0.5.2-cp35-cp35m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4240f73a873ccf0581f0f4d232b3b17defd0822e25381521152fa2660be23f39 |
|
MD5 | 11b46c4f65ea63c86983a5ce3768050b |
|
BLAKE2b-256 | 0a8db11adbacb38b11db65527f009e035830a9a3908519f8f51a82cd0ca5322f |
Hashes for higra-0.5.2-cp35-cp35m-macosx_10_13_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 274bc83719285f137f8642749ff3217ab0d184f6bdb29efa43dca4aa73ac3d03 |
|
MD5 | 8f51fa09b66638778fb4ddaef72cdd15 |
|
BLAKE2b-256 | 874d2d78c385154d0eaeadb5e0dcac3105cdd3d1b5ede140708cd65e44bc7585 |