def _transform(self, source_type: Type[S], target_type: Type[T]) -> Tuple[Callable[[S], T], int]:
try:
LOGGER.info("Searching type graph for shortest path from \"{source_type}\" to \"{target_type}\"".format(source_type=source_type.__name__, target_type=target_type.__name__))
path = dijkstra_path(self._type_graph, source=source_type, target=target_type, weight="cost")
LOGGER.info("Found a path from \"{source_type}\" to \"{target_type}\"".format(source_type=source_type.__name__, target_type=target_type.__name__))
except (KeyError, NetworkXNoPath):
raise NoConversionError("Pipeline can't convert \"{source_type}\" to \"{target_type}\"".format(source_type=source_type, target_type=target_type))
LOGGER.info("Building transformer chain from \"{source_type}\" to \"{target_type}\"".format(source_type=source_type.__name__, target_type=target_type.__name__))
chain = []
cost = 0
for source, target in _pairwise(path):
transformer = self._type_graph.adj[source][target][_TRANSFORMER]
chain.append((transformer, target))
cost += transformer.cost
LOGGER.info("Built transformer chain from \"{source_type}\" to \"{target_type}\"".format(source_type=source_type.__name__, target_type=target_type.__name__))
if not chain:
return _identity, 0
return partial(_transform, transformer_chain=chain), cost
python类NetworkXNoPath()的实例源码
def ordered_neighbors(nx_graph, our_address, target_address):
paths = list()
try:
all_neighbors = networkx.all_neighbors(nx_graph, our_address)
except networkx.NetworkXError:
# If `our_address` is not in the graph, no channels opened with the
# address
return []
for neighbor in all_neighbors:
try:
length = networkx.shortest_path_length(
nx_graph,
neighbor,
target_address,
)
heappush(paths, (length, neighbor))
except (networkx.NetworkXNoPath, networkx.NodeNotFound):
pass
return paths
def get_shortest_path_length(self, vertex1, vertex2):
"""
Parameters
----------
vertex1:
vertex2:
Returns
-------
NxGraph: Graph object
Examples
--------
>>>
"""
try:
return nx.shortest_path_length(self._graph, source=vertex1, target=vertex2, weight=self._weight_field)
except nx.NetworkXNoPath:
return 0
def get_shortest_path_length_with_limit(self, vertex1, vertex2, cutoff=None):
"""
Parameters
----------
vertex1:
vertex2:
cutoff:
Returns
-------
NxGraph: Graph object
Examples
--------
>>>
"""
try:
return nx.single_source_dijkstra(self._graph, source=vertex1, target=vertex2, cutoff=cutoff,
weight=self._weight_field)
except nx.NetworkXNoPath:
return 0
def rnd_walk(self, topo, node, steps, visited = {}):
i = 0
visited[node] = True
# self.log.debug("rnd_walk %d %d" % (node, steps))
res = [node]
if steps == 0:
return res
while i < self.MAX_ITER:
i += 1
nnode = self.rng.choice(topo.graph.neighbors(node))
if nnode in visited:
continue
res.extend(self.rnd_walk(topo, nnode, steps - 1, visited))
return res
self.log.debug("Giving up on random walk")
raise nx.NetworkXNoPath("No random path from %s." % (node))
def test_converter_path(self):
with self.assertRaisesRegexp(Exception, 'No such validator foo/bar'):
converter_path(Validator('foo', 'bar'), Validator('foo', 'baz'))
# There is no path for types which lie in different components
with self.assertRaises(NetworkXNoPath):
converter_path(self.stringTextValidator,
Validator('graph', 'networkx'))
self.assertEquals(converter_path(self.stringTextValidator,
self.stringTextValidator), [])
# There is a two-step path converting between these types
self.assertEquals(len(converter_path(self.stringTextValidator,
Validator('string', 'json'))), 2)
def _check_rule_typing(self, rule_id, graph_id, lhs_mapping, rhs_mapping):
all_paths = nx.all_pairs_shortest_path(self)
paths_from_target = {}
for s in self.nodes():
if s == graph_id:
for key in all_paths[graph_id].keys():
paths_from_target[key] = all_paths[graph_id][key]
for t in paths_from_target.keys():
if t != graph_id:
new_lhs_h = compose(
lhs_mapping,
self.compose_path_typing(paths_from_target[t]))
new_rhs_h = compose(
rhs_mapping,
self.compose_path_typing(paths_from_target[t]))
try:
# find homomorphisms from s to t via other paths
s_t_paths = nx.all_shortest_paths(self, rule_id, t)
for path in s_t_paths:
lhs_h, rhs_h = self.compose_path_typing(path)
if lhs_h != new_lhs_h:
raise HierarchyError(
"Invalid lhs typing: homomorphism does not commute with an existing " +
"path from '%s' to '%s'!" % (s, t)
)
if rhs_h != new_rhs_h:
raise HierarchyError(
"Invalid rhs typing: homomorphism does not commute with an existing " +
"path from '%s' to '%s'!" % (s, t)
)
except(nx.NetworkXNoPath):
pass
return
def has_path(self, source_address, target_address):
""" True if there is a connecting path regardless of the number of hops. """
try:
return networkx.has_path(self.graph, source_address, target_address)
except (networkx.NodeNotFound, networkx.NetworkXNoPath):
return False
def fully_connected(self):
if self.graph is None:
return False
for i in range(1, self.num_rooms):
try:
path = networkx.shortest_path_length(
self.graph, source=0, target=i,
)
except networkx.NetworkXNoPath:
print('Graph isnt fully connected! Regenerating.')
return False
return True
def dijkstra_path(G, source, target, get_weight):
"""Returns the shortest path from source to target in a weighted graph G"""
(length, path) = single_source_dijkstra(G, source, target, get_weight)
try:
return path[target]
except KeyError:
raise nx.NetworkXNoPath(
"node %s not reachable from %s" % (source, target))
def find_path(self, source, target, value):
"""
find path between source and target
the shortest path is found based on
- the number of hops
- the imbalance it adds or reduces in the accounts
"""
try:
path = dijkstra_path(self.graph, source, target, self._get_path_cost_function(value))
except (nx.NetworkXNoPath, KeyError): # key error for if source or target is not in graph
path = []
return path
def get_conversion_path(self, start_type, target_type):
start_type = self._normalise_type(start_type)
target_type = self._normalise_type(target_type)
try:
# Retrieve node sequence that leads from start_type to target_type.
path = networkx.shortest_path(self.conversion_graph, start_type, target_type)
# Look up edges between nodes and retrieve the conversion function for each edge.
return [self.conversion_graph.get_edge_data(node_a, node_b)['conversion_function'] for node_a, node_b in
zip(path[:-1], path[1:])]
except networkx.NetworkXNoPath:
raise UndefinedConversionError(
start_type,
target_type,
)
def get(self,
frame_to,
frame_from = None):
'''
Get the transform from one frame to another, assuming they are connected
in the transform tree.
If the frames are not connected a NetworkXNoPath error will be raised.
Arguments
---------
frame_from: hashable object, usually a string (eg 'world').
If left as None it will be set to self.base_frame
frame_to: hashable object, usually a string (eg 'mesh_0')
Returns
---------
transform: (4,4) homogenous transformation matrix
'''
if frame_from is None:
frame_from = self.base_frame
transform = np.eye(4)
path = self._get_path(frame_from, frame_to)
for i in range(len(path) - 1):
data, direction = self.transforms.get_edge_data_direction(path[i],
path[i+1])
matrix = data['matrix']
if direction < 0:
matrix = np.linalg.inv(matrix)
transform = np.dot(transform, matrix)
return transform
def add_edge(self, u, v, *args, **kwargs):
changed = False
if u == v:
if self.flags['strict']:
raise ValueError('Edge must be between two unique nodes!')
return changed
if self._undirected.has_edge(u, v):
self.remove_edges_from([[u, v], [v,u]])
elif len(self.nodes()) > 0:
try:
path = nx.shortest_path(self._undirected, u, v)
if self.flags['strict']:
raise ValueError('Multiple edge path exists between nodes!')
self.disconnect_path(path)
changed = True
except (nx.NetworkXError, nx.NetworkXNoPath):
pass
self._undirected.add_edge(u,v)
super(self.__class__, self).add_edge(u, v, *args, **kwargs)
if self.flags['assert_forest']:
# this is quite slow but makes very sure structure is correct
# so is mainly used for testing
assert nx.is_forest(nx.Graph(self))
return changed
def shortest_path(paths, graph):
""" Finding minimum path lengths between sources and targets pairs defined
in paths.
Parameters
----------
ways : list
List of tuples containing a source and target node
graph : :class:`networkx.classes.multigraph.MultiGraph
Graph representation of an electrical grid.
Returns
-------
df : pd.DataFrame
DataFrame holding source and target node and the minimum path length.
"""
idxnames = ['source', 'target']
idx = pd.MultiIndex.from_tuples(paths, names=idxnames)
df = pd.DataFrame(index=idx, columns=['path_length'])
df.sort_index(inplace=True)
for s, t in paths:
try:
df.loc[(s, t), 'path_length'] = \
nx.dijkstra_path_length(graph, s, t)
except NetworkXNoPath:
continue
return df
def _check_rule_typing(self, rule_id, graph_id, lhs_mapping, rhs_mapping):
all_paths = nx.all_pairs_shortest_path(self)
paths_from_target = {}
for s in self.nodes():
if s == graph_id:
for key in all_paths[graph_id].keys():
paths_from_target[key] = all_paths[graph_id][key]
for t in paths_from_target.keys():
if t != graph_id:
new_lhs_h = compose(
lhs_mapping,
self.compose_path_typing(paths_from_target[t]))
new_rhs_h = compose(
rhs_mapping,
self.compose_path_typing(paths_from_target[t]))
try:
# find homomorphisms from s to t via other paths
s_t_paths = nx.all_shortest_paths(self, rule_id, t)
for path in s_t_paths:
lhs_h, rhs_h = self.compose_path_typing(path)
if lhs_h != new_lhs_h:
raise HierarchyError(
"Invalid lhs typing: homomorphism does not "
"commute with an existing "
"path from '%s' to '%s'!" % (s, t)
)
if rhs_h != new_rhs_h:
raise HierarchyError(
"Invalid rhs typing: homomorphism does not "
"commute with an existing " +
"path from '%s' to '%s'!" % (s, t)
)
except(nx.NetworkXNoPath):
pass
return
def generate_path(self, topo, flow, link_caps):
try:
shortest_paths = [p for p in topo.get_shortest_paths(flow.src, flow.dst)]
except nx.exception.NetworkXNoPath:
self.log.debug("No shortest path for (%d, %d)" % (flow.src, flow.dst))
return False
for path in shortest_paths:
if not self.check_capacity(topo, path, link_caps, flow.vol, flow.reversed_vol):
continue
else:
self.allocate_link_cap(path, link_caps, flow.vol, flow.reversed_vol)
flow.path = path
break
return flow.path, None
def create_with_shortest_path(self, topo, flow, from_srcs, to_dsts, link_caps):
for src_key in from_srcs:
path_from_src = from_srcs[src_key]
if not self.check_capacity(topo, path_from_src, link_caps, flow.vol, flow.reversed_vol):
continue
for dst_key in to_dsts:
path_to_dst = to_dsts[dst_key]
if self.checking_joint(path_from_src, path_to_dst):
continue
else:
if not self.check_capacity(topo, path_to_dst, link_caps, flow.vol, flow.reversed_vol):
continue
try:
in_path = path_from_src + path_to_dst
mid_paths = [p for p in topo.get_shortest_paths(src_key, dst_key, False)]
for mid_path in mid_paths:
if mid_path != [] and not self.checking_joint(mid_path, in_path):
path = path_from_src + mid_path + path_to_dst
if not self.check_capacity(topo, path, link_caps, flow.vol, flow.reversed_vol):
continue
flow.path = path
flow.skip_mdbxes = [src_key, dst_key]
self.log.info(flow.path)
self.allocate_link_cap(flow.path, link_caps, flow.vol, flow.reversed_vol)
return True
except nx.exception.NetworkXNoPath:
continue
return False
def generate_path(self, topo, flow, link_caps):
path = []
count = 0
self.log.debug("Flow%d: %d --> %d: %s" % (flow.flow_id, flow.src, flow.dst, str(flow.vol)))
while len(path) == 0 and count < self.attempts - 3:
try:
from_srcs = defaultdict()
bfs_src = nx.bfs_successors(topo.graph, flow.src)
self.get_node_with_distance(bfs_src, flow.src, 0, 2, deque([]), from_srcs, False)
to_dsts = defaultdict()
bfs_dst = nx.bfs_successors(topo.graph, flow.dst)
self.get_node_with_distance(bfs_dst, flow.dst, 0, 2, deque([]), to_dsts, True)
except nx.exception.NetworkXNoPath:
count += 1
continue
if not self.create_with_middlebox(topo, flow, from_srcs, to_dsts, link_caps):
if not self.create_with_shortest_path(topo, flow, from_srcs, to_dsts, link_caps):
count += 1
continue
return True
if count == self.attempts - 3:
self.log.debug("Fail hard")
return False
return path
def convert(type, input, output, fetch=True, status=None, **kwargs):
"""
Convert data from one format to another.
:param type: The type specifier string of the input data.
:param input: A binding dict of the form
``{'format': format, 'data', data}``, where ``format`` is the format
specifier string, and ``data`` is the raw data to convert.
The dict may also be of the form
``{'format': format, 'uri', uri}``, where ``uri`` is the location of
the data (see :py:mod:`girder_worker.uri` for URI formats).
:param output: A binding of the form
``{'format': format}``, where ``format`` is the format
specifier string to convert the data to.
The binding may also be in the form
``{'format': format, 'uri', uri}``, where ``uri`` specifies
where to place the converted data.
:param fetch: Whether to do an initial data fetch before conversion
(default ``True``).
:returns: The output binding
dict with an additional field ``'data'`` containing the converted data.
If ``'uri'`` is present in the output binding, instead saves the data
to the specified URI and
returns the output binding unchanged.
"""
kwargs = kwargs.copy()
kwargs['auto_convert'] = False
if fetch:
input['data'] = io.fetch(input, **kwargs)
if input['format'] == output['format']:
data = input['data']
else:
data_descriptor = input
try:
conversion_path = converter_path(
Validator(type, input['format']), Validator(type, output['format']))
except NetworkXNoPath:
raise Exception('No conversion path from %s/%s to %s/%s' % (
type, input['format'], type, output['format']))
# Run data_descriptor through each conversion in the path
for conversion in conversion_path:
result = run(
conversion, {'input': data_descriptor}, status=status, **kwargs)
data_descriptor = result['output']
data = data_descriptor['data']
if status == utils.JobStatus.CONVERTING_OUTPUT:
job_mgr = kwargs.get('_job_manager')
set_job_status(job_mgr, utils.JobStatus.PUSHING_OUTPUT)
io.push(data, output, **kwargs)
return output
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)
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)
def run_cna(graph, root, targets, relationship_dict=None):
""" Returns the effect from the root to the target nodes represented as {-1,1}
:param pybel.BELGraph graph: A BEL graph
:param tuple root: The root node
:param iter targets: The targets nodes
:param dict relationship_dict: dictionary with relationship effects
:return list[tuple]:
"""
causal_effects = []
relationship_dict = causal_effect_dict if relationship_dict is None else relationship_dict
for target in targets:
try:
shortest_paths = nx.all_shortest_paths(graph, source=root, target=target)
effects_in_path = set()
for shortest_path in shortest_paths:
effects_in_path.add(get_path_effect(graph, shortest_path, relationship_dict))
if len(effects_in_path) == 1:
causal_effects.append((root, target, next(iter(effects_in_path)))) # Append the only predicted effect
elif Effect.activation in effects_in_path and Effect.inhibition in effects_in_path:
causal_effects.append((root, target, Effect.ambiguous))
elif Effect.activation in effects_in_path and Effect.inhibition not in effects_in_path:
causal_effects.append((root, target, Effect.activation))
elif Effect.inhibition in effects_in_path and Effect.activation not in effects_in_path:
causal_effects.append((root, target, Effect.inhibition))
else:
log.warning('Exception in set: {}.'.format(effects_in_path))
except nx.NetworkXNoPath:
log.warning('No shortest path between: {} and {}.'.format(root, target))
return causal_effects
