profonda copia una struttura grafico

Question

Ho una classe grafico con Node, dove ogni nodo può connettersi ad altri:

public class Node { 
    List<Node> connections; 
} 

vorrei fare una copia completa del l'intero grafico. Come primo tentativo, ho provato a fare un costruttore di copia come:

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

Così profonda copia un grafico sarebbe solo:

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

Ma che non funziona come che distrugge il rapporto di connessione tra i i nodi. Mi chiedo se qualcuno ha suggerimenti per farlo in un modo semplice? Grazie.

Answer 1

Il problema è che è necessario copiare l'identità dei nodi, non solo i loro valori . Nello specifico, quando copi un nodo, devi occuparti delle identità dei nodi a cui fa riferimento; ciò significa che un costruttore di copie, o qualche altro tipo di meccanismo di copia puramente locale, non può fare il lavoro, perché si occupa solo di un nodo alla volta. Non sono sicuro che abbia senso, ma l'ho digitato e il mio tasto backspace non funziona.

In ogni caso, ciò che si può fare è passare intorno ad altri oggetti che possono dire quale nuovo nodo corrisponde a quale vecchio nodo. Se si voleva essere fantasiosi (e chi no?) Si potrebbe fare riferimento a questo come graph isomorphism. Questo può essere qualcosa di semplice come una mappa. Come in questo codice completamente non testato:

// 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 utilizza la serializzazione; la serializzazione effettivamente fa qualcosa di abbastanza simile quando attraversa un grafico oggetto.

Answer 2

Yep, copia completa in Java (non solo in java) può essere fatto utilizzando la memoria serialization/deserialization come questo

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