私はC++で有向非循環グラフを作成しましたが、これをテキストファイルまたはファイルに保存したいと考えています。それ、どうやったら出来るの?有向非循環グラフをディスクに保存する方法は?
P.S:混乱して申し訳ありません...私はファイルのフォーマット方法を尋ねることを意味します。
ありがとうございます!
私はC++で有向非循環グラフを作成しましたが、これをテキストファイルまたはファイルに保存したいと考えています。それ、どうやったら出来るの?有向非循環グラフをディスクに保存する方法は?
P.S:混乱して申し訳ありません...私はファイルのフォーマット方法を尋ねることを意味します。
ありがとうございます!
まず、すべてのノードにノードIDを割り当てて保存し、開始ノードと終了ノードのノードIDを使用してすべてのアークを保存します。
これは(など...、非連結グラフを含む連結グラフを掛け、ループ)すべてのケースを処理する
あなたのグラフの各頂点は、あなたのファイルのために次のような構造を使用することができますIDのいくつかの種類を持っている場合:
<num vertexes>
1 <num neighbors> <neighbor ID> ... <neighbor ID>
...
N <num neighbors> <neighbor ID> ... <neighbor ID>
グラフを保存するには、正方行列を使用できます。
誰か他の人がどのようにしたかの例として、graphvizと 'ドット'言語を見てください。
既存のファイルフォーマットに基づいてファイルフォーマットを設定することは、独自の方法を考案するよりも良いアイデアです。あなたの持っていないものを考えていることがよくあります。そして、あなたがstabdard laguageに固執すれば、graphvizのウェブサイト上のフォーマットやツールへのリンクもたくさんあります。
行列の(i、j)エントリは、ノードiとノードjが接続されていることを示します。
ディスクに書き込むには、そこにあるノードの数を書き出し、行ごとに行列を書き出します。この方法で、n^2 + 1の数字をディスクに書き出します。
しかし、このアプローチは、グラフが疎である場合(つまり、ノードの数がノードの数であることを意味します)、非効率的です(ノードの数が< <であることを意味します)。しかし、シンプルなシリアライゼーション構造を持っています。
シリアライズするコードを記述します。 – sbi
*指向非循環グラフ*は* n-ary tree *に相当し、まったく同じ方法で保存できます。 – Seth
@Seth:DAGをツリーに変換すると、ツリーが指数関数的に大きくなることがあります。 – Potatoswatter