1

このリンクのhttps://www.python.org/doc/essays/graphs/情報に触発されて、グラフ構造を実装しています。私は一般的に

graph = {'A': ['B', 'C'],
             'B': ['C', 'D'],
             'C': ['D'],
             'D': ['C']}

edges = [('A','B',20),('A','C',40), ('B','C',10), ('B','D',15),('C','D',10),('D','C',10)]

これら 2 つは、C でのオブジェクト表現に最も近いものです。ただし、グラフ ラベルに関するより多くの情報を保存する必要がある場合もあります。たとえば、グラフ ノードは国内の州であるため、各ノードと共にフル ネーム (カリフォルニア州) と略語 (CA) を保存する必要があります。それを行う最善の方法は何ですか。ディクショナリの値はクラス インスタンスにできることはわかっていますが、ディクショナリのキーにはなりません。そのため、グラフノード「A」をキーとして、クラスインスタンス「StateDetails」を州と略語を含む値として別の辞書を作成することを考えていました。例えば

state_map = {'A': StateDetails('California','CA') ..    }

誰かが、特にこの問題に対処するためのより効率的な方法と、python で一般的にグラフを処理する方法を教えてくれれば幸いです

4

3 に答える 3

0

データを標準の JSON 形式で保存するのはどうですか?

state_map = { "A": { "state_name": "California", "state_code": "CA" } }

の州名を見つけるには、次のAように入力します

state_map['A']['state_name'] # California
于 2013-07-17T17:19:25.077 に答える
0

__eq__and を実装すると、クラスを dict キーとして使用できます。__hash__次に例を示します。

class StateDetails(object):
    def __init__(self, state, abbrev):
        self.state = state
        self.abbrev = abbrev
    def __eq__(self, other):
        return isinstance(other, self.__class__) and self.abbrev == other.abbrev
    def __hash__(self):
        return hash(self.abbrev)
    def __repr__(self):
        return '{}({!r}, {!r})'.format(self.__class__.__name__, self.state, self.abbrev)

CA = StateDetails('California', 'CA')
AZ = StateDetails('Arizona', 'AZ')
NV = StateDetails('Nevada', 'NV')
UT = StateDetails('Utah', 'UT')
graph = {CA: [AZ, NV],
         AZ: [CA, NV, UT],
         NV: [CA, AZ, UT],
         UT: [AZ, NV]}

結果：

>>> pprint.pprint(graph)
{StateDetails('California', 'CA'): [StateDetails('Arizona', 'AZ'),
                                    StateDetails('Nevada', 'NV')],
 StateDetails('Arizona', 'AZ'): [StateDetails('California', 'CA'),
                                 StateDetails('Nevada', 'NV'),
                                 StateDetails('Utah', 'UT')],
 StateDetails('Nevada', 'NV'): [StateDetails('California', 'CA'),
                                StateDetails('Arizona', 'AZ'),
                                StateDetails('Utah', 'UT')],
 StateDetails('Utah', 'UT'): [StateDetails('Arizona', 'AZ'),
                              StateDetails('Nevada', 'NV')]}
于 2013-07-17T17:20:08.123 に答える
0

追加情報をグラフの外に保存するだけです。例：辞書を保持する

full_name = {"CA": California,
             # 49 more entries
            }

次に"CA"、グラフ ノードとして使用します。

これにより、ノードがドラッグしている余分な情報を回避する必要がないため、グラフ アルゴリズムの実装が容易になります。保存している情報が変更される可能性があるため、グラフ アルゴリズムが保守しやすくなり、高速化される可能性もあります。

(実際、実際のアプリケーションでは、グラフ ノードとしてのみ整数インデックスを使用し、すべての追加情報を別の構造に格納します。そうすれば、NumPy と SciPy を使用して面倒な作業を行うことができます。)

于 2013-07-17T17:15:35.463 に答える