title: Family tree ancestor find algorithm
body: <p>My method cannot pass the unit test. I stared on it for 5 hours in vain. Could somebody help me to see what's wrong with it?</p>
  
  <p>PS: the getAllRelations() method in my code below is to separated the formatted inputs into arraylists of ArrayList of strings, for example, if I have a formatted input like this(I used it in my test case that couldn't pass) </p>
  
  <pre><code>String format = "John Doe , Mary Smith" + "\n" + "Brian William , John Doe" + "\n" + "Brian William ,Robert Andrew" + "\n" + "Mary Smith , Max Jackson";
  </code></pre>
  
  <p>In each line, the first person is the parent of the second person.
  the getAllRelations() method will split this formatted strings into arraylists that each of the list only contains the two name strings(without spaces after or before names) in each line as its elements. for example arraylist1 will be a list contains"John" and "Mary Smith".</p>
  
  <p>Here is my methods that I could not figure out what's wrong, I want to used this method to check if two people share the same ancestor.</p>
  
  <pre><code>private boolean hasSameAncestor(String person1, String person2){
      ArrayList&lt;ArrayList&lt;String&gt;&gt; allRelations = allRelations();
      int i = 0;
      int j = 0;
      String name1 = person1;
      String name2 = person2;
      String parent1;
      String parent2;
      for(i = 0, parent1 = ""; i &lt; allRelations.size(); i++){
          if(name1.equals(allRelations.get(i).get(1))){
              parent1 = allRelations.get(i).get(0);
              for(j = 0, name2 = person2, parent2 = ""; j &lt; allRelations.size(); j++){
                  if(name2.equals(allRelations.get(j).get(1))){
                      parent2 = allRelations.get(j).get(0);
                      if(parent2.equals(parent1)){
                          return true;
                      }
                      else{
                          name2 = parent2;
                          j = 0;
                      }
                  }
              }
              name1 = parent1;
              i = 0;
          }
      }
      return false;
  }
  </code></pre>
  
  <p>My test case that cannot pass is like this.</p>
  
  <pre><code>    @Test
      public void testHasSameAncestor()
      FamilyTree familyTree4 = new FamilyTree("John Doe , Mary Smith" + "\n" + "Brian William , John Doe" + "\n" + "Brian William ,Robert Andrew" + "\n" + "Mary Smith , Max Jackson");
      assertEquals(true, format.hasSameAncestor("Max Jackson", "Robert Andrew"));
  }
  </code></pre>
  
  <p>I cannot figure out what's wrong with my function, could somebody help me? Thank you very much.</p>
  
  <p>Code that could paste to eclipse for debugging help</p>
  
  <pre><code>package test;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  
  
  public class Test1 {
  
      String test;
  
      public Test1(String test){
          this.test = test;
      }
  
  
      private ArrayList&lt;String&gt; lineRelations(){
          int i;
          ArrayList&lt;String&gt; lineRelations = new ArrayList&lt;String&gt;();
          String[] lines = test.split("\n");
          for(i = 0; i &lt; lines.length; i++){
              lineRelations.add(lines[i]);
          }
          return lineRelations;
      }
  
      private ArrayList&lt;ArrayList&lt;String&gt;&gt; allRelations(){
          int i;
          ArrayList&lt;ArrayList&lt;String&gt;&gt; allRelations = new ArrayList&lt;ArrayList&lt;String&gt;&gt;();
          ArrayList&lt;String&gt; lineRelations = lineRelations();
          for(i = 0; i &lt; lineRelations.size(); i++){
              ArrayList&lt;String&gt; eachLine = new ArrayList&lt;String&gt;(Arrays.asList(lineRelations.get(i).split("\\s*,\\s*")));
              allRelations.add(eachLine);
          }
          return allRelations;
      }
  
      public boolean hasSameAncestor(String person1, String person2){
          ArrayList&lt;ArrayList&lt;String&gt;&gt; allRelations = allRelations();
          int i = 0;
          int j = 0;
          String name1 = person1;
          String name2 = person2;
          String parent1;
          String parent2;
          for(i = 0, parent1 = ""; i &lt; allRelations.size(); i++){
              if(name1.equals(allRelations.get(i).get(1))){
                  parent1 = allRelations.get(i).get(0);
                  for(j = 0, name2 = person2, parent2 = ""; j &lt; allRelations.size(); j++){
                      if(name2.equals(allRelations.get(j).get(1))){
                          parent2 = allRelations.get(j).get(0);
                          if(parent2.equals(parent1)){
                              return true;
                          }
                          else{
                              name2 = parent2;
                              j = 0;
                          }
                      }
                  }
                  name1 = parent1;
                  i = 0;
              }
          }
          return false;
      }
  }
  </code></pre>
  
  <p>test case</p>
  
  <pre><code>package test;
  import static org.junit.Assert.*;
  import test.Test1;
  
  import org.junit.Test;
  
  
  public class Test1Test {
  
      @Test
      public void testHasSameAncestor(){
          Test1 test1 = new Test1("John Doe , Mary Smith" + "\n" + "Brian William , John Doe" + "\n" + "Brian William ,Robert Andrew" + "\n" + "Mary Smith , Max Jackson");
          assertEquals(true, test1.hasSameAncestor("Max Jackson", "Robert Andrew"));
      }
  }
  </code></pre>