-
Notifications
You must be signed in to change notification settings - Fork 23
/
Copy pathremove_cycle_edges_by_hierarchy_greedy.py
102 lines (87 loc) · 3.44 KB
/
remove_cycle_edges_by_hierarchy_greedy.py
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
101
102
import networkx as nx
from s_c_c import filter_big_scc
from s_c_c import get_big_sccs
from file_io import write_pairs_to_file
from file_io import read_dict_from_file
import os.path
import sys
sys.setrecursionlimit(5500000)
def get_agony(edge,players):
u,v = edge
return max(players[u]-players[v],0)
def get_agonies(edges,players):
edges_agony_dict = {}
for edge in edges:
edges_agony_dict[edge] = get_agony(edge,players)
return edges_agony_dict
def remove_cycle_edges_by_agony(graph,players,edges_to_be_removed):
pair_agony_dict = {}
for pair in graph.edges():
u,v = pair
agony = max(players[u]-players[v],0)
pair_agony_dict[pair] = agony
from helper_funs import pick_from_dict
pair_max_agony,agony = pick_from_dict(pair_agony_dict)
edges_to_be_removed.append(pair_max_agony)
#print("edge to be removed: %s, agony: %0.4f" % (pair_max_agony,max_agony))
sub_graphs = filter_big_scc(graph,[pair_max_agony])
if sub_graphs:
num_subs = len(sub_graphs)
for index,sub in enumerate(sub_graphs):
#print("%d / %d scc: (%d,%d)" % (index+1,num_subs,sub.number_of_nodes(),sub.number_of_edges()))
remove_cycle_edges_by_agony(sub,players,edges_to_be_removed)
else:
return None
def remove_cycle_edges_by_agony_iterately(sccs,players,edges_to_be_removed):
while True:
graph = sccs.pop()
pair_max_agony = None
max_agony = -1
for pair in graph.edges():
u,v = pair
agony = max(players[u]-players[v],0)
if agony >= max_agony:
pair_max_agony = (u,v)
max_agony = agony
edges_to_be_removed.append(pair_max_agony)
#print("graph: (%d,%d), edge to be removed: %s, agony: %0.4f" % (graph.number_of_nodes(),graph.number_of_edges(),pair_max_agony,max_agony))
graph.remove_edges_from([pair_max_agony])
#print("graph: (%d,%d), edge to be removed: %s" % (graph.number_of_nodes(),graph.number_of_edges(),pair_max_agony))
sub_graphs = filter_big_scc(graph,[pair_max_agony])
if sub_graphs:
for index,sub in enumerate(sub_graphs):
sccs.append(sub)
if not sccs:
return
def scores_of_nodes_in_scc(sccs,players):
from s_c_c import nodes_in_scc
scc_nodes = nodes_in_scc(sccs)
scc_nodes_score_dict = {}
for node in scc_nodes:
scc_nodes_score_dict[node] = players[node]
#print("# scores of nodes in scc: %d" % (len(scc_nodes_score_dict)))
return scc_nodes_score_dict
def scc_based_to_remove_cycle_edges_recursilvely(g,nodes_score):
big_sccs = get_big_sccs(g)
scc_nodes_score_dict = scores_of_nodes_in_scc(big_sccs,nodes_score)
edges_to_be_removed = []
for sub in big_sccs:
scc_edges_to_be_removed = []
remove_cycle_edges_by_agony(sub,scc_nodes_score_dict,scc_edges_to_be_removed)
edges_to_be_removed += scc_edges_to_be_removed
#print(" # edges to be removed: %d" % len(edges_to_be_removed))
return edges_to_be_removed
def scc_based_to_remove_cycle_edges_iterately(g,nodes_score):
from remove_self_loops import remove_self_loops_from_graph
self_loops = remove_self_loops_from_graph(g)
big_sccs = get_big_sccs(g)
scc_nodes_score_dict = scores_of_nodes_in_scc(big_sccs,nodes_score)
edges_to_be_removed = []
if len(big_sccs) == 0:
print("After removal of self loop edgs: %s" % nx.is_directed_acyclic_graph(g))
return self_loops
remove_cycle_edges_by_agony_iterately(big_sccs,scc_nodes_score_dict,edges_to_be_removed)
#print(" # edges to be removed: %d" % len(edges_to_be_removed))
return edges_to_be_removed+self_loops
def remove_cycle_edges(graph_file,players_score):
return remove_cycle_edges_by_agony(graph_file,players_score)