Python networkx 模块，NetworkXNoPath() 实例源码

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

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