узел как узлы решетки в сети x - PullRequest
Новая
       42

узел как узлы решетки в сети x

1 голос
/ 02 мая 2020

У меня есть древовидные графы, которые выглядят как длинные стволы с ветвями, и у каждой ветви могут быть «листья». Это выглядит в основном как (ребра не изображены): 

    o
   oo
    oo     o
    o      o     o
oooooooooooooooooooooooooo
    o
    o

Длина ствола может быть произвольной, и каждая вертикальная ветвь имеет порядок десяти узлов, с максимумом только одного узла. Каждый узел ствола имеет не более 4 ребер. Поскольку гарантируется, что вертикальные «листья» никогда не перекрываются, я хотел бы иметь возможность преобразовать граф так, чтобы каждый узел находился в точке решетки, и получить словарь вида 

dict = {n1: (x1, y2), n2: (x2, y2), ...}

с ni идентификатор узла и (xi, yi) пара целых чисел, указывающих положение на решетке. Я попытался реализовать это сам, получив ствол, используя максимальное расстояние между всеми узлами графа G: 

nodeList = list(G.nodes)
dic = {}
for i, n1 in enumerate(nodeList):
        for n2 in nodeList[i+1:]:
            dic[(n1, n2)] = networkx.shortest_path(G,source=n1,target=n2)

    dicLength = {k: len(dic[k]) for k in dic}
    k = max(dicLength, key=dicLength.get)
    trunk = dic[k]

Затем я могу установить ствол в качестве координаты x решетки: 

lattice = {k: (i, 0) for i, k in enumerate(trunk)}

Затем я попытался вычислить вертикальные ветви, проверив, имеет ли узел в стволе более двух соседей, и перебрать от узла к узлу оттуда, но я сталкиваюсь с проблемами, когда приглашаю листья. Более того, он плохо масштабируется для больших соединительных линий.

Есть ли более простой способ сделать это с networkx?

РЕДАКТИРОВАТЬ: минимальный пример будет: 

G = nx.path_graph(10)
G.add_edges_from([(3,11),(11,12),(12,13),(13,14),(13,15),(1,16)])

1 Ответ

1 голос
/ 02 мая 2020

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

Вы можете начать с поиска nx.eccentricity графика, то есть максимальное расстояние между данным узлом и всеми другими узлами. Затем, найдя его максимальное значение, или, другими словами, диаметр графа, мы можем ограничить поиск shortest_path только парой максимально удаленных узлов в графе (в случае одного ствола без ветвления в обоих концах не понадобятся, достаточно будет найти кратчайший путь между extrema_cand): 

ecc = nx.eccentricity(G)
diam = max(ecc.values())
extrema_cand = [node for node, length in ecc.items() if length==diam]

Теперь мы можем искать кратчайшие пути только в вышеуказанном подмножестве узлов: 

from itertools import combinations
trunk=[]
for nodes in combinations(extrema_cand, r=2):
    trunk.append(nx.shortest_path(G,*nodes))
trunk = max(trunk, key=len)

Фильтруя max в последней строке, мы обеспечиваем защиту узлов от противоположных сторон графика. Хотя, как уже упоминалось, если имеется одна магистраль, nx.shortest_path(G,*nodes) на единственной паре узлов в extrema_cand должно быть достаточно.

Тогда для ветвей, возможно, можно было бы сделать итерацию по магистральным узлам, и обнаружите ответвления и последующие листья через поиск в ширину, игнорируя пути, объединяющие узлы из ствола или уже пройденные.

...