path_optimization.py 6.04 KB
Newer Older
Yoann Dufresne's avatar
Yoann Dufresne committed
1
import random
2
import networkx as nx
Yoann Dufresne's avatar
Yoann Dufresne committed
3
from collections import Counter
Yoann Dufresne's avatar
Yoann Dufresne committed
4

5
6
from deconvolution.d2graph.d2_path import Path

Yoann Dufresne's avatar
Yoann Dufresne committed
7
8
9
10
11
12
13
14
15
16

class Optimizer:

    def __init__(self, d2g):
        self.d2g = d2g
        self.solutions = []

    def init_random_solutions(self, nb_solutions):
        for _ in range(nb_solutions):
            rnd_sol = Solution(self.d2g)
Yoann Dufresne's avatar
Yoann Dufresne committed
17
            rnd_sol.random_init_best_quality()
Yoann Dufresne's avatar
Yoann Dufresne committed
18
19
            self.solutions.append(rnd_sol)

Yoann Dufresne's avatar
Yoann Dufresne committed
20
21
22
23
24
    def bb_solution(self, verbose=False):
        nb_steps_since_last_score_up = 0
        total_nb_steps = 0
        first_pass = True

Yoann Dufresne's avatar
Yoann Dufresne committed
25
26
27
28
29
30
        max_cov = set()
        for node in self.d2g.nodes():
            v = self.d2g.get_covering_variable_node(node)
            max_cov.update(v)
        max_cov = len(max_cov)

Yoann Dufresne's avatar
Yoann Dufresne committed
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
        used_nodes = {n:False for n in self.d2g.nodes()}
        coverage = Counter()

        # Init solution for
        init = list(used_nodes.keys())
        init = init[random.randint(0, len(init)-1)]

        best_path = []
        best_score = 0
        stack = [[init]]
        current_path = []
        last_increase_node = None

        while len(stack) > 0:
            total_nb_steps += 1
            # 1 - Get next node to extend
            current_node = stack[-1].pop()

            # 2 - Node exploitation
            # 2.1 - Add the node
            used_nodes[current_node] = True
            current_path.append(current_node)
            # 2.2 - Compute the coverage score
            vars = self.d2g.get_covering_variable_node(int(current_node))
            coverage += Counter(vars)
            # 2.3 - If best, save
            if len(coverage) > best_score:
                nb_steps_since_last_score_up = 0
                best_path = current_path.copy()
                best_score = len(coverage)
                last_increase_node = current_node
                if verbose:
                    print(f"New best: {len(best_path)} {best_score}")
Yoann Dufresne's avatar
Yoann Dufresne committed
64
65
66

                if len(coverage) == max_cov:
                    return best_path
Yoann Dufresne's avatar
Yoann Dufresne committed
67
68
69
70
71
72
73
74
75
76
            else:
                nb_steps_since_last_score_up += 1

            # 3 - Neighbors preparation
            neighbors = [x for x in self.d2g[current_node] if not used_nodes[x]]
            opt = self

            def node_sorting_value(node):
                u = opt.d2g.node_by_idx[int(node)]
                return (0 if len(Counter(opt.d2g.get_covering_variable_node(int(node))) - coverage) == 0 else 1,
Yoann Dufresne's avatar
Yoann Dufresne committed
77
78
                        - u.get_link_divergence(),
                        - self.d2g[str(u.idx)][str(current_node)]["distance"])
Yoann Dufresne's avatar
Yoann Dufresne committed
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
            neighbors.sort(key=node_sorting_value)
            stack.append(neighbors)

            # 4 - No more neighbors here - back up
            while len(stack[-1]) == 0:
                stack.pop()
                previous = current_path.pop()
                used_nodes[previous] = False
                prev_vars = self.d2g.get_covering_variable_node(int(previous))
                coverage -= Counter(prev_vars)

            # 5 - Reinit the search from a side and stop when done
            if total_nb_steps > 10000 and nb_steps_since_last_score_up >= total_nb_steps / 2:
                if first_pass:
                    used_nodes = {n: False for n in self.d2g.nodes()}
                    coverage = Counter()
                    best_path = []
                    best_score = 0
                    stack = [[last_increase_node]]
                    current_path = []
                    if verbose:
                        print("Start again !")
                    first_pass = False
                    total_nb_steps = 0
                    nb_steps_since_last_score_up = 0
                    import time
                    time.sleep(3)
                else:
                    return best_path

        return best_path

Yoann Dufresne's avatar
Yoann Dufresne committed
111
112
    def extends_until_end(self, solution):
        while self.extends(solution):
Yoann Dufresne's avatar
Yoann Dufresne committed
113
            continue
Yoann Dufresne's avatar
Yoann Dufresne committed
114
115
        solution.reverse()
        while self.extends(solution):
Yoann Dufresne's avatar
Yoann Dufresne committed
116
            continue
Yoann Dufresne's avatar
Yoann Dufresne committed
117
118
119
120
121
122
123
124
125
126
127
128
129
130

    def extends(self, solution):
        # Get all the neighbors
        cur_id = str(solution[-1].idx)
        neighbors = [self.d2g.node_by_idx[int(x)] for x in self.d2g.neighbors(cur_id) if
                     self.d2g.node_by_idx[int(x)] not in solution]

        current_vars = frozenset([x for x, y in solution.covering_variables.items() if y > 0])
        if len(neighbors) == 0:
            return False

        # Choose using the multiple optimization directions
        next_udg = min(neighbors,
                       key=lambda x: (1 if len(self.d2g.get_covering_variables(x) - current_vars) == 0 else 0,
Yoann Dufresne's avatar
Yoann Dufresne committed
131
132
                                      x.get_link_divergence(),
                                      self.d2g[str(x.idx)][cur_id]["distance"]))
Yoann Dufresne's avatar
Yoann Dufresne committed
133
134
135
136
137
138
139
140
141
        solution.add_path([next_udg])
        return True


class Solution(Path):

    def __init__(self, d2g):
        super(Solution, self).__init__(d2g)

Yoann Dufresne's avatar
Yoann Dufresne committed
142
143
144
145
146
147
    def random_init_best_quality(self):
        nodes = [self.d2g.node_by_idx[int(x)] for x in list(self.d2g.nodes())]
        min_div = (min(nodes, key=lambda x: x.get_link_divergence())).get_link_divergence()
        nodes = [x for x in nodes if x.get_link_divergence() == min_div]

        random_udg = random.choice(nodes)
Yoann Dufresne's avatar
Yoann Dufresne committed
148
149

        self.clear()
Yoann Dufresne's avatar
Yoann Dufresne committed
150
        self.add_path([random_udg])
151
152
153
154
155


    """ Only respect counts for now
    """
    def to_barcode_path(self):
156
        barcode_per_position = [set(udg.to_sorted_list()) for udg in self]
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
        compressed_barcodes = []

        for idx, barcodes in enumerate(barcode_per_position):
            for barcode in barcodes:
                offset = 1
                while idx + offset < len(barcode_per_position) and barcode in barcode_per_position[idx + offset]:
                    barcode_per_position[idx + offset].remove(barcode)
                    offset += 1
                compressed_barcodes.append(barcode)

        return compressed_barcodes

    def save_barcode_path(self, filename):
        barcodes = self.to_barcode_path()

        G = nx.Graph()
        for idx, barcode in enumerate(barcodes):
            G.add_node(idx)
            G.nodes[idx]["center"] = barcode

        nx.write_gexf(G, filename)