गहरी नकल एक ग्राफ संरचना

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 का उपयोग किया जा सकता है कि आप नोड्स की पहचान कॉपी करने की जरूरत है, न सिर्फ उनके मूल्यों है । विशेष रूप से, जब आप कुछ नोड की प्रतिलिपि बना रहे हैं, तो आपको नोड्स की पहचान से निपटने की आवश्यकता होती है; इसका मतलब है कि एक प्रतिलिपि निर्माता, या किसी अन्य प्रकार की पूरी तरह से स्थानीय प्रतिलिपि तंत्र, नौकरी नहीं कर सकता, क्योंकि यह केवल एक समय में एक नोड से संबंधित है। मुझे यकीन नहीं है कि कोई समझ में आता है, लेकिन मैंने इसे टाइप किया है और मेरी बैकस्पेस कुंजी काम नहीं करती है।

वैसे भी, आप जो कुछ भी कर सकते हैं वह किसी अन्य वस्तु के आसपास गुजरता है जो बता सकता है कि कौन सा नया नोड पुराने नोड से मेल खाता है। यदि आप फैंसी बनना चाहते थे (और कौन नहीं करता?) तो आप इसे 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; 
} 

सर्गी क्रमबद्धरण का उपयोग करने का उल्लेख करता है; serialization वास्तव में कुछ समान समान करता है जब यह किसी ऑब्जेक्ट ग्राफ़ को पार करता है।

Answer 2

हाँ, जावा में गहरी प्रतिलिपि (न केवल जावा में) इस

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