Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- [ { 1 }, { 2, 3 }, { 4 }, { 5, 6, 7 } ]
- 1
- /
- /
- /
- 2 3
- | |
- 4 4
- /| /|
- 5 6 7 5 6 7
- [ [ 1, 2, 4, 5 ], [ 1, 2, 4, 6 ], [ 1, 2, 4, 7 ], [ 1, 3, 4, 5 ], [ 1, 3, 4, 6 ], [ 1, 3, 4, 7 ] ]
- /**
- * 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);
- }
- /**
- * 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]
- 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)
- }
- 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;
- }
- 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));
- }
- }
Add Comment
Please, Sign In to add comment