Самый элегантный способ найти предшественников узла с помощью networkX

Question

Я работаю над проектом графической модели с использованием Python, используя NetworkX . NetworkX обеспечивает простую и хорошую функциональность, используя словари:

import networkx as nx
G = nx.DiGraph() # a directed graph
G.add_edge('a', 'b')
print G['a'] # prints {'b': {}}
print G['b'] # prints {}

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

Для данного узла я хочу найти предшественников этого узла. Для приведенного выше примера par ('b') должен вернуть ['a']. У NetworkX есть функция-преемник, которая находит дочерние элементы любого узла. Очевидно, что, пройдя все узлы и найдя те, которые имеют «b» в качестве дочернего элемента, будет работать, но это будет Ω (n) по числу узлов (что будет слишком дорого для моего приложения).

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

Одним из эффективных вариантов является сохранение направленной и ненаправленной версии графика; все неориентированные ребра, по существу, реализуются путем добавления обоих направленных ребер, и поэтому можно было бы принять заданное различие между соседними узлами и дочерними элементами (которые были бы предшественником).

Беда в том, что я не уверен в самом питоническом способе обернуть существующие классы Networkx DiGraph и Graph для достижения этой цели. На самом деле я просто хочу получить класс PGraph, который ведет себя точно так же, как класс DiGraph networkx, но имеет функцию predecessors(node) в дополнение к функции successors(node).

Должно ли PGraph наследовать от DiGraph и инкапсулировать Graph (для использования в функции предшественников)? Как тогда я должен заставить все узлы и ребра быть добавленными как к ориентированным, так и к ненаправленным графам, которые он содержит? Должен ли я просто переопределить функции для добавления и удаления узлов и ребер в PGraph (чтобы они добавлялись и удалялись как из направленной, так и ненаправленной версии)? Я беспокоюсь о том, что если я что-то упущу из виду, то позже у меня начнется головная боль, которая может не означать хорошего дизайна.

Или (и, пожалуйста, пусть это будет True), существует ли простой способ получить предшественников узла в сети x.DiGraph, и я полностью пропустил это?

Большое спасибо за вашу помощь.

---

EDIT:

Я думаю, что это делает работу. PGraph наследует от DiGraph и инкапсулирует другой DiGraph (этот перевернутый). Я переопределил методы для добавления и удаления узлов и ребер.

import networkx as nx

class PGraph(nx.DiGraph):
    def __init__(self):
        nx.DiGraph.__init__(self)
        self.reversed_graph = nx.DiGraph()
    def add_node(self, n, attr_dict=None, **attr):
        nx.DiGraph.add_node(self, n, attr_dict, **attr)
        self.reversed_graph.add_node(n, attr_dict, **attr)
    def add_nodes_from(self, ns, attr_dict=None, **attr):
        nx.DiGraph.add_nodes_from(self, ns, attr_dict, **attr)
        self.reversed_graph.add_nodes_from(ns, attr_dict, **attr)
    def add_edge(self, a, b, attr_dict=None, **attr):
        nx.DiGraph.add_edge(self, a, b, attr_dict, **attr)
        self.reversed_graph.add_edge(b, a, attr_dict, **attr)
    def add_edges_from(self, es, attr_dict=None, **attr):
        nx.DiGraph.add_edges_from(self, es, attr_dict, **attr)
        self.reversed_graph.add_edges_from(es, attr_dict, **attr)
    def remove_node(self, n):
        nx.DiGraph.remove_node(self, n)
        self.reversed_graph.remove_node(n)
    def remove_nodes_from(self, ns):
        nx.DiGraph.remove_nodes_from(self, ns)
        self.reversed_graph.remove_nodes_from(ns)
    def remove_edge(self, a, b):
        nx.DiGraph.remove_edge(self, b, a)
        self.reversed_graph.remove_edge(a, b)
    def remove_edges_from(self, es):
        nx.DiGraph.remove_edges_from(self, es)
        self.reversed_graph.remove_edges_from([ (b,a) for a,b in es])
# the predecessors function I wanted
    def predecessors(self, n):
        return self.reversed_graph.successors(n)

Что вы думаете об этом решении? Это может удвоить использование памяти, но я думаю, что это приемлемо. Это слишком сложно? Это хороший дизайн?

Answer 1

Существует метод-предшественник (и priorcessor_iter): http://networkx.lanl.gov/reference/generated/networkx.DiGraph.predecessors.html#networkx.DiGraph.predecessors

Также ничто не мешает вам получить доступ к структуре данных напрямую как G.pred

 In [1]: import networkx as nx
 In [2]: G = nx.DiGraph() # a directed graph
 In [3]: G.add_edge('a', 'b')
 In [4]: G.predecessors('b')
 Out[4]: ['a']
 In [5]: G.pred['b']
 Out[5]: {'a': {}}

Answer 2

Другой способ реализовать это может быть следующим:

Создание базового графика

import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()
G.add_edges_from([('A', 'B'), ('A', 'C'), ('D', 'B'), ('E', 'C'), ('E','F'), ('B', 'H'), ('B', 'G'), ('B', 'F'), ('C', 'G'), ('Q', 'D')])

pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos, cmap=plt.get_cmap('jet'),node_size = 50)
nx.draw_networkx_edges(G, pos, edge_color='r', arrows=True)
nx.draw_networkx_labels(G, pos)
plt.show()

Поиск нижних кромок

print("Downstream Edges of 'B' (just example)-->")
print(list(nx.dfs_edges(G,'B')))

Поиск верхних границ

print("Upstream Edges of 'B' (just example)-->")
print(list(nx.edge_dfs(G,'B', orientation='reverse')))

Подробнее в этом блоге

Answer 3

Граф не всегда является деревом, поэтому понятие «родитель» часто не имеет смысла.Поэтому я предполагаю, что это не реализовано.

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

Answer 4

Если G является экземпляром nx.DiGraph(), а node является исходным узлом, чьи предшественники вы ищете, следующее дает вам список предшествующих узлов:

predecessors = [pred for pred in G.predecessors(node)]