#!/usr/bin/env python

# connectivity.py
# definitions of connectivity characters
import collections
import math
from typing import Any

import networkx as nx
import numpy as np
from pandas import Series
from tqdm.auto import tqdm

__all__ = [
    "node_degree",
    "meshedness",
    "mean_node_dist",
    "cds_length",
    "mean_node_degree",
    "proportion",
    "cyclomatic",
    "edge_node_ratio",
    "gamma",
    "clustering",
    "closeness_centrality",
    "betweenness_centrality",
    "straightness_centrality",
    "subgraph",
    "mean_nodes",
    "node_density",
]


def node_degree(graph: nx.Graph, name: str = "degree") -> nx.Graph:
    """
    Calculates node degree for each node. Wrapper around ``networkx.degree()``.

    Parameters
    ----------
    graph : networkx.Graph
        A Graph representing a street network.
        Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`.
    name : str (default 'degree')
        The calculated attribute name.

    Returns
    -------
    netx : Graph
        A networkx.Graph object .

    Examples
    --------
    >>> network_graph = mm.node_degree(network_graph)
    """
    netx = graph.copy()

    degree = dict(nx.degree(netx))
    nx.set_node_attributes(netx, degree, name)

    return netx


def _meshedness(graph: nx.Graph) -> float:
    """Calculates meshedness of a graph."""
    e = graph.number_of_edges()
    v = graph.number_of_nodes()
    return (e - v + 1) / (2 * v - 5)


def meshedness(
    graph: nx.Graph,
    radius: int = 5,
    name: str = "meshedness",
    distance: Any | None = None,
    verbose: bool = True,
) -> nx.Graph:
    """
    Calculates meshedness for subgraph around each node if radius is set, or for
    whole graph, if ``radius=None``. A subgraph is generated around each node within
    set radius. If ``distance=None``, radius will define topological distance,
    otherwise it uses values in distance attribute.

    .. math::
        \\alpha=\\frac{e-v+1}{2 v-5}

    where :math:`e` is the number of edges in a subgraph and :math:`v`
    is the number of nodes in a subgraph.

    Adapted from :cite:`feliciotti2018`.

    Parameters
    ----------
    graph : networkx.Graph
        A Graph representing a street network.
        Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`.
    radius: int, optional
        Include all neighbors of distance <= radius from ``n``.
    name : str, optional
        The calculated attribute name.
    distance : str, optional
        Use specified edge data key as distance. For example, setting
        ``distance=’weight’`` will use the edge ``weight`` to
        measure the distance from the node ``n``.
    verbose : bool (default True)
        If ``True``, shows progress bars in loops and indication of steps.

    Returns
    -------
    netx : Graph
        A networkx.Graph object if ``radius`` is set.
    float
        The meshedness for the graph if ``radius=None``.

    Examples
    --------
    >>> network_graph = mm.meshedness(network_graph, radius=800, distance='edge_length')
    """
    netx = graph.copy()

    if radius:
        for n in tqdm(netx, total=len(netx), disable=not verbose):
            sub = nx.ego_graph(
                netx, n, radius=radius, distance=distance
            )  # define subgraph of steps=radius
            netx.nodes[n][name] = _meshedness(
                sub
            )  # save value calulated for subgraph to node

        return netx

    return _meshedness(netx)


def mean_node_dist(
    graph: nx.Graph, name: str = "meanlen", length: str = "mm_len", verbose: bool = True
) -> nx.Graph:
    """
    Calculates mean distance to neighbouring nodes.
    Mean of values in ``length`` attribute.

    Parameters
    ----------
    graph : networkx.Graph
        A Graph representing a street network.
        Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`.
    name : str, optional
        The calculated attribute name.
    length : str, optional
        The name of the attribute of segment length (geographical).
    verbose : bool (default True)
        If ``True``, shows progress bars in loops and indication of steps.

    Returns
    -------
    netx : Graph
        A networkx.Graph object.

    Examples
    --------
    >>> network_graph = mm.mean_node_dist(network_graph)
    """
    netx = graph.copy()

    for n, nbrs in tqdm(netx.adj.items(), total=len(netx), disable=not verbose):
        lengths = []
        for _nbr, keydict in nbrs.items():
            for _key, eattr in keydict.items():
                lengths.append(eattr[length])
        netx.nodes[n][name] = np.mean(lengths)

    return netx


def _cds_length(graph: nx.Graph, mode, length):
    """Calculates cul-de-sac length in a graph."""
    lens = []
    for u, v, k, cds in graph.edges.data("cdsbool", keys=True):
        if cds:
            lens.append(graph[u][v][k][length])
    if mode == "sum":
        return sum(lens)
    if mode == "mean":
        return np.mean(lens)
    raise ValueError(f"Mode '{mode}' is not supported. Use 'sum' or 'mean'.")


def cds_length(
    graph: nx.Graph,
    radius: int = 5,
    mode: str = "sum",
    name: str = "cds_len",
    degree: str = "degree",
    length: str = "mm_len",
    distance: Any | None = None,
    verbose: bool = True,
) -> nx.Graph:
    """
    Calculates length of cul-de-sacs for subgraph around each node if radius is set,
    or for whole graph, if ``radius=None``. A subgraph is generated around each node
    within set radius. If ``distance=None``, radius will define topological distance,
    otherwise it uses values in distance attribute.


    Parameters
    ----------
    graph : networkx.Graph
        A Graph representing a street network.
        Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`.
    radius : int
        Include all neighbors of distance <= radius from ``n``.
    mode : str (default 'sum')
        If ``'sum'``, calculate total length, if ``'mean'`` calculate mean length.
    name : str, optional
        The calculated attribute name.
    degree : str
        The name of attribute of node degree (:py:func:`momepy.node_degree`).
    length : str, optional
        The name of the attribute of segment length (geographical).
    distance : str, optional
        Use specified edge data key as distance. For example, setting
        ``distance=’weight’`` will use the edge ``weight`` to
        measure the distance from the node ``n``.
    verbose : bool (default True)
        If ``True``, shows progress bars in loops and indication of steps.

    Returns
    -------
    netx : Graph
        A networkx.Graph object if ``radius`` is set.
    float
        The length of cul-de-sacs for the graph if ``radius=None``.

    Examples
    --------
    >>> network_graph = mm.cds_length(network_graph, radius=9, mode='mean')
    """
    # node degree needed beforehand
    netx = graph.copy()

    for u, v, k in netx.edges(keys=True):
        if netx.nodes[u][degree] == 1 or netx.nodes[v][degree] == 1:
            netx[u][v][k]["cdsbool"] = True
        else:
            netx[u][v][k]["cdsbool"] = False

    if radius:
        for n in tqdm(netx, total=len(netx), disable=not verbose):
            sub = nx.ego_graph(
                netx, n, radius=radius, distance=distance
            )  # define subgraph of steps=radius
            netx.nodes[n][name] = _cds_length(
                sub, mode=mode, length=length
            )  # save value calculated for subgraph to node

        return netx

    return _cds_length(netx, mode=mode, length=length)


def _mean_node_degree(graph: nx.Graph, degree):
    """Calculates mean node degree in a graph."""
    return np.mean(list(dict(graph.nodes(degree)).values()))


def mean_node_degree(
    graph: nx.Graph,
    radius: int = 5,
    name: str = "mean_nd",
    degree: str = "degree",
    distance: Any | None = None,
    verbose: bool = True,
) -> nx.Graph:
    """
    Calculates mean node degree for subgraph around each node if radius is set, or for
    whole graph, if ``radius=None``. A subgraph is generated around each node within
    set radius. If ``distance=None``, radius will define topological distance,
    otherwise it uses values in ``distance`` attribute.

    Parameters
    ----------
    graph : networkx.Graph
        A Graph representing a street network.
        Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`.
    radius: int
        Include all neighbors of distance <= radius from ``n``.
    name : str, optional
        The calculated attribute name.
    degree : str
        The name of attribute of node degree (:py:func:`momepy.node_degree`).
    distance : str, optional
        Use specified edge data key as distance. For example, setting
        ``distance=’weight’`` will use the edge ``weight`` to
        measure the distance from the node ``n``.
    verbose : bool (default True)
        If ``True``, shows progress bars in loops and indication of steps.

    Returns
    -------
    netx : Graph
        A networkx.Graph object if ``radius`` is set.
    float
        The mean node degree for the graph if ``radius=None``.

    Examples
    --------
    >>> network_graph = mm.mean_node_degree(network_graph, radius=3)
    """
    netx = graph.copy()

    if radius:
        for n in tqdm(netx, total=len(netx), disable=not verbose):
            sub = nx.ego_graph(
                netx, n, radius=radius, distance=distance
            )  # define subgraph of steps=radius
            netx.nodes[n][name] = _mean_node_degree(sub, degree=degree)

        return netx

    return _mean_node_degree(netx, degree=degree)


def _proportion(graph: nx.Graph, degree):
    """Calculates the proportion of intersection types in a graph."""

    counts = collections.Counter(dict(graph.nodes(degree)).values())
    return counts


def proportion(
    graph: nx.Graph,
    radius: int = 5,
    three: str | None = None,
    four: str | None = None,
    dead: str | None = None,
    degree: str = "degree",
    distance: Any | None = None,
    verbose: bool = True,
) -> nx.Graph:
    """
    Calculates the proportion of intersection types for subgraph around each node if
    radius is set, or for whole graph, if ``radius=None``. A subgraph is generated
    around each node within set radius. If ``distance=None``, the radius will define
    topological distance, otherwise it uses values in ``distance`` attribute.

    Parameters
    ----------
    graph : networkx.Graph
        A Graph representing a street network.
        Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`.
    radius: int
        Include all neighbors of distance <= radius from ``n``.
    three : str, optional
        The attribute name for 3-way intersections proportion.
    four : str, optional
        The attribute name for 4-way intersections proportion.
    dead : str, optional
        The attribute name for deadends proportion.
    degree : str
        The name of attribute of node degree (:py:func:`momepy.node_degree`).
    distance : str, optional
        Use specified edge data key as distance. For example, setting
        ``distance=’weight’`` will use the edge ``weight`` to
        measure the distance from the node ``n``.
    verbose : bool (default True)
        If ``True``, shows progress bars in loops and indication of steps.

    Returns
    -------
    netx : Graph
        A networkx.Graph object if ``radius`` is set.
    result : dict
        A dict with proportions for the graph if ``radius=None``.

    Examples
    --------
    >>> network_graph = mm.proportion(
    ...     network_graph, three='threeway', four='fourway', dead='deadends'
    ... )  # noqa
    """
    if not three and not four and not dead:
        raise ValueError(
            "Nothing to calculate. Define names for at least "
            "one proportion to be calculated."
        )
    netx = graph.copy()

    if radius:
        for n in tqdm(netx, total=len(netx), disable=not verbose):
            sub = nx.ego_graph(
                netx, n, radius=radius, distance=distance
            )  # define subgraph of steps=radius
            counts = _proportion(sub, degree=degree)
            if three:
                netx.nodes[n][three] = counts[3] / len(sub)
            if four:
                netx.nodes[n][four] = counts[4] / len(sub)
            if dead:
                netx.nodes[n][dead] = counts[1] / len(sub)
        return netx

    # add example to docs explaining keys
    counts = _proportion(netx, degree=degree)
    result = {}
    if three:
        result[three] = counts[3] / len(netx)
    if four:
        result[four] = counts[4] / len(netx)
    if dead:
        result[dead] = counts[1] / len(netx)

    return result


def _cyclomatic(graph: nx.Graph) -> int:
    """Calculates the cyclomatic complexity of a graph."""
    e = graph.number_of_edges()
    v = graph.number_of_nodes()
    return e - v + 1


def cyclomatic(
    graph: nx.Graph,
    radius: int = 5,
    name: str = "cyclomatic",
    distance: Any | None = None,
    verbose: bool = True,
) -> nx.Graph:
    """
    Calculates cyclomatic complexity for subgraph around each node if radius is set, or
    for whole graph, if ``radius=None``. A subgraph is generated around each node
    within set radius. If ``distance=None``, radius will define topological distance,
    otherwise it uses values in ``distance`` attribute.

    .. math::
        \\alpha=e-v+1

    where :math:`e` is the number of edges in subgraph and :math:`v` is the number of
    nodes in subgraph.

    Adapted from :cite:`bourdic2012`.

    Parameters
    ----------
    graph : networkx.Graph
        A Graph representing a street network.
        Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`.
    radius: int
        Include all neighbors of distance <= radius from ``n``.
    name : str, optional
        The calculated attribute name.
    distance : str, optional
        Use specified edge data key as distance. For example, setting
        ``distance=’weight’`` will use the edge ``weight`` to
        measure the distance from the node ``n``.
    verbose : bool (default True)
        If ``True``, shows progress bars in loops and indication of steps.

    Returns
    -------
    netx : Graph
        A networkx.Graph object if ``radius`` is set.
    float
        The cyclomatic complexity for the graph if ``radius=None``.

    Examples
    --------
    >>> network_graph = mm.cyclomatic(network_graph, radius=3)
    """
    netx = graph.copy()

    if radius:
        for n in tqdm(netx, total=len(netx), disable=not verbose):
            sub = nx.ego_graph(
                netx, n, radius=radius, distance=distance
            )  # define subgraph of steps=radius
            netx.nodes[n][name] = _cyclomatic(
                sub
            )  # save value calulated for subgraph to node

        return netx

    return _cyclomatic(netx)


def _edge_node_ratio(graph: nx.Graph) -> float:
    """Calculates edge / node ratio of a graph."""
    e = graph.number_of_edges()
    v = graph.number_of_nodes()
    return e / v


def edge_node_ratio(
    graph: nx.Graph,
    radius: int = 5,
    name: str = "edge_node_ratio",
    distance: Any | None = None,
    verbose: bool = True,
) -> nx.Graph:
    """
    Calculates edge / node ratio for subgraph around each node if radius is set, or for
    whole graph, if ``radius=None``. A subgraph is generated around each node within
    set radius. If ``distance=None``, radius will define topological distance,
    otherwise it uses values in ``distance`` attribute.

    .. math::
        \\alpha=e/v

    where :math:`e` is the number of edges in subgraph and :math:`v` is the number of
    nodes in subgraph.

    Adapted from :cite:`dibble2017`.

    Parameters
    ----------
    graph : networkx.Graph
        A Graph representing a street network.
        Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`.
    radius: int
        Include all neighbors of distance <= radius from ``n``.
    name : str, optional
        The calculated attribute name.
    distance : str, optional
        Use specified edge data key as distance. For example, setting
        ``distance=’weight’`` will use the edge ``weight`` to
        measure the distance from the node ``n``.
    verbose : bool (default True)
        If ``True``, shows progress bars in loops and indication of steps.

    Returns
    -------
    netx : Graph
        A networkx.Graph object if ``radius`` is set.
    float
        The edge / node ratio for the graph if ``radius=None``.

    Examples
    --------
    >>> network_graph = mm.edge_node_ratio(network_graph, radius=3)
    """
    netx = graph.copy()

    if radius:
        for n in tqdm(netx, total=len(netx), disable=not verbose):
            sub = nx.ego_graph(
                netx, n, radius=radius, distance=distance
            )  # define subgraph of steps=radius
            netx.nodes[n][name] = _edge_node_ratio(
                sub
            )  # save value calulated for subgraph to node

        return netx

    return _edge_node_ratio(netx)


def _gamma(graph: nx.Graph):
    """Calculates gamma index of a graph."""
    e = graph.number_of_edges()
    v = graph.number_of_nodes()
    if v == 2:
        return np.nan
    return e / (3 * (v - 2))  # save value calulated for subgraph to node


def gamma(
    graph: nx.Graph,
    radius: int = 5,
    name: str = "gamma",
    distance: Any | None = None,
    verbose: bool = True,
) -> nx.Graph:
    """
    Calculates connectivity gamma index for subgraph around each node if radius is set,
    or for whole graph, if ``radius=None``. A subgraph is generated around each node
    within set radius. If ``distance=None``, radius will define topological distance,
    otherwise it uses values in ``distance`` attribute.

    .. math::
        \\alpha=\\frac{e}{3(v-2)}

    where :math:`e` is the number of edges in subgraph and :math:`v` is the number of
    nodes in subgraph.

    Adapted from :cite:`dibble2017`.

    Parameters
    ----------
    graph : networkx.Graph
        A Graph representing a street network.
        Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`.
    radius: int
        Include all neighbors of distance <= radius from ``n``.
    name : str, optional
        The calculated attribute name.
    distance : str, optional
        Use specified edge data key as distance. For example, setting
        ``distance=’weight’`` will use the edge ``weight`` to
        measure the distance from the node ``n``.
    verbose : bool (default True)
        If ``True``, shows progress bars in loops and indication of steps.

    Returns
    -------
    netx : Graph
        A networkx.Graph object if ``radius`` is set.
    float
        The gamma index for the graph if ``radius=None``.

    Examples
    --------
    >>> network_graph = mm.gamma(network_graph, radius=3)
    """
    netx = graph.copy()

    if radius:
        for n in tqdm(netx, total=len(netx), disable=not verbose):
            sub = nx.ego_graph(
                netx, n, radius=radius, distance=distance
            )  # define subgraph of steps=radius
            netx.nodes[n][name] = _gamma(sub)

        return netx

    return _gamma(netx)


def clustering(graph: nx.Graph, name: str = "cluster") -> nx.Graph:
    """
    Calculates the squares clustering coefficient for nodes.
    Wrapper around ``networkx.square_clustering``.

    Parameters
    ----------
    graph : networkx.Graph
        A Graph representing a street network.
        Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`.
    name : str, optional
        The calculated attribute name.

    Returns
    -------
    netx : Graph
        A networkx.Graph object.

    Examples
    --------
    >>> network_graph = mm.clustering(network_graph)
    """
    netx = graph.copy()

    vals = nx.square_clustering(netx)
    nx.set_node_attributes(netx, vals, name)

    return netx


def _closeness_centrality(graph: nx.Graph, u=None, length=None, len_graph=None):
    r"""Compute closeness centrality for nodes. Slight adaptation of networkx
    `closeness_centrality` to allow normalisation for local closeness.
    Adapted script used in networkx. The closeness centrality [1]_ of a node `u` is
    the reciprocal of the average shortest path distance to `u` over all
    `n-1` reachable nodes.

    .. math::

        C(u) = \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)},

    where `d(v, u)` is the shortest-path distance between `v` and `u`,
    and `n` is the number of nodes that can reach `u`. Notice that the
    closeness distance function computes the incoming distance to `u`
    for directed graphs. To use outward distance, act on `graph.reverse()`.

    Notice that higher values of closeness indicate higher centrality.

    Wasserman and Faust propose an improved formula for graphs with
    more than one connected component. The result is "a ratio of the
    fraction of actors in the group who are reachable, to the average
    distance" from the reachable actors [2]_. You might think this
    scale factor is inverted but it is not. As is, nodes from small
    components receive a smaller closeness value. Letting `N` denote
    the number of nodes in the graph,

    .. math::

        C_{WF}(u) = \frac{n-1}{N-1} \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)},

    Parameters
    ----------
    G : graph
        A NetworkX graph.
    u : node, optional
        Return only the value for node ``u``.
    distance : edge attribute key, optional (default=None)
        Use the specified edge attribute as the edge
        distance in shortest path calculations.
    len_graph : int
        The length of the complete graph.

    Returns
    -------
    nodes : dict
        Dictionary of nodes with closeness centrality as the value.

    References
    ----------
    .. [1] Linton C. Freeman: Centrality in networks: I.
       Conceptual clarification. Social Networks 1:215-239, 1979.
       http://leonidzhukov.ru/hse/2013/socialnetworks/papers/freeman79-centrality.pdf
    .. [2] pg. 201 of Wasserman, S. and Faust, K.,
       Social Network Analysis: Methods and Applications, 1994,
       Cambridge University Press.
    """

    if length is not None:
        import functools

        # use Dijkstra's algorithm with specified attribute as edge weight
        path_length = functools.partial(
            nx.single_source_dijkstra_path_length, weight=length
        )
    else:
        path_length = nx.single_source_shortest_path_length

    nodes = [u]
    closeness_centrality_ = dict.fromkeys(nodes, 0.0)
    for n in nodes:
        sp = dict(path_length(graph, n))
        totsp = sum(sp.values())
        if totsp > 0 and len(graph) > 1:
            closeness_centrality_[n] = (len(sp) - 1) / totsp
            # normalize to number of nodes-1 in connected part
            s = (len(sp) - 1) / (len_graph - 1)
            closeness_centrality_[n] *= s

    return closeness_centrality_[u]


def closeness_centrality(
    graph: nx.Graph,
    name: str = "closeness",
    weight: str = "mm_len",
    radius: int | None = None,
    distance: Any | None = None,
    verbose: bool = True,
    **kwargs,
) -> nx.Graph:
    """
    Calculates the closeness centrality for nodes.
    Wrapper around ``networkx.closeness_centrality``.
    Closeness centrality of a node `u` is the reciprocal of the
    average shortest path distance to `u` over all `n-1` nodes within reachable nodes.

    .. math::

        C(u) = \\frac{n - 1}{\\sum_{v=1}^{n-1} d(v, u)},

    where :math:`d(v, u)` is the shortest-path distance between :math:`v` and
    :math:`u`, and :math:`n` is the number of nodes that can reach :math:`u`.


    Parameters
    ----------
    graph : networkx.Graph
        A Graph representing a street network.
        Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`.
    name : str, optional
        The calculated attribute name.
    weight : str (default 'mm_len')
        The attribute holding the weight of edge (e.g. length, angle).
    radius: int
        Include all neighbors of distance <= radius from ``n``.
    distance : str, optional
        Use specified edge data key as distance.
        For example, setting ``distance=’weight’`` will use the edge ``weight`` to
        measure the distance from the node ``n`` during ``ego_graph`` generation.
    verbose : bool (default True)
        If ``True``, shows progress bars in loops and indication of steps.
    **kwargs : dict
        Keyword arguments for ``networkx.closeness_centrality``.

    Returns
    -------
    netx : Graph
        A networkx.Graph object.

    Examples
    --------
    >>> network_graph = mm.closeness_centrality(network_graph)
    """
    netx = graph.copy()

    if radius:
        lengraph = len(netx)
        for n in tqdm(netx, total=len(netx), disable=not verbose):
            sub = nx.ego_graph(
                netx, n, radius=radius, distance=distance
            )  # define subgraph of steps=radius
            netx.nodes[n][name] = _closeness_centrality(
                sub, n, length=weight, len_graph=lengraph
            )
    else:
        vals = nx.closeness_centrality(netx, distance=weight, **kwargs)
        nx.set_node_attributes(netx, vals, name)

    return netx


def betweenness_centrality(
    graph: nx.Graph,
    name: str = "betweenness",
    mode: str = "nodes",
    weight: str = "mm_len",
    endpoints: bool = True,
    radius: int | None = None,
    distance: Any | None = None,
    normalized: bool = False,
    verbose: bool = True,
    **kwargs,
) -> nx.Graph:
    """
    Calculates the shortest-path betweenness centrality for nodes.
    Wrapper around ``networkx.betweenness_centrality`` or
    ``networkx.edge_betweenness_centrality``.
    Betweenness centrality of a node `v` is the sum of the
    fraction of all-pairs shortest paths that pass through `v`

    .. math::

       c_B(v) =\\sum_{s,t \\in V} \\frac{\\sigma(s, t|v)}{\\sigma(s, t)}

    where `V` is the set of nodes, :math:`\\sigma(s, t)` is the number of
    shortest :math:`(s, t)`-paths,  and :math:`\\sigma(s, t|v)` is the number of
    those paths  passing through some  node `v` other than `s, t`.
    If `s = t`, :math:`\\sigma(s, t) = 1`, and if `v` in `{s, t}``,
    :math:`\\sigma(s, t|v) = 0`.
    Betweenness centrality of an edge `e` is the sum of the
    fraction of all-pairs shortest paths that pass through `e`

    .. math::

       c_B(e) =\\sum_{s,t \\in V} \\frac{\\sigma(s, t|e)}{\\sigma(s, t)}

    where `V` is the set of nodes, :math:`\\sigma(s, t)` is the number of
    shortest :math:`(s, t)`-paths, and :math:`\\sigma(s, t|e)` is the number of
    those paths passing through edge `e`.

    Adapted from :cite:`porta2006`.

    Parameters
    ----------
    graph : networkx.Graph
        A Graph representing a street network.
        Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`.
    name : str, optional
        The calculated attribute name.
    mode : str, default 'nodes'
        The mode of betweenness calculation. ``'node'`` for node-based
        or ``'edges'`` for edge-based.
    weight : str (default 'mm_len')
        The attribute holding the weight of edge (e.g. length, angle).
    radius: int
        Include all neighbors of distance <= radius from ``n``.
    distance : str, optional
        Use specified edge data key as distance.
        For example, setting ``distance=’weight’`` will use the edge ``weight`` to
        measure the distance from the node ``n`` during ``ego_graph`` generation.
    normalized : bool, optional
        If ``True`` the betweenness values are normalized by `2/((n-1)(n-2))`,
        where ``n`` is the number of nodes in a subgraph.
    verbose : bool (default True)
        If ``True``, shows progress bars in loops and indication of steps.
    **kwargs : dict
        Keyword argument for ``networkx.betweenness_centrality`` or
        ``networkx.edge_betweenness_centrality``.

    Returns
    -------
    netx : Graph
        A networkx.Graph object.

    Examples
    --------
    >>> network_graph = mm.betweenness_centrality(network_graph)

    Notes
    -----
    In case of angular betweenness, implementation is based on "Tasos Implementation".
    """
    netx = graph.copy()

    # has to be Graph not MultiGraph as MG is not supported by networkx2.4
    graph = nx.Graph()
    for u, v, k, data in netx.edges(data=True, keys=True):
        if graph.has_edge(u, v):
            if graph[u][v][weight] > netx[u][v][k][weight]:
                nx.set_edge_attributes(graph, {(u, v): data})
        else:
            graph.add_edge(u, v, **data)

    if radius:
        for n in tqdm(graph, total=len(graph), disable=not verbose):
            sub = nx.ego_graph(
                graph, n, radius=radius, distance=distance
            )  # define subgraph of steps=radius
            netx.nodes[n][name] = nx.betweenness_centrality(
                sub, weight=weight, normalized=normalized, **kwargs
            )[n]

    elif mode == "nodes":
        vals = nx.betweenness_centrality(
            graph, weight=weight, endpoints=endpoints, **kwargs
        )
        nx.set_node_attributes(netx, vals, name)
    elif mode == "edges":
        vals = nx.edge_betweenness_centrality(graph, weight=weight, **kwargs)
        for u, v, k in netx.edges(keys=True):
            try:
                val = vals[u, v]
            except KeyError:
                val = vals[v, u]
            netx[u][v][k][name] = val
    else:
        raise ValueError(f"Mode '{mode}' is not supported. Use 'nodes' or 'edges'.")

    return netx


def _euclidean(n, m):
    """Helper for straightness."""
    return math.sqrt((n[0] - m[0]) ** 2 + (n[1] - m[1]) ** 2)


def _straightness_centrality(graph: nx.Graph, weight, normalized=True):
    """Calculates straightness centrality."""
    straightness_centrality_ = dict.fromkeys(graph.nodes(), 0.0)

    for n in graph.nodes():
        sp = nx.single_source_dijkstra_path_length(graph, n, weight=weight)

        if len(sp) > 0 and len(graph) > 1:
            straightness = 0
            for target in sp:
                if n != target:
                    network_dist = sp[target]
                    euclidean_dist = _euclidean(n, target)
                    straightness = straightness + (euclidean_dist / network_dist)
            straightness_centrality_[n] = straightness * (1 / (len(graph) - 1))
            # normalize to number of nodes-1 in connected part
            if normalized and len(sp) > 1:
                s = (len(graph) - 1) / (len(sp) - 1)
                straightness_centrality_[n] *= s
    return straightness_centrality_


def straightness_centrality(
    graph: nx.Graph,
    weight: str = "mm_len",
    normalized: bool = True,
    name: str = "straightness",
    radius: int | None = None,
    distance: Any | None = None,
    verbose: bool = True,
) -> nx.Graph:
    """
    Calculates the straightness centrality for nodes.

    .. math::
        C_{S}(i)=\\frac{1}{n-1} \\sum_{j \\in V, j \\neq i} \\frac{d_{i j}^{E u}}
        {d_{i j}}

    where :math:`\\mathrm{d}^{\\mathrm{E} \\mathrm{u}}_{\\mathrm{ij}}` is the
    Euclidean distance between nodes `i` and `j` along a straight line.

    Adapted from :cite:`porta2006`.

    Parameters
    ----------
    graph : networkx.Graph
        A Graph representing a street network.
        Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`.
    weight : str (default 'mm_len')
        The attribute holding length of edge.
    normalized : bool
        Normalize to the number of ``nodes-1`` in the connected part
        (for local straightness it is recommended to set to ``normalized=False``).
    name : str, optional
        The calculated attribute name.
    radius: int
        Include all neighbors of distance <= radius from ``n``.
    distance : str, optional
        Use specified edge data key as distance.
        For example, setting ``distance=’weight’`` will use the edge ``weight`` to
        measure the distance from the node ``n`` during ``ego_graph`` generation.
    verbose : bool (default True)
        If ``True``, shows progress bars in loops and indication of steps.

    Returns
    -------
    netx : Graph
        A networkx.Graph object.

    Examples
    --------
    >>> network_graph = mm.straightness_centrality(network_graph)
    """
    netx = graph.copy()

    if radius:
        for n in tqdm(netx, total=len(netx), disable=not verbose):
            sub = nx.ego_graph(
                netx, n, radius=radius, distance=distance
            )  # define subgraph of steps=radius
            netx.nodes[n][name] = _straightness_centrality(
                sub, weight=weight, normalized=normalized
            )[n]
    else:
        vals = _straightness_centrality(netx, weight=weight, normalized=normalized)
        nx.set_node_attributes(netx, vals, name)

    return netx


def node_density(
    graph: nx.Graph,
    radius: int,
    length: str = "mm_len",
    distance: str | None = None,
    verbose: bool = True,
) -> nx.Graph:
    """Calculate the density of a node's neighbours (for all nodes)
    on the street network defined in ``graph``.

    Calculated as the number of neighbouring
    nodes / cumulative length of street network within neighbours.
    Returns two values - an unweighted and weighted density unweighted
    is calculated based on the number of neigbhouring nodes, whereas weighted
    density will take into account node degree as ``k-1``.

    Adapted from :cite:`dibble2017`.

    Parameters
    ----------
    graph : networkx.Graph
        A Graph representing a street network.
        Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`.
    radius: int
        Include all neighbors of distance <= radius from ``n``.
    length : str, default `mm_len`
        The name of the attribute of segment length (geographical).
    distance : str, optional
        Use specified edge data key as distance.
        For example, setting ``distance=’weight’`` will use the edge ``weight`` to
        measure the distance from the node ``n`` during ``ego_graph`` generation.
    verbose : bool (default True)
        If ``True``, shows progress bars in loops and indication of steps.

    Returns
    -------
    netx : Graph
        A networkx.Graph object.

    Examples
    --------
    >>> network_graph = mm.node_density(network_graph, radius: int=5)
    """
    netx = graph.copy()
    orig_nodes_degree = Series(nx.get_node_attributes(netx, "degree"))
    for n in tqdm(netx, total=len(netx), disable=not verbose):
        sub = nx.ego_graph(
            netx, n, radius=radius, distance=distance
        )  # define subgraph of steps=radius
        unweighted, weighted = _node_density(
            sub, length=length, orig_nodes_degree=orig_nodes_degree
        )
        netx.nodes[n]["node_density"] = unweighted
        netx.nodes[n]["node_density_weighted"] = weighted
    return netx


def _node_density(sub, length, orig_nodes_degree):
    """Calculates node density for a subgraph."""
    length_sum = sub.size(length)
    weighted_node_data = orig_nodes_degree[list(sub.nodes)] - 1
    unweighted_node_data = Series(1, index=weighted_node_data)
    unweighted = (unweighted_node_data.sum() / length_sum) if length_sum else 0
    weighted = (weighted_node_data.sum() / length_sum) if length_sum else 0
    return unweighted, weighted


def subgraph(
    graph: nx.Graph,
    radius: int = 5,
    distance: Any | None = None,
    meshedness: bool = True,
    cds_length: bool = True,
    mode: str = "sum",
    degree: str = "degree",
    length: str = "mm_len",
    mean_node_degree: bool = True,
    proportion: dict = {3: True, 4: True, 0: True},
    cyclomatic: bool = True,
    edge_node_ratio: bool = True,
    gamma: bool = True,
    local_closeness: bool = True,
    closeness_weight: Any | None = None,
    node_density: bool = True,
    verbose: bool = True,
) -> nx.Graph:
    """
    Calculates all subgraph-based characters. Generating subgraph might be a time
    consuming activity. If we want to use the same subgraph for more characters,
    ``subgraph`` allows this by generating subgraph and then analysing it using
    selected options.

    Parameters
    ----------
    graph : networkx.Graph
        A Graph representing a street network.
        Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`.
    radius: int
        Include all neighbors of distance <= radius from ``n``.
    distance : str, optional
        Use specified edge data key as distance. For example, setting
        ``distance=’weight’`` will use the edge ``weight`` to
        measure the distance from the node ``n``.
    meshedness : bool, default True
        Calculate meshedness (``True or ``False``).
    cds_length : bool, default True
        Calculate cul-de-sac length (``True or ``False``).
    mode : str (defualt 'sum')
        If ``'sum'``, calculate total ``cds_length``,
        if ``'mean'`` calculate mean ``cds_length``.
    degree : str
        The name of attribute of node degree (:py:func:`momepy.node_degree`).
    length : str, default `mm_len`
        The name of the attribute of segment length (geographical).
    mean_node_degree : bool, default True
        Calculate mean node degree (``True or ``False``).
    proportion : dict, default {3: True, 4: True, 0: True}
        Calculate proportion ``{3: True/False, 4: True/False, 0: True/False}``.
    cyclomatic : bool, default True
        Calculate cyclomatic complexity (``True or ``False``).
    edge_node_ratio : bool, default True
        Calculate edge node ratio (``True or ``False``).
    gamma : bool, default True
        Calculate gamma index (``True or ``False``).
    local_closeness : bool, default True
        Calculate local closeness centrality (``True or ``False``).
    closeness_weight : str, optional
        Use the specified edge attribute as the edge distance in shortest
        path calculations in closeness centrality algorithm.
    verbose : bool (default True)
        If ``True``, shows progress bars in loops and indication of steps.

    Returns
    -------
    netx : Graph
        A networkx.Graph object.

    Examples
    --------
    >>> network_graph = mm.subgraph(network_graph)
    """

    netx = graph.copy()

    if node_density:
        orig_nodes_degree = Series(nx.get_node_attributes(netx, "degree"))

    for n in tqdm(netx, total=len(netx), disable=not verbose):
        sub = nx.ego_graph(
            netx, n, radius=radius, distance=distance
        )  # define subgraph of steps=radius

        if meshedness:
            netx.nodes[n]["meshedness"] = _meshedness(sub)

        if cds_length:
            for u, v, k in netx.edges(keys=True):
                if netx.nodes[u][degree] == 1 or netx.nodes[v][degree] == 1:
                    netx[u][v][k]["cdsbool"] = True
                else:
                    netx[u][v][k]["cdsbool"] = False

            netx.nodes[n]["cds_length"] = _cds_length(sub, mode=mode, length=length)

        if mean_node_degree:
            netx.nodes[n]["mean_node_degree"] = _mean_node_degree(sub, degree=degree)

        if proportion:
            counts = _proportion(sub, degree=degree)
            if proportion[3]:
                netx.nodes[n]["proportion_3"] = counts[3] / len(sub)
            if proportion[4]:
                netx.nodes[n]["proportion_4"] = counts[4] / len(sub)
            if proportion[0]:
                netx.nodes[n]["proportion_0"] = counts[1] / len(sub)

        if cyclomatic:
            netx.nodes[n]["cyclomatic"] = _cyclomatic(sub)

        if edge_node_ratio:
            netx.nodes[n]["edge_node_ratio"] = _edge_node_ratio(sub)

        if gamma:
            netx.nodes[n]["gamma"] = _gamma(sub)

        if local_closeness:
            lengraph = len(netx)
            netx.nodes[n]["local_closeness"] = _closeness_centrality(
                sub, n, length=closeness_weight, len_graph=lengraph
            )

        if node_density:
            unweighted, weighted = _node_density(
                sub, length=length, orig_nodes_degree=orig_nodes_degree
            )
            netx.nodes[n]["node_density"] = unweighted
            netx.nodes[n]["node_density_weighted"] = weighted

    return netx


def mean_nodes(graph: nx.Graph, attr: Any):
    """Calculates mean value of nodes attr for each edge."""
    for u, v, k in graph.edges(keys=True):
        mean = (graph.nodes[u][attr] + graph.nodes[v][attr]) / 2
        graph[u][v][k][attr] = mean