Bioinformatics/bioinformatics/algorithms/eulerian_cycle.py at main · A-F-V/Bioinformatics · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
from typing import Set
from algorithms.sequencing_graph import Graph


def random_cycle(start, graph: Graph):
    """
    Find a random cycle in a graph starting and ending at first.
    A non recursive implementation.
    """
    edges = graph.edges
    cycle = [start]
    current = start
    while(current != start or len(cycle) == 1):
        nxt = edges[current].pop()
        if len(edges[current]) == 0:
            del edges[current]
        cycle.append(nxt)
        current = nxt
    return cycle


def eulerian_cycle(graph: Graph):
    """
    Find an Eulerian cycle in a graph.
    Does not check feasability.
    """
    cgraph = graph.copy()
    start = list(cgraph.nodes)[0]
    cycle = random_cycle(start, cgraph)
    while len(cgraph.edges) > 0:
        for i in range(len(cycle)):
            node = cycle[i]
            if node in cgraph.edges:  # if node has outgoing edges
                smaller_cycle = random_cycle(node, cgraph)
                cycle = cycle[:i]+smaller_cycle+cycle[i+1:]
                break
    return cycle


def hamiltonian_path(graph: Graph):  # untested
    memo = {}

    def aux(subset: set, ends):
        if (subset, ends) in memo:
            return memo[(subset, ends)]
        if len(subset) == 1:
            if ends == subset.pop():
                return [ends]
            return None
        for neighbour in graph.edges[ends]:
            if neighbour not in subset:
                continue
            subpath = aux(set.difference(subset, [ends]), neighbour)
            if subpath == None:
                continue
            res = subpath+[ends]
            memo[(subset, ends)] = res
            return res
        memo[(subset, ends)] = None
        return None

    for node in graph.nodes:
        attempt = aux(set(graph.nodes), node)
        if attempt != None:
            return attempt
    return None


def unbalanced_nodes(graph: Graph):
    """
    Find unbalanced nodes in a graph. Place Natural sinks at start and sources at end.
    """
    in_degree = {i: 0 for i in graph.nodes}
    out_degree = {i: 0 for i in graph.nodes}
    for source in graph.edges:
        out_degree[source] = len(graph.edges[source])
        for sink in graph.edges[source]:
            in_degree[sink] += 1
    unbalanced = []
    for node in graph.nodes:
        if in_degree[node] < out_degree[node]:  # node is a source
            unbalanced.append(node)
        if in_degree[node] > out_degree[node]:  # node is a sink
            unbalanced.insert(0, node)
    return unbalanced


def eulerian_path(graph: Graph):
    """
    Find an Eulerian path in a graph.
    """
    cgraph = graph.copy()
    pivots = unbalanced_nodes(cgraph)
    cgraph.add_edge(pivots[0], pivots[1])
    path = eulerian_cycle(cgraph)
    crossover = None
    for i in range(len(path)-1):
        if path[i] == pivots[0] and path[i+1] == pivots[1]:
            crossover = i+1
    return path[crossover:]+path[1:crossover]