Subversion Repositories an-fpga-implementation-of-low-latency-noc-based-mpsoc

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)