Mercurial > repos > cpt > cpt_linear_genome_plot
comparison dna_features_viewer/compute_features_levels.py @ 1:e923c686ead9 draft
planemo upload commit 94b0cd1fff0826c6db3e7dc0c91c0c5a8be8bb0c
author | cpt |
---|---|
date | Mon, 05 Jun 2023 02:45:31 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
0:621754dd31f8 | 1:e923c686ead9 |
---|---|
1 """Implements the method used for deciding which feature goes to which level | |
2 when plotting.""" | |
3 | |
4 import itertools | |
5 import math | |
6 | |
7 | |
8 class Graph: | |
9 """Minimal implementation of non-directional graphs. | |
10 | |
11 Parameters | |
12 ---------- | |
13 | |
14 nodes | |
15 A list of objects. They must be hashable | |
16 edges | |
17 A list of the form [(n1,n2), (n3,n4)...] where (n1, n2) represents | |
18 an edge between nodes n1 and n2 | |
19 """ | |
20 | |
21 def __init__(self, nodes, edges): | |
22 self.nodes = nodes | |
23 self.neighbors = {n: [] for n in nodes} | |
24 for n1, n2 in edges: | |
25 self.neighbors[n1].append(n2) | |
26 self.neighbors[n2].append(n1) | |
27 | |
28 | |
29 def compute_features_levels(features): | |
30 """Compute the vertical levels on which the features should be displayed | |
31 in order to avoid collisions. | |
32 | |
33 `features` must be a list of `dna_features_viewer.GraphicFeature`. | |
34 | |
35 The method used is basically a graph coloring: | |
36 - The nodes of the graph are features and they will be colored with a level | |
37 - Two nodes are neighbors if and only if their features's locations overlap | |
38 - Levels are attributed to nodes iteratively starting with the nodes | |
39 corresponding to the largest features. | |
40 - A node receives the lowest level (starting at 0) that is not already | |
41 the level of one of its neighbors. | |
42 """ | |
43 edges = [ | |
44 (f1, f2) | |
45 for f1, f2 in itertools.combinations(features, 2) | |
46 if f1.overlaps_with(f2) | |
47 ] | |
48 graph = Graph(features, edges) | |
49 levels = {n: n.data.get("fixed_level", None) for n in graph.nodes} | |
50 | |
51 def collision(node, level): | |
52 """Return whether the node placed at base_level collides with its | |
53 neighbors in the graph.""" | |
54 line_factor = 0.5 | |
55 nlines = node.data.get("nlines", 1) | |
56 for neighbor in graph.neighbors[node]: | |
57 neighbor_level = levels[neighbor] | |
58 if neighbor_level is None: | |
59 continue | |
60 neighbor_lines = neighbor.data.get("nlines", 1) | |
61 min_distance = line_factor * (nlines + neighbor_lines) | |
62 if abs(level - neighbor_level) < min_distance: | |
63 return True | |
64 return False | |
65 | |
66 for node in sorted(graph.nodes, key=lambda f: -f.length): | |
67 if levels[node] is None: | |
68 level = 0 | |
69 while collision(node, level): | |
70 level += 0.5 | |
71 levels[node] = level | |
72 return levels |