GRAPH/algorithm.py at master · subthings/GRAPH · 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
"""

The algorithm from
'A FAST & EFFECTIVE HEURISTIC FOR THE FEEDBACK ARC SET PROBLEM'
article
Peter Eades
Xuemin Lin
W. F. Smyth

"""


import networkx as nx
#from graphGenerator import DG as GD
from visualization import write_in_file
from cyclic import is_cyclic
from graphGenerator import graph_generator
from visualization import benchmark
from visualization import nc, diameter
GG = nx.MultiDiGraph()


@benchmark
def algorithm1(GG):
    G = GG.copy()


    S1 = []
    S2 = [] #REVERSED!!!!


    while G.nodes:
        A = list(G.out_degree(G.nodes()))
        B = list(G.in_degree(G.nodes()))

        for u in A:
            if u[1] == 0:
                S2.append(u[0])
                G.remove_node(u[0])
                A.remove(u)
                for i in B:
                    if i[0] == u[0]:
                        B.remove(i)

                #dictionary changed size during iteration

        for u in B:
            if u[1] == 0:
                S1.append(u[0])
                G.remove_node(u[0])
                B.remove(u)
                for i in A:
                    if i[0] == u[0]:
                        A.remove(i)


        delta_max = 0
        node_to_delete = -1

        " May be for non weighted "

        for out_deg in A:
            for in_deg in B:
                if out_deg[0] == in_deg[0]:
                    a = out_deg[0]
                    b = (out_deg[1]-in_deg[1])
                    #                delta.append((a, b))
                    if b >= delta_max:
                        delta_max = b
                        node_to_delete = a


        for u in G.nodes:
            if G.out_degree(u)-G.in_degree(u) > delta_max:
                delta_max = G.out_degree(u)-G.in_degree(u)
                node_to_delete = u


        if node_to_delete != -1:
            S1.append(node_to_delete)
            G.remove_node(node_to_delete)


    S2.reverse()
    S1.extend(S2)

    remove=[]

    for u in GG.edges():
        a = u[0]
        b = u[1]
        if S1.index(a) >= S1.index(b):
            remove.append(u)

    GG.remove_edges_from(remove)

    return GG