d2_graph.py 2.81 KB
Newer Older
Yoann Dufresne's avatar
Yoann Dufresne committed
1
import networkx as nx
2
3
4
import itertools

from d_graph import compute_all_max_d_graphs
Yoann Dufresne's avatar
Yoann Dufresne committed
5
6
7
8


class D2Graph(object):
    """D2Graph (read it (d-graph)²)"""
Yoann Dufresne's avatar
Yoann Dufresne committed
9
    def __init__(self, graph, index_size=10):
Yoann Dufresne's avatar
Yoann Dufresne committed
10
11
12
13
        super(D2Graph, self).__init__()
        self.graph = graph

        # Compute all the d-graphs
14
        self.d_graphs = compute_all_max_d_graphs(self.graph)
Yoann Dufresne's avatar
Yoann Dufresne committed
15
16
        
        # Index all the d-graphes
Yoann Dufresne's avatar
Yoann Dufresne committed
17
        self.index = self.create_index_from_tuples(index_size)
Yoann Dufresne's avatar
Yoann Dufresne committed
18
19


Yoann Dufresne's avatar
Yoann Dufresne committed
20
21

    def create_index_from_tuples(self, tuple_size=3):
Yoann Dufresne's avatar
Yoann Dufresne committed
22
        index = {}
23

24
25
26
        perfect = 0
        for node in self.d_graphs:
            for dg in self.d_graphs[node]:
Yoann Dufresne's avatar
Yoann Dufresne committed
27
28
29
30
31
32
33
                nodelist = dg.to_list()
                nodelist.sort()
                if len(nodelist) < tuple_size:
                    continue

                # Generate all tuplesize-mers
                for dmer in itertools.combinations(nodelist, tuple_size):
34
35
36
37
38
39
40
41
42
43
44
                    if not dmer in index:
                        index[dmer] = [dg]
                    else:
                        index[dmer].append(dg)

        return index


    def create_index_ordered(self):
        index = {}

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
        perfect = 0
        for node in self.d_graphs:
            for dg in self.d_graphs[node]:
                lst = dg.to_ordered_lists()
                # Generate all dmers without the first node
                # pull all the values 
                concat = [el for l in lst[1:] for el in l]
                # generate dmers
                for idx in range(len(lst[0])):
                    dmer = frozenset(concat + lst[0][:idx] + lst[0][idx+1:])
                    if not dmer in index:
                        index[dmer] = [dg]
                    else:
                        index[dmer].append(dg)

                # Generate all dmers without the last node
                # pull all the values 
                concat = [el for l in lst[:-1] for el in l]
                # generate dmers
                for idx in range(len(lst[-1])):
                    dmer = frozenset(concat + lst[-1][:idx] + lst[-1][idx+1:])
                    if not dmer in index:
                        index[dmer] = [dg]
                    else:
                        index[dmer].append(dg)

Yoann Dufresne's avatar
Yoann Dufresne committed
71
72
73
        return index


74
    def to_nx_graph(self):
Yoann Dufresne's avatar
Yoann Dufresne committed
75
76
77
78
        next_idx = 0
        nodes = {}
        G = nx.Graph()

79
80
81
82
83
84
        for dmer in self.index:
            for d_idx, dg in enumerate(self.index[dmer]):
                # Create a node name
                if not dg in nodes:
                    nodes[dg] = next_idx
                    next_idx += 1
Yoann Dufresne's avatar
Yoann Dufresne committed
85
                
86
87
                    # Add the node
                    G.add_node(nodes[dg])
Yoann Dufresne's avatar
Yoann Dufresne committed
88

89
90
91
                # Add the edges
                for prev_node in self.index[dmer][:d_idx]:
                    G.add_edge(nodes[dg], nodes[prev_node])
Yoann Dufresne's avatar
Yoann Dufresne committed
92

93
        return G, nodes
Yoann Dufresne's avatar
Yoann Dufresne committed
94
95