Felix committed Dec 30, 2020 1 ``````# cycle-coalescence-algorithm `````` Felix committed Jan 09, 2021 2 ``````## Introduction `````` Felix committed Jan 23, 2021 3 4 5 `````` Have you ever wondered how cycles in graphs form a vector space and encapsulate nesting information? If so, were you never really sure how to deal with this? Here is a tool ready to use, enabling you to calculate the cycle bases, mapping them onto a merging tree, and analyze this tree's asymmetry. `````` Felix committed Jan 23, 2021 6 ``````![modes](./gallery/modes_merging_algorithm_2016.png) `````` Felix committed Jan 23, 2021 7 `````` `````` Felix committed Jan 23, 2021 8 ``````This project is based on the algorithm published in 'Extracting Hidden Hierarchies in 3D Distribution Networks' by Modes et al, 2016. Please acknowledge if used for any further publication or projects. `````` Felix committed Dec 30, 2020 9 `````` `````` Felix committed Jan 09, 2021 10 `````` ./notebook contains examples to play with in the form of jupyter notebooks `````` Felix committed Jan 09, 2021 11 ``````## Installation `````` Felix committed May 08, 2021 12 ``````pip install cycle_analysis `````` Felix committed Jan 09, 2021 13 ``````## Usage `````` Felix committed Jan 09, 2021 14 `````` `````` Felix committed Jan 09, 2021 15 `````````python `````` Felix committed Jan 09, 2021 16 ``````import networkx as nx `````` Felix committed Jan 09, 2021 17 18 19 ``````import cycle_analysis.cycle_coalescence as cc import cycle_analysis.test as cat `````` Felix committed Jan 09, 2021 20 ``````# generate a dummy graph for testing `````` Felix committed Jan 12, 2021 21 ``````# put an edge weight distribution on the system, available are random/gradient/nested_square `````` Felix committed Jan 09, 2021 22 ``````G=nx.grid_graph((7,7,1)) `````` Felix committed Jan 09, 2021 23 ``````G=cat.generate_pattern(G,'nested_square') `````` Felix committed Jan 09, 2021 24 `````` `````` Felix committed Jan 12, 2021 25 ``````# merge all shortest cycles and calc the merging tree's asymmetry for each branch `````` Felix committed Jan 09, 2021 26 ``````asymmetry=cc.calc_cycle_asymmetry(G) `````` Felix committed Jan 09, 2021 27 ``````print(asymmetry) `````` Felix committed Jan 09, 2021 28 ````````` `````` Felix committed Jan 09, 2021 29 `````` `````` Felix committed Jan 09, 2021 30 ``````## Requirements `````` Felix committed Jan 09, 2021 31 ````````` networkx ```, ``` numpy ``` `````` Felix committed Jan 09, 2021 32 ``````## Gallery `````` Felix committed Jan 09, 2021 33 ``````random weight distribution\ `````` Felix committed Jan 09, 2021 34 ``````![random](./gallery/random.png) `````` Felix committed Jan 09, 2021 35 `````` `````` Felix committed Jan 09, 2021 36 37 ``````nested square weight distribution\ ![nested](./gallery/nested_square.png) `````` Felix committed Jan 09, 2021 38 `````` `````` Felix committed Jan 09, 2021 39 ``````gradient weight distribution\ `````` Felix committed Jan 09, 2021 40 ``````![gradient](./gallery/gradient.png) `````` Felix committed Jan 09, 2021 41 ``````## Acknowledgement `````` Felix committed Jan 09, 2021 42 `````````cycle_analysis``` written by Felix Kramer `````` Felix committed Dec 30, 2020 43 `````` `````` Felix committed Jan 09, 2021 44 45 ``````This implementation is based on the cycle coalescence algorithm as described by Modes et al, 2016. https://journals.aps.org/prx/pdf/10.1103/PhysRevX.6.031009``````