README.md 1.64 KB
Newer Older
Felix's avatar
Felix committed
1
# cycle-coalescence-algorithm
Felix's avatar
Felix committed
2
##  Introduction
Felix's avatar
Felix committed
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's avatar
Felix committed
6
![modes](./gallery/modes_merging_algorithm_2016.png)
Felix's avatar
Felix committed
7

Felix's avatar
Felix committed
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's avatar
Felix committed
9

Felix's avatar
Felix committed
10
  ./notebook contains examples to play with in the form of jupyter notebooks
Felix's avatar
Felix committed
11
##  Installation
Felix's avatar
Felix committed
12
pip install cycle_analysis
Felix's avatar
Felix committed
13
##  Usage
Felix's avatar
Felix committed
14

Felix's avatar
Felix committed
15
```python
Felix's avatar
Felix committed
16
import networkx as nx
Felix's avatar
Felix committed
17
18
19
import cycle_analysis.cycle_coalescence as cc
import cycle_analysis.test as cat

Felix's avatar
Felix committed
20
# generate a dummy graph for testing
Felix's avatar
Felix committed
21
# put an edge weight distribution on the system, available are random/gradient/nested_square
Felix's avatar
Felix committed
22
G=nx.grid_graph((7,7,1))
Felix's avatar
Felix committed
23
G=cat.generate_pattern(G,'nested_square')
Felix's avatar
Felix committed
24

Felix's avatar
Felix committed
25
# merge all shortest cycles and calc the merging tree's asymmetry for each branch
Felix's avatar
Felix committed
26
asymmetry=cc.calc_cycle_asymmetry(G)
Felix's avatar
Felix committed
27
print(asymmetry)
Felix's avatar
Felix committed
28
```
Felix's avatar
Felix committed
29

Felix's avatar
Felix committed
30
##  Requirements
Felix's avatar
Felix committed
31
``` networkx ```, ``` numpy ```
Felix's avatar
Felix committed
32
##  Gallery
Felix's avatar
Felix committed
33
random weight distribution\
Felix's avatar
Felix committed
34
![random](./gallery/random.png)
Felix's avatar
Felix committed
35

Felix's avatar
Felix committed
36
37
nested square weight distribution\
![nested](./gallery/nested_square.png)
Felix's avatar
Felix committed
38

Felix's avatar
Felix committed
39
gradient weight distribution\
Felix's avatar
Felix committed
40
![gradient](./gallery/gradient.png)
Felix's avatar
Felix committed
41
## Acknowledgement
Felix's avatar
Felix committed
42
```cycle_analysis``` written by Felix Kramer
Felix's avatar
Felix committed
43

Felix's avatar
Felix committed
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