java - Algorithm count of independent sets, always down by 1 -

i'm having trouble writing algorithm count number of independent sets in tree. (an independent set 2 nodes have no edge between them.)

here java class listnode:

 1public class listnode  2{  3    private object data;  4    private listnode next;  5  6    public listnode(object data, listnode next)  7    {  8        this.data = data;  9        this.next = next; 10    } 11 12    public object getdata()  {return data;} 13    public listnode getnext(){return next;} 14    public void setnext(listnode n){next = n;} 15    public void setdata(object d){data = d;} 16    public boolean search(listnode l, object o) 17    { 18        while (l != null){ 19            if (l.getdata().equals(o)) 20                return true; 21            l = l.getnext(); 22        } 23        return false; 24    } 25    public static listnode rev(listnode curr) 26    { 27        listnode rev = null; 28        while (curr != null){ 29            rev = new listnode(curr.getdata(), rev); 30            curr = curr.getnext(); 31        } 32        return rev;}} 

and java class treenode:

1public class treenode  2{   listnode children = null;  3    public void addchild(treenode t)  4    {  5        if (children == null)  6            children = new listnode(t, null);  7        else{  8            listnode curr = children;  9            while (curr.getnext() != null) 10                curr = curr.getnext(); 11            curr.setnext(new listnode(t, null)); 12        }} 13    public void setchildren(listnode t){this.children = t;} 14    public int numstableset() 15    { 16 17        if (children == null || children.getnext() == null) 18            return 2; 19        else{ 20            int count = 2; 21            setchildren(children.getnext()); 22            count *= numstableset(); 23            return count; 24        } 25    } 

the method numstableset 1 need coding help. set now, prints out 1 less correct answer. haven't figured out case each node tree itself.

help appreciated

i don't trust algorithm off one. let's consider few example cases, starting simple ones.

• no node => 1 independent set, empty set
• one node => 2 independent set, empty , 1 node
• one parent , sole child => 3 independent sets, empty , either node

since code seems give same result of 2 both single node , node single child, believe code wrong.

now let's consider recursive case, find right algorithm. visiting given node. decide not include node in stable set, visit children , choose arbitrary stable sets these. or decide include current node, if own parent not included, , when recursing children have ensure not count those. keep track of possible ways combine these choices, , have count. in pythonic pseudocode:

def combinationswithoutcurrent(current):   num = 1   child in current:     num *= stableset(child)   return num  def combinationswithcurrent(current):   num = 1   child in current:     num *= combinationswithoutcurrent(child)   return num  def stableset(current):   return (combinationswithcurrent(current) +           combinationswithoutcurrent(current)) 

as prefer java , obscure hand-made container classes, here java code on how guess data structures intended. since never call getdata in tree traversal, can't see actual recursion going on in code. guess might wrong.

private int combinationswithoutcurrent() {   int num = 1;   (listnode iter = children; iter != null; iter = iter.getnext())     num *= ((treenode)iter.getdata()).numstablesets();   return num; }  private int combinationswithcurrent() {   int num = 1;   (listnode iter = children; iter != null; iter = iter.getnext())     num *= ((treenode)iter.getdata()).combinationswithoutcurrent();   return num; }  public int numstableset() {   return combinationswithcurrent() + combinationswithoutcurrent(); }