Tree traversal

http://en.wikipedia.org/wiki/Tree_traversal
http://en.wikipedia.org/wiki/Breadth-first_search
http://en.wikipedia.org/wiki/Depth-first_search

Tree traversal in various languages
http://rosettacode.org/wiki/Tree_traversal#Java

Algorithms
http://algs4.cs.princeton.edu/home/
Graphs
http://algs4.cs.princeton.edu/40graphs/
Directed Graphs

http://algs4.cs.princeton.edu/42directed/

Java Data Structure: A Generic Tree

http://sujitpal.blogspot.com/2006/05/java-data-structure-generic-tree.html

Generic Node

public class Node<T> {
 
    public T data;
    public List<Node<T>> children;
    public List<Node<T>> parents;

Non-generic node

package dave;

/**
 * Non-generic subclass of Node<String>
 */
public class DaveNode extends Node<String> {
    public DaveNode() {
        super();
    }
}

Walk using stack

 /**
   *   
   * @param element
   * @return set of all nodes
   */
  public List<Node<T>> walk(Node<T> element){
      
      List<Node<T>> out = new ArrayList<Node<T>>();
      
      Queue<Node<T>> q = new LinkedList<Node<T>>();
      q.add(element);
      
      while(!q.isEmpty()){
          Node<T> x = q.poll();
          out.add(x);
          
          for(Node<T> child : x.getChildren()){
              q.add(child);
          }
      }
      
      return out;
      
  }

Walk from bottom up

  /**
   *   
   * @param element
   * @return set of all upper nodes
   */
  public Collection<Node<T>> pathBottomUp(Node<T> element){
      
      Set<Node<T>> out = new LinkedHashSet<Node<T>>();
      
      Queue<Node<T>> q = new LinkedList<Node<T>>();
      q.add(element);
      
      while(!q.isEmpty()){
          Node<T> x = q.poll();
          out.add(x);
          
          for(Node<T> parent : x.getParents()){
              q.add(parent);
          }
      }
      
      return out;
      
  }

Construct tree

package dave;


public class WalkTree {

    public static void main(String[] args) {
        
        DaveTree daveTree = new DaveTree();
        
        DaveNode daveNode = getDaveNode("1");
        
        DaveNode daveNode11 = getDaveNode("1.1");
        DaveNode daveNode12 = getDaveNode("1.2");
        DaveNode daveNode13 = getDaveNode("1.3");
        
        DaveNode daveNode131 = getDaveNode("1.3.1");
        DaveNode daveNode132 = getDaveNode("1.3.2");
        
        daveNode.addChild(daveNode11);
        daveNode.addChild(daveNode12);
        daveNode.addChild(daveNode13);
        
        daveNode12.addChild(daveNode131);
        
        daveNode13.addChild(daveNode131);
        daveNode13.addChild(daveNode132);
        
                
        daveTree.setRootElement(daveNode);
        
        System.out.println(daveTree.toList());
                
        Node<String> root = daveTree.getRootElement();
        
        System.out.println("walk:" + daveTree.walk(root));
        
        System.out.println("pathBottomUp:" +daveTree.pathBottomUp(daveNode131));

    }
    
    private static DaveNode getDaveNode(String profileName){
        
        DaveNode daveNode = new DaveNode();
        
        daveNode.setData(profileName);
        
        return daveNode;
        
    }

}

Program output

[{1,[1.1,1.2,1.3]}, {1.1,[]}, {1.2,[1.3.1]}, {1.3.1,[]}, {1.3,[1.3.1,1.3.2]}, {1.3.1,[]}, {1.3.2,[]}]
walk:[{1,[1.1,1.2,1.3]}, {1.1,[]}, {1.2,[1.3.1]}, {1.3,[1.3.1,1.3.2]}, {1.3.1,[]}, {1.3.1,[]}, {1.3.2,[]}]
pathBottomUp:[{1.3.1,[]}, {1.2,[1.3.1]}, {1.3,[1.3.1,1.3.2]}, {1,[1.1,1.2,1.3]}]

Functional x Imperative ?

http://rosettacode.org/wiki/Roman_numerals/Decode#Java

[dave@dave lisp]$ clisp 
        i
. i i i I i i i i     ooooo    o        ooooooo   ooooo   ooooo
I I I I I I I I I    8     8   8           8     8     o  8    8
I I  \ `+' /  I I    8         8           8     8        8    8
I  \  `-+-'  /  I    8         8           8      ooooo   8oooo
 \  `-__|__-'  /     8         8           8           8  8
  `--___|___--'      8     o   8           8     o     8  8
        |             ooooo    8oooooo  ooo8ooo   ooooo   8
--------+--------

Welcome to GNU CLISP 2.49 (2010-07-07) <http://clisp.cons.org/>

Code ( taken from Object Oriented Common Lisp )

defun roman-to-decimal  (num-list)
  (if  ( endp num-list)
      0
    (+  (or 
     (and (cdr num-list)
              (< (numeral-to-decimal (car num-list))
         (numeral-to-decimal (cadr num-list)))
              (- (numeral-to-decimal (car num-list))))
     (numeral-to-decimal (car num-list)))
    (roman-to-decimal (cdr num-list)))))

(load "roman-to-decimal.lisp")

[7]> (roman-to-decimal '(M C M L X I X ))
1969
[8]> (trace roman-to-decimal)
;; Tracing function ROMAN-TO-DECIMAL.
(ROMAN-TO-DECIMAL)
[9]> (roman-to-decimal '(M C M L X I X ))
1. Trace: (ROMAN-TO-DECIMAL '(M C M L X I X))
2. Trace: (ROMAN-TO-DECIMAL '(C M L X I X))
3. Trace: (ROMAN-TO-DECIMAL '(M L X I X))
4. Trace: (ROMAN-TO-DECIMAL '(L X I X))
5. Trace: (ROMAN-TO-DECIMAL '(X I X))
6. Trace: (ROMAN-TO-DECIMAL '(I X))
7. Trace: (ROMAN-TO-DECIMAL '(X))
8. Trace: (ROMAN-TO-DECIMAL 'NIL)
8. Trace: ROMAN-TO-DECIMAL ==> 0
7. Trace: ROMAN-TO-DECIMAL ==> 10
6. Trace: ROMAN-TO-DECIMAL ==> 9
5. Trace: ROMAN-TO-DECIMAL ==> 19
4. Trace: ROMAN-TO-DECIMAL ==> 69
3. Trace: ROMAN-TO-DECIMAL ==> 1069
2. Trace: ROMAN-TO-DECIMAL ==> 969
1. Trace: ROMAN-TO-DECIMAL ==> 1969
1969

Haskell
http://www.haskell.org/haskellwiki/Roman_numerals#More-than-one_liner
http://www.cs.york.ac.uk/ftpdir/pub/haskell/contrib/Roman.hs

[dave@dave haskell]$ ghci
GHCi, version 6.12.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Prelude> :l Roman.hs
[1 of 1] Compiling Main             ( Roman.hs, interpreted )
Ok, modules loaded: Main.
*Main> fromRoman "MCMLXIX"
1969

Simple Java implementation

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class RomanToDecimal {

    public static Map<String, Integer> romanNumberMap = new HashMap<String, Integer>();
    static {
        // ( (I 1) (V 5) (X 10) (L 50) (C 100) (D 500) (M 1000)))
        romanNumberMap.put("I", 1);
        romanNumberMap.put("V", 5);
        romanNumberMap.put("X", 10);
        romanNumberMap.put("L", 50);
        romanNumberMap.put("C", 100);
        romanNumberMap.put("D", 500);
        romanNumberMap.put("M", 1000);
    }

    public static void main(String[] args) {

        roman2dec("IV");

        roman2dec("LXIV");

        roman2dec("XCVIII");

        roman2dec("MCMLXIX");

    }

    private static int roman2dec(String roman) {

        int out = 0;

        List<Integer> list = new ArrayList<Integer>();

        for (int i = 0; i < roman.length(); i++) {
            list.add(romanNumberMap.get(String.valueOf(roman.charAt(i))));
        }

        System.out.println("list=" + list);

        while (list.size() > 0) {
            if ((list.size() > 1) && (list.get(0) < list.get(1))) {
                out -= list.remove(0);
            } else {
                out += list.remove(0);
            }
            System.out.println(" list=" + list + " out=" + out);
        }

        System.out.println("roman=" + roman + " dec=" + out);

        return out;

    }

}

list=[1, 5]
 list=[5] out=-1
 list=[] out=4
roman=IV dec=4
list=[50, 10, 1, 5]
 list=[10, 1, 5] out=50
 list=[1, 5] out=60
 list=[5] out=59
 list=[] out=64
roman=LXIV dec=64
list=[10, 100, 5, 1, 1, 1]
 list=[100, 5, 1, 1, 1] out=-10
 list=[5, 1, 1, 1] out=90
 list=[1, 1, 1] out=95
 list=[1, 1] out=96
 list=[1] out=97
 list=[] out=98
roman=XCVIII dec=98
list=[1000, 100, 1000, 50, 10, 1, 10]
 list=[100, 1000, 50, 10, 1, 10] out=1000
 list=[1000, 50, 10, 1, 10] out=900
 list=[50, 10, 1, 10] out=1900
 list=[10, 1, 10] out=1950
 list=[1, 10] out=1960
 list=[10] out=1959
 list=[] out=1969
roman=MCMLXIX dec=1969