def shortest_path_undirected(self, u, v):
path = nx.shortest_path(self._undirected, u, v)
return path
python类shortest_path()的实例源码
def _path_exists(graph, source, target):
try:
path = networkx.shortest_path(graph, source, target)
except NetworkXException:
path = []
return bool(path)
def guess(graph, question, choices):
MAX = 9999
SUBMAX = 999
ques_node = find_node(graph, question)
dists = []
for choice in choices:
choice_node = find_node(graph, choice)
if ques_node is None and choice_node is None:
dist = MAX
elif ques_node is None and choice_node is not None:
dist = SUBMAX
elif ques_node is not None and choice_node is None:
dist = MAX
else:
if nx.has_path(graph, ques_node, choice_node):
pl = len(nx.shortest_path(graph, ques_node, choice_node))
dist = pl
else:
dist = MAX
dists.append(dist)
answer, dist = min(enumerate(dists), key=lambda x: x[1])
max_dist = max(dists)
if dist == MAX:
return None
if dist == max_dist:
return None
return answer
def getHopsTo(self, link):
assert link != self
path = networkx.shortest_path(
sg.gnGraph.netGraph,
self.as_nodeA,
link.as_nodeA
)
path.remove(self.as_nodeA)
path.remove(link.as_nodeA)
if self.as_nodeB in path:
path.remove(self.as_nodeB)
if link.as_nodeB in path:
path.remove(link.as_nodeB)
return len(path) + 1
def get_path(self, source, destination):
"""Gets shortest path by weight attribute between the nodes.
@:return a sequence of nodes representing the shortest path"""
return nx.shortest_path(self.topo, source=source, target=destination)
def get_path(self, source, destination, weight='weight'):
"""Gets shortest path by the optionally specified weight attribute between the nodes.
@:return a sequence of nodes representing the shortest path"""
return nx.shortest_path(self.topo, source=source, target=destination, weight=weight)
def deploy_controller(self, sw, sw_to_ctrl_delays):
sw_to_ctrl_delays[sw] = 0
shortest_paths = nx.shortest_path(self.graph, target=sw, weight='delay')
shortest_path_lengths = nx.shortest_path_length(self.graph, target=sw, weight='delay')
log.info(shortest_paths)
for n in self.graph.nodes():
if n == sw:
continue
if n in shortest_path_lengths.keys():
sw_to_ctrl_delays[n] = shortest_path_lengths[n]
else:
sw_to_ctrl_delays[n] = 1
log.debug("sw to ctrl delays: %s" % str(sw_to_ctrl_delays))
def DSP_Path(DualGraph, terminal1, terminal2):
return nx.shortest_path(DualGraph, terminal1, terminal2)
def hasConnectedBoundaries(code, loops_graph, Exts):
if len(loops_graph.edges()) <= 1:
return False
for ext1 in loops_graph.nodes():
for ext2 in loops_graph.nodes():
if ext1 in Exts and ext2 in Exts and ext1 != ext2:
if nx.has_path(loops_graph,ext1,ext2):
path = nx.shortest_path(loops_graph, ext1, ext2)
for node in path:
if node not in Exts:
return True
return False
def connectedBoundaries(loops_graph, Exts):
for ext1 in loops_graph.nodes():
for ext2 in loops_graph.nodes():
if ext1 in Exts and ext2 in Exts and ext1 != ext2:
if nx.has_path(loops_graph,ext1,ext2):
path = nx.shortest_path(loops_graph, ext1, ext2)
for node in path:
if node not in Exts:
return ext1, ext2
def BoundTransport(code, fixed_node, mobile_node, dim, type, charge_type):
if 'external' in mobile_node[1]:
charge = mobile_node[1]['charge']
first_link = code.External[type][mobile_node[0]]['measure']
shared = code.External[type][mobile_node[0]]['data']
count = code.External[type][mobile_node[0]]['order']
num_sides = code.External[type][mobile_node[0]]['sides']
sign = common.Sign(count, num_sides)
delta_charge = sign * charge
first_link_charge = code.Primal.node[shared]['charge'][charge_type]
code.Primal.node[shared]['charge'][charge_type] = (first_link_charge - delta_charge)%dim
mobile_node = first_link
chain = nx.shortest_path(code.Dual[type], mobile_node, fixed_node[0])
chain_length = len(chain) - 1
for link in range(chain_length):
previous, next = chain[link], chain[link + 1]
for shared in code.Stabilizers[type][previous]['data']:
if shared in code.Stabilizers[type][next]['data']:
num_sides = code.Stabilizers[type][previous]['sides']
count = code.Stabilizers[type][previous]['data'][shared]
sign = common.Sign(count, num_sides)
delta_charge = sign * charge
data_charge = code.Primal.node[shared]['charge'][charge_type]
code.Primal.node[shared]['charge'][charge_type] = (data_charge - delta_charge)%dim
else:
Transport(code, fixed_node, mobile_node, dim, type, charge_type)
def _generateDAG(self):
'''
Generate workflow DAG using networkx directed graph implementation.
Return topological ordering of graphs. Note that nx.topological_sort(G)
requires the graph to be acyclic. Cyclic behavior is hard to implement
in practice since jobs are defined by calling specific dictionary elements.
'''
# Instantiate directed graph, add job dependency edges.
G = nx.DiGraph()
for job in self.jobs:
G.add_node(job)
if 'dependsOn' in self.jobs[job]:
for dependency in self.jobs[job]['dependsOn']:
G.add_edge(dependency['jobKey'], self.jobs[job]['jobKey'])
self.dag_graph = G # For printing purposes.
# Sort jobs in graph using topological sort, assigning job buckets.
# Jobs within the same bucket will be kicked off simultaneously.
topology = nx.topological_sort(G)
self.graph = [(0, topology[0])]
for edge in topology[1:]:
try:
self.graph.append((len(nx.shortest_path(G, topology[0], edge)) - 1, edge))
except nx.exception.NetworkXNoPath as error:
self.graph.append((0, edge))
def extractMinSubgraphContainingNodes(self, minSet):
"""
Find the minimum subgraph of the dependency graph that contains the provided set of nodes. Useful for finding dependency-path like structures
:param minSet: List of token indices
:type minSet: List of ints
:return: All the nodes and edges in the minimal subgraph
:rtype: Tuple of nodes,edges where nodes is a list of token indices, and edges are the associated dependency edges between those tokens
"""
assert isinstance(minSet, list)
for i in minSet:
assert isinstance(i, int)
assert i >= 0
assert i < len(self.tokens)
G1 = nx.Graph()
for a,b,depType in self.dependencies:
G1.add_edge(a,b,dependencyType=depType)
G2 = nx.Graph()
paths = {}
minSet = sorted(list(set(minSet)))
setCount1 = len(minSet)
minSet = [ a for a in minSet if G1.has_node(a) ]
setCount2 = len(minSet)
if setCount1 != setCount2:
sys.stderr.write("WARNING. %d node(s) not found in dependency graph!\n" % (setCount1-setCount2))
for a,b in itertools.combinations(minSet,2):
try:
path = nx.shortest_path(G1,a,b)
paths[(a,b)] = path
G2.add_edge(a,b,weight=len(path))
except nx.exception.NetworkXNoPath:
sys.stderr.write("WARNING. No path found between nodes %d and %d!\n" % (a,b))
# TODO: This may through an error if G2 ends up having multiple components. Catch it gracefully.
minTree = nx.minimum_spanning_tree(G2)
nodes = set()
allEdges = set()
for a,b in minTree.edges():
path = paths[(min(a,b),max(a,b))]
for i in range(len(path)-1):
a,b = path[i],path[i+1]
dependencyType = G1.get_edge_data(a,b)['dependencyType']
edge = (min(a,b),max(a,b),dependencyType)
allEdges.add(edge)
nodes.update(path)
return nodes,allEdges
def TraverseGraph(transitions, states, args=None):
"""Does that actual graph traversal, going through all transitions."""
transition_graph, initial_vertex = stl.graph.BuildTransitionGraph(
transitions, states)
graph_file = None
if args:
graph_file = args.graph
visualizer = Visualizer(transition_graph, graph_file)
circuit_stack = stl.traverse.MinEdgeCoverCircuit(transition_graph,
initial_vertex)
circuit_stack.reverse()
success = True
while circuit_stack:
edge = circuit_stack.pop()
source, target, edge_i = edge
attr = transition_graph[source][target][edge_i]
transition = attr['transition']
visualizer.TransitionRunning(edge)
if attr['weight'] != float('inf'):
logging.info('\033[93m[ RUNNING ]\033[0m: %s', transition.name)
if transition.Run():
logging.info('\033[92m[ PASSED ]\033[0m: %s', transition.name)
visualizer.TransitionPassed(edge)
continue
else:
logging.error('\033[91m[ FAILED ]\033[0m: %s', transition.name)
success = False
attr['weight'] = float('inf')
error_vertex_id = attr['error_vertex_id']
visualizer.TransitionFailed(edge, error_vertex_id)
new_path = nx.shortest_path(
transition_graph, error_vertex_id, target, weight='weight')
path_stack = []
for i in range(len(new_path) - 1):
s = new_path[i]
t = new_path[i + 1]
# Get the edge-index with the smallest weight
multi_edge = transition_graph[s][t]
min_weight = float('inf')
min_edge_i = 0
for key, value in multi_edge.iteritems():
if value['weight'] < min_weight:
min_weight = value['weight']
min_edge_i = key
if transition_graph[s][t][min_edge_i]['weight'] == float('inf'):
return success
path_stack.append((s, t, min_edge_i))
# TODO(seantopping): Implement a better error recovery algorithm.
circuit_stack.extend(reversed(path_stack))
return success
def main():
if len(sys.argv) != 3:
print "Usage: send.py [this_host] [target_host]"
print "For example: send.py h1 h2"
sys.exit(1)
src, dst = sys.argv[1:]
nb_hosts, nb_switches, links = read_topo()
port_map = {}
for a, b in links:
if a not in port_map:
port_map[a] = {}
if b not in port_map:
port_map[b] = {}
assert(b not in port_map[a])
assert(a not in port_map[b])
port_map[a][b] = len(port_map[a]) + 1
port_map[b][a] = len(port_map[b]) + 1
G = nx.Graph()
for a, b in links:
G.add_edge(a, b)
shortest_paths = nx.shortest_path(G)
shortest_path = shortest_paths[src][dst]
print "path is:", shortest_path
port_list = []
first = shortest_path[1]
for h in shortest_path[2:]:
port_list.append(port_map[first][h])
first = h
print "port list is:", port_list
port_str = ""
for p in port_list:
port_str += chr(p)
while(1):
msg = raw_input("What do you want to send: ")
# finding the route
first = None
p = SrcRoute(num_valid = len(port_list)) / port_str / msg
print p.show()
sendp(p, iface = "eth0")
# print msg
def _get_path(self, src_vnf, dst_vnf, src_vnf_intf, dst_vnf_intf):
"""
Own implementation of the get_path function from DCNetwork, because we just want the path and not set up
flows on the way.
:param src_vnf: Name of the source VNF
:type src_vnf: ``str``
:param dst_vnf: Name of the destination VNF
:type dst_vnf: ``str``
:param src_vnf_intf: Name of the source VNF interface
:type src_vnf_intf: ``str``
:param dst_vnf_intf: Name of the destination VNF interface
:type dst_vnf_intf: ``str``
:return: path, src_sw, dst_sw
:rtype: ``list``, ``str``, ``str``
"""
# modified version of the _chainAddFlow from emuvim.dcemulator.net._chainAddFlow
src_sw = None
dst_sw = None
logging.debug("Find shortest path from vnf %s to %s",
src_vnf, dst_vnf)
for connected_sw in self.net.DCNetwork_graph.neighbors(src_vnf):
link_dict = self.net.DCNetwork_graph[src_vnf][connected_sw]
for link in link_dict:
if (link_dict[link]['src_port_id'] == src_vnf_intf or
link_dict[link][
'src_port_name'] == src_vnf_intf):
# found the right link and connected switch
src_sw = connected_sw
break
for connected_sw in self.net.DCNetwork_graph.neighbors(dst_vnf):
link_dict = self.net.DCNetwork_graph[connected_sw][dst_vnf]
for link in link_dict:
if link_dict[link]['dst_port_id'] == dst_vnf_intf or \
link_dict[link][
'dst_port_name'] == dst_vnf_intf:
# found the right link and connected
dst_sw = connected_sw
break
logging.debug("From switch %s to %s " % (src_sw, dst_sw))
# get shortest path
try:
# returns the first found shortest path
# if all shortest paths are wanted, use: all_shortest_paths
path = nx.shortest_path(self.net.DCNetwork_graph, src_sw, dst_sw)
except:
logging.exception("No path could be found between {0} and {1} using src_sw={2} and dst_sw={3}".format(
src_vnf, dst_vnf, src_sw, dst_sw))
logging.debug("Graph nodes: %r" % self.net.DCNetwork_graph.nodes())
logging.debug("Graph edges: %r" % self.net.DCNetwork_graph.edges())
for e, v in self.net.DCNetwork_graph.edges():
logging.debug("%r" % self.net.DCNetwork_graph[e][v])
return "No path could be found between {0} and {1}".format(src_vnf, dst_vnf)
logging.info("Shortest path between {0} and {1}: {2}".format(src_vnf, dst_vnf, path))
return path, src_sw, dst_sw
def main():
if len(sys.argv) != 3:
print "Usage: send.py [this_host] [target_host]"
print "For example: send.py h1 h2"
sys.exit(1)
src, dst = sys.argv[1:]
nb_hosts, nb_switches, links = read_topo()
port_map = {}
for a, b in links:
if a not in port_map:
port_map[a] = {}
if b not in port_map:
port_map[b] = {}
assert(b not in port_map[a])
assert(a not in port_map[b])
port_map[a][b] = len(port_map[a]) + 1
port_map[b][a] = len(port_map[b]) + 1
G = nx.Graph()
for a, b in links:
G.add_edge(a, b)
shortest_paths = nx.shortest_path(G)
shortest_path = shortest_paths[src][dst]
print "path is:", shortest_path
port_list = []
first = shortest_path[1]
for h in shortest_path[2:]:
port_list.append(port_map[first][h])
first = h
print "port list is:", port_list
port_str = ""
for p in port_list:
port_str += chr(p)
while(1):
msg = raw_input("What do you want to send: ")
# finding the route
first = None
p = SrcRoute(num_valid = len(port_list)) / port_str / msg
print p.show()
sendp(p, iface = "eth0")
# print msg
def get_path_to_netbox(netbox):
"""Returns a likely path from netbox to its apparent gateway/router.
If any switches on the path, or the router itself is down,
no current path exists and a False value is returned. However,
if there is insufficient information for NAV to find a likely path,
a True value is returned.
"""
prefix = netbox.get_prefix()
if not prefix:
_logger.warning("couldn't find prefix for %s", netbox)
return True
router_ports = prefix.get_router_ports()
if router_ports:
router_port = router_ports[0]
else:
_logger.warning("couldn't find router ports for %s", prefix)
return True
router = router_port.interface.netbox
_logger.debug("reachability check for %s on %s (router: %s)",
netbox, prefix, router)
graph = get_graph_for_vlan(prefix.vlan)
try:
netbox.add_to_graph(graph)
except AttributeError:
pass
# first, see if any path exists
if not _path_exists(graph, netbox, router):
_logger.warning("cannot find a path between %s and %s on VLAN %s",
netbox, router, prefix.vlan)
return True
# now, remove nodes that are down and see if a path still exists
strip_down_nodes_from_graph(graph, keep=netbox)
if netbox not in graph or router not in graph:
if router.up == router.UP_UP:
_logger.warning("%(netbox)s topology problem: router %(router)s "
"is up, but not in VLAN graph for %(prefix)r. "
"Defaulting to 'reachable' status.", locals())
return True
_logger.debug("%s not reachable, router or box not in graph: %r",
netbox, graph.edges())
return False
try:
path = networkx.shortest_path(graph, netbox, router)
except NetworkXException as error:
_logger.debug("an internal networkx exception was raised in "
"shortest_path, assuming no path was found: %s", error)
path = []
else:
_logger.debug("path to %s: %r", netbox, path)
return path
def _build_routes(self, boundary_ports, graph, logical_ports):
root_ports = dict((lp.ofp_port.port_no, lp.root_port)
for lp in logical_ports if lp.root_port == True)
routes = {}
for source, source_port_no in boundary_ports.iteritems():
for target, target_port_no in boundary_ports.iteritems():
if source is target:
continue
# Ignore NNI - NNI routes
if source_port_no in root_ports \
and target_port_no in root_ports:
continue
# Ignore UNI - UNI routes
if source_port_no not in root_ports \
and target_port_no not in root_ports:
continue
path = nx.shortest_path(graph, source, target)
# number of nodes in valid paths is always multiple of 3
if len(path) % 3:
continue
# in fact, we currently deal with single fan-out networks,
# so the number of hops is always 6
assert len(path) == 6
ingress_input_port, ingress_device, ingress_output_port, \
egress_input_port, egress_device, egress_output_port = path
ingress_hop = RouteHop(
device=graph.node[ingress_device]['device'],
ingress_port=graph.node[ingress_input_port]['port'],
egress_port=graph.node[ingress_output_port]['port']
)
egress_hop = RouteHop(
device=graph.node[egress_device]['device'],
ingress_port=graph.node[egress_input_port]['port'],
egress_port=graph.node[egress_output_port]['port']
)
routes[(source_port_no, target_port_no)] = [
ingress_hop, egress_hop
]
return routes
def getNetworkTransP(s1, s2, graph, endpoints, segmentlengths, pathnodes, decayconstantNet):
"""
Returns transition probability of going from segment s1 to s2, based on network distance of segments, as well as corresponding path
"""
subpath = []
s1_point = None
s2_point = None
if s1 == s2:
dist = 0
else:
#Obtain edges (tuples of endpoints) for segment identifiers
s1_edge = endpoints[s1]
s2_edge = endpoints[s2]
s1_l = segmentlengths[s1]
s2_l = segmentlengths[s2]
#This determines segment endpoints of the two segments that are closest to each other
minpair = [0,0,100000]
for i in range(0,2):
for j in range(0,2):
d = round(pointdistance(s1_edge[i],s2_edge[j]),2)
if d<minpair[2]:
minpair = [i,j,d]
s1_point = s1_edge[minpair[0]]
s2_point = s2_edge[minpair[1]]
## if (s1_point in pathnodes or s2_point in pathnodes): # Avoid paths reusing an old pathnode (to prevent self-crossings)
## dist = 100
## else:
if s1_point == s2_point:
#If segments are touching, use a small network distance
dist = 5
else:
try:
#Compute a shortest path (using segment length) on graph where segment endpoints are nodes and segments are (undirected) edges
if graph.has_node(s1_point) and graph.has_node(s2_point):
dist = nx.shortest_path_length(graph, s1_point, s2_point, weight='length')
path = nx.shortest_path(graph, s1_point, s2_point, weight='length')
#get path edges
path_edges = zip(path,path[1:])
#print "edges: "+str(path_edges)
subpath = []
# get object ids for path edges
for e in path_edges:
oid = graph.edge[e[0]][e[1]]["OBJECTID"]
subpath.append(oid)
#print "oid path:"+str(subpath)
else:
#print "node not in segment graph!"
dist = 3*decayconstantNet #600
except nx.NetworkXNoPath:
#print 'no path available, assume a large distance'
dist = 3*decayconstantNet #700
#print "network distance between "+str(s1) + ' and '+ str(s2) + ' = '+str(dist)
return (getNDProbability(dist,decayconstantNet),subpath,s2_point)
