python类shortest_path_length()的实例源码

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 add_cycle_edges_by_path(g,number_of_edges,path_length = 5):
    number = 0
    num_nodes = g.number_of_nodes()
    nodes = g.nodes()
    extra_edges = []
    while number < number_of_edges:
        u,v = np.random.randint(0,num_nodes,2)
        u = nodes[u]
        v = nodes[v]
        if nx.has_path(g,u,v):
            length = nx.shortest_path_length(g,source = u,target = v)
            if length <= path_length:
                extra_edges.append((v,u))
                number += 1
        if nx.has_path(g,v,u):
            length = nx.shortest_path_length(g,source = v,target = u)
            if length <= path_length:
                extra_edges.append((u,v))
                number += 1
    print("# extra edges added with path length <= %d: %d" % (path_length,len(extra_edges)))
    return extra_edges

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 bell_reweighting(tree, root, sublinear=False):
    # convert the hierarchy to a tree if make_bfs_tree is true

    distance_by_target = nx.shortest_path_length(tree, source=root)

    level_count = defaultdict(int)
    for val in distance_by_target.values():
        level_count[val] += 1

    for edge in tree.edges():
        parent, child = edge
        if sublinear:
            # use smoothed logarithm
            tree[parent][child]['weight'] = 1.0 / log(1 + level_count[distance_by_target[child]], 10)
        else:
            tree[parent][child]['weight'] = 1.0 / level_count[distance_by_target[child]]

    return tree

def prune(self):
        """TODO:
        """
        # set of allowed symbols, i.e. singletons and emptyset
        symbols = set([0] + self.props.values())
        # update transitions and mark for deletion
        del_transitions = deque()
        for u, v, d in self.g.edges_iter(data=True):
            sym = d['input'] & symbols
            if sym:
                d['input'] = sym
            else:
                del_transitions.append((u, v))
        self.g.remove_edges_from(del_transitions)
        # delete states unreachable from the initial state
        init = next(self.init.iterkeys())
        reachable_states = nx.shortest_path_length(self.g, source=init).keys()
        del_states = [n for n in self.g.nodes_iter() if n not in reachable_states]
        self.g.remove_nodes_from(del_states)
        # update accepting pairs
        for f, b in self.final:
            f.difference_update(del_states)
            b.difference_update(del_states)
        return del_states, del_transitions

def prune(self):
        """TODO:

        Note: Does not update the final data structure, because it is dependent
        on the automaton type.
        """
        # set of allowed symbols, i.e. singletons and emptyset
        symbols = set([0] + self.props.values())
        # update transitions and mark for deletion
        del_transitions = deque()
        for u, v, d in self.g.edges_iter(data=True):
            sym = d['input'] & symbols
            if sym:
                d['input'] = sym
            else:
                del_transitions.append((u, v))
        self.g.remove_edges_from(del_transitions)
        # delete states unreachable from the initial state
        init = next(self.init.iterkeys())
        reachable_states = nx.shortest_path_length(self.g, source=init).keys()
        del_states = [n for n in self.g.nodes_iter() if n not in reachable_states]
        self.g.remove_nodes_from(del_states)
        return del_states, del_transitions

def InternalRecovery(code, terminal1, terminal2, type, charge_type):
    measure_chain = nx.shortest_path(code.Dual[type], terminal1, terminal2)
    chain_length = nx.shortest_path_length(code.Dual[type], terminal1, terminal2)
    for link in range(chain_length):
        vertex1 = measure_chain[link]
        vertex2 = measure_chain[link + 1]
        for data_qubit in code.Stabilizers[type][vertex1]['data']:
            if data_qubit in code.Stabilizers[type][vertex2]['data']:
                prior_charge = code.Primal.node[data_qubit]['charge'][charge_type]
                code.Primal.node[data_qubit]['charge'][charge_type] = (prior_charge + 1) % 2

    return code

def AssociatedExternal(node, Dual, External):
    associate = External.iterkeys().next()
    min_dist = nx.shortest_path_length(Dual, node, External[associate]['measure']) + 1

    for candidate in External:
        distance = nx.shortest_path_length(Dual, node, External[candidate]['measure']) + 1
        if distance < min_dist:
            min_dist = distance
            associate = candidate
    return associate

def distance(self, type, node1, node2):
        if node1 in self.Dual[type].nodes() and node2 in self.Dual[type].nodes():
            return nx.shortest_path_length(self.Dual[type], node1, node2)
        elif node1 in self.Dual[type].nodes() and node2 not in self.Dual[type].nodes():
            node2 = self.External[type][node2]['measure']
            return nx.shortest_path_length(self.Dual[type], node1, node2) + 1
        elif node1 not in self.Dual[type].nodes() and node2 in self.Dual[type].nodes():
            node1 = self.External[type][node1]['measure']
            return nx.shortest_path_length(self.Dual[type], node1, node2) + 1
        else:
            node1 = self.External[type][node1]['measure']
            node2 = self.External[type][node2]['measure']
            return nx.shortest_path_length(self.Dual[type], node1, node2) + 2


    # Re-initializes Measurement qubits

def sp_kernel(g1, g2=None):
    if g2 != None:
        graphs = []
        for g in g1:
            graphs.append(g)
        for g in g2:
            graphs.append(g)
    else:
        graphs = g1

    N = len(graphs)
    all_paths = {}
    sp_counts = {}
    for i in range(N):
        sp_lengths = nx.shortest_path_length(graphs[i])
        sp_counts[i] = {}
        nodes = graphs[i].nodes()
        for v1 in nodes:
            for v2 in nodes:
                if v2 in sp_lengths[v1]:
                    label = tuple(sorted([graphs[i].node[v1]['label'], graphs[i].node[v2]['label']]) + [sp_lengths[v1][v2]])
                    if label in sp_counts[i]:
                        sp_counts[i][label] += 1
                    else:
                        sp_counts[i][label] = 1

                    if label not in all_paths:
                        all_paths[label] = len(all_paths)

    phi = np.zeros((N,len(all_paths)))

    for i in range(N):
        for label in sp_counts[i]:
            phi[i,all_paths[label]] = sp_counts[i][label]

    if g2 != None:
        K = np.dot(phi[:len(g1),:],phi[len(g1):,:].T)
    else:
        K = np.dot(phi,phi.T)

    return K

def prepare_plot(graph):
    """
    Prepares a Matplotlib plot for further handling
    :param graph: datamodel.base.Graph instance
    :return: None
    """
    G = graph.nxgraph

    # Color map for nodes: color is proportional to depth level
    # http://matplotlib.org/examples/color/colormaps_reference.html
    depth_levels_from_root = nx.shortest_path_length(G, graph.root_node)
    vmax = 1.
    colormap = plt.get_cmap('BuGn')
    step = 1./len(graph)
    node_colors = [vmax - step * depth_levels_from_root[n] for n in G.nodes()]

    # Draw!
    # https://networkx.github.io/documentation/networkx-1.10/reference/drawing.html
    pos = nx.spectral_layout(G)
    nx.draw_networkx_labels(G, pos,
                            labels=dict([(n, n.name) for n in G.nodes()]),
                            font_weight='bold',
                            font_color='orangered')
    nx.draw_networkx_nodes(G, pos,
                           node_size=2000,
                           cmap=colormap,
                           vmin=0.,
                           vmax=vmax,
                           node_color=node_colors)
    nx.draw_networkx_edge_labels(G, pos,
                                 edge_labels=dict([((u, v,), d['name']) for u, v, d in G.edges(data=True)]))
    nx.draw_networkx_edges(G, pos,
                           edgelist=[edge for edge in G.edges()],
                           arrows=True)

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 inputASL(network,inputc):
    """
    Returns the average shortest path length within the input-receiving subgraph.

    Args:
        network: networkx graph
        inputc: MxN array, all nonzero positions are treated as 'input receiving'
    """
    inputnodes = [tuple(ind) for ind in np.transpose(inputc.nonzero())]
    lengths = [nx.shortest_path_length(network,src,trg) for src in inputnodes for trg in inputnodes]
    return np.mean(lengths)

def distances_to_roi(network,inputc,roi):
    """
    Returns a list of shortest path lengths from each
    input-receiving cell to all measured cells.

    Args:
        network: networkx graph
        inputc: MxN array, nonzero positions are treated as 'input receiving'
        inputc: MxN array, nonzero positions are treated as 'measured'
    """
    inputnodes = [tuple(ind) for ind in np.transpose(inputc.nonzero())]
    roinodes   = [tuple(ind) for ind in np.transpose(roi.nonzero())]
    lengths = [nx.shortest_path_length(network,src,trg) for src in inputnodes for trg in roinodes]
    return lengths

def createroiidxs(network,distance):
    """
    Choose two central nodes, some distance apart, and return their (i,j) indices.

    Args:
        network: networkx graph
        distance: how far apart the two nodes should be.

    Returns:
        A tuple of two (i,j) indices / node labels
    """
    nodes,centralities = zip(*nx.closeness_centrality(network).items())
    # sort nodes from most central to least central:
    centr_arxs = np.argsort(centralities)
    nodes_sorted = [n for n in reversed(np.array(nodes)[centr_arxs])]
    k = 0
    while k<len(nodes_sorted):
        # pick some node in the middle of the graph (high centrality)
        middlenode = tuple(nodes_sorted[k])
        # now pick the most central node that meets the given distance criterion.
        # [since we dont want to end up near the boundaries)
        for n in nodes_sorted:
            if nx.shortest_path_length(network,middlenode,tuple(n)) == distance:
                return middlenode,tuple(n)
        # if that didnt work, try starting with a different, less central middlenode.
        k = k+1
    raise Exception("speficied distance to high for this network")

def plot_tasks_dependency_graph(tasks, ax=None):
    """Plot the graph of all inter-dependencies in the provided tasks list."""
    if not NX_AVAILABLE:
        raise ImportError("Install Networkx to plot task dependency graphs.")
    if not MATPLOTLIB_AVAILABLE:
        raise ImportError("Install Matplotlib to plot task dependency graphs.")
    g = nx.DiGraph()
    tasks_dict = {
        task.id: task
        for task in tasks
    }
    for task_id, task in tasks_dict.items():
        for parent_task in task.follows:
            g.add_edge(parent_task.id, task_id)

    nodes_depths = {
        node: 0
        for node in g.nodes()
    }
    for source, lengths in nx.shortest_path_length(g):
        for target, length in lengths.items():
            nodes_depths[target] = max(nodes_depths[target], length)
    levels = [
        sorted([
            node
            for node, depth in nodes_depths.items()
            if depth == this_depth
        ])[::-1]
        for this_depth in range(max(nodes_depths.values()) + 1)
    ]

    def draw_node(x, y, node, ax):
        task = tasks_dict[node]
        text = task.name.replace("_", "\n") + "\nduration: %d" % task.duration
        ax.text(x, y, text, verticalalignment="center",
                horizontalalignment="center",
                bbox={'facecolor': 'white', 'lw': 0})
    return plot_tree_graph(levels, g.edges(), draw_node, width_factor=2, ax=ax)

def truncate_graph_dist(G, source_node, max_distance=1000, weight='length', retain_all=False):
    """
    Remove everything further than some network distance from a specified node
    in graph.

    Parameters
    ----------
    G : networkx multidigraph
    source_node : int
        the node in the graph from which to measure network distances to other
        nodes
    max_distance : int
        remove every node in the graph greater than this distance from the
        source_node
    weight : string
        how to weight the graph when measuring distance (default 'length' is
        how many meters long the edge is)
    retain_all : bool
        if True, return the entire graph even if it is not connected

    Returns
    -------
    networkx multidigraph
    """

    # get the shortest distance between the node and every other node, then
    # remove every node further than max_distance away
    start_time = time.time()
    G = G.copy()
    distances = nx.shortest_path_length(G, source=source_node, weight=weight)
    distant_nodes = {key:value for key, value in dict(distances).items() if value > max_distance}
    G.remove_nodes_from(distant_nodes.keys())
    log('Truncated graph by weighted network distance in {:,.2f} seconds'.format(time.time()-start_time))

    # remove any isolated nodes and retain only the largest component (if
    # retain_all is True)
    if not retain_all:
        G = remove_isolated_nodes(G)
        G = get_largest_component(G)

    return G

def getNearestUnvisited(self, currentNode):
        shortestLength = self.farAway
        for node in self.g.nodes():
            if self.g.degree(node) < node.nbPathsOut + 1:
                length = nx.shortest_path_length(self.g, currentNode, node, weight = 'weight')
                print "Length to node ", node.uid, ": ", length
                if length < shortestLength:
                    nearestUnvisited = node
                    shortestLength = length
        print "Distance to nearest node with unvisited paths: ", shortestLength
        return nearestUnvisited

def calc_arc_choord(anno, nxg=None):
    """
    Calculates the arc choord length of an annotation object as a measure of
    the tortuosity of an annotation. The return value is 1 for a completely
    straight skeleton. It uses the two most distant end nodes in an
    annotation and divides it by the graph path length between them.
    :param anno:
    :param nxg:
    :return: float
    """

    if not nxg:
        nxg = su.annoToNXGraph(anno)

    # find end nodes
    e_nodes = list({k for k, v in nxg.degree().iteritems() if v == 1})
    # get euclidian distance between end nodes max away
    # this can be done more efficiently by computing a convex hull first,
    # but the naive implementation should be fast enough for now
    dists = []
    for pair in itertools.permutations(e_nodes, 2):
        dists.append((pair, pair[0].distance_scaled(pair[1])))
    dists = sorted(dists, key=lambda x: x[1])
    try:
        path_len = nx.shortest_path_length(nxg, source=dists[-1][0][0],
                                           target=dists[-1][0][1],
                                           weight='weight')
    except:
        # print('No path between nodes for tortuosity calculation for neuron %s' %
        #       anno.filename)
        return 0
    return dists[-1][1] / path_len

def _score(self, freq, scores, row, col, memoization=None):
        mem = memoization if memoization is not None else [False] * scores.shape[1]

        # memoization hit
        if mem[col]: return scores[row, col]

        children = self.hierarchy.successors(self.feature_names[col] if self.feature_names else col)
        if len(children) == 0:
            # Base case for leaves
            scores[row, col] = freq[row, col]
            mem[col] = True
            return scores[row, col]

        # recursively compute children score
        score = float(0)
        for child in children:
            child_idx = self.vocabulary[child] if self.vocabulary else child
            score += self._score(freq, scores, row, child_idx, memoization=mem)

        # scale them with some method specific factor
        if self.method in ["bell", "belllog"]:
            k = nx.shortest_path_length(self.hierarchy, self.root, self.feature_names[col] if self.feature_names else col)
            print(k+1, self.levels[k+1])
            print("Count of children:", len(children))
            denom = self.levels[k+1]
            if self.method == "belllog": denom = log(denom, 10) #TODO problem when zero
            score *= 1.0 / denom
        elif self.method == "children":
            score *= 1.0 / len(children)
        elif self.method == "basic":
            score *= self.decay 

        # add the freq of the concept just now since it should not be scaled
        score += freq[row, col]


        scores[row, col] = score
        mem[col] = True

        return scores[row, col]

def fit(self, X, y=None):
        # the bell methods require additional information
        if self.method in ["bell", "belllog"]:
            # precompute node count by level
            self.levels = defaultdict(int)
            for node in self.hierarchy.nodes():
                l = nx.shortest_path_length(self.hierarchy, self.root, node)
                self.levels[l] += 1


            print(self.levels)
        return self

def compute_potentials(pa):
    '''Computes the potential function for each state of the product automaton.
    The potential function represents the minimum distance to a self-reachable
    final state in the product automaton.
    '''
    assert 'v' not in pa.g
    # add virtual node which connects to all initial states in the product
    pa.g.add_node('v')
    pa.g.add_edges_from([('v', p) for p in pa.init])
    # create strongly connected components of the product automaton w/ 'v'
    scc = list(nx.strongly_connected_components(pa.g))
    dag = nx.condensation(pa.g, scc)
    # get strongly connected component which contains 'v'
    for k, sc in enumerate(scc[::-1]):
        if 'v' in sc:
            start = len(scc) - k - 1
            break
    assert 'v' in scc[start]
    assert map(lambda sc: 'v' in sc, scc).count(True) == 1
    # get self-reachable final states
    pa.srfs = self_reachable_final_states_dag(pa, dag, scc, start)
    # remove virtual node from product automaton
    pa.g.remove_node('v')
    assert 'v' not in pa.g
    if not pa.srfs:
        return False
    # add artificial node 'v' and edges from the set of self reachable
    # states (pa.srfs) to 'v'
    pa.g.add_node('v')
    for p in pa.srfs:
        pa.g.add_edge(p, 'v', **{'weight': 0})
    # compute the potentials for each state of the product automaton
    lengths = nx.shortest_path_length(pa.g, target='v', weight='weight')
    for p in pa.g:
        pa.g.node[p]['potential'] = lengths[p]
    # remove virtual state 'v'
    pa.g.remove_node('v')
    return True

def remove_trap_states(self):
        '''
        Removes all states of the automaton which do not reach a final state.
        Returns True whenever trap states have been removed from the automaton.
        '''
        # add virtual state which has incoming edges from all final states
        self.g.add_edges_from([(state, 'virtual') for state in self.final])
        # compute trap states
        trap_states = set(self.g.nodes_iter())
        trap_states -= set(nx.shortest_path_length(self.g, target='virtual'))
        # remove trap state and virtual state
        self.g.remove_nodes_from(trap_states | set(['virtual']))
        return len(trap_states - set(['virtual'])) == 0

def remove_trap_states(self):
        '''
        Removes all states of the automaton which do not reach a final state.
        Returns True whenever trap states have been removed from the automaton.
        '''
        # add virtual state which has incoming edges from all final states
        self.g.add_edges_from([(state, 'virtual') for state in self.final])
        # compute trap states
        trap_states = set(self.g.nodes_iter())
        trap_states -= set(nx.shortest_path_length(self.g, target='virtual'))
        # remove trap state and virtual state
        self.g.remove_nodes_from(trap_states | set(['virtual']))
        return len(trap_states - set(['virtual'])) == 0

def remove_trap_states(self):
        '''
        Removes all states of the automaton which do not reach a final state.
        Returns True whenever trap states have been removed from the automaton.
        '''
        # add virtual state which has incoming edges from all final states
        self.g.add_edges_from([(state, 'virtual') for state in self.final])
        # compute trap states
        trap_states = set(self.g.nodes_iter())
        trap_states -= set(nx.shortest_path_length(self.g, target='virtual'))
        # remove trap state and virtual state
        self.g.remove_nodes_from(trap_states | set(['virtual']))
        return len(trap_states - set(['virtual'])) == 0

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 create_profile_graph(self, y_values):
        self.regenerate_network(load_names=False, gen_names=False)

        swing_bus = self.swing_bus
        bus_distance_matrix_df = pd.DataFrame(nx.shortest_path_length(self.graph))

        pos = dict()
        for k, v in bus_distance_matrix_df.loc[swing_bus].sort_values().to_dict().items():
            pos[k] = (v, y_values[k])

        self.positions = pos

def sp_kernel(g1, g2=None):
    if g2 != None:
        graphs = []
        for g in g1:
            graphs.append(g)
        for g in g2:
            graphs.append(g)
    else:
        graphs = g1

    sp_lengths = []

    for graph in graphs:
        sp_lengths.append(nx.shortest_path_length(graph))

    N = len(graphs)
    all_paths = {}
    sp_counts = {}
    for i in range(N):
        sp_counts[i] = {}
        nodes = graphs[i].nodes()
        for v1 in nodes:
            for v2 in nodes:
                if v2 in sp_lengths[i][v1]:
                    label = sp_lengths[i][v1][v2]
                    if label in sp_counts[i]:
                        sp_counts[i][label] += 1
                    else:
                        sp_counts[i][label] = 1

                    if label not in all_paths:
                        all_paths[label] = len(all_paths)

    phi = lil_matrix((N,len(all_paths)))

    for i in range(N):
        for label in sp_counts[i]:
            phi[i,all_paths[label]] = sp_counts[i][label]

    if g2 != None:
        K = np.dot(phi[:len(g1),:],phi[len(g1):,:].T)
    else:
        K = np.dot(phi,phi.T)

    K = np.asarray(K.todense())

    return K

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)