本文整理汇总了Python中networkx.single_source_dijkstra_path函数的典型用法代码示例。如果您正苦于以下问题：Python single_source_dijkstra_path函数的具体用法？Python single_source_dijkstra_path怎么用？Python single_source_dijkstra_path使用的例子？那么恭喜您, 这里精选的函数代码示例或许可以为您提供帮助。
在下文中一共展示了single_source_dijkstra_path函数的20个代码示例，这些例子默认根据受欢迎程度排序。您可以为喜欢或者感觉有用的代码点赞，您的评价将有助于我们的系统推荐出更棒的Python代码示例。
示例1: test_dijkstra
def test_dijkstra(self):
(D, P) = nx.single_source_dijkstra(self.XG, 's')
validate_path(self.XG, 's', 'v', 9, P['v'])
assert_equal(D['v'], 9)
validate_path(
self.XG, 's', 'v', 9, nx.single_source_dijkstra_path(self.XG, 's')['v'])
assert_equal(dict(
nx.single_source_dijkstra_path_length(self.XG, 's'))['v'], 9)
validate_path(
self.XG, 's', 'v', 9, nx.single_source_dijkstra(self.XG, 's')[1]['v'])
validate_path(
self.MXG, 's', 'v', 9, nx.single_source_dijkstra_path(self.MXG, 's')['v'])
GG = self.XG.to_undirected()
# make sure we get lower weight
# to_undirected might choose either edge with weight 2 or weight 3
GG['u']['x']['weight'] = 2
(D, P) = nx.single_source_dijkstra(GG, 's')
validate_path(GG, 's', 'v', 8, P['v'])
assert_equal(D['v'], 8) # uses lower weight of 2 on u<->x edge
validate_path(GG, 's', 'v', 8, nx.dijkstra_path(GG, 's', 'v'))
assert_equal(nx.dijkstra_path_length(GG, 's', 'v'), 8)
validate_path(self.XG2, 1, 3, 4, nx.dijkstra_path(self.XG2, 1, 3))
validate_path(self.XG3, 0, 3, 15, nx.dijkstra_path(self.XG3, 0, 3))
assert_equal(nx.dijkstra_path_length(self.XG3, 0, 3), 15)
validate_path(self.XG4, 0, 2, 4, nx.dijkstra_path(self.XG4, 0, 2))
assert_equal(nx.dijkstra_path_length(self.XG4, 0, 2), 4)
validate_path(self.MXG4, 0, 2, 4, nx.dijkstra_path(self.MXG4, 0, 2))
validate_path(
self.G, 's', 'v', 2, nx.single_source_dijkstra(self.G, 's', 'v')[1]['v'])
validate_path(
self.G, 's', 'v', 2, nx.single_source_dijkstra(self.G, 's')[1]['v'])
validate_path(self.G, 's', 'v', 2, nx.dijkstra_path(self.G, 's', 'v'))
assert_equal(nx.dijkstra_path_length(self.G, 's', 'v'), 2)
# NetworkXError: node s not reachable from moon
assert_raises(nx.NetworkXNoPath, nx.dijkstra_path, self.G, 's', 'moon')
assert_raises(
nx.NetworkXNoPath, nx.dijkstra_path_length, self.G, 's', 'moon')
validate_path(self.cycle, 0, 3, 3, nx.dijkstra_path(self.cycle, 0, 3))
validate_path(self.cycle, 0, 4, 3, nx.dijkstra_path(self.cycle, 0, 4))
assert_equal(
nx.single_source_dijkstra(self.cycle, 0, 0), ({0: 0}, {0: [0]}))
开发者ID:AllenDowney，项目名称:networkx，代码行数:49，代码来源:test_weighted.py
示例2: hirarcy
def hirarcy(self, c, files_dict):
edges = []
interfaces = 'select path, superClass from classes'
files_Names = [x.split(".")[-1] for x in files_dict]
pathNames = {}
for row in c.execute(interfaces):
nameClass = (row[0]).split(".")[-1]
pathNames[nameClass] = row[0]
nameSuper = (row[1]).split(".")[-1]
if (nameClass in files_Names):
sup = 'root'
if (nameSuper in files_Names):
sup = nameSuper
edges.append((sup, nameClass))
g = networkx.DiGraph()
g.add_node('root')
g.add_edges_from(edges)
degs = g.out_degree()
degsIN = g.in_degree()
succ = dict(networkx.bfs_successors(g, 'root'))
for s in succ:
succ[s] = len(succ[s])
paths = networkx.single_source_dijkstra_path(g, 'root')
depth = {}
for n in g.nodes():
depth[n] = 2
if (n in paths):
depth[n] = len(paths[n])
self.addFromDict(files_dict,degs,pathNames)
self.addFromDict(files_dict,degsIN,pathNames)
self.addFromDict(files_dict,succ,pathNames)
self.addFromDict(files_dict,depth,pathNames)
return files_Names,
开发者ID:amir9979，项目名称:Debugger，代码行数:33，代码来源:OOMethods.py
示例3: test_dijkstra
def test_dijkstra(self):
(D,P)= nx.single_source_dijkstra(self.XG,'s')
assert_equal(P['v'], ['s', 'x', 'u', 'v'])
assert_equal(D['v'],9)
assert_equal(nx.single_source_dijkstra_path(self.XG,'s')['v'],
['s', 'x', 'u', 'v'])
assert_equal(nx.single_source_dijkstra_path_length(self.XG,'s')['v'],9)
assert_equal(nx.single_source_dijkstra(self.XG,'s')[1]['v'],
['s', 'x', 'u', 'v'])
assert_equal(nx.single_source_dijkstra_path(self.MXG,'s')['v'],
['s', 'x', 'u', 'v'])
GG=self.XG.to_undirected()
# make sure we get lower weight
# to_undirected might choose either edge with weight 2 or weight 3
GG['u']['x']['weight']=2
(D,P)= nx.single_source_dijkstra(GG,'s')
assert_equal(P['v'] , ['s', 'x', 'u', 'v'])
assert_equal(D['v'],8) # uses lower weight of 2 on u<->x edge
assert_equal(nx.dijkstra_path(GG,'s','v'), ['s', 'x', 'u', 'v'])
assert_equal(nx.dijkstra_path_length(GG,'s','v'),8)
assert_equal(nx.dijkstra_path(self.XG2,1,3), [1, 4, 5, 6, 3])
assert_equal(nx.dijkstra_path(self.XG3,0,3), [0, 1, 2, 3])
assert_equal(nx.dijkstra_path_length(self.XG3,0,3),15)
assert_equal(nx.dijkstra_path(self.XG4,0,2), [0, 1, 2])
assert_equal(nx.dijkstra_path_length(self.XG4,0,2), 4)
assert_equal(nx.dijkstra_path(self.MXG4,0,2), [0, 1, 2])
assert_equal(nx.single_source_dijkstra(self.G,'s','v')[1]['v'],
['s', 'u', 'v'])
assert_equal(nx.single_source_dijkstra(self.G,'s')[1]['v'],
['s', 'u', 'v'])
assert_equal(nx.dijkstra_path(self.G,'s','v'), ['s', 'u', 'v'])
assert_equal(nx.dijkstra_path_length(self.G,'s','v'), 2)
# NetworkXError: node s not reachable from moon
assert_raises(nx.NetworkXNoPath,nx.dijkstra_path,self.G,'s','moon')
assert_raises(nx.NetworkXNoPath,nx.dijkstra_path_length,self.G,'s','moon')
assert_equal(nx.dijkstra_path(self.cycle,0,3),[0, 1, 2, 3])
assert_equal(nx.dijkstra_path(self.cycle,0,4), [0, 6, 5, 4])
assert_equal(nx.single_source_dijkstra(self.cycle,0,0),({0:0}, {0:[0]}) )
开发者ID:CipherHat，项目名称:networkx，代码行数:47，代码来源:test_weighted.py
示例4: compute_shortest_paths
def compute_shortest_paths(self, ydim):
start = time.time()
self.source = self.N.nodes()[argmin(self.P[self.N.nodes(), ydim])]
self.shortest_paths = nx.single_source_dijkstra_path(self.N,
self.source)
self.max_path_len = max(nx.single_source_dijkstra_path_length(self.N,
self.source).values())
print 'G compute time: %f seconds' % (time.time() - start)
开发者ID:cjauvin，项目名称:pypetree，代码行数:8，代码来源:modified_vl_reconstruction.py
示例5: test_dijkstra
def test_dijkstra(self):
(D,P)= nx.single_source_dijkstra(self.XG,'s')
assert_equal(P['v'], ['s', 'x', 'u', 'v'])
assert_equal(D['v'],9)
assert_equal(nx.single_source_dijkstra_path(self.XG,'s')['v'],
['s', 'x', 'u', 'v'])
assert_equal(nx.single_source_dijkstra_path_length(self.XG,'s')['v'],9)
assert_equal(nx.single_source_dijkstra(self.XG,'s')[1]['v'],
['s', 'x', 'u', 'v'])
assert_equal(nx.single_source_dijkstra_path(self.MXG,'s')['v'],
['s', 'x', 'u', 'v'])
GG=self.XG.to_undirected()
(D,P)= nx.single_source_dijkstra(GG,'s')
assert_equal(P['v'] , ['s', 'x', 'u', 'v'])
assert_equal(D['v'],8) # uses lower weight of 2 on u<->x edge
assert_equal(nx.dijkstra_path(GG,'s','v'), ['s', 'x', 'u', 'v'])
assert_equal(nx.dijkstra_path_length(GG,'s','v'),8)
assert_equal(nx.dijkstra_path(self.XG2,1,3), [1, 4, 5, 6, 3])
assert_equal(nx.dijkstra_path(self.XG3,0,3), [0, 1, 2, 3])
assert_equal(nx.dijkstra_path_length(self.XG3,0,3),15)
assert_equal(nx.dijkstra_path(self.XG4,0,2), [0, 1, 2])
assert_equal(nx.dijkstra_path_length(self.XG4,0,2), 4)
assert_equal(nx.dijkstra_path(self.MXG4,0,2), [0, 1, 2])
assert_equal(nx.single_source_dijkstra(self.G,'s','v')[1]['v'],
['s', 'u', 'v'])
assert_equal(nx.single_source_dijkstra(self.G,'s')[1]['v'],
['s', 'u', 'v'])
assert_equal(nx.dijkstra_path(self.G,'s','v'), ['s', 'u', 'v'])
assert_equal(nx.dijkstra_path_length(self.G,'s','v'), 2)
# NetworkXError: node s not reachable from moon
assert_raises(nx.NetworkXNoPath,nx.dijkstra_path,self.G,'s','moon')
assert_raises(nx.NetworkXNoPath,nx.dijkstra_path_length,self.G,'s','moon')
assert_equal(nx.dijkstra_path(self.cycle,0,3),[0, 1, 2, 3])
assert_equal(nx.dijkstra_path(self.cycle,0,4), [0, 6, 5, 4])
assert_equal(nx.single_source_dijkstra(self.cycle,0,0),(0, [0]) )
开发者ID:aaronmcdaid，项目名称:networkx，代码行数:44，代码来源:test_weighted.py
示例6: test_bidirectional_dijkstra
def test_bidirectional_dijkstra(self):
assert_equal(nx.bidirectional_dijkstra(self.XG, "s", "v"), (9, ["s", "x", "u", "v"]))
assert_equal(nx.bidirectional_dijkstra(self.G, "s", "v"), (2, ["s", "x", "v"]))
assert_equal(nx.bidirectional_dijkstra(self.cycle, 0, 3), (3, [0, 1, 2, 3]))
assert_equal(nx.bidirectional_dijkstra(self.cycle, 0, 4), (3, [0, 6, 5, 4]))
assert_equal(nx.bidirectional_dijkstra(self.XG3, 0, 3), (15, [0, 1, 2, 3]))
assert_equal(nx.bidirectional_dijkstra(self.XG4, 0, 2), (4, [0, 1, 2]))
# need more tests here
assert_equal(nx.dijkstra_path(self.XG, "s", "v"), nx.single_source_dijkstra_path(self.XG, "s")["v"])
开发者ID:Bludge0n，项目名称:AREsoft，代码行数:10，代码来源:test_weighted.py
示例7: __configure_routing
def __configure_routing(self):
for n in self.graph:
self.routing[n] = single_source_dijkstra_path(self.graph, n)
self.ipdestlpm = PyTricia()
for n,d in self.graph.nodes_iter(data=True):
dlist = d.get('ipdests','').split()
for destipstr in dlist:
ipnet = ipaddr.IPNetwork(destipstr)
xnode = {}
self.ipdestlpm[str(ipnet)] = xnode
if 'dests' in xnode:
xnode['dests'].append(n)
else:
xnode['net'] = ipnet
xnode['dests'] = [ n ]
# install static forwarding table entries to each node
# FIXME: there's a problematic bit of code here that triggers
# pytricia-related (iterator) core dump
for nodename,nodeobj in self.nodes.iteritems():
if isinstance(nodeobj, Router):
for prefix in self.ipdestlpm.keys():
lpmnode = self.ipdestlpm.get(prefix)
if nodename not in lpmnode['dests']:
routes = self.routing[nodename]
for d in lpmnode['dests']:
try:
path = routes[d]
except KeyError:
self.logger.warn("No route from {} to {}".format(nodename, d))
continue
nexthop = path[1]
nodeobj.addForwardingEntry(prefix, nexthop)
self.owdhash = {}
for a in self.graph:
for b in self.graph:
key = a + ':' + b
rlist = [ a ]
while rlist[-1] != b:
nh = self.nexthop(rlist[-1], b)
if not nh:
self.logger.debug('No route from %s to %s (in owd; ignoring)' % (a,b))
return None
rlist.append(nh)
owd = 0.0
for i in xrange(len(rlist)-1):
owd += self.delay(rlist[i],rlist[i+1])
self.owdhash[key] = owd
开发者ID:hardwood89，项目名称:fs，代码行数:54，代码来源:configurator.py
示例8: test_single_source_shortest_path
def test_single_source_shortest_path(self):
p=nx.shortest_path(self.cycle,0)
assert_equal(p[3],[0,1,2,3])
assert_equal(p,nx.single_source_shortest_path(self.cycle,0))
p=nx.shortest_path(self.grid,1)
validate_grid_path(4, 4, 1, 12, p[12])
# now with weights
p=nx.shortest_path(self.cycle,0,weight='weight')
assert_equal(p[3],[0,1,2,3])
assert_equal(p,nx.single_source_dijkstra_path(self.cycle,0))
p=nx.shortest_path(self.grid,1,weight='weight')
validate_grid_path(4, 4, 1, 12, p[12])
开发者ID:rvu95，项目名称:networkx，代码行数:12，代码来源:test_generic.py
示例9: test_single_source_shortest_path
def test_single_source_shortest_path(self):
p=nx.shortest_path(self.cycle,0)
assert_equal(p[3],[0,1,2,3])
assert_equal(p,nx.single_source_shortest_path(self.cycle,0))
p=nx.shortest_path(self.grid,1)
assert_equal(p[12],[1, 2, 3, 4, 8, 12])
# now with weights
p=nx.shortest_path(self.cycle,0,weighted=True)
assert_equal(p[3],[0,1,2,3])
assert_equal(p,nx.single_source_dijkstra_path(self.cycle,0))
p=nx.shortest_path(self.grid,1,weighted=True)
assert_equal(p[12],[1, 2, 3, 4, 8, 12])
开发者ID:c0ns0le，项目名称:zenoss-4，代码行数:12，代码来源:test_generic.py
示例10: test_SPF
def test_SPF():
edgeLen = 50
G = tNetworkX.createGridTopo(edgeLen=edgeLen)
# print "G: "+str(G.edges(data=True))
s = time.clock()
s1 = time.time()
path = nx.single_source_dijkstra_path(G,'0000.0000.0000')
e = time.clock()
e1 = time.time()
print "time.clock() consume time: "+str(e-s)
print "time.time() consume time: "+str(e1-s1)
pass
开发者ID:hxgqh，项目名称:jailmonitor，代码行数:13，代码来源:test_networkx.py
示例11: allpairs
def allpairs(graph_file=None,wt_attr=None):
"""
Print the shortest path for all nodes, using
the attribute named <b>wt_attr</b> as the weighting
function.
"""
if graph_file is None and wt_attr is None:
parser = argparse.ArgumentParser()
parser.add_argument("-w", help="Attribute to use for shortest path weight",
metavar="<weight attribute>")
parser.add_argument("graph_file",help="Modelnet Graph File")
args = parser.parse_args()
graph_file = args.graph_file
wt_attr = args.w
gr = load_graph(graph_file)
print '<?xml version="1.0" encoding="ISO-8859-1"?>'
print '<allpairs>'
numdone = 0
sys.stderr.write("Routing Node %s" % str(numdone))
for src in gr.nodes():
if gr.node[src]['vn'] == -1:
continue
if wt_attr:
sp = nx.single_source_dijkstra_path(gr,src,wt_attr)
else:
sp = nx.single_source_shortest_path(gr,src)
for dst in sp:
if gr.node[dst]['vn'] == -1:
continue
if dst == src:
continue
path = sp[dst]
hops = [gr[x][y]['int_idx'] for x,y in pairwise(path)]
print ('<path int_vndst="%d" int_vnsrc="%d" hops="%s"/>'
% (gr.node[dst]['vn'],
gr.node[src]['vn'],
" ".join(map(str,hops))))
sys.stderr.write('\b'*len(str(numdone)))
sys.stderr.write("%d" % int(numdone+1))
numdone += 1
print '</allpairs>'
开发者ID:cwacek，项目名称:experimentor_tools，代码行数:51，代码来源:ValidatePathDistances.py
示例12: test_dijkstra
def test_dijkstra(self):
(D, P) = nx.single_source_dijkstra(self.XG, "s")
assert_equal(P["v"], ["s", "x", "u", "v"])
assert_equal(D["v"], 9)
assert_equal(nx.single_source_dijkstra_path(self.XG, "s")["v"], ["s", "x", "u", "v"])
assert_equal(nx.single_source_dijkstra_path_length(self.XG, "s")["v"], 9)
assert_equal(nx.single_source_dijkstra(self.XG, "s")[1]["v"], ["s", "x", "u", "v"])
assert_equal(nx.single_source_dijkstra_path(self.MXG, "s")["v"], ["s", "x", "u", "v"])
GG = self.XG.to_undirected()
(D, P) = nx.single_source_dijkstra(GG, "s")
assert_equal(P["v"], ["s", "x", "u", "v"])
assert_equal(D["v"], 8) # uses lower weight of 2 on u<->x edge
assert_equal(nx.dijkstra_path(GG, "s", "v"), ["s", "x", "u", "v"])
assert_equal(nx.dijkstra_path_length(GG, "s", "v"), 8)
assert_equal(nx.dijkstra_path(self.XG2, 1, 3), [1, 4, 5, 6, 3])
assert_equal(nx.dijkstra_path(self.XG3, 0, 3), [0, 1, 2, 3])
assert_equal(nx.dijkstra_path_length(self.XG3, 0, 3), 15)
assert_equal(nx.dijkstra_path(self.XG4, 0, 2), [0, 1, 2])
assert_equal(nx.dijkstra_path_length(self.XG4, 0, 2), 4)
assert_equal(nx.dijkstra_path(self.MXG4, 0, 2), [0, 1, 2])
assert_equal(nx.single_source_dijkstra(self.G, "s", "v")[1]["v"], ["s", "u", "v"])
assert_equal(nx.single_source_dijkstra(self.G, "s")[1]["v"], ["s", "u", "v"])
assert_equal(nx.dijkstra_path(self.G, "s", "v"), ["s", "u", "v"])
assert_equal(nx.dijkstra_path_length(self.G, "s", "v"), 2)
# NetworkXError: node s not reachable from moon
assert_raises(nx.NetworkXNoPath, nx.dijkstra_path, self.G, "s", "moon")
assert_raises(nx.NetworkXNoPath, nx.dijkstra_path_length, self.G, "s", "moon")
assert_equal(nx.dijkstra_path(self.cycle, 0, 3), [0, 1, 2, 3])
assert_equal(nx.dijkstra_path(self.cycle, 0, 4), [0, 6, 5, 4])
开发者ID:Bludge0n，项目名称:AREsoft，代码行数:38，代码来源:test_weighted.py
示例13: test_bidirectional_dijkstra
def test_bidirectional_dijkstra(self):
assert_equal(nx.bidirectional_dijkstra(self.XG, "s", "v"), (9, ["s", "x", "u", "v"]))
(dist, path) = nx.bidirectional_dijkstra(self.G, "s", "v")
assert_equal(dist, 2)
# skip this test, correct path could also be ['s','u','v']
# assert_equal(nx.bidirectional_dijkstra(self.G,'s','v'),
# (2, ['s', 'x', 'v']))
assert_equal(nx.bidirectional_dijkstra(self.cycle, 0, 3), (3, [0, 1, 2, 3]))
assert_equal(nx.bidirectional_dijkstra(self.cycle, 0, 4), (3, [0, 6, 5, 4]))
assert_equal(nx.bidirectional_dijkstra(self.XG3, 0, 3), (15, [0, 1, 2, 3]))
assert_equal(nx.bidirectional_dijkstra(self.XG4, 0, 2), (4, [0, 1, 2]))
# need more tests here
assert_equal(nx.dijkstra_path(self.XG, "s", "v"), nx.single_source_dijkstra_path(self.XG, "s")["v"])
开发者ID:etrain，项目名称:networkx，代码行数:14，代码来源:test_weighted.py
示例14: test_dijkstra_vs_networkx_single_source_all_lenghts_and_paths
def test_dijkstra_vs_networkx_single_source_all_lenghts_and_paths():
""" Test Dijkstra: Rion's implementation vs Networkx implementation > Single Source """
# NX Version
G = nx.from_edgelist(edgelist_james)
nx.set_edge_attributes(G, 'weight', edgelist_james)
nx_lenghts = nx.single_source_dijkstra_path_length(G, source='s', weight='weight')
nx_paths = nx.single_source_dijkstra_path(G, source='s', weight='weight')
# My Version
d = Dijkstra()
d.from_edgelist(edgelist_james, directed=False)
dc_lenghts, dc_paths = d.single_source_shortest_paths('s', kind='metric')
assert (nx_lenghts == dc_lenghts)
assert (nx_paths == dc_paths)
开发者ID:rionbr，项目名称:distanceclosure，代码行数:15，代码来源:test_dijkstra.py
示例15: clip
def clip(self, d):
self.G = nx.single_source_dijkstra_path(self.N, self.source)
g = nx.Graph()
P = set()
print 'geodesic clipping..'
for path in pbar(self.G.values()):
if len(path) < 2: continue
curr_dist = 0
for p in range(1, len(path)): # from source (level 0) to i
curr_dist += self.N[path[p-1]][path[p]]['weight']
if curr_dist <= d:
g.add_edge(path[p-1], path[p])
P.add(harray(self.P[path[p-1]]))
P.add(harray(self.P[path[p]]))
else:
break
return vstack(P)
开发者ID:cjauvin，项目名称:pypetree，代码行数:17，代码来源:point_cloud.py
示例16: test_bidirectional_dijkstra
def test_bidirectional_dijkstra(self):
assert_equal(nx.bidirectional_dijkstra(self.XG, 's', 'v'),
(9, ['s', 'x', 'u', 'v']))
assert_equal(nx.bidirectional_dijkstra(self.G,'s','v'),
(2, ['s', 'x', 'v']))
assert_equal(nx.bidirectional_dijkstra(self.cycle,0,3),
(3, [0, 1, 2, 3]))
assert_equal(nx.bidirectional_dijkstra(self.cycle,0,4),
(3, [0, 6, 5, 4]))
assert_equal(nx.bidirectional_dijkstra(self.XG3,0,3),
(15, [0, 1, 2, 3]))
assert_equal(nx.bidirectional_dijkstra(self.XG4,0,2),
(4, [0, 1, 2]))
# need more tests here
assert_equal(nx.dijkstra_path(self.XG,'s','v'),
nx.single_source_dijkstra_path(self.XG,'s')['v'])
开发者ID:rafaelpiresm，项目名称:projetos_gae，代码行数:17，代码来源:test_weighted.py
示例17: test_bidirectional_dijkstra
def test_bidirectional_dijkstra(self):
validate_length_path(
self.XG, 's', 'v', 9, *nx.bidirectional_dijkstra(self.XG, 's', 'v'))
validate_length_path(
self.G, 's', 'v', 2, *nx.bidirectional_dijkstra(self.G, 's', 'v'))
validate_length_path(
self.cycle, 0, 3, 3, *nx.bidirectional_dijkstra(self.cycle, 0, 3))
validate_length_path(
self.cycle, 0, 4, 3, *nx.bidirectional_dijkstra(self.cycle, 0, 4))
validate_length_path(
self.XG3, 0, 3, 15, *nx.bidirectional_dijkstra(self.XG3, 0, 3))
validate_length_path(
self.XG4, 0, 2, 4, *nx.bidirectional_dijkstra(self.XG4, 0, 2))
# need more tests here
P = nx.single_source_dijkstra_path(self.XG, 's')['v']
validate_path(self.XG, 's', 'v', sum(self.XG[u][v]['weight'] for u, v in zip(
P[:-1], P[1:])), nx.dijkstra_path(self.XG, 's', 'v'))
开发者ID:jklaise，项目名称:networkx，代码行数:18，代码来源:test_weighted.py
示例18: maketree
def maketree(self, prune=False):
try:
self.tree = tree = networkx.minimum_spanning_tree(self.graph)
path = networkx.single_source_dijkstra_path(tree, self.uid)
except KeyError:
self.route = self.via = {}
return
self.route = route = dict((node, path[1]) for node, path in path.iteritems() if len(path) > 1)
self.via = via = {}
for k, v in route.iteritems():
try:
via[v].append(k)
except KeyError:
via[v] = [k]
if prune:
gr = self.graph
prune = set(gr.nodes()) - set(path)
prune.discard(self.uid)
gr.remove_nodes_from(prune)
开发者ID:inportb，项目名称:playground，代码行数:19，代码来源:jsoncluster.py
示例19: assign
def assign(self):
#does 4 iterations in which it assigns od, updates t_a. find paths to minimize travel time and we record route for each od pair
pdb.set_trace()
for i in range(4): #do 4 iterations
for origin in self.demand.keys():
#find the shortest paths from this origin to each destination
print origin
paths_dict = nx.single_source_dijkstra_path(self.G, origin, cutoff = None, weight = 't_a') #Compute shortest path between source and all other reachable nodes for a weighted graph. Returns dict keyed by by target with the value being a list of node ids of the shortest path
for destination in self.demand[origin].keys():
print destination
od_flow = iteration_vals[i] * self.demand[origin][destination]*0.053 #to get morning flows, take 5.3% of daily driver values. 11.5/(4.5*6+11.5*10+14*4+4.5*4) from Figure S10 of http://www.nature.com/srep/2012/121220/srep01001/extref/srep01001-s1.pdf
#get path
path_list = paths_dict[destination] #list of nodes
#increment flow on the paths and update t_a
for index in range(0, len(path_list) - 1):
u = path_list[index]
v = path_list[index + 1]
num_multi_edges = len( self.G[u][v])
if num_multi_edges >1: #multi-edge
print 'multiedge: ', num_multi_edges
#identify multi edge with lowest t_a
best = 0
best_t_a = float('inf')
for multi_edge in self.G[u][v].keys():
new_t_a = self.G[u][v][multi_edge]['t_a']
if (new_t_a < best_t_a) and (self.G[u][v][multi_edge]['capacity']>0):
best = multi_edge
best_t_a = new_t_a
else:
best = 0
if (self.G[u][v][best]['capacity']>0):
print 'adding flow'
self.G[u][v][best]['flow'] += od_flow
t = util.TravelTime(self.G[u][v][best]['t_0'], self.G[u][v][best]['capacity'])
travel_time= t.get_new_travel_time(od_flow) #TODO #min(t.get_new_travel_time(od_flow), self.G[u][v][best]['distance_0']*1.0/3600.0) #distance in miles, t_a in seconds!! So we are saying that the minimum of the t_a and distance (in miles) * (1 hr/ 1 mile) * (1hr / 3600s)
if travel_time > self.G[u][v][best]['distance_0']*3600:
print travel_time
print 'and 1mph: ', self.G[u][v][best]['distance_0']*3600
self.G[u][v][best]['t_a'] = travel_time
return self.G
开发者ID:muenchner，项目名称:ita，代码行数:42，代码来源:ita+copy.py
示例20: test_single_source_shortest_path
def test_single_source_shortest_path(self):
p = nx.shortest_path(self.cycle, 0)
assert_equal(p[3], [0, 1, 2, 3])
assert_equal(p, nx.single_source_shortest_path(self.cycle, 0))
p = nx.shortest_path(self.grid, 1)
validate_grid_path(4, 4, 1, 12, p[12])
# now with weights
p = nx.shortest_path(self.cycle, 0, weight='weight')
assert_equal(p[3], [0, 1, 2, 3])
assert_equal(p, nx.single_source_dijkstra_path(self.cycle, 0))
p = nx.shortest_path(self.grid, 1, weight='weight')
validate_grid_path(4, 4, 1, 12, p[12])
# weights and method specified
p = nx.shortest_path(self.cycle, 0, method='dijkstra', weight='weight')
assert_equal(p[3], [0, 1, 2, 3])
assert_equal(p, nx.single_source_shortest_path(self.cycle, 0))
p = nx.shortest_path(self.cycle, 0, method='bellman-ford',
weight='weight')
assert_equal(p[3], [0, 1, 2, 3])
assert_equal(p, nx.single_source_shortest_path(self.cycle, 0))
开发者ID:jianantian，项目名称:networkx，代码行数:20，代码来源:test_generic.py
注：本文中的networkx.single_source_dijkstra_path函数示例由纯净天空整理自Github/MSDocs等源码及文档管理平台，相关代码片段筛选自各路编程大神贡献的开源项目，源码版权归原作者所有，传播和使用请参考对应项目的License；未经允许，请勿转载。 |
客服电话
APP下载
官方微信
请发表评论