1

同様のトピックを検索しましたが、私の理解度と理解度に対して回答が曖昧すぎて、私の質問に対して十分に具体的ではないと思います。

同様のスレッド:
ツリー (有向非巡回グラフ) の実装
DAG (有向非巡回グラフ) の表現

質問：

次の形式のデータを含むテキスト ファイルをフォーマットしました...
データセットの例:
GO:0000109#is_a: GO:0000110#is_a: GO:0000111#is_a: GO:0000112#is_a: GO:0000113#is_a: GO :0070312#is_a: GO:0070522#is_a: GO:0070912#is_a: GO:0070913#is_a: GO:0071942#part_of: GO:0008622
GO:0000112#part_of: GO:0000442 GO:0000118#is_a:16 81
: #is_a: GO:0034967#is_a: GO:0070210#is_a: GO:0070211#is_a: GO:0070822#is_a: GO:0070823#is_a: GO:0070824
GO:0000120#is_a: GO:0000500#is_a: GO: 0005668#is_a: GO:0070860
GO:0000123#is_a: GO:0005671#is_a: GO:0043189#is_a: GO:0070461#is_a: GO:0070775#is_a: GO:0072487
GO:0000126#is_a: 4#GO: is_a: GO:0034733
GO:0000127#part_of: GO:0034734#part_of: GO:0034735
GO:0000133#is_a: GO:0031560#is_a: GO:0031561#is_a: GO:0031562#is_a: GO:0031563#part_of: GO:0031500
GO:0000137#part_of: GO:0000136

このデータから重み付けされた有向 DAG を構築しようとしています (上記は単なるスニペットです)。106kb のデータセット全体はこちら:ソース

--------------------------------------------------

行ごとに考慮して、各行のデータを次のように説明し
ます
。 : GO:0000113#is_a: GO:0070312#is_a: GO:0070522#is_a: GO:0070912#is_a: GO:0070913#is_a: GO:0071942#part_of: GO:0008622

「#」は、行データの区切り文字/トークナイザーです。
最初の項 GO:0000109 はノード名です。
is_a: GO:xxxxxxx OR part_of: GO:xxxxxxx の次の項は、GO:0000109 に接続されているノードです。
データセットに示されているように、後続の用語の一部にも接続があります。
is_a の場合、エッジの重みは 0.8 です。
part_of の場合、エッジの重みは 0.6 です。

--------------------------------------------------

私は DAG の仕組みについて Google で検索しましたが、その概念は理解しています。ただし、それをコードに入れる方法はまだわかりません。私はJavaを使用しています。
私の理解では、グラフは一般にノードとアークで構成されています。このグラフは、接続の方向を決定するために隣接リストを必要としますか? もしそうなら、グラフと隣接リストを組み合わせて相互に通信する方法がわかりません。グラフを作成した後の次の目標は、ルート ノードから各ノードの次数を調べることです。データセットにルート ノードがあります。

説明のために、データの最初の行の接続のサンプルを以下に示します:
画像リンク

私がここで達成しようとしていることを皆さんが理解してくれることを願っています。私の問題を調べてくれてありがとう。:)

4

2 に答える 2

1

考えやすいので、ツリーで表現したいと思います。(また、マップを横断して中間度を維持することが容易になります。)

Node子Nodeオブジェクトの Collection を持つクラスを持つことができます。必要に応じて、子関係をRelationship重みとNodeポインタの両方を持つオブジェクトとして表すこともでき、オブジェクトのコレクションを格納することもできRelationshipます。

次に、ルートから開始してツリーをウォークし、訪問した各ノードに次数をマークします。

class Node{
    String name;
    List<Relationship> children;
}

class Relationship{
    Node child;
    double weight;
}

class Tree{
    Node root;
}

ここでTreeは、おそらく次のようなメソッドが必要です。

public Node findNodeByName(String name);

そしてNode、おそらく次のようなメソッドが必要です。

public void addChild(Node n, double weight);

次に、各行を解析するときに、 Tree.findNodeByName() を呼び出して一致するノードを検索し (存在しない場合は作成します...ただし、データが適切な場合は発生しないはずです)、次の項目を追加しますそのノードへの回線。

ご指摘のとおり、特に一部のノードには複数の親があるため、DAG を実際にツリーに変換することはできません。できることは、特定のノードがトラバースされたかどうかを判断するためにハッシュ テーブルを使用して、複数の親の子として同じノードを挿入することです。

于 2011-12-15T08:45:22.057 に答える
0

コメントを読むと、ノードにノードを含むリレーションシップを含める方法に混乱しているように見えます。これは非常に一般的な戦略であり、一般に複合パターンと呼ばれます。

ツリーの場合の考え方は、ツリーが複数のサブツリーで構成されていると考えることができるということです。ノードとそのすべての祖先をツリーから切断した場合、切断されたノードは、より小さいものではありますが、ツリーを作成します。したがって、ツリーを表す自然な方法は、各ノードに他のノードを子として含めることです。このアプローチにより、多くのことを再帰的に行うことができます。これは、ツリーの場合、多くの場合、やはり自然です。

ノードにその子を追跡させ、ツリーの他の部分も数学的な有向グラフをエミュレートしないようにします。各頂点はそのエッジのみを「認識」し、他には何も認識しません。

再帰ツリーの実装例

たとえば、二分探索木で要素を検索するには、ルートの検索メソッドを呼び出します。次に、ルートは、検索された要素がそれ自体と等しいか、それより小さいか、または大きいかをチェックします。等しい場合、検索は適切な戻り値で終了します。小さいか大きい場合、ルートは代わりに左または右の子でそれぞれ search を呼び出し、まったく同じことを行います。

同様に、新しいノードをツリーに追加するには、新しいノードをパラメーターとしてルートの add メソッドを呼び出します。ルートは、新しいノードを採用するか、その子の 1 つに渡すかを決定します。後者の場合、子を選択し、新しい Node をパラメータとして add メソッドを呼び出します。

于 2011-12-20T00:52:03.947 に答える