URL
https://opencores.org/ocsvn/an-fpga-implementation-of-low-latency-noc-based-mpsoc/an-fpga-implementation-of-low-latency-noc-based-mpsoc/trunk
Subversion Repositories an-fpga-implementation-of-low-latency-noc-based-mpsoc
[/] [an-fpga-implementation-of-low-latency-noc-based-mpsoc/] [trunk/] [mpsoc/] [remove_cycle/] [remove_cycle_edges_by_hierarchy_greedy.py] - Rev 52
Go to most recent revision | Compare with Previous | Blame | View Log
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)
Go to most recent revision | Compare with Previous | Blame | View Log