本文整理汇总了Python中networkx.all_simple_paths函数的典型用法代码示例。如果您正苦于以下问题:Python all_simple_paths函数的具体用法?Python all_simple_paths怎么用?Python all_simple_paths使用的例子?那么恭喜您, 这里精选的函数代码示例或许可以为您提供帮助。
在下文中一共展示了all_simple_paths函数的20个代码示例,这些例子默认根据受欢迎程度排序。您可以为喜欢或者感觉有用的代码点赞,您的评价将有助于我们的系统推荐出更棒的Python代码示例。
示例1: test_all_simple_paths_multigraph
def test_all_simple_paths_multigraph():
G = nx.MultiGraph([(1, 2), (1, 2)])
paths = nx.all_simple_paths(G, 1, 1)
assert_equal(paths, [])
nx.add_path(G, [3, 1, 10, 2])
paths = nx.all_simple_paths(G, 1, 2)
assert_equal(set(tuple(p) for p in paths), {(1, 2), (1, 2), (1, 10, 2)})
开发者ID:wkschwartz,项目名称:networkx,代码行数:7,代码来源:test_simple_paths.py
示例2: vote
def vote(src,dest,intent):
path = []
confidence = 0
if(intent == 0): #Good Guy. Non Malicious
path = netshortestpath(src ,dest)
confidence = get_weight(path)
#path,confidence=BestBottleneckPath(src,dest)
return (path,confidence)
if(intent == 1): #Evil Guy. malicious
for paths in nx.all_simple_paths(graph_extern, src, dest):
temp= get_weight(paths)
if (temp>confidence):
confidence = temp
path = copy.deepcopy(paths)
#return shortest path weigth -1
return (path,(get_weight(netshortestpath(src, dest))-1))
if(intent == 2): #Good Guy. mis-configured
for paths in nx.all_simple_paths(graph_extern, src, dest):
temp= get_weight(paths)
if (temp>confidence):
confidence = temp
path = copy.deepcopy(paths)
break
#return shortest path weigth -1
return (path,confidence)
开发者ID:VikasLShetty,项目名称:Jedi,代码行数:29,代码来源:administrators.py
示例3: find_sg_multiple
def find_sg_multiple(G,inode_list,onode_list):
#print 'Input node list:',inode_list
#print 'Output node list:', onode_list
#start = inode_list[0]
oldreltypes = ['s','n','si','ni','sn','sni']
for stop in onode_list:
reltypes = []
for start in inode_list:
#print 'start is:', start, 'stop is:', stop
roads = nx.all_simple_paths(G,start,stop)
roads = list(roads)
path_list = sorted(roads, lambda x,y: 1 if len(x)>len(y) else -1 if len(x)<len(y) else 0)
if len(path_list)>1:
if start==stop:
route = path_list[1]
else:
route = path_list[0]
else:
continue
prev_rel = 'sn'
#print 'Looking at path',route
for i in range(len(route)-1):
etype = G[route[i]][route[i+1]]['edge_attr']
rel = path.add(prev_rel,etype)
if rel == None:
#print 'Path cannot be added at',route[i],'to',route[i+1]
srel = sg_add(prev_rel,etype)
regs = G.predecessors(route[i+1])
if len(regs)<=1:
rel = None
for regulator in regs:
if regulator == route[i]:
continue
found = False
for source in inode_list:
if not nx.has_path(G,source,regulator):
continue
for p in nx.all_simple_paths(G,source,regulator):
ptype = path.path_type(G,p)
rtype = G[regulator][route[i+1]]['edge_attr']
if sg_add(ptype,rtype) == srel:
found = True
break
if found:
break
if found:
continue
else:
rel = None
rel = srel
prev_rel = rel
reltypes.append(rel)
#print 'for end point',stop,'stored relationships are:',reltypes
oldreltypes = list(set(reltypes) & set(oldreltypes))
return oldreltypes
开发者ID:parulm,项目名称:suff_necc,代码行数:55,代码来源:subgraph.py
示例4: test_all_simple_paths_on_non_trivial_graph
def test_all_simple_paths_on_non_trivial_graph():
''' you may need to draw this graph to make sure it is reasonable '''
G = nx.path_graph(5, create_using=nx.DiGraph())
G.add_edges_from([(0, 5), (1, 5), (1, 3), (5, 4), (4, 2), (4, 3)])
paths = nx.all_simple_paths(G, 1, [2, 3])
assert_equal(set(tuple(p) for p in paths), {
(1, 2), (1, 3, 4, 2), (1, 5, 4, 2), (1, 3), (1, 2, 3), (1, 5, 4, 3),
(1, 5, 4, 2, 3)})
paths = nx.all_simple_paths(G, 1, [2, 3], cutoff=3)
assert_equal(set(tuple(p) for p in paths), {
(1, 2), (1, 3, 4, 2), (1, 5, 4, 2), (1, 3), (1, 2, 3), (1, 5, 4, 3)})
paths = nx.all_simple_paths(G, 1, [2, 3], cutoff=2)
assert_equal(set(tuple(p) for p in paths), {(1, 2), (1, 3), (1, 2, 3)})
开发者ID:networkx,项目名称:networkx,代码行数:13,代码来源:test_simple_paths.py
示例5: get_routes
def get_routes(origin, destin, mode, days, hours, weights=WEIGHTS):
key = (origin, destin, mode, days, hours)
if key in ROUTES:
routes = ROUTES[key]
else:
start = time()
graph = get_graph(mode, hours)
ncity = NUMCITIES[days, hours]
print('INFO: Graph was built in {0:.3f}s'
.format(time() - start))
start = time()
routes = list(nx.all_simple_paths(graph, source=origin, target=destin,
cutoff=ncity))
if not routes:
while not routes and ncity < days:
print hours
if hours == 4:
hours = 7
graph = get_graph(mode, hours)
ncity = NUMCITIES[days, hours]
elif hours == 7:
hours = 10
graph = get_graph(mode, hours)
ncity = NUMCITIES[days, hours]
else:
ncity += 1
routes = list(nx.all_simple_paths(graph, source=origin, target=destin,
cutoff=ncity))
else:
roundway = origin == destin
# print 'MAX: ', days, hours, '->', max((len(r) - roundway for r in routes))
if hours > 4:
routes.extend(get_routes(origin, destin, mode, days, 4, weights)[0])
# print 'MAX: ', days, hours, '->', max((len(r) - roundway for r in routes))
elif hours > 7:
routes.extend(get_routes(origin, destin, mode, days, 7, weights)[0])
# print 'MAX: ', days, hours, '->', max((len(r) - roundway for r in routes))
print('INFO: {} routes were calculated in {:.3f}'
.format(len(routes), time() - start))
start = time()
routes = filter_routes(routes)
print('INFO: {} routes were selected in {:.3f}'
.format(len(routes), time() - start))
ROUTES[key] = routes
return routes, hours
开发者ID:abakan,项目名称:euroute.me,代码行数:51,代码来源:router.py
示例6: find_directed_paths
def find_directed_paths(request, project_id=None):
""" Given a set of two or more skeleton IDs, find directed paths of connected neurons between them, for a maximum inner path length as given (i.e. origin and destination not counted). A directed path means that all edges are of the same kind, e.g. presynaptic_to. """
sources = set(int(v) for k,v in request.POST.iteritems() if k.startswith('skeleton_ids['))
if len(sources) < 2:
raise Exception('Need at least 2 skeleton IDs to find directed paths!')
path_length = int(request.POST.get('n_circles', 1))
cursor = connection.cursor()
mins, relations = _clean_mins(request, cursor, int(project_id))
presynaptic_to = relations['presynaptic_to']
graph = nx.DiGraph()
next_sources = sources
all_sources = sources
length = path_length
def rev_args(fn):
def f(arg1, arg2):
fn(arg2, arg1)
return f
# Create a graph by growing the sources
while length > 0 and next_sources:
length -= 1
next_circles = _next_circle(next_sources, cursor)
next_sources = set()
for skid1, c in next_circles.iteritems():
for relationID, targets in c.iteritems():
threshold = mins[relationID]
add_edge = graph.add_edge if relationID == presynaptic_to else rev_args(graph.add_edge)
for skid2, count in targets.iteritems():
if count < threshold:
continue
add_edge(skid1, skid2)
next_sources.add(skid2)
next_sources = next_sources - all_sources
all_sources = all_sources.union(next_sources)
# Find all directed paths between all pairs of inputs
unique = set()
for start, end in combinations(sources, 2):
for paths in [nx.all_simple_paths(graph, start, end, path_length + 1),
nx.all_simple_paths(graph, end, start, path_length + 1)]:
for path in paths:
for node in path:
unique.add(node)
skeleton_ids = tuple(unique - sources)
return HttpResponse(json.dumps([skeleton_ids, _neuronnames(skeleton_ids, project_id)]))
开发者ID:catsop,项目名称:CATMAID,代码行数:49,代码来源:circles.py
示例7: _prune_states
def _prune_states(K, graph, source, sink):
"""
Removes cycles and redundant nodes (that are not reachable from source)
from the subgraph of graph defined by the nodes in K.
"""
# Create a subgraph with the nodes now in K
# Find and remove cycles by deleting the edge between
# the second to last node and the last node of the cycle,
# thus keeping nodes that may be important
# to the trust calculation.
subgraph = graph.subgraph(K)
cycles = nx.simple_cycles(subgraph)
if cycles:
for cycle in cycles:
subgraph.remove_edges_from([(cycle[-2], cycle[-1])])
# Get all paths from source to sink without cycles and redundant nodes
simple_paths = list(nx.all_simple_paths(G=graph, source=source, target=sink))
relevant_nodes = set(chain.from_iterable(simple_paths))
# Remove nodes no longer used (not in simple_paths)
for n in K:
if n not in relevant_nodes:
subgraph.remove_node(n)
return subgraph
开发者ID:marianela4711,项目名称:Veracitor,代码行数:28,代码来源:generate_bn.py
示例8: get_ontology_paths
def get_ontology_paths(basic_ontology, from_type, to_obj):
"""
type-to-type ontology path
:param ontology:
:param from_type:
:param to_obj:
:return:
"""
assert from_type.name in basic_ontology.types
assert to_obj.type.name in basic_ontology.types
graph = basic_ontology.ontology_graph.copy()
assert isinstance(graph, nx.DiGraph)
for function in basic_ontology.functions.values():
if function.valence > 1:
graph.remove_node(function.id)
"""
if from_type is to_obj:
paths = [cycle for cycle in nx.simple_cycles(basic_ontology.ontology_graph) if from_type.id in cycle]
"""
if not nx.has_path(graph, from_type.id, to_obj.type.id):
paths = []
elif from_type == to_obj.type:
paths = [[from_type.id]]
else:
paths = list(nx.all_simple_paths(graph, from_type.id, to_obj.type.id))
path_dict = {key: OntologyPath(basic_ontology, [basic_ontology.get_by_id(id_) for id_ in path] + [to_obj], key)
for key, path in enumerate(paths)}
return path_dict
开发者ID:allenai,项目名称:EquationTree,代码行数:35,代码来源:get_ontology_paths.py
示例9: pathOD_incidence
def pathOD_incidence(graph, haspath=False):
"""
get path-OD incidence matrix
Parameters
----------
graph: graph object
haspath: if True, simple has already been set before
Return value
------------
C: matrix of incidence path-OD
"""
nnode, nlink = graph.numnodes, graph.numlinks
npair = len(graph.ODs.keys())
G = nx.DiGraph()
G.add_nodes_from(graph.nodes.keys())
G.add_edges_from([(key[0],key[1]) for key in graph.links.keys()])
if not haspath:
for OD in graph.ODs.itervalues():
for nodes_on_path in nx.all_simple_paths(G, OD.o, OD.d):
graph.add_path_from_nodes(nodes_on_path)
npath = len(graph.paths)
entries, I, J = [], [], []
for OD in graph.ODs.itervalues():
u = OD.o; v=OD.d
indcol = graph.indods[(u,v)]
for path in graph.paths.iterkeys():
if (u == path[0]) and (v == path[-1]):
indrow = graph.indpaths[path]
entries.append(1.0); I.append(indrow), J.append(indcol)
C = spmatrix(entries, I, J, (npath, npair))
return C
开发者ID:cedavidyang,项目名称:bridge_ranking,代码行数:34,代码来源:ue_util.py
示例10: write_sat_dcbusprop2
def write_sat_dcbusprop2(G,buslist, genlist):
H = copy.deepcopy(G)
for i in buslist:
f.write('(assert (=> (not (or ')
for j in genlist:
gen_temp = copy.deepcopy(gens)
gen_temp.remove(j)
H.remove_nodes_from(gen_temp)
for path in nx.all_simple_paths(H,i,j):
f.write(' (and')
for k in range(1,len(path)):
if path[k] in gens:
f.write(' (= g'+str(path[k])+' true)')
elif path[k] in busac:
f.write(' (= b'+str(path[k])+' true)')
elif path[k] in null:
f.write(' (= b'+str(path[k])+' true)')
elif path[k] in rus:
f.write(' (= r'+str(path[k])+' true)')
for m in range(0,len(path)-1):
if path[m] in busdc and path[m+1] in rus:
pass
elif path[m] in rus and path[m+1] in busdc:
pass
elif path[m] < path[m+1]:
f.write(' (= c'+str(path[m])+str(path[m+1])+' true)')
elif path[m+1] < path[m]:
f.write(' (= c'+str(path[m+1])+str(path[m])+' true)')
f.write(')')
H = copy.deepcopy(G)
f.write(')) (= b'+str(i)+' false)))\n')
开发者ID:ericskim,项目名称:tulip-control,代码行数:31,代码来源:AES_specgen.py
示例11: dcbusspec
def dcbusspec(G,busno,gen):
"""Creates specifications for when DC bus gets powered
Parameters
----------
G : networkX graph
busno : node
dc bus
gen : node
generator
"""
paths = []
C = []
temp = []
edges = []
D = copy.deepcopy(G)
gens2 = copy.deepcopy(gens)
gens2.remove(gen)
D.remove_nodes_from(gens2)
for path in nx.all_simple_paths(D,busno,gen,cutoff=None):
paths.append(path)
for j in range(0,len(paths)):
f.write('guarantees += '"'"'&\\n\\t[]((B'+str(busno)+str(gen)+str(j)+') -> (b'+str(busno)+'=1))'"'"'\n')
开发者ID:ericskim,项目名称:tulip-control,代码行数:26,代码来源:AES_specgen.py
示例12: GetLocalBridge
def GetLocalBridge(g, topic, windowsize, date):
'''
通过遍历边,对是否为捷径进行判断,将跨度最大的前10名存放在数据库中
'''
localbridge = []
edges_list = g.edges()
for (a,b) in edges_list:
a_n = set(g.neighbors(a))
b_n = set(g.neighbors(b))
l_a_n = len(a_n)
l_b_n = len(b_n)
l_ab_n = len(a_n & b_n)
if (l_a_n!=1)&(l_b_n!=1)&(l_ab_n==0):
paths_list = nx.all_simple_paths(g, source=a, target=b)
span_ab = 0
len_path = 0
for path in paths_list:
len_path += 1
if len(path) > span_ab:
span_ab = len(path)
if len_path == 1:
span_ab = 10000 # 当去除了仅有的那条边之后没有其他路径能够连接ab,则使跨度为10000
localbridge.append((a, b, span_ab, l_a_n, l_b_n))
SaveLocalBridge(topic, date, windowsize, localbridge) # 存放localbridge数组
开发者ID:huxiaoqian,项目名称:case,代码行数:26,代码来源:localbridge.py
示例13: slice_graph
def slice_graph(graph, node, frontier, include_frontier=False):
"""
Generate a slice of the graph from the head node to the given frontier.
:param networkx.DiGraph graph: The graph to work on.
:param node: The starting node in the graph.
:param frontier: A list of frontier nodes.
:param bool include_frontier: Whether the frontier nodes are included in the slice or not.
:return: A subgraph.
:rtype: networkx.DiGraph
"""
subgraph = networkx.DiGraph()
for frontier_node in frontier:
for simple_path in networkx.all_simple_paths(graph, node, frontier_node):
for src, dst in zip(simple_path, simple_path[1:]):
if include_frontier or (src not in frontier and dst not in frontier):
subgraph.add_edge(src, dst)
if not list(subgraph.nodes):
# HACK: FIXME: for infinite loop nodes, this would return an empty set, so we include the loop body itself
# Make sure this makes sense (EDG thinks it does)
if (node, node) in graph.edges:
subgraph.add_edge(node, node)
return subgraph
开发者ID:AmesianX,项目名称:angr,代码行数:25,代码来源:region_identifier.py
示例14: get_all_simple_path
def get_all_simple_path(self, source, dest):
"""Get all simple path from a point to an other.
Return
------
Return a networkX list of path
"""
source_node = None
dest_node = None
if source:
for i in self.subnet_list:
if Ip.ListContains([i], source):
source_node = i
break
if dest:
for i in self.subnet_list:
if Ip.ListContains([i], dest):
dest_node = i
break
if not source or not dest:
for node in self.graph.nodes(data=True):
if node[1]['object'].marker_type == 'from':
source_node = node[0]
if node[1]['object'].marker_type == 'to':
dest_node = node[0]
if not source_node or not self.multidigraph.has_node(source_node)\
or not dest_node or not self.multidigraph.has_node(dest_node):
raise
return nx.all_simple_paths(self.multidigraph, source_node, dest_node)
开发者ID:hellox-project,项目名称:springbok,代码行数:34,代码来源:NetworkGraph.py
示例15: least_overlapping_backup_path
def least_overlapping_backup_path(G):
for n, nattr in G.nodes(data=True):
pp = nattr['primary_paths']
bp = nattr['backup_paths']
bnh = nattr['backup_next_hop']
print "\nCalculating Node = %d" % n
for m, mattr in G.nodes(data=True):
if m == n:
pp.append([])
bp.append([])
bnh[m] = None
else:
ppx = nx.shortest_path(G, source=n, target=m)
pp.append(ppx)
pm = nx.all_simple_paths(G, source=n, target=m)
# random.shuffle(pm)
bp.append(get_single_backup(ppx, pm))
bnh[m] = (bp[m][1])
sys.stdout.write('.')
# print "Path Matrix of %d to %d = %s" % (n, m, pm)
# print "Primary_path of %d to %d = %s" % (n, m, pp[m])
# print "Backup_path of %d to %d = %s" % (n, m, bp[m])
# print "Backup_next_hop of %d to %d = %.0f" % (n, m, bnh[m])
nattr['primary_paths'] = pp
nattr['backup_paths'] = bp
nattr['backup_next_hop'] = bnh
开发者ID:BeccaMG,项目名称:adhoc-backup-path,代码行数:27,代码来源:least_overlapping_backup_path.py
示例16: find_same_level_regions
def find_same_level_regions(region):
# Load graph
graph = load_graph()
if not graph:
logger.error("Can't trace multiple regions: Region call graph not available.\n\
Run cere profile.\n\
Tracing region {0}".format(region))
return
# Find region node id
region_node = get_region_id(region, graph)
#Find roots
roots = [n for n,d in graph.in_degree().items() if d==0]
#Compute for every nodes, the max distance from himself to each root
max_path_len = {}
for root in roots:
for n, d in graph.nodes(data=True):
if n not in max_path_len: max_path_len[n]=0
#Get every paths from the current root to the node
paths = list(nx.all_simple_paths(graph, root, n))
#Keep the max length path
for path in paths:
if len(path)-1 > max_path_len[n]:
max_path_len[n] = len(path)-1
#Keep region which have the same depth than the requested region
for n, p in max_path_len.iteritems():
if p == max_path_len[region_node]:
yield graph.node[n]['_name']
开发者ID:rayahz,项目名称:cere-1,代码行数:31,代码来源:__init__.py
示例17: get_maximal_path_length
def get_maximal_path_length(self):
"""
Get the maximal path length from all simple paths that traverses the projection graph from
one leave node to another.
.. note::
This measure is sensitive to the resolution of a projection
the same way the length of a coastline is sensitive to the resoltuion.
.. warning::
Whether this code will stay in the library or not depends
on future evaluation of the usefulness of this and similar descriptors.
"""
import networkx as nx
maxl = 0
for i, node1 in enumerate(self.proj_graph.nodes()):
for j, node2 in enumerate(self.proj_graph.nodes()):
if j <= i:
continue
all_paths = nx.all_simple_paths(self.proj_graph, node1, node2)
for path in all_paths:
l = self._get_path_length(path)
if l > maxl:
maxl = l
return maxl
开发者ID:pkerpedjiev,项目名称:forgi,代码行数:26,代码来源:projection2d.py
示例18: get_long_walk_score
def get_long_walk_score(node1, node2, graph):
edge_removed = False
if graph.has_edge(node1, node2):
edge_removed = True
edge_data = graph[node1][node2]
graph.remove_edge(node1, node2)
all_simple_paths = nx.all_simple_paths(graph, source=node1, target=node2, cutoff=PATH_LENGTH_CUTOFF)
output = 0
num_paths = 0
for path in all_simple_paths:
path_score = 1
for loc1,loc2 in zip(*(path[i:] for i in [0,1])): # for every connected pair
dat = graph[loc1][loc2]
num_lines = dat["first_user_num_lines"]+dat["second_user_num_lines"]
path_score *= (1 - 1/float(num_lines+1) )
output = max(output,path_score)
num_paths += 1
if edge_removed:
graph.add_edge(node1, node2, attr_dict=edge_data)
return output
开发者ID:jayhack,项目名称:Chatous,代码行数:25,代码来源:feature_functions.py
示例19: _generate_path
def _generate_path(self, topo, src_mac, dst_mac, src_port,
dst_port, src_dpid, dst_dpid):
"""Generate path method."""
net = nx.DiGraph(data=topo)
net.add_node(src_mac)
net.add_node(dst_mac)
net.add_edge(int(src_dpid), src_mac, {'port': int(src_port)})
net.add_edge(src_mac, int(src_dpid))
net.add_edge(int(dst_dpid), dst_mac, {'port': int(dst_port)})
net.add_edge(dst_mac, int(dst_dpid))
target_path = None
try:
path = nx.shortest_path(net, src_mac, dst_mac)
path2 = nx.shortest_path(net, src_mac, dst_mac)
path2.pop()
path2.pop(0)
list_load = check_switch_load(path2, data_collection.switch_stat, constant.load_limitation)
if len(list_load) > 0:
# print 'lui', list_load
all_paths = nx.all_simple_paths(net, src_mac, dst_mac)
path_list = list(all_paths)
target_path_index, target_path_cost = calculate_least_cost_path(path_list, data_collection.switch_stat, net)
target_path = path_list[target_path_index]
else:
target_path = path
print 'tarrr', target_path
except Exception:
target_path = None
return target_path
开发者ID:hsnl-dev,项目名称:vcpe-hub,代码行数:30,代码来源:forwarding.py
示例20: get_assemblie
def get_assemblie(G,read_db):
contigs={}
if len(G.nodes())>1:
starting_nodes=[n for n in G.nodes() if G.in_degree(n)==0]
ending_nodes=[n for n in G.nodes() if G.out_degree(n)==0]
paths=[]
for start_node in starting_nodes:
for end_node in ending_nodes:
two_nodes_paths=nx.all_simple_paths(G,start_node,end_node)
for path in two_nodes_paths:
print path
contig_key='contig_'+':'.join(path)
contigs[contig_key]=read_db[path[0]]
for idx in range(1,len(path)):
prev,current=path[idx-1],path[idx]
seq=read_db[current]
#pdb.set_trace()
overlap=int(G[prev][current]["label"])
contigs[contig_key]+=seq[overlap:]
#contigs.append(contig)
else:
contig_key='contig_'+G.nodes()[0]
contigs[contig_key]=read_db[G.nodes()[0]]
return contigs
开发者ID:chjiao,项目名称:Metagenomics,代码行数:27,代码来源:plot_overlap_graph_label4_assembly.py
注:本文中的networkx.all_simple_paths函数示例由纯净天空整理自Github/MSDocs等源码及文档管理平台,相关代码片段筛选自各路编程大神贡献的开源项目,源码版权归原作者所有,传播和使用请参考对应项目的License;未经允许,请勿转载。 |
请发表评论