深いコピーグラフ構造

Question

私はノードの、各ノードは他の人に接続できる場所でグラフのクラスを持っている：

public class Node { 
    List<Node> connections; 
} 

私は、グラフ全体の深いコピーを作成したいと思います。

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

だから、深いコピーはグラフだけで次のようになります：最初の試みとして、私のようなコピーコンストラクタを作ってみました

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

しかし、それは間の接続関係を破壊するとして、それは動作しません。ノード。誰かがこれを簡単なやり方でやるよう提案しているのではないかと疑問に思っていますか？ありがとう。

Answer 1

問題のようにメモリserialization/deserialization を使用して製造することができるJavaで深いコピーを使用すると、ノードのIDをコピーするだけでなく、それらの値を必要とするということです。具体的には、ノードをコピーするときは、そのノードが参照するノードのIDを処理する必要があります。これは、一度に1つのノードしか扱わないため、コピーコンストラクタまたは純粋にローカルなコピーメカニズムの他の種類のものでは、ジョブを実行できないことを意味します。私はそれが意味をなさないか分からないが、私はそれをタイプし、私のバックスペースキーは機能しません。

とにかく、新しいノードがどの古いノードに対応しているかを知ることができる他のオブジェクトを渡すことができます。もしあなたがファンシーになりたいならば、それはgraph isomorphismと呼ぶことができます。これは地図のような単純なものにすることができます。この完全にテストされていないコードの場合：

// 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はシリアル化を使用しています。シリアライゼーションは、オブジェクトグラフを横断するときに、実際にはかなり類似しています。

Answer 2

うん、（だけでなく、Javaでは）この

public static Object copy(Object orig) { 
     Object obj = null; 
     try { 
      // Write the object out to a byte array 
      ByteArrayOutputStream bos = new ByteArrayOutputStream(); 
      ObjectOutputStream out = new ObjectOutputStream(bos); 
      out.writeObject(orig); 
      out.flush(); 
      out.close(); 

      // Make an input stream from the byte array and read 
      // a copy of the object back in. 
      ObjectInputStream in = new ObjectInputStream(
       new ByteArrayInputStream(bos.toByteArray())); 
      obj = in.readObject(); 
     } 
     catch(IOException e) { 
      e.printStackTrace(); 
     } 
     catch(ClassNotFoundException cnfe) { 
      cnfe.printStackTrace(); 
     } 
     return obj; 
    }