Solved

Problem using recursive function to compare trees in Java

Posted on 2012-04-09
5
586 Views
Last Modified: 2012-04-15
Hi

I have to find the best matching subtrees in two xml trees.
here is the code (in brief):

public static void FindBestMatchingSubtree(int doc1, int doc2, Node n1, Node n2, SQLScript statement) {
        // retrieve internal nodes for the first and second trees  
        
        ArrayList<Node> t1Nodes = statement.getInternalChildNodes(doc1, n1);
        ArrayList<Node> t1Nodes = statement.getInternalChildNodes(doc2, n2);

        for (Node t1childNode : t1Nodes) {  // to iterate child nodes of the 1st ArrayList
            for (Node t2childNode : t2Nodes) {  // to iterate child nodes of the 2nd ArrayList
                
                if (t1childNode.getNodeName().equals(t2childNode.getNodeName())) {
                    score = calculateScore(t1childNode, t2childNode, statement);
                    
                    // Test if two pair of nodes for the two trees are matched
                    if (score == 1.0) { // Identical nodes
                        System.out.println("Identical");
                    }
                    else if ((score < 1.0) && (score > 0)) { // Matched nodes (semi)
                        System.out.println("Matched");
                        // recursively match the child nodes of the current ones 
                        FindBestMatchingSubtree(doc1, doc2, t1childNode, t2childNode, statement);    
                    }
                } // end if

            }  // end for
            // Just hint for the output
            System.out.println("Finish one child from the first tree");
        }  // end for
    }

Open in new window


Job of the function:
- It takes as input two document ids and two nodes of them (say root nodes of XML document.
- It then create two ArrayLists of child nodes for both given nodes n1 & n2.
- It will then compare pairs of nodes to find if they are Identical or matched (using special function calculateScore).
- If they are identical, print that.
- If they are matched (not exactly the same), go deeper and repeat the process by comparing child nodes of the current pair.

The problem:
I get wrong result because I think when the function (FindBestMatchingSubtree) is called inside itself it will repeat creating the two ArrayLists: t1Nodes & t2Nodes, which is wrong

Can anyone help to achieve the goal without having such a problem

Regards
0
Comment
Question by:hamsalgla
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
  • 2
5 Comments
 
LVL 11

Assisted Solution

by:anilallewar
anilallewar earned 100 total points
ID: 37826686
The array lists t1Nodes & t2Nodes that are created with each recursive call is fine as those would be different objects that get created on stack.

What is the significance of int doc1, int doc2 as they get passed for each recursive call but don't change within the execution?

I will need more information including the code to make further suggestions.
0
 
LVL 20

Expert Comment

by:gatorvip
ID: 37827270
>>I get wrong result

How can you tell? Please post sample data, the resulting output using your code and the desired output
0
 
LVL 20

Assisted Solution

by:gatorvip
gatorvip earned 100 total points
ID: 37827279
>>       ArrayList<Node> t1Nodes = statement.getInternalChildNodes(doc1, n1);
        ArrayList<Node> t1Nodes = statement.getInternalChildNodes(doc2, n2);

Check your code, this should probably say t2Nodes. I assume this is just a copy/paste typo in here as in real code you should be getting an error (t2Nodes would be undefined).
0
 

Accepted Solution

by:
hamsalgla earned 0 total points
ID: 37828202
What is the significance of int doc1, int doc2 as they get passed for each recursive call but don't change within the execution?

doc1 and doc2 are passed as parameters getInternalChildNodes function to get the list of nodes for doc1 and doc1 (see line 4 and 5).
They do not affect the results.

>>       ArrayList<Node> t1Nodes = statement.getInternalChildNodes(doc1, n1);
        ArrayList<Node> t1Nodes = statement.getInternalChildNodes(doc2, n2);

Check your code, this should probably say t2Nodes. I assume this is just a copy/paste typo in here as in real code you should be getting an error (t2Nodes would be undefined).

Yes I made a typo mistake.

Actually I found the problem. that is a exit from the function:
if (t1Nodes.isEmpty() || t2Nodes.isEmpty()) {
            System.exit(0);
}

Open in new window

It was in line 9 (inside the two loops)
I remove it from the code here because I thought it is not significant.
When I replace it with If..Else condition, the program works fine and I get the correct results.

Thanks guys for your helps.

I will back to you as soon as i have probs since this is just a very small part of my big project :)

Regadrs
0
 

Author Closing Comment

by:hamsalgla
ID: 37848065
Calling 'System.exit()' inside the function can be a good practice as long as you know it will not end the program unexpectedly.

Use 'if, else' statement instead.
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
How to get all the API from website? 11 125
check java version using powershell 13 293
ejb example issues 3 52
Html Table Looping (part 2) 5 35
Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importing…
Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:

756 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question