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

from s_c_c import filter_big_scc

from s_c_c import scc_nodes_edges

from s_c_c import get_big_sccs

from file_io import write_pairs_to_file

import networkx as nx

def get_nodes_degree_dict(g,nodes):

        # get nodes degree dict: key = node, value = (max(d(in)/d(out),d(out)/d(in),"in" or "out")

        in_degrees = g.in_degree(nodes)

        out_degrees = g.out_degree(nodes)

        degree_dict = {}

        for node in nodes:

                in_d = in_degrees[node]

                out_d = out_degrees[node]

                if in_d >= out_d:

                        try:

                                value = in_d * 1.0 / out_d

                        except Exception as e:

                                value = 0

                        f = "in"

                else:

                        try:

                                value = out_d * 1.0 / in_d

                        except Exception as e:

                                value = 0

                        f = "out"

                degree_dict[node] = (value,f)

                #print("node: %d: %s" % (node,degree_dict[node]))

        return degree_dict

def greedy_local_heuristic(sccs,degree_dict,queue):

        edges_to_be_removed = []

        while True:

                graph = sccs.pop()

                temp_nodes_degree_dict = {}

                for node in graph.nodes():

                        temp_nodes_degree_dict[node] = degree_dict[node][0]

                from helper_funs import pick_from_dict

                max_node,_ = pick_from_dict(temp_nodes_degree_dict)

                max_value = degree_dict[max_node]

                #degrees = [(node,degree_dict[node]) for node in list(graph.nodes())]

                #max_node,max_value = max(degrees,key = lambda x: x[1][0])

                if max_value[1] == "in":

                        # indegree > outdegree, remove out-edges

                        edges = [(max_node,o) for o in graph.neighbors(max_node)]

                else:

                        # outdegree > indegree, remove in-edges

                        edges = [(i,max_node) for i in graph.predecessors(max_node)]

                edges_to_be_removed += edges

                sub_graphs = filter_big_scc(graph,edges_to_be_removed)

                if sub_graphs:

                        for index,sub in enumerate(sub_graphs):

                                sccs.append(sub)

                if not sccs:

                        break

        queue.put(edges_to_be_removed)

def remove_cycle_edges_by_mfas(graph_file,nodetype = int):

        g = nx.read_edgelist(graph_file,create_using = nx.DiGraph(),nodetype = nodetype)

        scc_nodes,_,_,_ = scc_nodes_edges(g)

        degree_dict = get_nodes_degree_dict(g,scc_nodes)

        sccs = get_big_sccs(g)

        edges_to_be_removed = []

        from multiprocessing import Process, Queue

        import timeit

        t1 = timeit.default_timer()

        jobs = []

        q = Queue()

        for scc in sccs:

                p = Process(target = greedy_local_heuristic, args = ([scc],degree_dict,q))

                jobs.append(p)

                p.start()

        for p in jobs:

                p.join()

                edges_to_be_removed += list(q.get())

        t2 = timeit.default_timer()

        print("mfas time usage: %0.4f s" % (t2 - t1))

        #greedy_local_heuristic(sccs,degree_dict,edges_to_be_removed)

        edges_to_be_removed = list(set(edges_to_be_removed))

        g.remove_edges_from(edges_to_be_removed)

        edges_to_be_removed_file = graph_file[:len(graph_file)-6] + "_removed_by_mfas.edges"

        write_pairs_to_file(edges_to_be_removed,edges_to_be_removed_file)

        return edges_to_be_removed

def mfas_performance(graph_file,gt_edges_file):

        edges_to_be_removed = remove_cycle_edges_by_mfas(graph_file)

        from measures import report_performance

        report_performance(gt_edges_file,edges_to_be_removed,"MFAS")

import argparse

if __name__ == "__main__":

        parser = argparse.ArgumentParser()

        parser.add_argument("-g","--graph_file",default= " ", help = "input graph file name (edges list)")

        parser.add_argument("-t","--gt_edges_file",default = None, help = "ground truth edges")

        args = parser.parse_args()

        graph_file = args.graph_file

        gt_file = args.gt_edges_file

        mfas_performance(graph_file,gt_file)