d_graph.py 6.66 KB
Newer Older
1
2
from functools import total_ordering

Yoann Dufresne's avatar
Yoann Dufresne committed
3

Yoann Dufresne's avatar
Yoann Dufresne committed
4

5
6
7
@total_ordering
class Dgraph(object):
    """docstring for Dgraph"""
Yoann Dufresne's avatar
Yoann Dufresne committed
8
    def __init__(self, center):
9
        super(Dgraph, self).__init__()
Yoann Dufresne's avatar
Yoann Dufresne committed
10
        self.idx = -1
Yoann Dufresne's avatar
Yoann Dufresne committed
11
        self.center = center
12
        self.score = 0
Yoann Dufresne's avatar
Yoann Dufresne committed
13
        self.halves = [[], []]
14
        self.connexity = [{}, {}]
15
        self.nodes = [self.center]
16
        self.node_set = set(self.nodes)
17
        self.ordered_list = None
18
        self.sorted_list = None
19
20
21
        self.edges = set()

    @staticmethod
Yoann Dufresne's avatar
Yoann Dufresne committed
22
    def load(lcp_txt, score, variables):
23
24
25
26
        """ Static method to load a dgraph from a text
            :param lcp_txt: the saved d-graph
            :return: a new d-graph object corresponding to the test
        """
27
        # basic split
28
29
        lcp_txt = lcp_txt.replace(']', '')
        _, head, h1, h2 = lcp_txt.split('[')
30
31

        # Head parsing
Yoann Dufresne's avatar
Yoann Dufresne committed
32
        center = head.replace(' ', '')
33
        dg = Dgraph(center)
34

35
        # Reload halves
36
37
        h1 = [x for x in h1.split(',')]
        h2 = [x for x in h2.split(',')]
38
39
40
41
42
43
44

        dg.halves[0] = h1
        dg.node_set.update(h1)
        dg.nodes.extend(h1)
        dg.halves[1] = h2
        dg.node_set.update(h2)
        dg.nodes.extend(h2)
45

Yoann Dufresne's avatar
Yoann Dufresne committed
46
47
48
49
50
51
        # Score parsing
        dg.score = int(score.split('/')[0])

        # covering variable loading
        dg.edges = {int(x) for x in variables.split(' ')}

52
        return dg
Yoann Dufresne's avatar
Yoann Dufresne committed
53

54
    def put_halves(self, h1, h2, graph):
55
56
57
58
59
        """ Compute the d-graph quality (score) according to the connectivity between the two halves.
            :param h1: First half of the d-graph
            :param h2: Second half of the d-graph
            :param graph: The barcode graph
        """
60
        self.score = 0
61
        # First half
62
        self.halves[0] = h1
63
64
65
66
        self.node_set.update(h1)
        self.nodes.extend(h1)
        self.connexity[0] = {key: 0 for key in h1}
        # second half
67
        self.halves[1] = h2
68
69
70
        self.node_set.update(h2)
        self.nodes.extend(h2)
        self.connexity[1] = {key: 0 for key in h2}
71
72

        # Compute link arities
73
        for node1 in self.halves[0]:
74
75
            neighbors = set(graph.neighbors(node1))

76
            for node2 in self.halves[1]:
77
78
                if node1 == node2 or node2 in neighbors:
                    self.score += 1
Yoann Dufresne's avatar
Yoann Dufresne committed
79
80
81
                    self.connexity[0][node1] += 1
                    self.connexity[1][node2] += 1

82
83
84
85
        # Compute covering variable
        subgraph = graph.subgraph(self.nodes)
        for _, _, id in subgraph.edges.data("uniq_idx"):
            self.edges.add(id)
86

87
    def get_link_divergence(self):
88
        return int(abs(self.score - self.get_optimal_score()))
89
90
91

    def get_optimal_score(self):
        max_len = max(len(self.halves[0]), len(self.halves[1]))
92
        return int(max_len * (max_len - 1) / 2)
93

94
95
    def to_sorted_list(self):
        if self.sorted_list is None:
Yoann Dufresne's avatar
Yoann Dufresne committed
96
            self.sorted_list = sorted(self.nodes)
97
        return self.sorted_list
Yoann Dufresne's avatar
Yoann Dufresne committed
98

99
    def to_ordered_lists(self):
100
        if self.ordered_list is None:
101
            hands = [[], []]
102
103
104
105
106
107
108
109
110
111
112
113
            for idx in range(2):
                prev_connectivity = -1
                for node in self.halves[idx]:
                    # group nodes by similar connectivity
                    value = self.connexity[idx][node]
                    if value != prev_connectivity:
                        hands[idx].append([])
                        prev_connectivity = value
                    hands[idx][-1].append(node)

            self.ordered_list = hands[0][::-1] + [[self.center]] + hands[1]
        return self.ordered_list
Yoann Dufresne's avatar
Yoann Dufresne committed
114

115
116
    def to_node_set(self):
        return frozenset(self.to_sorted_list())
117

Yoann Dufresne's avatar
Yoann Dufresne committed
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
    def to_uniq_triplet(self):
        """ Return the triplet (center, left_clique, right_clique) where the cliques are sorted by name.
            The left clique have a lexicography order smaller than the right one.
        """
        left = sorted(self.halves[0])
        left_repr = ",".join(str(node) for node in left)
        right = sorted(self.halves[1])
        right_repr = ",".join(str(node) for node in right)

        if left_repr > right_repr:
            save = left
            left = right
            right = save

        return self.center, left, right
133

134
    def distance_to(self, dgraph):
Yoann Dufresne's avatar
Yoann Dufresne committed
135
136
        nodes_1 = self.to_sorted_list()
        nodes_2 = other_nodes = dgraph.to_sorted_list()
137
138
139

        dist = 0
        idx1, idx2 = 0, 0
Yoann Dufresne's avatar
Yoann Dufresne committed
140
141
        while idx1 != len(nodes_1) and idx2 != len(nodes_2):
            if nodes_1[idx1] == nodes_2[idx2]:
142
143
144
145
                idx1 += 1
                idx2 += 1
            else:
                dist += 1
Yoann Dufresne's avatar
Yoann Dufresne committed
146
                if nodes_1[idx1] < nodes_2[idx2]:
147
148
149
                    idx1 += 1
                else:
                    idx2 += 1
Yoann Dufresne's avatar
Yoann Dufresne committed
150
        dist += len(nodes_1) - idx1 + len(nodes_2) - idx2
151
152
153

        return dist

154
155
156
157
158
159
    """ Verify if dg1 is dominated by dg2. The domination is determined by two points: All the nodes
    of dg1 are part of dg2 and the divergeance of dg1 is greater than dg2.
    @param dg1 (resp dg2) A d_graph object.
    @return True if dg1 is dominated by dg2.
    """
    def is_dominated(self, dg):
160
161
        dg1_nodes = self.to_node_set()
        dg2_nodes = dg.to_node_set()
162
163
164
165
166
167
168

        # domination first condition: inclusion of all the nodes
        if not dg1_nodes.issubset(dg2_nodes):
            return False

        # domination second condition
        if len(dg1_nodes) == len(dg2_nodes):
169
            if self.get_link_divergence() > dg.get_link_divergence():
170
                return True
171
        elif self.get_link_divergence() >= dg.get_link_divergence():
172
173
174
175
            return True

        return False

176
    def __eq__(self, other):
177
178
179
        if other is None:
            return False

Yoann Dufresne's avatar
Yoann Dufresne committed
180
        if self.idx != -1 and self.idx == other.idx:
181
182
183
            return True

        if self.node_set != other.node_set:
Yoann Dufresne's avatar
Yoann Dufresne committed
184
185
            return False

Yoann Dufresne's avatar
Yoann Dufresne committed
186
        return self.to_uniq_triplet() == other.to_uniq_triplet()
187
188
189
190
191

    def __ne__(self, other):
        return not (self == other)

    def __lt__(self, other):
192
193
        my_tuple = (self.get_link_divergence(), self.get_optimal_score())
        other_tuple = (other.get_link_divergence(), other.get_optimal_score())
Yoann Dufresne's avatar
Yoann Dufresne committed
194
        return my_tuple < other_tuple
195

196
    def __hash__(self):
Yoann Dufresne's avatar
Yoann Dufresne committed
197
        return str(self).__hash__()
198

Yoann Dufresne's avatar
Yoann Dufresne committed
199
    def __full_repr__(self):
Yoann Dufresne's avatar
Yoann Dufresne committed
200
        # print(self.halves)
201
        representation = str(self.center) + " "
Yoann Dufresne's avatar
Yoann Dufresne committed
202
203
204
        representation += "[" + ", ".join([f"{node} {self.connexity[0][node]}" for node in self.halves[0]]) + "]"
        representation += "[" + ", ".join([f"{node} {self.connexity[1][node]}" for node in self.halves[1]]) + "]"
        return representation
205

Yoann Dufresne's avatar
Yoann Dufresne committed
206
207
208
    def __repr__(self):
        c, left, right = self.to_uniq_triplet()
        return f"[{c}][{','.join(str(x) for x in left)}][{','.join(str(x) for x in right)}]"