d2_algorithms.py 4.91 KB
Newer Older
1
import networkx as nx
2
from itertools import combinations
3

Yoann Dufresne's avatar
Yoann Dufresne committed
4
5
from d2_path import Path, Unitig

6
7
8
9

""" Remove unnecessary transitions
"""
def transitive_reduction(d2g):
10
    edges = list(d2g.edges(data=True))
11
12
13
14
    
    # Remove self edges
    for edge in edges:
        if edge[0] == edge[1]:
15
16
17
            d2g.remove_edge(*edge)

    edges = list(d2g.edges(data=True))
18
19

    nb_removed = 0
20
21
22
    while len(edges) > 0:
        dg1_name, dg2_name, data = edges.pop(0)

23
        # Extract dgs
24
25
        dg1 = d2g.node_by_name[dg1_name]
        dg2 = d2g.node_by_name[dg2_name]
26
27

        # Extract common neighbors
28
29
        nei1 = frozenset(d2g.neighbors(dg1_name))
        nei2 = frozenset(d2g.neighbors(dg2_name))
30
31
32
        common = nei1.intersection(nei2)

        # Look for all the common neighbors, if edge must be remove or not
33
        current_dist = d2g[dg1_name][dg2_name]["distance"]
34
        for node in common:
35
36
            com_dg = d2g.node_by_name[node]
            extern_dist = d2g[dg1_name][node]["distance"] + d2g[node][dg2_name]["distance"]
37
38
39
40

            # If better path, remove the edge
            if extern_dist <= current_dist:
                # Remove from graph
41
42
43
44
45
46
47
                d2g.remove_edge(dg1_name, dg2_name)
                # Remove from edge list
                edge = (dg1_name, dg2_name, data)
                if edge in edges:
                    edges.remove(edge)

                # Mark as removed
48
49
50
51
                nb_removed += 1
                break

    print(f"{nb_removed} edge removed")
52
    print(f"{len(d2g.edges())} remaining")
53
54


Yoann Dufresne's avatar
Yoann Dufresne committed
55
""" For each node of the d2 graph, construct a node in the reduced graph.
56
57
58
59
60
    Then, for each node, compute the closest neighbors in d2 (with equal scores) and add an edge
    in the greedy graph.
    @param d2 Input d2 graph (with distances already computed)
    @return A greedy constructed graph.
"""
61
62
63
64
65
66
67
def greedy_reduct(d2):
    gG = nx.Graph()

    for node in d2.nodes:
        gG.add_node(node)

    for dgraph, node in d2.nodes.items():
68
        if not dgraph.idx in d2.distances or len(d2.distances[dgraph.idx]) == 0:
69
70
            continue

71
        distances = d2.distances[dgraph.idx]
72
73
        min_dist = min(distances.values())

74
        for graph_idx, dist in distances.items():
75
            if dist == min_dist:
76
                gG.add_edge(node, d2.nodes[d2.node_by_idx[graph_idx]])
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

    return gG


def filter_singeltons(graph):
    """ Remove the isolated nodes from graph.
    """
    nodelist = list(graph.nodes())

    for node in nodelist:
        if len(graph[node]) == 0:
            graph.remove_node(node)

    return graph


Yoann Dufresne's avatar
Yoann Dufresne committed
93
94
95
96
97
""" Compute the unambiguous paths in a graph. The graph must not contain singletons.s
    @param graph a networkx graph
    @return a list of unitigs
"""
def compute_unitigs(graph):
98
    unitigs = []
Yoann Dufresne's avatar
Yoann Dufresne committed
99
100
    used_nodes = {node:False for node in graph.nodes()}
    current_unitig = Unitig()
Yoann Dufresne's avatar
Yoann Dufresne committed
101

Yoann Dufresne's avatar
Yoann Dufresne committed
102
103
104
    for node in graph.nodes():
        # If already tested
        if used_nodes[node]:
Yoann Dufresne's avatar
Yoann Dufresne committed
105
            continue
Yoann Dufresne's avatar
Yoann Dufresne committed
106
        used_nodes[node] = True
Yoann Dufresne's avatar
Yoann Dufresne committed
107

Yoann Dufresne's avatar
Yoann Dufresne committed
108
109
        if graph.degree(node) > 2:
            # Not a unitig
Yoann Dufresne's avatar
Yoann Dufresne committed
110
111
            continue

Yoann Dufresne's avatar
Yoann Dufresne committed
112
113
114
115
116
        # Create new unitigs
        unitig = compute_unitig_from(graph, node)
        unitigs.append(unitig)
        for node in unitig:
            used_nodes[node] = True
Yoann Dufresne's avatar
Yoann Dufresne committed
117

Yoann Dufresne's avatar
Yoann Dufresne committed
118
    return unitigs
Yoann Dufresne's avatar
Yoann Dufresne committed
119
120


Yoann Dufresne's avatar
Yoann Dufresne committed
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
""" Compute a unitig starting from the node regarding the graph.
    The unitig will be extended on both sides
    @param graph The graph to look for unitig
    @param node The start node of the unitig
    @return The constructed unitig
"""
def compute_unitig_from(graph, node):
    unitig = Unitig(nodes=[node])
    if graph.degree(node) == 2:
        left, right = graph.neighbors(node)
    else:
        left = next(graph.neighbors(node))
        right = None

    # Extends first side
    prev_node = node
    current_node = left
    unitig = extend_unitig(unitig, graph, prev_node, current_node)
    unitig.revert()

    # Extends second side
    prev_node = node
    current_node = right
    unitig = extend_unitig(unitig, graph, prev_node, current_node)

    return unitig


""" Directional extension of the unitig. Uses the previous and current nodes to detect the extension direction.
    @param unitig The unitig to extend. Will be modified during the execution.
    @param graph The graph to follow for extension
    @param prev_node Node already added in the unitig
    @param current_node Node to add into the unitig and used to select the next node to add. If not set, stop the extension.
    @return Return the modified unitig. 
"""
def extend_unitig(unitig, graph, prev_node, current_node):
    if current_node == None:
        return unitig

    # Add the node
    unitig.add_right(current_node)

    # Look for the next node
    next_candidates = list(graph.neighbors(current_node))
    next_candidates.remove(prev_node)
    # Select next node
    next_node = next_candidates[0] if len(next_candidates) == 1 else None
    # Continue extension
    return extend_unitig(unitig, graph, current_node, next_node)
170