percolation-python/percolation_graph.py at master · ussserrr/percolation-python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
# --------------------------------------------------------------------------- #
#                     Percolation library (graph edition)                     #
# --------------------------------------------------------------------------- #


import numpy as np

import networkx as nx


def generate_graph(grid, grid_y_dimension, grid_x_dimension):
    """
    Generate graph where each node represent one occupied cell of the grid

    returns:
        networkx.Graph instance
    """

    G = nx.Graph()

    idx = 0
    for y in range(1, grid_y_dimension+1):
        for x in range(1, grid_x_dimension+1):
            if grid[y][x]==1:
                G.add_node(idx, coords=[y,x])
                idx += 1

    return G


def find_clusters(grid, graph):
    """
    Create connections (graph edges) between nodes (neighboring occupied cells)

    returns:
        array of subgraphs representing individual clusters
    """

    num_of_ones = len(graph)
    for i in range(num_of_ones):
        # extract coordinates
        y,x = graph.nodes[i]['coords'][0], graph.nodes[i]['coords'][1]

        if grid[y-1][x]==1:
            for node in graph.nodes.items():
                if node[1]['coords']==[y-1,x]:
                    graph.add_edge( i, node[0] )

        if grid[y][x-1]==1:
            for node in graph.nodes.items():
                if node[1]['coords']==[y,x-1]:
                    graph.add_edge( i, node[0] )

    return nx.connected_component_subgraphs(graph)


def is_percolation(clusters, grid_y_dimension, grid_x_dimension):
    """
    Define whether there is a percolation and what its type

    input:
        clusters
        array of graphs representing clusters (neighboring occupied cells)
    """

    upwards_global = False
    lefttoright_global = False

    for cluster in clusters:
        upwards = False
        lefttoright = False

        # Transform coordinates array to find cluster's items at both bounds
        #
        #    x y
        #   [0,1]      xs [0,2,4]
        #   [2,3]  =>  ys [1,3,5]
        #   [4,5]
        #
        #  coords     coords_ys_xs
        #
        coords = np.array([ node[1]['coords'] for node in cluster.nodes.items() ])
        coords_ys_xs = coords.T

        ys = coords_ys_xs[0]; xs = coords_ys_xs[1]

        if (1 in ys) and (grid_y_dimension in ys):
            upwards = True
        if (1 in xs) and (grid_x_dimension in xs):
            lefttoright = True

        if upwards and not lefttoright:
            upwards_global = True
        elif not upwards and lefttoright:
            lefttoright_global = True
        elif upwards and lefttoright:
            upwards_global = True
            lefttoright_global = True

    if upwards_global and not lefttoright_global:
        return 'upwards'
    elif not upwards_global and lefttoright_global:
        return 'lefttoright'
    elif upwards_global and lefttoright_global:
        return 'both'
    else:
        return 0