Можно ли добавить вес / вероятность к узлу в теории графов (используя networkx)

Я использую networkx (библиотека для Python для работы с графиками). У меня в основном есть узлы с разными краями, но я хочу посмотреть, как бы выглядел путь, если бы он использовал узлы, которые были наиболее связаны.

Я могу использовать эту команду, чтобы увидеть количество подключений:

len(G.edges(CurrentNode))

и я могу получить количество ребер, но я не уверен, как применить это к списку в качестве пути. Например, я могу добавить это число как атрибут, но я не думаю, что атрибуты принимаются во внимание при поиске пути, и поскольку я добавляю это после соединения ребер, я не могу добавлять веса к самим ребрам. Другая проблема заключается в том, что чем выше оценка, тем больше я хочу, чтобы путь следовал, но с краями, я думаю, он следует по краю с наименьшим весом.

Мне интересно, какой подход используют другие люди для поиска путей на основе определенных характеристик узла? Если кто-то знает, как это сделать для networkx, отлично! но я думаю, что networkx имеет много функций, поэтому, если я смогу получить теорию или общий подход, я уверен, что смогу найти способ сделать это на python.

ОБНОВЛЕНИЕ: извините, я могу это неправильно объяснить. Я понимаю, что могу добавлять атрибуты к узлам, но не уверен, как принимать решения о пути на основе этих атрибутов. Итак, в моем случае, исходя из определенных условий, я добавляю ребра между узлами. Каждая группа узлов представляет другой день (day1data .., day2data .., day3data ..), поэтому я подключаю несколько узлов из day1 к узлам day2, только если соблюдаются определенные правила. После того, как я соединю края, я хочу, чтобы они более тщательно рассматривались при выборе пути. Поэтому я добавил атрибут «вес» к каждому узлу текущего дня, который в основном представляет собой общее количество ребер, соединяющих этот узел. Моя проблема в том, что атрибут веса не используется ни в одном из решений пути, потому что это атрибут, который я создал и назвал себя (я мог бы создать метку с именем 'abc' = 'hello world', и он применил бы этот атрибут к узлу ). Как я могу учитывать этот вес при создании пути (края уже созданы, поэтому я не думаю, что могу вернуться и воссоздать их)?


python algorithm networkx graph-theory
person Lostsoul    schedule 20.10.2011    source источник
comment
Это может вам помочь: en.wikipedia.org/wiki/Shortest_path_problem - Но я не используйте networkx и не можете сказать вам, как добавлять веса к путям ... извините.   -  person Louis    schedule 20.10.2011

Ответы (3)


arrow_upward
6
arrow_downward

Вы, конечно, можете добавить веса к ребрам в NetworkX. Фактически, вы можете установить произвольные данные для ребер, так как это в основном dict.

In [30]: import networkx as nx

In [31]: G = nx.Graph()

In [32]: G.add_edge(1, 2, weight=3, type="green")

In [33]: G[1][2]
Out[33]: {'type': 'green', 'weight': 3}

In [34]: G[1][2]["weight"]
Out[34]: 3

Кроме того, вы можете изменить параметры ребер (или узлов) после их добавления.

In [35]: G[1][2]["weight"] = 5

In [36]: del G[1][2]["type"]

In [37]: G[1][2]["color"] = "green"

In [38]: G[1][2]
Out[38]: {'color': 'green', 'weight': 5}

И, конечно, вы можете рассчитать путь в соответствии с весами (или любым другим атрибутом, указанным в параметре веса).

In [39]: G.add_edge(1, 3, weight=1)

In [40]: G.add_edge(2, 3, weight=2)

In [41]: G.edges()
Out[41]: [(1, 2), (1, 3), (2, 3)]

In [42]: nx.shortest_path(G, source=1, target=2, weight="weight")
Out[42]: [1, 3, 2]

В вашем случае определение веса ребер может быть непростым. Имейте в виду, что взвешенный кратчайший путь обычно рассчитывается с помощью алгоритма Джикстры, и он поддерживает меньшие веса. Это также требует положительных весов. Одним из возможных решений может быть присвоение веса 1/max(k_i,k_j) ребру (i,j), где k_i, k_j - степень узлов i и j.

Правильный способ вычисления кратчайших путей по вероятностям перехода - преобразовать веса ребер, чтобы представить неожиданность: то есть отрицательный логарифм вероятности. Это приводит к получению положительных весов, и любой заданный кратчайший путь затем интерпретируется как минимизирующий неожиданность. А поскольку алгоритм Дейкстры суммирует веса, он делает это в журнальном пространстве, что означает, что он действительно умножает вероятности. Чтобы восстановить совместную вероятность наблюдения любого заданного кратчайшего пути, вы просто берете экспоненту отрицательного сюрприза.

person Avaris    schedule 20.10.2011
comment
Спасибо за ответ Аварис. Ребра уже созданы, и на основе этого я вычисляю вес (общее количество ребер узла). Я обновил вопрос, чтобы немного прояснить это. - person Lostsoul; 21.10.2011
comment
@Lostsoul: На самом деле, я понял ваш вопрос как обновление. Не добавляйте веса узлам. Гири должны доходить до краев. Края определяют путь, а не узлы. Сначала вы создаете свою обычную сеть без весов, затем назначаете веса ребрам в соответствии с их количеством (кстати, это обычно называется степенью в теории графов). Ах да, вы можете получить количество ребер узла с помощью graph.degree(node). Вам не нужно делать len(...). - person Avaris; 21.10.2011
comment
Другой способ добавить атрибуты после добавления узла - использовать set_node_attributes. - person Joel; 21.10.2015

arrow_upward
0
arrow_downward

Из Руководства по NetworkX

>>> G.add_edge(1, 2, weight=4.7 )
>>> G.add_edges_from([(3,4),(4,5)], color='red')
>>> G.add_edges_from([(1,2,{'color':'blue'}), (2,3,{'weight':8})])
>>> G[1][2]['weight'] = 4.7
>>> G.edge[1][2]['weight'] = 4

Похоже, что веса могут быть добавлены постфактум.

person Ethan Furman    schedule 20.10.2011
comment
Спасибо за ответ, Итан. Я пробовал и делаю это прямо сейчас, но проблема в том, что добавление атрибута не меняет путь, который он принимает. Я хочу, чтобы этот атрибут веса учитывался при создании самого пути. Я обновил вопрос, чтобы уточнить. - person Lostsoul; 21.10.2011

arrow_upward
0
arrow_downward

Мой единственный способ принять во внимание самодельные attributes - это редактировать файл в самом фреймворке.

Ищете файл networkx/algorithms/shortest_paths/weighted.py

Там будет лямбда-объявление get_weight function, которое выглядит следующим образом:

if G.is_multigraph():
    get_weight = lambda u, v, data: min(
        eattr.get(weight, 1) for eattr in data.values())
else:
    get_weight = lambda u, v, data: data.get(weight, 1)

Я хотел придать своим node определенный вес, поэтому изменил его следующим образом:

if G.is_multigraph():
    get_weight = lambda u, v, data: min(
        eattr.get(weight, 1) for eattr in data.values())
else:
    get_weight = lambda u, v, data: (data.get(weight,0) + nx.get_node_attributes(G, "node_weight").get(v,0))

Я установил вес края по умолчанию на 0: data: data.get(weight,0) и добавил значение моего собственного атрибута «node_weight» (по умолчанию 0).

data: (data.get(weight,0) + nx.get_node_attributes(G, "node_weight").get(v,0))

v является следующим node достижимым на графике.

Теперь вы можете установить свой attribute после создания графика.

nx.set_node_attributes(G, "node_weight", {1:3.5, 2:56})
person Jsail    schedule 10.11.2017