2012-10-14 2 views
8

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

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.

risposta

13

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.

+2

Per coloro che non conoscono IdentityHashMap, controllare [documentazione] (http://docs.oracle.com/javase/7/docs/api/java/util/IdentityHashMap.html) – Swapnil

+0

Questo funziona anche se il grafico ha cicli, giusto? –

+0

@ GonçaloRibeiro: Sì, penso di si. L'ho scritto qualche tempo fa, quindi non ne sono assolutamente certo, ma penso che il fatto di mettere i nodi nella mappa degli isomorfismi prima di visitare le loro connessioni significa che i cicli sono gestiti correttamente. –

6

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

Si noti che se si desidera eseguire questa operazione per una classe Graph o una classe BinaryTree personalizzata come quella che avevo, è necessario scrivere "implementa Serializable" sia sulla classe Node interna che sulla classe BinaryTree. – John61590

Problemi correlati