PythonのプログラムをPHPで書き直したい

Question

下記のサイトのプログラムをPHPで書き直そうとしています。

http://www.geocities.jp/m_hiroi/light/pyalgo62.html

この中の一番下のプログラム３巡回セールスマン問題 (クラスカルのアルゴリズムの変形版)のぶぶんについてです。

質問したいのは、class Edgeのなかのdef cmp(x, y)が何の役割を持っているのかということです。

__~~__というメソッドなので、PHPでいうところのコンストラクタの役割を果たしていることはわかるのですが、（厳密にはPythonにはコンストラクタの考えがないということはわかっています）
このメソッドが必要な箇所がよくわかりません。
メソッドの処理内容はxのweightとyのweightの差を求めているということはわかります。

また実際、def make_edge(size)の中のe = Edge(i, j, distance_table[i][j])には何が入っているのでしょうか？

丁寧な説明、よろしくお願いします。

Answer 1

バージョン2.7のドキュメントで見つけました。
http://docs.python.jp/2.7/reference/datamodel.html#customization
大小比較するときに呼ばれるメソッドのようですね。
class Edgeのインスタンス同士の比較用に、weightプロパティの大小で決定するということで、
これがないとインスタンスのアドレス同士の比較というトンチンカンな振る舞いになってしまうため、
比較基準を正しく与えているということのようです。

Comments

[tacchan]

回答ありがとうございます。
初心者で、用語をうまく扱えないためイメージでの文章になってしまいますが、
つまり
インスタンスe = Edge(i, j, distance_table[i][j])のプロパティ？(要素？)はそのまま、i、j、distance_table[i][j]の三つなので、
異なるインスタンス同士の比較をしようにもどれを基準に比べていいのかわからない。
そこで、__cmp__を使ってどのように二つのインスタンスをくらべればいいのかを定義してあげることによって、そのあとedges = PQueue()に入れたときに正常に作動するという認識でよろしいでしょうか？

プログラムに精通していないつたない文章ですみません。

[退会済みユーザー]

PQueue()に関しては同じ作者の他のページ：
http://www.geocities.jp/m_hiroi/light/pyalgo03.html
にソースが出ていますね。
edges = PQueue()
は単にclass PQueueのインスタンス生成で、データ比較用のヒープを確保しているようです。
e = Edge(i, j, distance_table[i][j])
で、地点iと地点jの間の距離(weight)を与えて、クラスEdgeのインスタンスを生成、
そのeをクラスPQueueインスタンスのedgeに対してedge.push(e)なので、
結果的に地点ごとに他の地点への距離データベースが構築されていくことになります。

[tacchan]

何度も解説ありがとうございます。

>結果的に地点ごとに他の地点への距離データベースが構築されていくことになります。

この部分で少し疑問点が出てしまったのですが、「地点ごとに」とは地点i（つまり１～n）に対して他地点への距離の短い順に並べられるということですか？
それとも、i、j関係なく短い順に並べられるということですか？

i=1に対して1<=j<=sizeの距離
次にi=2に対して1<=j<=sizeの距離
～～以下i=sizeまで続く

となるのか、もしくは

i,jは関係なく距離が短い順となる

のかがよくわからなくなってしまいました。
当初は自分の考えは「i,jは関係なく距離が短い順となる」だったので確認しておきたいのでよろしくお願いします。

[退会済みユーザー]

edges = make_edge(point_size)
が呼ばれた時点で、
def make_edge(size):にて定義された処理が走ります。
global distance_tableによってグローバル変数distance_tableを参照する宣言がされ、
edges = PQueue()にて、優先度つき待ち行列が初期化されます、詳しくは
http://www.geocities.jp/m_hiroi/light/pyalgo03.html
の「●プログラムリスト２」をご参照ください。
e = Edge(i, j, distance_table[i][j])にて、def __init__(self, p1, p2, weight):で定義された処理が走ります。
eにはclass Edgeのインスタンスが入り、次の
edges.push(e) にて優先度つき待ち行列に組み込まれます。
優先度つき待ち行列に組み込まれる際に、
class PQueue:にて定義される、def push(self, data):にて定義された処理が走ります。
そこで、def _upheap(buff, n):にて定義された処理が走り、
大小比較された上で順序の入れ替えが起こります。
結果、edges.push(e) の時点で大小関係が整列されています。

[tacchan]

回答ありがとうございます。
自分の考えていた処理の順番と同じことが確認できましたので、安心しました。
何度もご教授下さりありがとうございました。