Обход графа с помощью Networkx (Python)

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

>>> G = nx.Graph()
>>> G.add_edge("A","B")
>>> G.add_edge("A","H")
>>> G.add_edge("H","C")
>>> G.add_edge("B","C")
>>> G.add_edge("B","D")

           A
         /   \
       H       B
     /        /  \
   C         C     D

Итак, здесь мы видим, что перед запуском A нам нужно запустить H и B, а для запуска H нам нужно запустить C, а затем, чтобы начать B, нам нужно запустить C и D.

Немного повозившись с Networkx, я обнаружил, что могу получить это, выполнив обход dfs

print nx.dfs_successors(G,"A")
{A:[H,B], H:[C], B:[D] }

Но у меня проблема с этим методом. Как вы можете видеть, когда в дереве есть две одинаковые буквы, Networkx решила поместить только одну из них в окончательную структуру (что правильно). Но мне нужна полная структура. Как я могу заставить Networkx добавить в структуру B :[ОКРУГ КОЛУМБИЯ] ??

Я хочу уточнить это, сделав

>>> nx.dfs_successors(G,"B")
{'B': ['C', 'D']}

Так что все "внутренне" правильно, просто dfs_successors отображает это не так, как я хотел бы.

Спасибо


python networkx
person Johny19    schedule 10.01.2013    source источник

Ответы (2)


arrow_upward
7
arrow_downward

Взяв ваш код, ваш график выходит не так, как вы ожидали. Если вы это сделаете:

import pylab as p
import networkx as nx

G = nx.Graph()
G.add_edge("A","B")
G.add_edge("A","H")
G.add_edge("H","C")
G.add_edge("B","C")
G.add_edge("B","D")

nx.draw(G)
p.show()

вы увидите свой график как: Graph

Это связано с логикой G.add_edge("A", "B"):

  1. Если G не имеет узла с идентификатором «A», добавьте его.
  2. Если G не имеет узла с идентификатором «B», добавьте его.
  3. Соедините «A» с «B» новым краем.

Таким образом, вы создаете только пять узлов, а не шесть, как на вашем рисунке.

Изменить Networkx может принимать любое хешируемое значение в качестве значения для узла, а на графике он использует str (узел) для обозначения каждого круга. Итак, мы можем просто определить наш собственный класс Node (который вы, возможно, захотите назвать Server?) И придать ему желаемое поведение.

import pylab as p
import networkx as nx


class Node(object):
    nodes = []

    def __init__(self, label):
        self._label = label

    def __str__(self):
        return self._label

nodes = [Node(l) for l in ["A","B","C","C","D","H"]]
edges = [(0,1),(0,5),(5,2),(1,3),(1,4)]

G = nx.Graph()
for i,j in edges:
    G.add_edge(nodes[i], nodes[j])

nx.draw(G)
p.show()

дает нам New graphи так, что вы хотели.

person Thorsten Kranz    schedule 10.01.2013
comment
Спасибо, что нарисовали график. Я думал, что это то, что Networkx делает в моей спине. Таким образом, у меня будет вопрос: как с помощью Networkx создать дерево, как в моем примере? Типично то, что для меня было бы идеальным, - это когда я создаю G.add_edge (B, C), новый узел C создается вместо того, чтобы повторно использовать подключенный к H. - person Johny19; 10.01.2013
comment
Тогда вам нужно будет назвать новый узел как-нибудь еще. Возможно, C1 и C2. Насколько мне известно, NetworkX не позволяет использовать несколько узлов с одной и той же меткой. - person brentlance; 10.01.2013
comment
Но мне нужно, чтобы узел был таким же. как я сказал в основном потоке. мой узел - это имя сервера, я не могу изменить имена, иначе я не знаю, какой из них какой ... Но на самом деле График, на котором Торстен Кранц не прав, он правильный, B зависит от C И D. это просто алгоритм dfs_successors () выводит, что B зависит только от D, и ЭТО неверно. Если мое дерево невозможно с Networkx, возможно ли это с другой библиотекой? Благодарность - person Johny19; 10.01.2013
comment
Добавлен второй пример, надеюсь, это соответствует вашим потребностям. - person Thorsten Kranz; 10.01.2013

arrow_upward
7
arrow_downward

Я думаю, что вы ищете топологическую сортировку http://networkx.github.com/documentation/latest/reference/generated/networkx.algorithms.dag.topological_sort.html

Это работает, только если у вас есть DAG (направленный ациклический граф). Если да, то вы тоже можете нарисовать дерево, которое хотите - вот так:

import uuid
import networkx as nx
import matplotlib.pyplot as plt
G = nx.DiGraph()
G.add_edge("A","B")
G.add_edge("A","H")
G.add_edge("H","C")
G.add_edge("B","C")
G.add_edge("B","D")

order =  nx.topological_sort(G)
print "topological sort"
print order

# build tree
start = order[0]
nodes = [order[0]] # start with first node in topological order
labels = {}
print "edges"
tree = nx.Graph()
while nodes:
    source = nodes.pop()
    labels[source] = source
    for target in G.neighbors(source):
        if target in tree:
            t = uuid.uuid1() # new unique id
        else:
            t = target
        labels[t] = target
        tree.add_edge(source,t)
        print source,target,source,t
        nodes.append(target)

nx.draw(tree,labels=labels)
plt.show()

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

введите описание изображения здесь

person Aric    schedule 11.01.2013