0

在 Java 中，想要创建一个包含相等顶点/边的简单图（未加权、无向图，不包含图循环或多条边）。

我有两个 Java 类，一个用于顶点：

 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 的两个顶点相等。

如果随后创建两个具有相同字段但 id 不同的顶点，则 v1.equals(v2) 将为 false，并且两个 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;
}

另一种解决方案是简单地从 Vertex 中删除 hashcode 和 equals 方法，以便使用从 Object 继承的方法，在这种情况下，当且仅当它们引用相同的对象（即内存地址）时，两个 Vertex 实例才相等。

Edge 类也是如此。我不太确定您打算如何使用 Edge 的字段属性，但我只是将其删除以避免遇到同样的问题。

于 2014-04-17T07:13:57.047 回答