問題タブ [adjacency-list]

私はこの数時間をオンラインでこの質問の解決策を見つけようとして過ごしました。ネストされたセットから隣接に変換する方法については、たくさんの例を見つけました...しかし、その逆の例はほとんどありません。私が見つけた例は、機能しないか、MySQLプロシージャを使用していません。残念ながら、このプロジェクトの手順を使用することはできません。純粋なPHPソリューションが必要です。

以下の隣接モデルを使用するテーブルがあります。

そして、それを以下のネストされたセットテーブルに変換したいと思います。

これが私が必要とするものの画像です：

このフォーラム投稿（ http://www.sitepoint.com/forums/showthread.php?t=320444 ）の擬似コードに基づいた関数がありますが、機能しません。左に同じ値を持つ複数の行を取得します。これは起こらないはずです。

これは、上記のスクリプトの出力です。

INSERT INTO nested_table（id、、、 ）VALUES（NULL lft、 '2' rgt、category'5'、'ハードカバー'）

INSERT INTO nested_table（id、、、 ）VALUES（NULL lft、 '2' rgt、category'7'、'大判'）

INSERT INTO nested_table（id、、、 ）VALUES（NULL lft、 '1' rgt、category'8'、'Books'）

INSERT INTO nested_table（id、、、 ）VALUES（NULL lft、 '1' rgt、category'10'、'CD \'s'）

INSERT INTO nested_table（id、、、 ）VALUES（NULL lft、 '10' rgt、category'13'、'Vintage'）

INSERT INTO nested_table（id、、、 ）VALUES（NULL lft、 '1' rgt、category'14'、'雑誌'）

INSERT INTO nested_table（id、、、 ）VALUES（NULL lft、 '0' rgt、category'15'、'ROOT'）

ご覧のとおり、「1」のlft値を共有する複数の行があります。同じことが「2」にも当てはまります。入れ子集合では、左と右の値は一意である必要があります。ネストされたセットの左右のIDに手動で番号を付ける方法の例を次に示します。

画像クレジット：Gijs Van Tulder、参考記事

パス列挙列からパンくずを作成したいと思います。

これが私が持っているデータセットの例です。

https://spreadsheets.google.com/ccc?key=0AsGYQbeSAIgFdGRscFpsZFJpQUtfWGIwYWNUY2ktRHc&hl=en_GB&authkey=CPOuuogF

id woeid parent_woeid country_code name language place_type ancestry

1/23424975/24554868/12602167/12696151ancestry は、イギリスのブライトンのパスなど、列挙されたパスです。

name列にクエリを実行してブレッドクラムを取得し、すべての親を取得できるようにしたいと考えています。

すなわち。世界、ヨーロッパ、イングランド、[郡]、[町]、[地域]、[場所]

([] = a placeholder)

データは決して変更されないため、このテーブルでは隣接リストとパスの列挙が使用されます。

世界のすべての地理的な場所とそれらの関係の場所を含むテーブルがあります。

階層を示す例を次に示します。データが実際に 3 つすべてとして保存されていることがわかります。

• 列挙パス
• 隣接リスト
• ネストされたセット

データも明らかに変更されることはありません。以下は、woeid が 13911 であるイギリスのブライトンの場所の直接の祖先の例です。

表: geoplanet_places(560 万行) 大きい画像: http://tinyurl.com/68q4ndx

次に、 という別のテーブルがありますentities。このテーブルには、地理的な場所にマップしたいアイテムが保存されます。いくつかの基本的な情報を保存しますが、最も重要なのwoeidは からの外部キーであるを保存することですgeoplanet_places。

最終的に、entitiesテーブルには数千のエンティティが含まれます。そして、エンティティを含むすべてのノードの完全なツリーを返すことができる方法が欲しいです。

地理的な位置に基づいてエンティティのフィルタリングと検索を容易にし、その特定のノードで見つかるエンティティの数を検出できるようにするための何かを作成する予定です。

したがって、entitiesテーブルにエンティティが 1 つしかない場合、次のようなものになる可能性があります

`地球 (1)

イギリス (1)

イングランド (1)

イーストサセックス (1)

ブライトンとホーブ市 (1)

ブライトン (1)`

次に、デボンにある別のエンティティがあるとしましょう。次のように表示されます。

アース (2)

イギリス (2)

イングランド (2)

デボン (1)

イーストサセックス (1) ... など

各地理的位置の「内部」にあるエンティティの数を示す (カウント) は、ライブである必要はありません。毎時間オブジェクトを生成してキャッシュすることで生活できます。

目的は、エンティティを持つ国のみを表示するインターフェイスを作成できるようにすることです..

以下のようなので

Argentina (1021)、Chile (291)、...、United States (32,103)、United Kingdom (12,338)

次に、ユーザーが United Kingdom などの場所をクリックすると、United Kingdom の子孫であり、エンティティを含む直接の子ノードがすべて表示されます。

英国に 32 の郡があるが、最終的にドリルダウンしたときに 23 の郡のみにエンティティが格納されている場合、残りの 9 郡は表示したくありません。それは場所だけです。

このサイトは、私が達成したい機能を適切に示しています: http://www.homeaway.com/vacation-rentals/europe/r5

このようなデータ構造をどのように管理することをお勧めしますか?

私が使用しているもの。

• PHP
• MySQL
• ソル

ドリルダウンはできるだけ迅速に行う予定です。私は、検索のためにシームレスな AJAX インターフェイスを作成したいと考えています。

また、インデックスを作成することをお勧めする列を知りたいです。

ツリー構造を表す ID と ParentID を持つデータベースに隣接リストがあります。

もちろん、レコードでは ParentID が ID と同じであってはなりませんが、無限ループを防ぐために循環参照も防止する必要があります。これらの循環参照は、理論的には 2 つ以上のレコードを含む可能性があります。( a->b、b->c、c->a など)

レコードごとに、パスを次のような文字列列に保存します。

私の質問は次のとおりです。挿入/更新するときに、循環参照が発生するかどうかを確認する方法はありますか?

ネストされたセットモデルなどについてすべて知っていることを付け加えておく必要があります。保存されたパスを使用した隣接方法を選択したのは、はるかに直感的だからです。トリガーと別のパステーブルで動作するようになりました。循環参照の可能性を除いて、魅力的に動作します。

レベルごとにカテゴリのツリーを表示する必要があります（各レベルのすべてのツリー要素）。

Nested Set構造で実装しようとしましたが、問題が発生しました。親のノードIDを取得する簡単な方法がありません（データベースへの個別のクエリなし）。代わりに隣接リストを使用する必要がありますか？

目標は、理想的にはデータベースへの1つのクエリで、表示をできるだけ速くすることです。

これは私の宿題だと認めます。タスク ステートメントには、標準入力によって入力されるグラフの位相順序を見つけるプログラムを作成する必要があると書かれていました。次に、教授のサーバーで採点するために提出する必要があります。

今はアルゴリズムの問​​題ではありません。それよりも技術的な問題です。私のコンピュータでは、.NET コンパイラ (csc) を使用していますが、教授のグレーディング マシンは何らかの形式のモノを使用しています。

採点者が私が 30/100 を得たと言うまで、それはうまくいきます。私の友人は、採点者の「手動入力システム」を使用することを提案したので、ここでは、隣接リスト用に 100000 個のリストの配列を作成するようにしました。

採点者は、数秒後、私のプログラムがクラッシュしたと報告しました。

これは私にとってちょっと奇妙で不安ですが、私はまだこれに対する答えを見つけていません. 繰り返しますが、このプログラムは私の PC で問題なく動作しました。

これはプログラムの私の部分です：

どうもありがとうございました。すべての応答に感謝します。

編集：グレーダーの出力をもう一度見て、何か見逃していないかどうかを確認しましたが、実際に見落としていました。「syscal: 2」とありましたが、「プログラムが正常に終了しなかった」ということしかわかりません。

編集＃2：5000、10000などの範囲のさまざまなサイズのリストの配列を作成しようとするプログラムを作成しようとしました.40000の後、「手動入力システム」はプログラムがSystem.OutOfMemoryException. 学生が許可されているグレーダーのさまざまな部分をさらに詳しく調べたところ、教授がグレーディング パラメータを誤って構成し、発表されたよりもメモリが少なかったようです。(彼は「32MB」と言いましたが、約 16MB でプログラムがクラッシュします)

私は彼にエラーを報告しましたが、彼は (現在) 調査中です。

私は、10〜15個の異なるIPアドレスから特定のIPアドレスへのtracerouteを作成するプロジェクトに取り組んでいます。ほとんどのtracerouteは、同じ宛先への途中（ホップ）にある特定の一般的なルーターに沿って進みます。結果のデータは私にグラフを与えます。このデータを表す最良の方法は隣接リストだと思います。このようなグラフのインスタンスを取得して、さまざまなtraceroute呼び出しを行うときにエッジ（ホップ）を追加できるCライブラリはありますか？

最短経路プログラムを書きたいです。アルゴリズムの仕組みは知っているが、どこから始めればよいか分からない

最初は、隣接行列を使用することを考えていましたが、スペースの関係で断念しました。今、隣接リストの方が良いと思います。

プログラムに入力を与えるために隣接リストの作成を開始する方法をウェブサイトまたはチュートリアルで教えてもらえますか?

リストは、pushing_back時にメモリを割り当てる際にほとんどの時間を消費します。一方、サイズ変更が必要な場合、ベクターは要素をコピーする必要があります。したがって、隣接リストを格納するのに最も効率的なコンテナはどれですか？

800 x 600 の画像があります。行列のように扱い、隣接する要素を取得したい

元。

(0,0) (1,0) (2,0) (3,0)

(0,1) (1,1) (2,1) (3,1)

(0,2) (1,2) (2,2) (3,2)

(0,3) (1,3) (2,3) (3,3)

解の例: (0,0) は (1,0) (0,1) (1,1) に隣接しています。

(1,1) は (0,0) (1,0) (2,0) (2,1) (2,2) (1,2) (0,2) (0,1) に隣接しています。

だから私はこれらのポイントのそれぞれを格納する構造体配列を書きました

私の最初のアイデアは、dfs を実装することでしたが、それは実際にはうまくいきませんでした。そのため、自分自身を正しい軌道に乗せるために外部の意見を得たいと考えました。ありがとう