深度复制图结构 [英] deep copying a graph structure

问题描述

我有一个带有节点的图类，其中每个节点都可以连接到其他节点:

I have a graph class with Node's, where each Node can connect to others:

public class Node {
  List<Node> connections;
}

我想制作整个图表的深层副本.作为第一次尝试，我尝试制作一个复制构造函数，如:

I would like to make a deep copy of the entire graph. As a first attempt, I tried making a copy constructor like:

public Node(Node other) {
  connections = new ArrayList<Node>();
  for (Node n : other.connections) { 
    connections.add(new Node(n));
  }
}

对图形进行如此深的复制就是:

So deep copying a graph would just be:

public Graph deepCopy () {
  Graph g = new Graph();
  g.nodes = new ArrayList<Node>();
  for (Node n : nodes) { 
    g.nodes.add(new Node(n));
  }
}

但这不起作用，因为这破坏了节点之间的连接关系.我想知道是否有人建议以简单的方式做到这一点?谢谢.

But that doesn't work as that destroys the connection relationship among the nodes. I am wondering if anyone has suggestions to do this in a simple way? Thanks.

推荐答案

问题是您需要复制节点的身份，而不仅仅是它们的值.具体来说，当你复制某个节点时，你需要处理它所引用的节点的身份；这意味着复制构造函数或其他某种纯粹的本地复制机制无法完成这项工作，因为它一次只处理一个节点.我不确定这是否有意义，但我已经输入了它并且我的退格键不起作用.

The problem is that you need to copy the identities of the nodes, not just their values. Specifically, when you're copying some node, you need to deal with the identities of the nodes it refers to; that means that a copy constructor, or some other kind of purely local copying mechanism, can't do the job, because it only deals with one node at a time. I'm not sure that makes any sense, but I've typed it and my backspace key doesn't work.

无论如何，您可以做的是传递一些其他对象，这些对象可以告诉哪个新节点对应于哪个旧节点.如果你想变得花哨(谁不想?)，你可以将其称为 图同构.这可以像地图一样简单.在这个完全未经测试的代码中:

Anyway, what you can do is pass around some other object which can tell which new node corresponds to which old node. If you wanted to be fancy (and who doesn't?) you could refer to this as a graph isomorphism. This can be something as simple as a map. As in this completely untested code:

// in Graph
public Graph deepCopy () {
  Graph g = new Graph();
  g.nodes = new ArrayList<Node>();
  Map<Node, Node> isomorphism = new IdentityHashMap<Node, Node>();
  for (Node n : nodes) { 
    g.nodes.add(n.deepCopy(isomorphism));
  }
  return g;
}

// in Node
public Node deepCopy(Map<Node, Node> isomorphism) {
    Node copy = isomorphism.get(this);
    if (copy == null) {
        copy = new Node();
        isomorphism.put(this, copy);
        for (Node connection: connections) {
            copy.connections.add(connection.deepCopy(isomorphism));
        }
    }
    return copy;
}

Sergii 提到使用序列化；序列化在遍历对象图时实际上做了一些非常相似的事情.

Sergii mentions using serialization; serialization actually does something pretty similar when it traverses an object graph.

这篇关于深度复制图结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！