9

各ノードが他のノードに接続できるノードを持つグラフ クラスがあります。

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

しかし、それはノード間の接続関係を破壊するため機能しません。簡単な方法でこれを行うための提案があるかどうか疑問に思っていますか? ありがとう。

4

3 に答える 3

15

問題は、ノードの値だけでなく、ノードの ID をコピーする必要があることです。具体的には、ノードをコピーする場合、それが参照するノードの ID を処理する必要があります。つまり、コピー コンストラクターやその他の純粋なローカル コピー メカニズムでは、一度に 1 つのノードしか処理できないため、ジョブを実行できません。意味があるかどうかわかりませんが、入力しましたが、バックスペース キーが機能しません。

とにかく、できることは、どの新しいノードがどの古いノードに対応するかを伝えることができる他のオブジェクトを渡すことです。派手になりたい場合 (そうでない人はいないでしょうか?)、これをグラフ同型と呼ぶことができます。これは、地図のような単純なものです。この完全にテストされていないコードのように:

// 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 はシリアライゼーションの使用について言及しています。シリアライゼーションは、オブジェクト グラフをトラバースするときに、実際にはかなり似たようなことを行います。

于 2012-10-14T20:40:49.630 に答える
6

はい、Java（Javaだけでなく）のディープコピーは、serialization/deserialization このようなメモリを使用して作成できます

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;
    }
于 2012-10-14T20:12:36.360 に答える