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

import networkx as nx

def filter_big_scc(g,edges_to_be_removed):

        #Given a graph g and edges to be removed

        #Return a list of big scc subgraphs (# of nodes >= 2)

        g.remove_edges_from(edges_to_be_removed)

        sub_graphs = filter(lambda scc: scc.number_of_nodes() >= 2, nx.strongly_connected_component_subgraphs(g))

        return sub_graphs

def get_big_sccs(g):

        self_loop_edges = g.selfloop_edges()

        g.remove_edges_from(g.selfloop_edges())

        num_big_sccs = 0

        edges_to_be_removed = []

        big_sccs = []

        for sub in nx.strongly_connected_component_subgraphs(g):

                number_of_nodes = sub.number_of_nodes()

                if number_of_nodes >= 2:

                        # strongly connected components

                        num_big_sccs += 1

                        big_sccs.append(sub)

        #print(" # big sccs: %d" % (num_big_sccs))

        return big_sccs

def nodes_in_scc(sccs):

        scc_nodes = []

        scc_edges = []

        for scc in sccs:

                scc_nodes += list(scc.nodes())

                scc_edges += list(scc.edges())

        #print("# nodes in big sccs: %d" % len(scc_nodes))

        #print("# edges in big sccs: %d" % len(scc_edges))

        return scc_nodes

def scc_nodes_edges(g):

        scc_nodes = set()

        scc_edges = set()

        num_big_sccs = 0

        num_nodes_biggest_scc = 0

        biggest_scc = None

        for sub in nx.strongly_connected_component_subgraphs(g):

                number_nodes = sub.number_of_nodes()

                if number_nodes >= 2:

                        scc_nodes.update(sub.nodes())

                        scc_edges.update(sub.edges())

                        num_big_sccs += 1

                        if num_nodes_biggest_scc < number_nodes:

                                num_nodes_biggest_scc = number_nodes

                                biggest_scc = sub

        nonscc_nodes = set(g.nodes()) - scc_nodes

        nonscc_edges = set(g.edges()) - scc_edges

        print num_nodes_biggest_scc

        print("num of big sccs: %d" % num_big_sccs)

        if biggest_scc == None:

                return scc_nodes,scc_nodes,nonscc_nodes,nonscc_edges

        print("# nodes in biggest scc: %d, # edges in biggest scc: %d" % (biggest_scc.number_of_nodes(),biggest_scc.number_of_edges()))

        print("# nodes,edges in scc: (%d,%d), # nodes, edges in non-scc: (%d,%d) " % (len(scc_nodes),len(scc_edges),len(nonscc_nodes),len(nonscc_edges)))

        num_of_nodes = g.number_of_nodes()

        num_of_edges = g.number_of_edges()

        print("# nodes in graph: %d, # of edges in graph: %d, percentage nodes, edges in scc: (%0.4f,%0.4f), percentage nodes, edges in non-scc: (%0.4f,%0.4f)" % (num_of_nodes,num_of_edges,len(scc_nodes)*1.0/num_of_nodes,len(scc_edges)*1.0/num_of_edges,len(nonscc_nodes)*1.0/num_of_nodes,len(nonscc_edges)*1.0/num_of_edges))

        return scc_nodes,scc_edges,nonscc_nodes,nonscc_edges

def c_c(graph_file):

        g = nx.read_edgelist(graph_file,create_using = nx.Graph(),nodetype = int)

        graphs = nx.connected_component_subgraphs(g)

        for graph in graphs:

                print graph.number_of_nodes(),graph.number_of_edges()

        print len(graphs)