import random


def random_walk(G, walk_depth: int, walk_path: list) -> list:
    """Function to generate a series data by walking in the input graph data randomly

    Args:
        G: input graph data
        walk_depth: the length of the walking result
        walk_path: the existing walking history; walking will start at the last element in walk_path

    Returns:
        a list consisting of every passed vertex

    Examples:
        >>> import networkx as nx
        >>> G = nx.Graph()
        >>> G.add_nodes_from([
        ...     ('Beijing', {'Country': 'CN'}),
        ...     ('London', {'Country': 'UK'}),
        ...     ('Zhuzhou', {'Country': 'CN'}),
        ...     ('Manchester', {'Country': 'UK'}),
        ...     ('New York', {'Country': 'US'}),
        ...     ('Michigan', {'Country': 'US'}),
        ...     ('Shanghai', {'Country': 'CN'})
        ... ])
        >>> G.add_edges_from([
        ...     ('Beijing', 'Zhuzhou'),
        ...     ('Beijing', 'London'),
        ...     ('Beijing', 'New York'),
        ...     ('Beijing', 'Shanghai'),
        ...     ('Zhuzhou', 'Shanghai'),
        ...     ('Shanghai', 'London'),
        ...     ('Shanghai', 'New York'),
        ...     ('Shanghai', 'Michigan'),
        ...     ('London', 'Manchester'),
        ...     ('London', 'New York'),
        ...     ('New York', 'Michigan')
        ... ])
        >>> result = []
        >>> for vertex in G.nodes:
        ...     result.append(random_walk(G=G, walk_depth=5, walk_path=[vertex]))
        >>> len(result), len(result[0])
        (7, 5)
        >>> [_[0] for _ in result]
        ['Beijing', 'London', 'Zhuzhou', 'Manchester', 'New York', 'Michigan', 'Shanghai']

    """
    if len(walk_path) < 1:
        raise ValueError("'walk_path' should include at least 1 vertex to start walking.")
    while len(walk_path) < walk_depth:
        current_vertex = walk_path[-1]
        neighbours_list = list(G.neighbors(current_vertex))
        # if current vertex has neighbours
        if len(neighbours_list) > 0:
            walk_path.append(random.choice(neighbours_list))
        # if current vertex is isolated
        else:
            break

    return walk_path