# Function for assigning 'rank' and 'offspring' attributes to graph vertices
def rank_set(G, start, last_vertex):
    # Traversing a graph with attribute assignment
    # G           --- graph as a networkx object
    # vertex      --- vertex from which the graph search begins
    # kernel_path --- list of vertexes that are part of the main path that the search is being built from
    def bfs_attributes(G, vertex, kernel_path):
        # Creating a copy of the graph
        G_copy = G.copy()
        # Deleting all edges that are associated with the reference vertexes
        for kernel_vertex in kernel_path:
            # Leaving the reference vertex from which we start the crawl
            if kernel_vertex == vertex:
                pass
            else:
                # For all other vertexes, we delete edges
                kernel_n = list(nx.bfs_successors(G_copy, source = kernel_vertex, depth_limit = 1))
                kernel_n = kernel_n[0][1]
                for i in kernel_n:
                    try:
                        G_copy.remove_edge(i, kernel_vertex)
                    except Exception:
                        pass
        # The obtained subgraph is isolated from all reference vertices, except the one
        # from which the search begins at this iteration
        # Breadth-first search
        all_neighbors = list(nx.bfs_successors(G_copy, source = vertex))
        # Attention!
        # Labels are not assigned on an isolated subgraph, but on the source graph
        for component in all_neighbors:
            v = component[0] # The vertex where we are at this iteration
            neighbors = component[1] # Vertices that are neighboring (which we haven't visited yet)
            # Value of the 'rank' attribute in the considering vertex
            att = G.nodes[v].get('rank')
            if att != None:
                # The value of the attribute to be assigned to neighboring vertices
                att_number = att + 1
            # We look at all the closest first offspring
            first_n = list(nx.bfs_successors(G, source = v, depth_limit = 1))
            first_n = first_n[0][1]
            # Assigning ranks to vertices
            for i in first_n:
                # If the neighboring vertex is the main node in this iteration, then skip it
                # vertex - the reference point from which we started the search
                if i == vertex:
                    pass
                else:
                    current_i_rank = G.nodes[i].get('rank')
                    # If the rank value has not yet been assigned, then assign it
                    if current_i_rank == None:
                        attrs = {i: {'rank': att_number}}
                        nx.set_node_attributes(G, attrs)
                    # If the rank in this node is already assigned
                    else:
                        # The algorithm either "looks back" at vertices that it has already visited
                        # In this case we don't do anything
                        # Either the algorithm "came up" to the main path (kernel path) in the graph
                        if any(i == bearing_v for bearing_v in kernel_path):
                            G.remove_edge(v, i)
                        else:
                            pass
            # Additional "search"
            for neighbor in neighbors:
                # We look at all the closest first offspring
                first_n = list(nx.bfs_successors(G, source = neighbor, depth_limit = 1))
                first_n = first_n[0][1]
                for i in first_n:
                    # If the neighboring vertex is the main node in this iteration, then skip it
                    # vertex - the reference point from which we started the search
                    if i == vertex:
                        pass
                    else:
                        # The algorithm either "looks back" at vertices that it has already visited
                        # In this case we don't do anything
                        # Either the algorithm "came up" to the main path (kernel path) in the graph
                        if any(i == bearing_v for bearing_v in kernel_path):
                            G.remove_edge(neighbor, i)
                        else:
                            pass
    # Finding the shortest path A* - building a route around which we will build the next searchs
    a_path = list(nx.astar_path(G, source = start, target = last_vertex, weight = 'weight'))
    ##############################
    #   Route validation block   #
    ##############################
    true_a_path = []
    for index, V in enumerate(a_path):
        if index == 0:
            true_a_path.append(V)
        elif index == (len(a_path) - 1):
            true_a_path.append(V)
        else:
            # Previous and next vertices for the reference path (a_path)
            V_prev = a_path[index - 1]
            V_next = a_path[index + 1]
            # Which vertexes are adjacent to this one
            V_prev_neighborhood = list(nx.bfs_successors(G, source = V_prev, depth_limit = 1))
            V_prev_neighborhood = V_prev_neighborhood[0][1]
            V_next_neighborhood = list(nx.bfs_successors(G, source = V_next, depth_limit = 1))
            V_next_neighborhood = V_next_neighborhood[0][1]
            # If the next and previous vertices are connected to each other without an intermediary
            # in the form of vertex V, then vertex V is excluded from the reference path
            if any(V_next == VPREV for VPREV in V_prev_neighborhood):
                if any(V_prev == VNEXT for VNEXT in V_next_neighborhood):
                    pass
                else:
                    true_a_path.append(V)
            else:
                true_a_path.append(V)
    ##############################
    #   Route validation block   #
    ##############################
    # Verification completed
    a_path = true_a_path
    RANK = 1
    for v in a_path:
        # Assign the attribute rank value - 1 to the starting vertex. The further away, the greater the value
        attrs = {v: {'rank' : RANK}}
        nx.set_node_attributes(G, attrs)
        RANK += 1
    # The main route is ready, then we will iteratively move from each node
    for index, vertex in enumerate(a_path):
        # Starting vertex
        if index == 0:
            next_vertex = a_path[index + 1]
            # Disconnect vertices
            G.remove_edge(vertex, next_vertex)
            # Subgraph BFS block
            bfs_attributes(G, vertex = vertex, kernel_path = a_path)
            # Connect vertices back
            G.add_edge(vertex, next_vertex)
        # Finishing vertex
        elif index == (len(a_path) - 1):
            prev_vertex = a_path[index - 1]
            # Disconnect vertices
            G.remove_edge(prev_vertex, vertex)
            # Subgraph BFS block
            bfs_attributes(G, vertex = vertex, kernel_path = a_path)
            # Connect vertices back
            G.add_edge(prev_vertex, vertex)
        # Vertices that are not the first or last in the reference path
        else:
            prev_vertex = a_path[index - 1]
            next_vertex = a_path[index + 1]
            # Disconnect vertices
            # Previous with current vertex
            try:
                G.remove_edge(prev_vertex, vertex)
            except Exception:
                pass
            # Current with next vertex
            try:
                G.remove_edge(vertex, next_vertex)
            except Exception:
                pass
            # Subgraph BFS block
            bfs_attributes(G, vertex = vertex, kernel_path = a_path)
            # Connect vertices back
            try:
                G.add_edge(prev_vertex, vertex)
                G.add_edge(vertex, next_vertex)
            except Exception:
                pass
    # Attribute assignment block - number of descendants
    vert_list = list(nx.bfs_successors(G, source = start))
    for component in vert_list:
        vertex = component[0] # The vertex where we are at this iteration
        neighbors = component[1] # Vertices that are neighboring (which we haven't visited yet)
        # Adding an attribute - the number of descendants of this vertex
        n_offspring = len(neighbors)
        attrs = {vertex: {'offspring' : n_offspring}}
        nx.set_node_attributes(G, attrs)