2

グラフのデータ構造を処理するためのクラスをJavaで実装したいと思います。NodeクラスとEdgeクラスがあります。Graphクラスは、ノードのリストとエッジのリストの2つのリストを維持します。各ノードには一意の名前が必要です。このような状況を防ぐにはどうすればよいですか。 

Graph g = new Graph();

Node n1 = new Node("#1");
Node n2 = new Node("#2");

Edge e1 = new Edge("e#1", "#1", "#2");

// Each node is added like a reference
g.addNode(n1);
g.addNode(n2);
g.addEdge(e1);

// This will break the internal integrity of the graph
n1.setName("#3");   
g.getNode("#2").setName("#4");

ノードとエッジをグラフに追加するときにクローンを作成し、グラフの構造的整合性を維持するNodeEnvelopeクラスを返す必要があると思います。これはこれを行う正しい方法ですか、それとも設計は最初から壊れていますか？

4

6 に答える 6

4

私は Java でグラフ構造をよく扱いますが、私のアドバイスは、Graph がその構造を維持するために依存する Node および Edge クラスのデータ メンバーを、setter を使用せずに final にすることです。実際、可能であれば、Node と Edge を完全に不変にします。これには多くのメリットがあります。

たとえば、次のようになります。

public final class Node {

    private final String name;

    public Node(String name) {
           this.name = name;
    }

    public String getName() { return name; }
    // note: no setter for name
}

次に、Graph オブジェクトで一意性チェックを行います。

public class Graph {
    Set<Node> nodes = new HashSet<Node>();
    public void addNode(Node n) {
        // note: this assumes you've properly overridden 
        // equals and hashCode in Node to make Nodes with the 
        // same name .equal() and hash to the same value.
        if(nodes.contains(n)) {
            throw new IllegalArgumentException("Already in graph: " + node);
        }
        nodes.add(n);
    }
}

ノードの名前を変更する必要がある場合は、古いノードを削除して新しいノードを追加します。これは余分な作業のように聞こえるかもしれませんが、すべてをまっすぐに保つための多くの労力を節約できます。

実際には、ゼロから独自のグラフ構造を作成することはおそらく不要です。この問題は、独自のグラフ構造を構築した場合に遭遇する可能性が高い多くの問題の最初の 1 つにすぎません。

優れたオープン ソースの Java グラフ ライブラリを見つけて、代わりにそれを使用することをお勧めします。何をしているかに応じて、いくつかのオプションがあります。私は過去にJUNGを使用したことがあり、良い出発点としてお勧めします。

于 2008-09-15T17:19:00.797 に答える
3

ノードの文字列名の追加の間接化を追加する理由は明確ではありません。Edge コンストラクターの署名がではpublic Edge(String, Node, Node)なく、public Edge (String, String, String)

ここでクローンがどこで役立つかわかりません。

ETA: ノードの作成後にノード名を変更することで危険が生じるIllegalOperationException場合は、クライアントが既存の名前を持つノードで setName() を呼び出そうとすると、 をスローします。

于 2008-09-15T15:17:02.773 に答える
1

私の意見では、データ構造がそれを行うと明示的に述べない限り、要素を複製するべきではありません。

ほとんどのものの望ましい機能は、参照によってデータ構造に渡される実際のオブジェクトを必要とします。

クラスをより安全にしたい場合Nodeは、グラフの内部クラスにします。

于 2008-09-15T15:12:28.277 に答える
1

NodeEnvelopes またはエッジ/ノード ファクトリを使用することは、過剰設計のように思えます。

本当に Node で setName() メソッドを公開したいですか? あなたの例には、それが必要であることを示唆するものは何もありません。Node クラスと Edge クラスの両方を不変にすると、想定している整合性違反のシナリオのほとんどが不可能になります。(変更可能にする必要があるが、グラフに追加されるまでのみ必要な場合は、Node/Edge クラスに isInGraph フラグを設定し、Graph.Add{Node, Edge} によって true に設定することでこれを強制できます。このフラグが設定された後に呼び出された場合、ミューテーターが例外をスローするようにします。)

Node オブジェクトを (文字列の代わりに) Edge コンストラクターに渡すことは良いアイデアのように聞こえるという jhkiley の意見に同意します。

より侵入的なアプローチが必要な場合は、Node クラスからそれが存在する Graph へのポインターを保持し、Node の重要なプロパティ (名前など) が変更された場合に Graph を更新することができます。しかし、Edge の関係を維持しながら既存のノードの名前を変更できるようにする必要があることが確実でない限り、私はそうしません。

于 2008-09-15T17:51:34.697 に答える
1

Object.clone() にはいくつかの大きな問題があり、ほとんどの場合、その使用はお勧めできません。完全な回答については、Joshua Bloch による「 Effective Java 」の項目 11 を参照してください。プリミティブ型の配列で Object.clone() を安全に使用できると思いますが、それとは別に、clone を適切に使用してオーバーライドすることについて慎重に考える必要があります。おそらく、セマンティクスに従ってオブジェクトを明示的に複製するコピー コンストラクターまたは静的ファクトリ メソッドを定義する方がよいでしょう。

于 2008-12-09T22:48:25.403 に答える
0

@jhkiley.blogspot.com によるコメントに加えて、すでに使用されている名前のオブジェクトの作成を拒否する Edge と Node のファクトリを作成できます。

于 2008-09-15T16:47:21.107 に答える