<commit_before>from warnings import warn

from libpysal import cg
from libpysal.common import requires

try:
    import geopandas as gpd
    from shapely.geometry import Point, LineString
except ImportError:
    err_msg = 'geopandas/shapely not available. '\
              + 'Some functionality will be disabled.'
    warn(err_msg)

import numpy as np


def compute_length(v0, v1):
    """Compute the euclidean distance between two points.
    
    Parameters
    ----------
    
    v0 : tuple
        sequence in the form x, y
    
    vq : tuple
        sequence in the form x, y
    
    Returns
    --------
    
    euc_dist : float
        Euclidean distance
    
    Examples
    --------
    
    >>> import spaghetti as spgh
    >>> point1, point2 = (0,0), (1,1)
    >>> spgh.util.compute_length(point1, point2)
    1.4142135623730951
    
    """
    euc_dist = np.sqrt((v0[0] - v1[0])**2 + (v0[1] - v1[1])**2)
    return euc_dist


def get_neighbor_distances(ntw, v0, l):
    """Get distances to the nearest node neighbors along
    connecting edges.
    
    Parameters
    ----------
    
    ntw : spaghetti.Network
        spaghetti Network object.
    
    v0 : int
        Node id
    
    l : dict
        key is tuple (start node, end node); value is ``float``.
        Cost per edge to travel, e.g. distance.
    
    Returns
    -------
    
    neighbors : dict
        key is int (node id); value is ``float`` (distance)
    
    Examples
    --------
    
    >>> import spaghetti as spgh
    >>> from libpysal import examples
    >>> ntw = spgh.Network(examples.get_path('streets.shp'))
    >>> neighs = spgh.util.get_neighbor_distances(ntw, 0,
    ...                                           ntw.edge_lengths)
    >>> neighs[1]
    102.62353453439829
    
    """
    edges = ntw.enum_links_node(v0)
    neighbors = {}
    for e in edges:
        if e[0] != v0:
            neighbors[e[0]] = l[e]
        else:
            neighbors[e[1]] = l[e]
    return neighbors


def generatetree(pred):
    """Rebuild the shortest path from root origin to destination.
    
    Parameters
    ----------
    
    pred : list
        List of preceeding nodes for traversal route.
    
    Returns
    --------
    
    tree : dict
        key is root origin; value is root origin to destination.
    
    Examples
    --------
    
    >>> import spaghetti as spgh
    >>> from libpysal import examples
    >>> ntw = spgh.Network(examples.get_path('streets.shp'))
    >>> distance, pred = spgh.util.dijkstra(ntw, ntw.edge_lengths, 0)
    >>> tree = spgh.util.generatetree(pred)
    >>> tree[3]
    [23, 22, 20, 19, 170, 2, 0]
    
    """
    tree = {}
    for i, p in enumerate(pred):
        if p == -1:
            # root node
            tree[i] = [i]
            continue
        idx = p
        path = [idx]
        while idx >= 0:
            nextnode = pred[idx]
            idx = nextnode
            if idx >= 0:
                path.append(nextnode)
        tree[i] = path
    return tree


def dijkstra(ntw, cost, v0, initial_dist=np.inf):
    """Compute the shortest path between a start node and all other
    nodes in an origin-destination matrix.
    
    Parameters
    ----------
    
    ntw :  spaghetti.Network
        spaghetti Network object.
    
    cost : dict
        key is tuple (start node, end node); value is ``float``.
        Cost per edge to travel, e.g. distance.
    
    v0 : int
        Start node ID
    
    initial_dist : float
        integer break point to stop iteration and return n neighbors.
        Default is ``'inf'``.
    
    Returns
    -------
    
    distance : list
        List of distances from node to all other nodes.
    
    pred : list
        List of preceeding nodes for traversal route.
    
    Notes
    -----
    
    Based on :cite:`Dijkstra1959a`.
    
    Examples
    --------
    
    >>> import spaghetti as spgh
    >>> from libpysal import examples
    >>> ntw = spgh.Network(examples.get_path('streets.shp'))
    >>> distance, pred = spgh.util.dijkstra(ntw, ntw.edge_lengths, 0)
    >>> round(distance[196], 4)
    5505.6682
    >>> pred[196]
    133
    
    """
    
    distance = [initial_dist for x in ntw.node_list]
    idx = ntw.node_list.index(v0)
    distance[ntw.node_list.index(v0)] = 0
    pred = [-1 for x in ntw.node_list]
    a = set()
    a.add(v0)
    while len(a) > 0:
        # Get node with the lowest value from distance.
        dist = initial_dists
        for node in a:
            if distance[node] < dist:
                dist = distance[node]<commit_msg>fixing variable typo in dijkstra<commit_after>from warnings import warn

from libpysal import cg
from libpysal.common import requires

try:
    import geopandas as gpd
    from shapely.geometry import Point, LineString
except ImportError:
    err_msg = 'geopandas/shapely not available. '\
              + 'Some functionality will be disabled.'
    warn(err_msg)

import numpy as np


def compute_length(v0, v1):
    """Compute the euclidean distance between two points.
    
    Parameters
    ----------
    
    v0 : tuple
        sequence in the form x, y
    
    vq : tuple
        sequence in the form x, y
    
    Returns
    --------
    
    euc_dist : float
        Euclidean distance
    
    Examples
    --------
    
    >>> import spaghetti as spgh
    >>> point1, point2 = (0,0), (1,1)
    >>> spgh.util.compute_length(point1, point2)
    1.4142135623730951
    
    """
    euc_dist = np.sqrt((v0[0] - v1[0])**2 + (v0[1] - v1[1])**2)
    return euc_dist


def get_neighbor_distances(ntw, v0, l):
    """Get distances to the nearest node neighbors along
    connecting edges.
    
    Parameters
    ----------
    
    ntw : spaghetti.Network
        spaghetti Network object.
    
    v0 : int
        Node id
    
    l : dict
        key is tuple (start node, end node); value is ``float``.
        Cost per edge to travel, e.g. distance.
    
    Returns
    -------
    
    neighbors : dict
        key is int (node id); value is ``float`` (distance)
    
    Examples
    --------
    
    >>> import spaghetti as spgh
    >>> from libpysal import examples
    >>> ntw = spgh.Network(examples.get_path('streets.shp'))
    >>> neighs = spgh.util.get_neighbor_distances(ntw, 0,
    ...                                           ntw.edge_lengths)
    >>> neighs[1]
    102.62353453439829
    
    """
    edges = ntw.enum_links_node(v0)
    neighbors = {}
    for e in edges:
        if e[0] != v0:
            neighbors[e[0]] = l[e]
        else:
            neighbors[e[1]] = l[e]
    return neighbors


def generatetree(pred):
    """Rebuild the shortest path from root origin to destination.
    
    Parameters
    ----------
    
    pred : list
        List of preceeding nodes for traversal route.
    
    Returns
    --------
    
    tree : dict
        key is root origin; value is root origin to destination.
    
    Examples
    --------
    
    >>> import spaghetti as spgh
    >>> from libpysal import examples
    >>> ntw = spgh.Network(examples.get_path('streets.shp'))
    >>> distance, pred = spgh.util.dijkstra(ntw, ntw.edge_lengths, 0)
    >>> tree = spgh.util.generatetree(pred)
    >>> tree[3]
    [23, 22, 20, 19, 170, 2, 0]
    
    """
    tree = {}
    for i, p in enumerate(pred):
        if p == -1:
            # root node
            tree[i] = [i]
            continue
        idx = p
        path = [idx]
        while idx >= 0:
            nextnode = pred[idx]
            idx = nextnode
            if idx >= 0:
                path.append(nextnode)
        tree[i] = path
    return tree


def dijkstra(ntw, cost, v0, initial_dist=np.inf):
    """Compute the shortest path between a start node and all other
    nodes in an origin-destination matrix.
    
    Parameters
    ----------
    
    ntw :  spaghetti.Network
        spaghetti Network object.
    
    cost : dict
        key is tuple (start node, end node); value is ``float``.
        Cost per edge to travel, e.g. distance.
    
    v0 : int
        Start node ID
    
    initial_dist : float
        integer break point to stop iteration and return n neighbors.
        Default is ``'inf'``.
    
    Returns
    -------
    
    distance : list
        List of distances from node to all other nodes.
    
    pred : list
        List of preceeding nodes for traversal route.
    
    Notes
    -----
    
    Based on :cite:`Dijkstra1959a`.
    
    Examples
    --------
    
    >>> import spaghetti as spgh
    >>> from libpysal import examples
    >>> ntw = spgh.Network(examples.get_path('streets.shp'))
    >>> distance, pred = spgh.util.dijkstra(ntw, ntw.edge_lengths, 0)
    >>> round(distance[196], 4)
    5505.6682
    >>> pred[196]
    133
    
    """
    
    distance = [initial_dist for x in ntw.node_list]
    idx = ntw.node_list.index(v0)
    distance[ntw.node_list.index(v0)] = 0
    pred = [-1 for x in ntw.node_list]
    a = set()
    a.add(v0)
    while len(a) > 0:
        # Get node with the lowest value from distance.
        dist = initial_dist
        for node in a:
            if distance[node] < dist:
                dist = distance[node]
{'fraction_non_alphanumeric': 0.1176726955763783, 'fraction_numerical': 0.024624101111353235, 'mean_word_length': 1.6737547334692688, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 129, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '64586', 'n_tokens_mistral': 3049, 'n_tokens_neox': 2914, 'n_words': 851}