21

NetworkXを使用してPythonでグラフィカルモデルプロジェクトに取り組んでいます。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 {}

方向性のある依存関係をコーディングしているので、有向グラフを使用したいと思います（上記の例では、「a」を条件とする「b」の閉じた形式がありますが、その逆ではありません）。

特定のノードについて、そのノードの先行ノードを見つけたいと思います。上記の例では、par（'b'）は['a']を返す必要があります。NetworkXには、任意のノードの子を検出する後継関数があります。明らかに、すべてのノードを調べて、子として「b」を持つノードを見つけることは機能しますが、ノードの数はΩ（n）になります（これは私のアプリケーションには高すぎるでしょう）。

このシンプルなものがこのよくできたパッケージから除外されるとは想像できませんが、何も見つかりません。

効率的なオプションの1つは、グラフの有向バージョンと無向バージョンを保存することです。すべての無向エッジは、基本的に両方の有向エッジを追加することによって実装されるため、隣接するノードと子（先行ノード）の間でセットごとの違いをとることができます。

問題は、これを達成するために既存のnetworkxDiGraphおよびGraphクラスをラップする最もPython的な方法がわからないことです。predecessors(node)本当に私は、networkx DiGraphクラスとまったく同じように動作するが、関数に加えて関数を持っているクラスPGraphを作成したいと思っていsuccessors(node)ます。

PGraphはDiGraphから継承し、Graphをカプセル化する必要がありますか（先行関数で使用するため）？それでは、すべてのノードとエッジを、そこに含まれる有向グラフと無向グラフの両方に強制的に追加するにはどうすればよいですか？PGraphでノードとエッジを追加および削除するための関数を再実装する必要がありますか（有向バージョンと無向バージョンの両方に追加および削除されるように）？何かわかりにくいものを見逃してしまうと、後で頭痛がするのではないかと心配しています。これは、優れたデザインを意味するものではないかもしれません。

または（そしてこれをそうさせてくださいTrue）networkx.DiGraphでノードの先行ノードを取得する簡単な方法はありますか？私はそれを完全に見逃しましたか？

どうもありがとうございました。

編集：

私はこれが仕事をしていると思います。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)

このソリューションについてどう思いますか？メモリ使用量が2倍になるかもしれませんが、それは許容できると思います。複雑すぎませんか？これは良いデザインですか？

4

4 に答える 4

39

先行者 (および predecessor_iter) メソッドがあります 。

また、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': {}}
于 2010-11-04T15:00:10.413 に答える
1

グラフは常にツリーであるとは限らないため、「親」の概念は意味をなさないことがよくあります。したがって、これは実装されていないと思います。

必要なものを実装するDiGraphには、ノードを追加できるすべてのメソッドを継承してオーバーロードします。その情報からツリー データ構造を構築します。

于 2010-09-28T08:08:38.487 に答える