Java中无向图的边缘

假设我正在编写一个Java类来表示无向图的边。此类Edge包含两个顶点to和from。Java中无向图的边缘

 
class Edge<Vertex> { 

    private final Vertex to, from 

    public Edge(Vertex to, Vertex from) { 
    this.to = to; 
    this.from = from; 
    } 
    ... // getters, equals, hashCode ... 
}

显然e1 = new Edge(v1, v2)和e2 = new Edge(v2, v1)实际上是无向图是相同的。是否有意义？你将如何实现类Edge以满足这一要求？

来源

2012-12-17 Michael

你是否想对有向边和无向边使用这一个实现？我会重新考虑这一点。 – bowmore

好了，我的头顶部，该naivest方法是：

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-17 16:51:00 noMAD

另请参见：http://docs.oracle.com/javase/6/docs/api/java/lang/Comparable.html –

想必节点包含某种标量值 - 排序基于这些值的参数（使用compareTo方法）并使用工厂创建新实例或返回现有实例。

来源

2012-12-17 16:58:24 symcbean

根据某个唯一标识符对构造函数中的顶点执行排序。这种方式，不管顺序如何，它们都是一致的。

我觉得这比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-17 16:59:05 dbyrne

我喜欢这个解决方案，但它假设'Vertex'有一些可比较的'Id'。然而，数学中的图并不假设。 – Michael

我其实不会有这种逻辑在我Edge类，而是某种过度眼见类如Graph类。原因是因为Edge只是一个有2个顶点的对象。它不知道图中其余边的任何内容。

所以，为了扩大对@牧民的回答，我真的把他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))) 
    } 
}

BTW：我会重新命名to和from到vertex1和vertex2，因为它是一个无向图并指示方向，但这只是我的观点。

来源

2012-12-17 16:59:21

Java中无向图的边缘

回答

相关问题