def draw_leg(self):
# nx.draw(self.LEG)
print "Connected Components of LEG:\n" + str(list(nx.connected_components(self.leg)))
python类connected_components()的实例源码
def is_feasible(self):
for cc in nx.connected_components(self.leg):
loci_dct = collections.defaultdict(set)
for label in cc:
species, locus = label
loci_dct[species].add(locus)
for species in loci_dct.keys():
if len(loci_dct[species]) >= 2:
return False
return True
def is_feasible(self):
for cc in nx.connected_components(self.LEG):
for i in xrange(0, len(cc)):
for j in xrange(i+1, len(cc)):
if list(cc)[i].split('_')[0] == list(cc)[j].split('_')[0]:
return False
return True
def get_subgraphs(graph):
subgraphs = []
for subgraph in networkx.connected_components(graph):
if len(subgraph) > 0:
subgraphs.append(graph.subgraph(subgraph))
return subgraphs
def sem_clust(self, w2p, simsdict):
''' Baseline SEMCLUST method (dynamic thresholding), based on:
Marianna Apidianaki, Emilia Verzeni, and Diana McCarthy. Semantic
Clustering of Pivot Paraphrases. In LREC 2014.
Builds a graph where nodes are words, and edges connect words that
have a connection in <w2p>. Weights edges by the values given in
<simsdict>.
:param w2p: word -> {paraphrase: score} dictionary, used to decide which nodes to connect with edges
:param simsdict: word -> {paraphrase: score} OR word -> vector, used for edge weights
:return:
'''
self.reset_sense_clustering()
wordlist = self.pp_dict.keys()
oov = [w for w in wordlist if w not in w2p or w not in simsdict]
if len(oov) > 0:
sys.stderr.write('WARNING: Paraphrases %s are OOV. '
'Removing from ppset.\n' % str(oov))
wordlist = list(set(wordlist) - set(oov))
if len(wordlist) == 1:
self.add_sense_cluster([wordlist[0]])
return
# Using cosine similarity of word-paraphrase vectors:
if type(simsdict.values()[0]) != dict:
similarities = np.array([[1-cosine(simsdict[i], simsdict[j])
for j in wordlist] for i in wordlist])
else:
similarities = np.array([[(1-dict_cosine_dist(simsdict[i], simsdict[j]))
for j in wordlist] for i in wordlist])
gr = sem_clust.toGraph(similarities, wordlist, self.target_word, w2p)
for c in nx.connected_components(gr):
self.add_sense_cluster(c)
def dag(recipe_folder, config, packages="*", format='gml', hide_singletons=False):
"""
Export the DAG of packages to a graph format file for visualization
"""
dag, name2recipes = utils.get_dag(utils.get_recipes(recipe_folder, packages), config)
if hide_singletons:
for node in nx.nodes(dag):
if dag.degree(node) == 0:
dag.remove_node(node)
if format == 'gml':
nx.write_gml(dag, sys.stdout.buffer)
elif format == 'dot':
write_dot(dag, sys.stdout)
elif format == 'txt':
subdags = sorted(map(sorted, nx.connected_components(dag.to_undirected())))
subdags = sorted(subdags, key=len, reverse=True)
singletons = []
for i, s in enumerate(subdags):
if len(s) == 1:
singletons += s
continue
print("# subdag {0}".format(i))
subdag = dag.subgraph(s)
recipes = [
recipe for package in nx.topological_sort(subdag)
for recipe in name2recipes[package]]
print('\n'.join(recipes) + '\n')
if not hide_singletons:
print('# singletons')
recipes = [recipe for package in singletons for recipe in
name2recipes[package]]
print('\n'.join(recipes) + '\n')
def test_graph_init():
"""Test graph initialization."""
instream = kevlar.open(data_file('var1.reads.augfastq'), 'r')
graph = kevlar.ReadGraph()
graph.load(kevlar.parse_augmented_fastx(instream))
graph.populate_edges(strict=True)
# 10 reads in the file, but read16f has no valid connections due to error
assert len(graph.nodes()) == 10
# The given read shares its interesting k-mer and has compatible overlaps
# with 6 other reads (read13f and read15f have errors).
r23name = 'read23f start=67,mutations=0'
assert len(graph[r23name]) == 6
# Test the values of one of the edges.
r35name = 'read35f start=25,mutations=0'
assert graph[r23name][r35name]['offset'] == 42
assert graph[r23name][r35name]['overlap'] == 58
# Should all be a single CC
assert len(list(connected_components(graph))) == 2
assert len([p for p in graph.partitions()]) == 1
r8name = 'read8f start=8,mutations=0'
r37name = 'read37f start=9,mutations=0'
assert graph[r37name][r8name]['offset'] == 1
assert graph[r37name][r8name]['overlap'] == 99
pair = OverlappingReadPair(
tail=graph.get_record(r8name), head=graph.get_record(r37name),
offset=1, overlap=99, sameorient=True, swapped=False
)
assert merge_pair(pair) == ('CACTGTCCTTACAGGTGGATAGTCGCTTTGTAATAAAAGAGTTAC'
'ACCCCGGTTTTTAGAAGTCTCGACTTTAAGGAAGTGGGCCTACGG'
'CGGAAGCCGTC')
def partitions(self, dedup=True, minabund=None, maxabund=None,
abundfilt=False):
"""
Retrieve all partitions (connected components) from this graph.
The `minabund` and `maxabund` parameters are used at graph construction
time to filter out k-mers whose abundance is too large or small. If
`abundfilt` is true, the minimum bundance is also applied to the number
of sequences (reads or contigs) in the partition.
"""
for cc in sorted(networkx.connected_components(self), reverse=True,
# Sort first by number of reads, then by read names
key=lambda c: (len(c), sorted(c))):
if len(cc) == 1 and list(cc)[0] in self.readnames:
continue # Skip unassembled input reads
if dedup:
partition = ReadGraph()
readstream = [self.get_record(readid) for readid in cc]
partition.load(readstream, minabund, maxabund, dedup=True)
assert partition.number_of_nodes() > 0
if abundfilt:
if minabund and partition.number_of_nodes() < minabund:
continue # Skip partitions that are too small
yield partition
else:
yield cc
def extract_inter_function_cfg():
#loop over every segments
#seg: the starting address for each segments
#initialized a directed graph to store cfg
cfg = nx.DiGraph()
for seg in Segments():
if SegName(seg) == ".text" or SegName(seg) == ".plt":
functions = Functions(seg)
for func_ea in functions:
#It will add some isolated node into the graph
cfg.add_node(func_ea)
for ref in CodeRefsTo(func_ea, 1):
calling_func = get_func(ref)
if not calling_func:
continue
calling_func_startEA = calling_func.startEA
cfg.add_edge(calling_func_startEA, func_ea)
#for ref in CodeRefsFrom(func_ea, 1):
# print " calling %s(0x%x)" % (GetFunctionName(ref), ref)
nodes = cfg.nodes()
for node in nodes:
ns = cfg.successors(node)
if not ns:
print hex(node)
#print nx.connected_components(cfg)
#nx.draw(cfg)
#plt.show()
#plt.savefig("graph.png", dpi=1000)
'''
#testing
print cfg.number_of_nodes()
print cfg.number_of_edges()
#print cfg.node()
nodes = cfg.nodes()
print
for node in nodes:
print "parent: "
print hex(node)
print "child: "
ns = cfg.successors(node)
for n in ns:
print hex(n)
#endtesting
'''
return cfg
def face_adjacency(faces, return_edges=False):
'''
Returns an (n,2) list of face indices.
Each pair of faces in the list shares an edge, making them adjacent.
Arguments
----------
faces: (n, d) int, set of faces referencing vertices by index
return_edges: bool, return the edges shared by adjacent faces
Returns
---------
adjacency: (m,2) int, indexes of faces that are adjacent
if return_edges:
edges: (m,2) int, indexes of vertices which make up the
edges shared by the adjacent faces
Example
----------
This is useful for lots of things, such as finding connected components:
graph = nx.Graph()
graph.add_edges_from(mesh.face_adjacency)
groups = nx.connected_components(graph_connected)
'''
# first generate the list of edges for the current faces
# also return the index for which face the edge is from
edges, edge_face_index = faces_to_edges(faces, return_index = True)
edges.sort(axis=1)
# this will return the indices for duplicate edges
# every edge appears twice in a well constructed mesh
# so for every row in edge_idx, edges[edge_idx[*][0]] == edges[edge_idx[*][1]]
# in this call to group rows, we discard edges which don't occur twice
edge_groups = group_rows(edges, require_count=2)
if len(edge_groups) == 0:
log.error('No adjacent faces detected! Did you merge vertices?')
# the pairs of all adjacent faces
# so for every row in face_idx, self.faces[face_idx[*][0]] and
# self.faces[face_idx[*][1]] will share an edge
face_adjacency = edge_face_index[edge_groups]
if return_edges:
face_adjacency_edges = edges[edge_groups[:,0]]
return face_adjacency, face_adjacency_edges
return face_adjacency
