1

いくつかのグラフアルゴリズムを実装したいので、一種のグラフフレームワークを作成しています。これまで、次のクラスを使用して有向グラフを非常に簡単に実装しました。

class Vertex {
    String id;
    String name;
}


class Edge {
    String id;
    Vertex source;
    Vertex destination;
    int weight;
}

class Graph {
     List<Vertex> vertexes;
     List<Edge> edges; }

それをテストするとき、私は作成します：

Edge edge = new Edge(id, source_node, destination_node, weight)

これは、有向グラフではまったく問題ありません。ただし、無向グラフでは; 私はこのように書かなければなりません。A、Bの2つのノードがあり、それらの間の重みが10であるとします。したがって、無向グラフの構造のため、2つのエッジを配置する必要があります。

Edge e1 = new Edge(id1, A, B, 10)
Edge e2 = new Edge(id2, B, A, 10)

このタイプのエッジ作成は、非効率的で網羅的です。

したがって、無向グラフの2つのノードの間に2つのエッジを配置する必要がないように、コードを変更するにはどうすればよいですか。無向グラフタイプをコードに統合するための最良の方法は何ですか？

御時間ありがとうございます。

4

5 に答える 5

3

私が最近出会った興味深いJavaAPIがあります。これは、TinkerpopによるBlueprintsと呼ばれ、使用したり、独自のグラフフレームワークを実装する方法のアイデアを得たりすることができます。

JSONを利用したグラフフレームワークを開発しています。これは、グラフの可変性によるものです。グラフ理論のアルゴリズムは、他のアルゴリズムが使用するグラフにデータを追加する傾向があります。エルゴ、グラフを具体的に説明しようとすると、本質的に欠陥があります。

于 2013-03-15T00:36:15.950 に答える
1

自然な解決策は、エッジの方向を属性にすることです。列挙型を作成します。

public enum EdgeType {
     Undirected,
     From1to2,
     From2to1,
     Cyclic
}

次に、Edgeクラスに属性を追加します。

public EdgeType enumEdgeType;

トラバーサルやその他の操作を行う場合は、switchステートメントを使用して4つの異なるケースを処理できます。私の経験では、このアプローチは最も単純で最も効率的です。

于 2013-02-11T17:25:46.813 に答える
1

私は既存の答えに反対するつもりです...

通常、コードでグラフを表現する場合、効率上の理由から、エッジを1つの大きなリストとして、またはオブジェクトとしても保存することは望ましくありません。通常、隣接行列（比較的密なグラフの場合）または隣接リスト（比較的まばらなグラフの場合）を使用することをお勧めします。これにより、頂点の近傍を簡単に検索できます。これは、ほとんどの場合、グラフアルゴリズムで使用するものです。したがって、多くの場合、実装で必要なのは、インデックス付きの配列またはVertexオブジェクトのセットまたはリストだけです。

無向グラフでは、データ構造(i,j)だけでなくエッジも追加します。(j,i)有向グラフでは、そのうちの1つを追加するだけです。

于 2013-02-11T18:21:29.233 に答える
0

実装するグラフアルゴリズムに応じて、異なるグラフ表現が必要になるため、これらのいくつかを使用できる必要があります。ほとんどのアルゴリズムは近隣リストを使用しますが、コードではエッジリストを使用します。

エッジの作成について心配する必要はありません。ほとんどの場合、実際のアルゴリズムと比較すると無視できます。何をしようとしているかによっては、片方のエッジだけが必要な場合もありますが、ほとんどの場合、両方のエッジを持つことは完全に問題なく、正気です。

于 2013-02-11T12:43:51.230 に答える
0

私は青写真に関する答えに反対しなければなりません。このライブラリには多くの誇大宣伝があり、グラフ実装の抽象化の優れた機能を除いて、グラフアルゴリズム（炉）パッケージには何も実装されていないため、複雑なスタックはまったく役に立たなくなります。

何も実装されていないということは、実際には何もありません（ここを見てください）。リポジトリはしばらくの間更新されていないので、死んでいると見なすことができます。使用したい場合

私の2セントは、経験豊富なグラフフレームワークを使用しています：Jgrapht。私はそれをいくつかの研究プロジェクトに使用しています。20の標準（およびいくつかの重要な）グラフアルゴリズムが実装されています。したがって、車輪の再発明をする必要はありません。また、大量のグラフタイプをサポートします。

誇大広告を避け、実用的な解決策を探しましょう。

于 2013-03-30T12:53:23.333 に答える