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

[Anonymous]

Я работаю над проектом графической модели на 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', а не для 'a'). наоборот).

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

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

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

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

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

Или (и пожалуйста, пусть это будет правдой

Или (и пожалуйста, пусть это будет правдой

Или) code>) есть ли простой способ получить предшественников узла в networkx.DiGraph, и я его совершенно пропустил?

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



РЕДАКТИРОВАТЬ:

Я думаю, что это делает свою работу. 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)

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

Подробнее здесь: https://stackoverflow.com/questions/381 ... h-networkx