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

问题描述

我有一个节点的图类，每个节点可以连接到其他节点：

  public class Node {
列表<节点>连接
} 
  

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

  public Node（Node other）{
 connections =新的ArrayList< Node>（）; 
（Node n：other.connections）{
 connections.add（new Node（n））; 
} 
} 
  

所以深入复制一个图表只是： p>

  public Graph deepCopy（）{
图g = new Graph（）; 
 g.nodes = new ArrayList< Node>（）; （节点n：节点）
 {
 g.nodes.add（new Node（n））; 
} 
} 
  

但是这不会破坏连接节点之间的关系。我想知道有没有人有一个简单的方法来做这个建议？谢谢。

解决方案

问题是您需要复制节点的身份，而不仅仅是它们的值。具体来说，当你复制一些节点时，你需要处理它所指节点的身份;这意味着复制构造函数或其他纯粹的本地复制机制无法做到这一点，因为它一次只处理一个节点。我不知道这有什么意义，但是我已经输入了，我的退格键不起作用。

无论如何，你可以做的是传递一些其他对象可以告诉哪个新节点对应于哪个旧节点。如果你想成为（而不是谁），你可以将它称为图形同构。这可以像地图一样简单。在这个完全未经测试的代码中：

  // in Graph 
 public Graph deepCopy（）{
图g = new Graph（）; 
 g.nodes = new ArrayList< Node>（）; 
映射<节点，节点> isomorphism = new IdentityHashMap< Node，Node>（）; （节点n：节点）
 {
 g.nodes.add（n.deepCopy（isomorphism））; 
} 
} 
 
 //在Node 
 public Node deepCopy（Map&Node，Node> isomorphism）{
 Node copy = isomorphism.get这个）; 
 if（copy == null）{
 copy = new Node（）; 
 isomorphism.put（this，copy）; 
 for（Node connection：connections）{
 copy.connections.add（connection.deepCopy（isomorphism））; 
} 
} 
返回副本; 
} 
  

Sergii提到使用序列化;当它遍历一个对象图时，序列化实际上做的很相似。

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));
  }
}

// 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 mentions using serialization; serialization actually does something pretty similar when it traverses an object graph.

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