グラフをシリアル化する方法は？

Question

これはinterview questionです：グラフをシリアル化するには？私はこれを見たanswerしかし、これで十分かどうかはわかりません。

これは非常に混乱している "オープンな質問"のように見え、候補者はおそらくノードとエッジが何であるか、それらがどのように直列化されているか、このグラフが重み付けされ、指示されているかなど、 、グラフにはノード/エッジの数があります。インフラストラクチャはどうですか？それは普通のファイルシステムですか、あるいはデータベースを使うべきですか？

この質問にどう答えますか？

Answer 1

あなたの答えはprovidedだと思います。 IMOは、基本的にあなたはアプリケーションの背景を知る必要があります、私は少なくとも質問します：

• それは指示かどうかですか？
• 頂点、エッジ、グラフ自体に関連するプロパティは何ですか？
• は疎なグラフです（もしそうなら、隣接行列を使わない方が良いでしょう）。

最も簡単な方法は、エッジリストとして保存することです。 しかし、異なるアプリケーションでは、それを行ういくつかの古典的な方法があります。 たとえば、回路シミュレーションを行っている場合、グラフは疎であり、得られたグラフ/マトリックスは列圧縮形式で保存することができます。 あなたが（最小コスト）最大流量の問題を解決しているなら、公共のソルバーがそれを読んで書くことができるように既にDIMACSのフォーマットがあります。人間が読めるようにするには、構造化された方法も良い選択です。XMLは自己検証を提供できます（既に標準でGraphMLがあります）。ちなみに、dot形式は完全に自己完結型です。

Answer 2

Meh。あなたがそれを格納するものは、基本的には次のとおりです。

グラフの各頂点を出力します。すべての頂点を最初に持っていない場合は、グラフを再読み込みするときにPITAを使用します。

頂点間にエッジを保存することができます。うまくいけば、あなたの頂点は一意に識別するための何らかの形のIDを持っているといいでしょう。私が見たこのバージョンは、「データベースに（グラフ|ツリー）を格納する」というものです。したがって、ノードを読み込み、O（1）償却されたルックアップのためにハッシュテーブルなどに格納します。次に、foreach edge、ID-sourceとID-destを検索し、リンクします。

ヴォイラ、あなたはそれをデシリアライズしました。 DBでない場合、同じ考え方が一般的に成り立ちます。まずノードを直列化し、次にエッジを直列化します。