2

こんにちは、ノードが親ノードの子になり、別の子ノードの親になる可能性がある XML でグラフを表現するための最良の方法は何でしょうか。それ自体を参照でき、複数のノードが同じ親を持つことができます。また、ノードは複数の親を持つことができます。すべてのノードは同じクラスのものです。親ノードから子ノードについて学ぶことができれば、すべてのノードを反復することなく特定の子タグに移動できるように、効率的に構築したいと考えています。出来ますか？たとえば、ここに概要があります。

A->B,C,D

B->C,D

のように見えるかもしれません

<Node name=A>
 <childNode name=B>
 <childNode name=C>
 <childNode name=D>
</Node>

<Node name=B>
 <childNode name=C>
 <childNode name=D>
</Node>

それで、これよりも良いアプローチはありますか？A、つまりBから子を取得するたびに、基本的にすべてのノードを反復処理し、名前属性をBと一致させて、Bを表すノードを見つける必要があります。

4

3 に答える 3

7

最初に考えたようなツリーではなく、グラフがあるので、GraphMLを使用してみませんか?

GraphML は、包括的で使いやすいグラフ用のファイル形式です。これは、グラフの構造プロパティを記述する言語コアと、アプリケーション固有のデータを追加するための柔軟な拡張メカニズムで構成されています。

グラフの他の多くのファイル形式とは異なり、GraphML はカスタム構文を使用しません。代わりに、XML に基づいているため、グラフを生成、アーカイブ、または処理するあらゆる種類のサービスの共通分母として理想的に適しています。

于 2012-10-15T23:52:10.180 に答える
0

問題を完全に理解しているとは言えませんが、XML ファイルから高級言語で (有向) グラフを再構築しようとしていると思いますよね? 高級言語でどのような表現を持っているかを知ることは役に立ちます。または、実際には言語です。C++ と隣接リストを想定すると、次のようになります。

最初に を作成しmap<string, Node*>、名前をノードにマッピングします。私のXMLは次のようになります。

<edge from='A' to='B' />
<edge from='A' to='C' />
<edge from='A' to='D' />
<edge from='B' to='C' />
<edge from='B' to='D' />

これはかなりコンパクトで、SAX パーサーで解析できます。これは常に優れています。エッジを順番に読み取りながら、マップにノードが既にあるかどうかを確認します。ない場合は、ノードを保存します。

if(mapping.find(from) == map.end()) map.insert(make_pair(from, new Node()));
if(mapping.find(to) == map.end()) map.insert(make_pair(to, new Node()));

両方のエンド ノードがマップに表示されたら、次の方法でエッジを追加できます。

mapping[from]->add_egde_to(mapping[to]);

解析が完了すると、ノードがマップに表示され、名前順に並べられます。

とにかく、ウィキペディアのグラフ表現に関する要約を見たいと思うかもしれません。それはあなたにアイデアを与えるかもしれません。

于 2012-10-15T23:47:06.297 に答える