0

Java で、等しい頂点/エッジを含む単純なグラフ (グラフ ループまたは複数のエッジを含まない重み付けされていない無向グラフ) を作成したい。

2 つの Java クラスがあり、1 つは頂点用です。

 class Vertex {

    private int field;

    public Vertex(int field) {
        this.field = field;
    }

    @Override
    public boolean equals(Object obj) {

        if (obj.getClass().getPackage()
                .equals(this.getClass().getPackage())
                && obj.getClass().getName()
                        .equals(this.getClass().getName())) {

            Vertex vertex = (Vertex) obj;

            if (this.field == vertex.field)
                return true;
        }

        // Else
        return false;
    }

    @Override
    public int hashCode() {
        // No need for a perfect hash
        return this.field;
    }
}

エッジのクラス:

class Edge {

    private int field;

    public Edge(int field) {
        this.field = field;
    }

    @Override
    public boolean equals(Object obj) {

        if (obj.getClass().getPackage()
                .equals(this.getClass().getPackage())
                && obj.getClass().getName()
                        .equals(this.getClass().getName())) {

            Edge edge = (Edge) obj;

            if (this.field == edge.field)
                return true;
        }

        // Else
        return false;
    }

    @Override
    public int hashCode() {
        // No need for a perfect hash
        return this.field;
    }
}

現在、JGraphT ライブラリを使用しています。しかし、私はIllegalArgumentException: "loops not allowed"このコードを開始した後に遭遇しました:

    // Define a EdgeFactory
    EdgeFactory<Vertex, Edge> BOND_FACTORY = new EdgeFactory<Vertex, Edge>() {
        @Override
        public Edge createEdge(Vertex sourceVertex, Vertex targetVertex) {
            return new Edge(2);
        }
    };
    // Create the graph
    SimpleGraph<Vertex, Edge> graph = new SimpleGraph<Vertex, Edge>(
            BOND_FACTORY);

    // Create vertexes
    Vertex v1 = new Vertex(1);
    Vertex v2 = new Vertex(1);

    // Add them to the graph
    graph.addVertex(v1);
    graph.addVertex(v2);
    graph.addEdge(v1, v2);

問題は、グラフに追加しようとすることですv2が、グラフに追加されないためv1.equals(v2) == true v2です。lib の JavaDoc から:

指定された頂点がまだ存在しない場合は、このグラフに追加します。より正式には、このグラフに u.equals(v) となる頂点 u が含まれていない場合、指定された頂点 v をこのグラフに追加します。

このチェックはここに実装されています。

しかし、それでは、どうすれば自分がやろうとしていることを達成できますか? このライブラリに使用できる別の実装がありますか、それともequals()メソッドを変更するのは良い考えですか?

4

1 に答える 1

1

あなたにとって、例の頂点 v1 と v2 は区別できるようです。次に、それらがグラフでも区別できるようにする必要があります。つまり、v1.equals(v2) が false を返すことを確認してください。メンバー変数「id」(または何か) を Vertex に追加し、その変数に基数とハッシュコードを追加することを検討することをお勧めします。そのメンバー変数の契約は、同じ ID を持つ 2 つの頂点が等しいということです。

次に、フィールドが同じで ID が異なる 2 つの頂点を作成すると、v1.equals(v2) は false になり、2 つの Vertex オブジェクトはグラフ内の異なる頂点を表します。例えば：

Vertex v1 = new Vertex("a", 1);
Vertex v2 = new Vertex("b", 1);

Vertex のコンストラクタは次のようになります。

public Vertex(String id, int field) {
  this.id = id;
  this.field = field;
}

もう 1 つの解決策は、Vertex から hashcode メソッドと equals メソッドを単純に削除して、Object から継承されたメソッドが使用されるようにすることです。この場合、2 つの Vertex インスタンスは、同じオブジェクト (つまり、メモリ アドレス) を参照している場合にのみ等しくなります。

同じことが Edge クラスにも当てはまります。Edge のフィールド プロパティをどのように使用するつもりなのかよくわかりませんが、同じ種類の問題が発生しないように、単純に削除します。

于 2014-04-17T07:13:57.047 に答える