Возвращает количество последующих узлов на узел в сети x - PullRequest
Новая
       9

Возвращает количество последующих узлов на узел в сети x

0 голосов
/ 13 марта 2020

Я хотел бы знать, сколько ребер следует за каждым узлом в сети. Я создал график из 20 узлов, но он предпочтительно должен работать для любого количества узлов. Код приведен здесь, и изображение графика также показано. 

def create_graph(number_of_nodes):
        # Set seed to get reproducible graph
        seed = 10
        random.seed(seed)
        np.random.seed(seed)

        # Create a random tree with x nodes
        global G
        G = nx.random_tree(number_of_nodes, seed=seed)
        pos = nx.nx_pydot.graphviz_layout(G, prog='dot', root=0)

        # Draw the graph
        nx.draw(G, pos, with_labels=True)
        plt.show()
        return G


create_graph(20)

Рисунок, показывающий график

У меня есть код, который работает, когда график меньше, то есть не имеет много ветвей. Однако в этом примере он не работает с 20 узлами. 

# Dictionaries for traversing
d = dict(nx.bfs_successors(graph, root_node))
print(d.items())

key_to_value_lengths = {k: len(v) for k, v in d.items()}
print(key_to_value_lengths)

edges_succeeding = {}
total_removed = 0

for k, v in key_to_value_lengths.items():
    total = sum(key_to_value_lengths.values())
    edges_succeeding[k] = total - total_removed
    total_removed = total_removed + key_to_value_lengths[k]

print("Number of edges succeeding " + str(edges_succeeding))

Вывод, который я получаю, таков: 

    Number of edges succeeding {0: 19, 6: 17, 14: 16, 15: 15, 16: 12, 10: 11, 1: 10, 2: 8, 5: 7, 7: 6, 8: 5, 11: 4, 18: 3, 13: 1}

Таким образом, это верно для первых нескольких узлов, но заканчивается неправильно после узла 16, потому что оно также включает ветвь на другая сторона (после узла 10).

Я хочу, чтобы словарь edges_succeeding возвращал число ребер, следующих за этим узлом, в данной ветви. Например, верным для узла 16 будет 16: 8, а не 16: 12

Предпочтительно, он также должен иметь возможность увеличивать и уменьшать его для любого заданного размера сети.

1 Ответ

0 голосов
/ 14 марта 2020

Следующий код должен решить вашу проблему. Шаги для достижения решения

  1. Я использовал поиск в глубину (dfs) вместо поиска в ширину (bfs), потому что мы хотим обрабатывать узлы от самого высокого уровня до самого низкого уровня (если мы думаем о дереве DFS). Поэтому первым шагом является создание dfs_tree и вычисление глубины узлов.
  2. Создание порядка обработки узлов (ordered_nodes): как уже упоминалось, мы хотим обработать узлы по уровню в dfs-tree, поскольку наивысшим уровнем являются те узлы с 0 последующими ребрами. Начиная с этих узлов, мы можем итеративно рассчитать количество ребер до второго по величине уровня, посчитав количество ребер до узлов с наивысшим уровнем.
  3. Это как раз и есть цель for node in ordered_nodes l oop , Итеративный расчет последующих ребер от самого высокого уровня до самого низкого уровня (т. Е. root узел). 
import networkx as nx
import numpy as np
import random

def create_graph(number_of_nodes):
    # Set seed to get reproducible graph
    seed = 10
    random.seed(seed)
    np.random.seed(seed)

    # Create a random tree with x nodes
    G = nx.random_tree(number_of_nodes, seed=seed)
    return G


graph = create_graph(20)

# 1 dfs-tree and node levels
# dictionary to store the "depth" or level or each node
levels = {0: 0}
# directed dfs tree to store the predecessors
dfs_tree = nx.DiGraph()
for u, v in nx.dfs_edges(graph, 0):
    levels[v] = levels[u] + 1
    dfs_tree.add_edge(u, v)

print(levels)
# {0: 0, 17: 1, 6: 1, 14: 2, 15: 3, 12: 4, 16: 4, 1: 5, 4: 6, 5: 6, 8: 7, 18: 8, 3: 9, 13: 9, 9: 10, 10: 4, 2: 5, 7: 6, 11: 7, 19: 8}

# 2 sorting nodes
# process nodes by highest level first
ordered_nodes = sorted(graph.nodes, key=lambda node: levels[node], reverse=True)

# 3 iteratively calculation
# final dict
edges_succeeeding = {}
for node in ordered_nodes:
    if graph.degree(node) == 1:
        # add lowest entry to the dict
        edges_succeeeding[node] = 0

    # start adding information about the predecessor
    for predecessor in dfs_tree.predecessors(node):
        edges_succeeeding[predecessor] = edges_succeeeding.get(predecessor, 0) + edges_succeeeding[node] + 1

print(edges_succeeeding)
# {9: 0, 13: 1, 3: 0, 18: 3, 8: 4, 19: 0, 11: 1, 5: 5, 7: 2, 4: 0, 1: 7, 2: 3, 16: 8, 10: 4, 15: 15, 12: 0, 14: 16, 6: 17, 0: 19, 17: 0}
...