जावा

Question

में दिए गए सबट्री से मेल खाने वाले पेड़ में सभी सबट्री खोजें I जावा में कोड लिख रहा हूं जो एक अनियंत्रित, जड़ वाले पेड़ का उपयोग करता है जहां प्रत्येक नोड में बच्चे नोड्स की संख्या हो सकती है। एक वृक्ष टी और एक उपट्री एस को देखते हुए, मैं टी में सभी उपट्री ढूंढने में सक्षम होना चाहता हूं जो एस से मेल खाता है (जो एस में सभी सबट्री है जो एस के लिए आइसोमोर्फिक हैं)।

टी का एक सबट्री एस isomorphic को है, एस के नोड्स को इस तरह से टी के नोड्स मैप किया जा सकता है, तो यह है कि टी

में किनारों को एस नक्शे के किनारों

एक previous question पर कहा गया है कैसे पता लगाएं कि एक पेड़ में एक और उपट्री है, लेकिन मैं सभी टी में मिलान करने वाले टी में उपट्री ढूंढने में सक्षम होना चाहता हूं। इसके अतिरिक्त मैं टी में प्रत्येक मैच में प्रत्येक नोड से प्रत्येक नोड से मानचित्र में सक्षम होना चाहता हूं।

यह है कि, जब एक मैच मिल जाता है, तो इसे टी में नोड के पॉइंटर के रूप में वापस नहीं किया जाना चाहिए जहां एक पेड़ रूट होता है जो एस से मेल खाता है, लेकिन मैच को सोमथी के रूप में वापस किया जाना चाहिए ng को पॉइंटर्स के जोड़े की सूची की तरह [[टी 1, एस 1), (टी 2, एस 2), ... (टीएन, एसएन)] जैसे कि टी 1 टी में नोड के लिए एक सूचक है जो नक्शे में एस 1 को नोड करने के लिए मानचित्र करता है subtree और इतने पर।

वैकल्पिक रूप से बस मूल्यों के जोड़े की एक सूची को वापस किया जा सकता है क्योंकि पेड़ टी में प्रत्येक नोड और उपट्री एस के साथ एक अद्वितीय पूर्णांक पहचानकर्ता है।

उदाहरण के लिए:

को देखते हुए पेड़ टी इस प्रकार है:

a 
/\ 
    b c 
/\ 
d e 

और सबट्री एस के रूप में:

x 
/\ 
    y z 

मैचों में से निम्न सूची वापस आ जाना चाहिए:

[(ए, एक्स), (बी, वाई), (सी, जेड)] [(ख, एक्स), (घ, y), (ई, जेड)]

एक अद्वितीय मैच टी में नोड्स के सेट से निर्धारित होता है, नहीं टी में नोड्स के बीच मानचित्रण और एस

तो निम्नलिखित मैच:

[(क, एक्स), (ख, z), (ग, y)]

की डुप्लीकेट माना जाता है [(क, एक्स), (ख, y), (ग, z)]

वे नोड्स एक ही प्रकार की वजह से टी (ए, बी, सी) से इसलिए केवल एक मैच वापस किया जाना चाहिए।

एक और उदाहरण के रूप में, यह देखते हुए पेड़ टी:

a 
    /|\ 
    b c d 

और सबट्री एस:

x 
/\ 
y z 

मैचों में से निम्न सूची वापस आ जाना चाहिए:

[(क, एक्स), (बी, वाई), (सी, जेड)] [(ए, एक्स), (बी, वाई), (डी, जेड)] [(ए, एक्स), (सी, वाई), (डी , जेड)]

क्या कोई इसे कैसे करना है इसका कोई उदाहरण कोड दे सकता है?

(क्रिस Kannon की टिप्पणी के संबंध में) संपादित करें:

मैं तुम्हें किसी कोड करने के लिए आप के लिए जवाब चाहिए सोच रहा हूँ? आप कितने दूर तक प्राप्त कर चुके हैं? आपने किस कोड को लिखा है? - क्रिस Kannon 1 घंटे पहले

मैं निम्नलिखित कोड है जो जब चलाने के लिए, पेड़ में नोड्स जहां subtrees निहित हैं कि दिए गए सबट्री से मिलान करने के संकेत दिए की एक सूची (matchesList) बनाता है। हालांकि एक ही नोड पर रूट किए गए कई सबट्री हो सकते हैं और वर्तमान में प्रत्येक नोड केवल मैचों में सबसे अधिक बार जोड़ा जाएगा, इस पर ध्यान दिए बिना कि कितने मैच रूट हैं।

इसके अतिरिक्त, मैं मूल पेड़ में पाए गए मैच में उपट्री और नोड्स में नोड्स के बीच वर्णित मैपिंग का निर्माण कैसे कर सकता हूं।

package Example; 

import java.util.LinkedList; 
import java.util.Vector; 

public class PartialTreeMatch { 
    public static void main(String[] args) { 
     NodeX testTree = createTestTree(); 
     NodeX searchTree = createSearchTree(); 

     System.out.println(testTree); 
     System.out.println(searchTree); 

     partialMatch(testTree, searchTree); 
    } 

    static LinkedList<NodeX> matchesList = new LinkedList<NodeX>(); 

    private static boolean partialMatch(NodeX tree, NodeX searchTree) { 
     findSubTreeInTree(tree, searchTree); 
     System.out.println(matchesList.size()); 
     for (NodeX n : matchesList) { 
      if (n != null) { 
       System.out.println("Found: " + n); 
      } 
     } 

     return false; 
    } 

    private static NodeX findSubTreeInTree(NodeX tree, NodeX node) { 
     if (tree.value == node.value) { 
      if (matchChildren(tree, node)) { 
       matchesList.add(tree); 

      } 
     } 

     NodeX result = null; 
     for (NodeX child : tree.children) { 
      result = findSubTreeInTree(child, node); 

      if (result != null) { 
       if (matchChildren(tree, result)) { 
        matchesList.add(result); 

       } 
      } 
     } 

     return result; 
    } 

    private static boolean matchChildren(NodeX tree, NodeX searchTree) { 
     if (tree.value != searchTree.value) { 
      return false; 
     } 

     if (tree.children.size() < searchTree.children.size()) { 
      return false; 
     } 

     boolean result = true; 
     int treeChildrenIndex = 0; 

     for (int searchChildrenIndex = 0; searchChildrenIndex < searchTree.children 
       .size(); searchChildrenIndex++) { 

      // Skip non-matching children in the tree. 
      while (treeChildrenIndex < tree.children.size() 
        && !(result = matchChildren(tree.children 
          .get(treeChildrenIndex), searchTree.children 
          .get(searchChildrenIndex)))) { 
       treeChildrenIndex++; 
      } 

      if (!result) { 
       return result; 
      } 
     } 

     return result; 
    } 

    private static NodeX createTestTree() { 

     NodeX subTree2 = new NodeX('A'); 
     subTree2.children.add(new NodeX('A')); 
     subTree2.children.add(new NodeX('A')); 

     NodeX subTree = new NodeX('A'); 
     subTree.children.add(new NodeX('A')); 
     subTree.children.add(new NodeX('A')); 
     subTree.children.add(subTree2); 

     return subTree; 
    } 

    private static NodeX createSearchTree() { 
     NodeX root = new NodeX('A'); 
     root.children.add(new NodeX('A')); 
     root.children.add(new NodeX('A')); 

     return root; 
    } 
} 

class NodeX { 
    char value; 
    Vector<NodeX> children; 

    public NodeX(char val) { 
     value = val; 
     children = new Vector<NodeX>(); 
    } 

    public String toString() { 
     StringBuilder sb = new StringBuilder(); 

     sb.append('('); 
     sb.append(value); 

     for (NodeX child : children) { 
      sb.append(' '); 
      sb.append(child.toString()); 
     } 

     sb.append(')'); 

     return sb.toString(); 
    } 
} 

कोड ऊपर के सभी subgraphs खोजने की कोशिश करता:

A 
/|\ 
A A A 
/\ 
    A A 

जो मैच:

A 
/\ 
    A A 

कोड सफलतापूर्वक का पता लगाता है एक मैच में एक शीर्ष नोड निहित है कि वहाँ पहला पेड़ और पहले पेड़ के तीसरे बच्चे। हालांकि, वास्तव में शीर्ष नोड पर रूट किए गए 3 मैच हैं, केवल एक ही नहीं। इसके अलावा, कोड पेड़ और नोड्स में नोड्स के बीच मैपिंग का निर्माण नहीं करता है और मैं यह नहीं कर सकता कि यह कैसे करें।

क्या कोई इस बारे में कोई सलाह दे सकता है कि यह कैसे करें?

Answer 1

मुझे लगता है कि आपकी रिकर्सिव विधि को केवल एक बूलियन की बजाय आंशिक मिलान की सूची लौटने की आवश्यकता है। यह आपकी समस्याओं को हल करने के लिए एक लंबा रास्ता तय करेगा (मैचों की सूची वापस करने की आवश्यकता है, साथ ही साथ कई मैचों को ढूंढना)।

जावा की तरह पुनरावर्ती क्रिया के लिए स्यूडोकोड कुछ इस तरह दिख सकता है:

findMatches(treeNode, searchNode) { 
    if searchNode has no children { 
     // search successful 
     pairs = [] // empty list 
     return [pairs] // list of lists 
    } 
    else { 
     matches = [] // empty list 
     searchChild = first child node of searchNode 
     searchNode2 = searchNode with searchChild removed 
     // NOTE: searchNode2 is created by doing a shallow copy of just the node 
     // (not it's children) and then removing searchChild from the child list. 

     for each treeChild in treeNode.children { 
      if treeChild.value == searchChild.value { 
       treeNode2 = treeNode with treeChild removed // also a shallow copy 
       childMatches = findMatches(searchChild, treeChild) 
       nodeMatches = findMatches(treeNode2, searchNode2) 

       // cross-product 
       for each nodeMatchPairs in nodeMatches { 
        for each childMatchPairs in childMatches { 
         fullMatchPairs = [(searchChild, treeChild)] 
          + childMatchPairs + nodeMatchPairs // concatenate lists 
         add fullMatchPairs to matches 
        } 
       } 
      } 
     } 

     return matches 
    } 
} 

सूचना है कि इस समारोह treeNode.value == searchNode.value का परीक्षण नहीं है, या की सूची में जोड़ने। कॉलर को ऐसा करने की ज़रूरत है। इस समारोह को पेड़ के हर नोड पर चलाने की जरूरत है।

वर्तमान में डिज़ाइन किए गए अनुसार, यह शायद बहुत अधिक मेमोरी का उपयोग करता है, लेकिन इसे अनुकूलित किया जा सकता है।

Answer 2

This सहायक हो सकता है।