Я работаю над графическим проектом модели с помощью 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', а не наоборот).
Для данного node я хочу найти предшественники этого node. В приведенном выше примере par ('b') должен возвращать ['a']. NetworkX имеет функцию-преемник, которая находит дочерние элементы любого node. Очевидно, что, пройдя все узлы и найдя те, у которых есть "b", как ребенок, будет работать, но это будет Q (n) в количестве узлов (что будет слишком дорого для моего приложения).
Я не могу себе представить, что что-то такое простое было бы исключено из этого хорошо сделанного пакета, но ничего не может найти.
Одним эффективным вариантом является сохранение направленной и неориентированной версии графика; все неориентированные ребра по существу реализуются путем добавления обоих направленных ребер, и поэтому можно было бы установить разницу между соседними узлами и дочерними элементами (которая была бы предшественником).
Проблема заключается в том, что я не уверен в наиболее питоническом способе обернуть существующий класс DiGraph и Graph для этого. На самом деле я просто хочу получить класс PGraph, который ведет себя точно так же, как и класс DiGraph для сети, но имеет функцию predecessors(node) в дополнение к функции successors(node).
Должен ли PGraph наследовать от DiGraph и инкапсулировать Graph (для использования в функции предшественников)? Как тогда я должен заставить все узлы и ребра быть добавлены как к направленным, так и к неориентированным графам, которые он содержит? Должен ли я просто переопределить функции для добавления и удаления узлов и ребер в PGraph (чтобы они были добавлены и удалены как из направленной, так и неориентированной версии)? Я беспокоюсь, что, если я пропущу что-то неясное, у меня будет головная боль позже, что может не означать хороший дизайн.
Или (и, пожалуйста, пусть это будет True) есть простой способ получить предшественников node в networkx.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)
Что вы думаете об этом решении? Это может удвоить использование памяти, но я думаю, что это приемлемо. Это слишком сложно? Это хороший дизайн?
