Getting paths from root to leaves in a specific tree encoding

I have a tree represented as a Set<Integer>[]

The following Set<Integer>[]:

[ { 1 }, { 2, 3 }, { 4 }, { 5, 6, 7 } ]

represents the following tree:

      1
     / \
    /   \
   /     \
  2       3
  |       |
  4       4
 /|\     /|\
5 6 7   5 6 7

So each level in the tree is encoded as a Set. All set of children at a particular level in the tree are the same. There can be more than one integers in the first set.

I want to get, from the Set<Integer>[], a list of all the paths from root to le开发者_Go百科aves:

[ [ 1, 2, 4, 5 ], [ 1, 2, 4, 6 ], [ 1, 2, 4, 7 ], [ 1, 3, 4, 5 ], [ 1, 3, 4, 6 ], [ 1, 3, 4, 7 ] ]

The Key for Searching in trees is usually implementing a good Ajacency function that gives the adjacent nodes for a specific node.

For this tree, adjacency function would want to find which level the node lies in, and then return the nodes in the next level as adjacents. It will look something like that:

  /**
   * This returns the adjacent nodes to an integer node in the tree
   * @param node
   * @return a set of adjacent nodes, and null otherwise
   */
  public Set<Integer> getAdjacentsToNode(Integer node) {

    for (int i = 0; i < tree.size(); i++) {
      Set<Integer> level = tree.get(i);
      if (level.contains(node) && i < tree.size() - 1) {
        return tree.get(i + 1);
      }
    }
    return null;
  }

Assuming that we already have the tree defined as a field in the class.

Before we run our search we would want to initalize setting the root appropriately and doing some prework to the paths. Therefore we do the following:

/**
 * initializes our search, sets the root and adds it to the path
 */
  public void initialize() {
    root = -1;
    for (Integer node : tree.get(0)) {
      root = node;
    }
    currentPath.add(root);
  }

Assuming that currentPath and root are already defined as fields.

Then, we run a DFS search on the tree appending each node to our current path as we traverse the tree, and adding that path to our set paths and reseting it when we reach a deadend (the leafs):

  /**
   * runs a DFS on the tree to retrieve all paths
   * @param tree
   */
  public void runDFS(Integer node) {
    if (getAdjacentsToNode(node) != null) {
      for (Integer adjNode : getAdjacentsToNode(node)) {
        currentPath.add(adjNode);
        runDFS(adjNode);
      }
      currentPath.remove(currentPath.size() -1);
    } else {
      paths.add(currentPath.toArray(new Integer[0]));
      currentPath.remove(currentPath.size() -1);
    }
  }

The whole class, therefore, looks like this:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DFS {
  private List<Integer> currentPath = new ArrayList<Integer>();
  private List<Integer[]> paths = new ArrayList<Integer[]>();
  private ArrayList<Set<Integer>> tree;
  private Integer root;
  /**
   * constructor
   * @param tree
   */
  public DFS(ArrayList<Set<Integer>> tree) { 
    this.tree = tree;
  }

  public List<Integer[]> getPaths() {
    return paths;
  }
  public void setPaths(List<Integer[]> paths) {
    this.paths = paths;
  }
  public Integer getRoot() {
    return root;
  }
  public void setRoot(Integer root) {
    this.root = root;
  }

/**
 * initializes our search, sets the root and adds it to the path
 */
  public void initialize() {
    root = -1;
    for (Integer node : tree.get(0)) {
      root = node;
    }
    currentPath.add(root);
  }

  /**
   * This returns the adjacent nodes to an integer node in the tree
   * @param node
   * @return a set of adjacent nodes, and null otherwise
   */
  public Set<Integer> getAdjacentsToNode(Integer node) {

    for (int i = 0; i < tree.size(); i++) {
      Set<Integer> level = tree.get(i);
      if (level.contains(node) && i < tree.size() - 1) {
        return tree.get(i + 1);
      }
    }
    return null;
  }

  /**
   * runs a DFS on the tree to retrieve all paths
   * @param tree
   */
  public void runDFS(Integer node) {
    if (getAdjacentsToNode(node) != null) {
      for (Integer adjNode : getAdjacentsToNode(node)) {
        currentPath.add(adjNode);
        runDFS(adjNode);
      }
      currentPath.remove(currentPath.size() -1);
    } else {
      paths.add(currentPath.toArray(new Integer[0]));
      currentPath.remove(currentPath.size() -1);
    }
  }
}

To test it, we try this:

public static void main(String[] args) { 
    ArrayList<Set<Integer>> tree = new ArrayList<Set<Integer>>();
    Set<Integer> level1 = new HashSet<Integer>();
    level1.add(new Integer(1));

    Set<Integer> level2 = new HashSet<Integer>();
    level2.add(new Integer(2));
    level2.add(new Integer(3));

    Set<Integer> level3 = new HashSet<Integer>();
    level3.add(new Integer(4));

    Set<Integer> level4 = new HashSet<Integer>();
    level4.add(new Integer(5));
    level4.add(new Integer(6));
    level4.add(new Integer(7));

    tree.add(level1);
    tree.add(level2);
    tree.add(level3);
    tree.add(level4);

    DFS dfsSearch = new DFS(tree); 
    dfsSearch.initialize();
    dfsSearch.runDFS(dfsSearch.getRoot());

    for (Integer[] path : dfsSearch.getPaths()) { 
      System.out.println(Arrays.toString(path));
    }

and we get the following output:

[1, 2, 4, 5]
[1, 2, 4, 6]
[1, 2, 4, 7]
[1, 3, 4, 5]
[1, 3, 4, 6]
[1, 3, 4, 7]

Try something like this:

public static List<Integer[]> getAllPaths(Set<Integer>[] tree){

    // Get the overall number of path
    int totalSize = 1;
    for(Set<Integer> line : tree){
        totalSize *= line.size();
    }

    // Create the empty paths
    List<Integer[]> allPaths = new ArrayList<Integer[]>(totalSize);
    for(int i = 0 ; i<totalSize ; ++i){
        Integer[] path = new Integer[tree.length];
        allPaths.add(path);
    }

    // Fill the paths
    int indexLine = 0;
    for (Set<Integer> line : tree) {
        Iterator<Integer[]> pathIterator = allPaths.iterator();
        Iterator<Integer> lineIterator = line.iterator();
        while(pathIterator.hasNext()){
            if(!lineIterator.hasNext()){
                lineIterator = line.iterator();
            }
            pathIterator.next()[indexLine] = lineIterator.next();
        }
        ++indexLine;
    }
    return allPaths;
}

It works for your example:

public static void main(String[] args) {

    Set<Integer> line1 = new HashSet<Integer>();
    line1.add(new Integer(1));
    Set<Integer> line2 = new HashSet<Integer>();
    line2.add(new Integer(2));
    line2.add(new Integer(3));
    Set<Integer> line3 = new HashSet<Integer>();
    line3.add(new Integer(4));
    Set<Integer> line4 = new HashSet<Integer>();
    line4.add(new Integer(5));
    line4.add(new Integer(6));
    line4.add(new Integer(7));

    Set[] test = {line1, line2,line3,line4};

    List<Integer[]> allPaths = getAllPaths(test);

    for(Integer[] path : allPaths){
        System.out.println(Arrays.toString(path));
    }
}

I'm not going to write the code, but the easiest way will be a depth first traversal, where at each level you append each entry to the current paths.

Also, your return value will be a collection (or array) of lists (since a vertical path can't be an unordered set).

in pseudo-code:

def getPaths(levels) {
  return getPaths(levels, 0, new Set())
}

def getPaths(levels, currentIndex, paths) {

  if(currentIndex == levels.length)
    return paths

  def newPaths = new Set(paths)

  for(path : paths) {
    for(level : levels) {
      newPaths.add( path + level )
    }
  }

  return getPaths(levels, currentIndex + 1, newPaths)

}