Find dependencies between many lists

Question

I have a list of integer lists List<List<Integer>> dependency = new ArrayList<List<Integer>>() that contains the following lists:

[0, 0]
[1, 0]
[2, 1]
[3, 1]
[4, 3]
[5, 1]
[6, 4]
[8, 5]
[9, 3]
[10, 2]
[11, 6]

Each list consists of ID and its dependent from another list. For example, [2,1] can be read as the ID of 2 depends on the list of ID = 1 ([1,0]).

I would like to know the dependencies between the lists similar to the following example:

10 <- 2 <- 1 <- 0 (this can be read as: List of ID = 10 depends on list of ID = 2 that depends on list of ID = 1 that depends on list of ID = 0)

8 <- 2 <- 1 <- 0 (List of ID = 8 depends on list of ID = 5 that depends on list of ID = 1 that depends on list of ID = 0)

To do that, I did the following:

    for(List<Integer> x: dependency) {
        x1 = x.get(0);
        x2 = x.get(1);

        int x3 = dependency.get(x2).get(1);
        System.out.println(x1 + " -- " + x2 + " -- " + x3);
    }

But this doesn't work with the case of ID = 6 since it has more dependencies: 6 <- 4 <- 3 <- 1 <- 0

Also, in the case of 11: 11 <- 6 <- 4 <- 3 <- 1 <- 0

How to fix the issue so that I can get as many dependencies as possible?

Your problem would be much easier to solve if you had a `Map` or `Map>` associating an id with its (list of?) depencency. There's no good reason to handle the id/dependency pair as a `List`. — Aaron, Mar 21 '19 at 13:07
why don't you use map if there are just 2 values? that will perfectly fit your situation — Danyal Sandeelo, Mar 21 '19 at 13:07
Maybe a [tree](https://stackoverflow.com/a/17490124/5914654) is a better design, for what you're trying to achieve — vincrichaud, Mar 21 '19 at 13:11

Berkoz · Answer 1 · 2019-09-25T12:48:18.850

Looks like a classic case of recursion usage to me. I used the following code:

import java.util.ArrayList;
import java.util.List;

public class Listofintegerlists {

    public static void init(List<List<Integer>> list) {
    ...
    }

    public static void main(String[] args) {
        List<List<Integer>> dependency = new ArrayList<List<Integer>>();
        init(dependency);
        System.out.println(dependency);
        printDependenciesAux(dependency);
    }

    public static void printDependenciesAux(List<List<Integer>> dependency) {
        for (List<Integer> x : dependency) {
            System.out.print("Printing dependencies for ID = " + x.get(0) + ": ");
            printDepedencies(x, dependency);
            System.out.println();
        }
    }
    public static void printDepedencies(List<Integer> curList, List<List<Integer>> dependency) {
        int curID = curList.get(0);
        int nextID = curList.get(1);

        System.out.print(curID + " <-- ");
        if (nextID == 0) {
            System.out.print("0");
            return;
        }
        List<Integer> nextList = getNextList(nextID, dependency);
        printDepedencies(nextList, dependency);
    }

    private static List<Integer> getNextList(int nextID, List<List<Integer>> dependency) {
        for (List<Integer> x : dependency) {
            if (x.get(0) == nextID) {
                return x;
            }
        }
        return null;
    }
}

output:

[[0, 0], [1, 0], [2, 1], [3, 1], [4, 3], [5, 1], [6, 4], [8, 5], [9, 3], [10, 2], [11, 6]]
Printing dependencies for ID = 0: 0 <-- 0
Printing dependencies for ID = 1: 1 <-- 0
Printing dependencies for ID = 2: 2 <-- 1 <-- 0
Printing dependencies for ID = 3: 3 <-- 1 <-- 0
Printing dependencies for ID = 4: 4 <-- 3 <-- 1 <-- 0
Printing dependencies for ID = 5: 5 <-- 1 <-- 0
Printing dependencies for ID = 6: 6 <-- 4 <-- 3 <-- 1 <-- 0
Printing dependencies for ID = 8: 8 <-- 5 <-- 1 <-- 0
Printing dependencies for ID = 9: 9 <-- 3 <-- 1 <-- 0
Printing dependencies for ID = 10: 10 <-- 2 <-- 1 <-- 0
Printing dependencies for ID = 11: 11 <-- 6 <-- 4 <-- 3 <-- 1 <-- 0

score 1 · Answer 2 · answered Mar 21 '19 at 15:03

Assuming that there are no reciprocal dependencies like [1, 2] & [2, 1] creating a map navigate the map recursively can be an option:

public static void main(String[] args)  {
    List<List<Integer>> dependency = new ArrayList<>(); // fill your list
    //create a map
    Map<Integer,Integer> depMap = dependency.stream().collect(Collectors.toMap(k->k.get(0), k->k.get(1)));
    //print dependencies using the recursive method provided below 
    System.out.println(getdependencies(depMap,10)); 
}

public static String getdependencies(Map<Integer,Integer> map, Integer key) {
    if(map.containsKey(key)){
        if (map.get(key) == 0) {
            return key + " <- " + map.get(key).toString();
        }
        return key + " <- " + getdependencies(map, map.get(key));
    }
    return "Key: "+key+" not found";
}

Find dependencies between many lists

2 Answers2