0

無向グラフのエッジを表す Java クラスを作成しているとします。このクラスには とEdgeの 2 つの頂点が含まれtoますfrom。

class Edge<頂点> {

  プライベート最終頂点へ、から

  public Edge(Vertex to, Vertex from) {
    this.to = to;
    this.from = from;
  }
  ... // ゲッター、equals、hashCode ...
}

無向グラフでは明らかにe1 = new Edge(v1, v2)とは同じです。e2 = new Edge(v2, v1)それは理にかなっていますか？Edgeその要件を満たすために クラスをどのように実装しますか?

4

4 に答える 4

2

一意の識別子に基づいて、コンストラクターの頂点で並べ替えを実行します。このようにして、順序に関係なく一貫して保存されます。

これらのオブジェクトと相互作用するすべてのコードは、の実装だけでなく、それらを同じように扱うため、これはnoMADのソリューションよりも好ましいと思いますequals。

また、クラスメンバーに電話をかけると、to有向グラフfromのように聞こえるので混乱します。vertex1これらの名前を、やのようなより一般的なものに変更しvertex2ます。

  public Edge(Vertex x, Vertex y) {
      if (vertex2.getId() > vertex1.getId()) {
          this.vertex1 = x;
          this.vertex2 = y;
      } else {
          this.vertex1 = y;
          this.vertex2 = x;
      }
  }
于 2012-12-17T16:59:05.500 に答える
2

私は実際にはこのロジックをEdgeクラスに持っていませんが、クラスなどのある種の監視クラスを持っていGraphます。Edgeこれは、が2つの頂点を持つ単なるオブジェクトであるためです。グラフの残りのエッジについては何も知りません。

したがって、@ noMadの答えを拡張するために、実際に彼のcheckIfSameEdgeメソッドをGraphクラスに配置します。

public class Graph {
    private List<Edge> edges;
    ....
    public void addEdge(Edge e) {
        for (Edge edge : edges) {
            if (isSameEdge(edge, e) {
                return; // Edge already in Graph, nothing to do
        }
        edges.add(e);
    }
    private boolean isSameEdge(Edge edge1, Edge edge2) {
        return ((edge1.to.equals(edge2.to) && edge1.from.equals(edge2.from))
             || (edge1.to.equals(edge2.from) && edge1.from.equals(edge2.to)))
    }
}

ところで：それは無向グラフであり、方向を示すために名前を変更しますが、それは私の意見ですto。fromvertex1vertex2

于 2012-12-17T16:59:21.043 に答える
1

おそらく、ノードにはある種のスカラー値が含まれています。これらの値に基づいてパラメーターを並べ替え（compareToメソッドを使用）、ファクトリを使用して新しいインスタンスを作成するか、既存のインスタンスを返します。

于 2012-12-17T16:58:24.263 に答える
1

まあ、私の頭の中で、最も単純な方法は次のとおりです。

protected boolean checkIfSameEdge(Vertex to, Vertex from) {
  if(to.equals(this.from) && from.equals(this.to) || to.equals(this.to) && from.equals(this.from)) {
    return true;
  return false;
}

明らかに、オーバーライドする必要がありequalsますhashcode

于 2012-12-17T16:51:00.133 に答える