Getting paths from root to leaves in a specific tree encoding

Question

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

Next one Set<Integer>[]:

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

represents the following tree:

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

Thus, each level in the tree is encoded as Set. All children at a certain level in the tree are the same. The first set may contain several integers.

I want to get from the Set<Integer>[]list of all paths from root to leaves:

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

Answer 1

The key for searching in trees usually implements a good Ajacency function, which gives neighboring nodes for a specific node.

, node, . :

  /**
   * 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;
  }

, , .

, . :

/**
 * 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);
  }

, currentPath root .

DFS , node , , , ():

  /**
   * 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);
    }
  }

, :

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);
    }
  }
}

, :

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));
    }

:

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

Answer 2

, , .

, ( ) ( ).

:

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)

}

Answer 3

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;
}

This 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));
    }
}