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/] [s_c_c.py] - Rev 52
Go to most recent revision | Compare with Previous | Blame | View Log
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)
Go to most recent revision | Compare with Previous | Blame | View Log