tief Kopieren eine Graphenstruktur

Question

Ich habe eine Graph Klasse mit Knotens, wobei jeder Knoten an andere anschließen kann:

public class Node { 
    List<Node> connections; 
} 

würde Ich mag eine tiefe Kopie des gesamten Graphen machen. Als erster Versuch habe ich versucht, wie ein Copykonstruktor machen:

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

So tief Kopieren wäre ein Graph einfach:

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

Aber das funktioniert nicht so, dass die Verbindungsbeziehung zwischen dem zerstört Knoten. Ich frage mich, ob jemand Vorschläge hat, dies auf eine einfache Art und Weise zu tun? Vielen Dank.

Answer 1

Das Problem gemacht werden, ist, dass Sie die Identitäten der Knoten, nicht nur ihre Werte kopieren müssen . Insbesondere wenn Sie einen Knoten kopieren, müssen Sie sich mit den Identitäten der Knoten befassen, auf die er sich bezieht. Das bedeutet, dass ein Kopierkonstruktor oder eine andere Art von rein lokalem Kopiermechanismus die Aufgabe nicht erfüllen kann, da es sich jeweils nur um einen Knoten handelt. Ich bin mir nicht sicher, ob das Sinn macht, aber ich habe es eingegeben und meine Rücktaste funktioniert nicht.

Wie auch immer, Sie können ein anderes Objekt übergeben, das erkennen kann, welcher neue Knoten welchem ​​alten Knoten entspricht. Wenn Sie Lust haben (und wer nicht?), Können Sie dies als graph isomorphism bezeichnen. Dies kann so einfach wie eine Karte sein. Wie in diesem vollständig nicht getesteten 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 erwähnt Serialisierung; Die Serialisierung macht tatsächlich etwas ziemlich Ähnliches, wenn sie einen Objektgraphen durchläuft.

Answer 2

Yep, tiefe Kopie in java (nicht nur in Java) können Speicher mit serialization/deserialization wie diese

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