2

都市や州の名前、緯度や場所などの全地球測位データを取得するプロジェクトを設計しようとしています。また、都市のすべてのペア間の距離もあります。このすべての情報を使用してグラフを作成し、それを操作していくつかのグラフアルゴリズムを実行したいと思います。各場所のデータを含む都市オブジェクトを作成することにしました。オブジェクトを区別するためのハッシュ関数が必要ですか？そして、ノードを組み合わせてエッジを削除するグラフアルゴリズムをどのように処理する必要がありますか？

def minCut(self):
    """Returns the lowest-cost set of edges that will disconnect a graph"""

    smcut = (float('infinity'), None)
    cities = self.__selectedcities[:]
    edges = self.__selectededges[:]
    g = self.__makeGRAPH(cities, edges)
    if not nx.is_connected(g):
        print("The graph is already diconnected!")
        return
    while len(g.nodes()) >1:
        stphasecut = self.mincutphase(g)
        if stphasecut[2] < smcut:
            smcut = (stphasecut[2], None) 
        self.__merge(g, stphasecut[0], stphasecut[1])
    print("Weight of the min-cut:  "+str(smcut[1]))

本当に悪い状態です。元のプログラムを書き直していますが、これは以前のバージョンから採用したアプローチです。

4

3 に答える 3

1

インストールしたnetworkxのバージョンに応じて、min_cutの組み込み実装が利用可能です。

1.0RC1パッケージをインストールしましたが、それは利用できませんでした。しかし、1.4にアップグレードすると、min_cutがあります。

これが（ばかげた）例です：

import networkx as nx
g = nx.DiGraph()
g.add_nodes_from(['London', 'Boston', 'NY', 'Dallas'])
g.add_edge('NY', 'Boston', capacity)
g.add_edge('Dallas', 'Boston')
g.add_edge('Dallas', 'London')
# add capacity to existing edge
g.edge['Dallas']['London']['capacity'] = 2
# create edge with capacity attribute
g.add_edge('NY', 'London', capacity=3)
print nx.min_cut(g, 'NY', 'London')
于 2011-01-19T19:40:14.167 に答える
0

都市オブジェクトのハッシュ関数を作成する必要はありません。都市オブジェクトをNetworkxに直接渡すことができます。チュートリアルから「ノードは、テキスト文字列、画像、XMLオブジェクト、別のグラフなど、任意のハッシュ可能なオブジェクトにすることができます。カスタマイズされたノードオブジェクトなど。」

都市のリストを反復処理してノードとして追加してから、距離情報を反復処理してグラフを作成できます。

チュートリアルを見たことがありますか？ http://networkx.lanl.gov/tutorial/tutorial.html

于 2011-01-19T18:54:04.873 に答える
0

ノードをマージするときに、新しいノードを作成し、これらの新しいノードをハッシュして、マージされた都市のリストを作成できます。たとえば、上記のコードでは、新しいノードlen（g）に名前を付け、それをstphasecut [0] + stphasecut [1]にハッシュできます。＃stphasecut[1]と[2]がリストであると仮定します。

于 2011-01-19T19:27:48.007 に答える