2

我想在 Java 中实现一个用于处理图形数据结构的类。我有一个 Node 类和一个 Edge 类。Graph 类维护两个列表：节点列表和边列表。每个节点必须有一个唯一的名称。我该如何防范这样的情况： 

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 类的任何数据成员都成为最终的，没有设置器。事实上，如果可以的话，我会让 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);
    }
}

如果您需要修改节点名称，请移除旧节点并添加新节点。这可能听起来像是额外的工作，但它可以节省很多精力来保持一切正常。

但是，实际上，从头开始创建自己的 Graph 结构可能是不必要的——如果您自己构建，这个问题只是您可能遇到的许多问题中的第一个。

我建议找到一个好的开源 Java 图形库，然后使用它。根据您在做什么，有一些选择。我过去使用过JUNG，我会推荐它作为一个很好的起点。

于 2008-09-15T17:19:00.797 回答
3

我不清楚为什么要为节点添加额外的字符串名称间接。public Edge(String, Node, Node)你的 Edge 构造函数的签名不是更有意义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 类都设为不可变，那么您设想的大多数违反完整性的场景都将变得不可能。（如果您需要它们是可变的，但仅在它们被添加到图表之前，您可以通过在节点/边缘类上设置一个 isInGraph 标志来强制执行此操作，该标志由 Graph.Add{Node, Edge} 设置为 true，并且如果在设置此标志后调用，让您的 mutator 抛出异常。）

我同意 jhkiley 的观点，将 Node 对象传递给 Edge 构造函数（而不是字符串）听起来是个好主意。

如果您想要一种更具侵入性的方法，您可以使用从 Node 类返回到它所在的 Graph 的指针，并在 Node 的任何关键属性（例如，名称）发生变化时更新 Graph。但我不会这样做，除非您确定需要能够更改现有节点的名称，同时保留边缘关系，这似乎不太可能。

于 2008-09-15T17:51:34.697 回答
1

Object.clone() 存在一些重大问题，在大多数情况下不鼓励使用它。请参阅 Joshua Bloch 的“ Effective Java ”中的第 11 条以获得完整答案。我相信您可以在原始类型数组上安全地使用 Object.clone()，但除此之外，您需要谨慎地正确使用和覆盖克隆。您最好定义一个复制构造函数或根据您的语义显式克隆对象的静态工厂方法。

于 2008-12-09T22:48:25.403 回答
0

除了@jhkiley.blogspot.com 的评论之外，您还可以为 Edges 和 Nodes 创建一个工厂，拒绝创建具有已使用名称的对象。

于 2008-09-15T16:47:21.107 回答