CODEWITHSUNDEEP
javarecursion
nlopez
nlopez

Reputation: 351

How to get all paths between to items

I have to compute all possible paths between two items from a list. Each item has two fields: its name and its neighbor's name.

I have to generate a list containing all items that would allow me to make a path between two particular items.

Imagine I have Item(A, B) and Item(A, C) and I am being asked for the solution from B to C. I have to return both Items as I can reach C from B by using both of them: B->A->C.

Note that I have no limit on the Items I need to reach a destination.

I have tried several solutions but none of them was successful. I know I have to use some kind of recursive function but I can't figure out how.

This is my Item class:

public class Item {
    private String name;
    private String neighbor;

    public Item(String name, String neighbor){

        this.name = name;
        this.neighbor = neighbor;
    }

    //getters and setters
}

As I have to obtain all possible paths between two particular items, I have to return a list of lists:

List<List<Item>> solution;

My workaround

I finally converted my items to a Graph and, once it is build, I use Depth First Transversal (DFT) in order to find all possible paths between a source and a destination.

I set key-value pairs relating each Item's name with a graph representation and, from the Graph I get a list of Integers that indicates the path in the graph (1-2-3-5, for instance). From that list I find my Items and I return a list of lists with the format I've already explained.

Posting just for someone with a similar problem!

Upvotes: 1

Views: 204

Answers (1)

John
John

Reputation: 2425

Try something like this based on my comment:

you could iterate over each node and perform a depth-first search on each node to see if you can reach the desired node

You mark visited nodes both to avoid cycles (if they're even possible in your use-case) and to track the path.

List<Item> depthFirstSearch(Item startItem, Item desiredItem, List<Item> visitedNodes) {
    if (startItem.equals(desiredItem)) {
        return visitedNodes;
    }

     // Exit if we reach a cycle or no more neighbors to follow
    if (visitedNodes.contains(startItem) || startItem.getNeighbor() == null) {
        return null;
    }

    visitedNodes.add(startItem); 

     // Recurse; continue search from neighbor
    return depthFirstSearch(startItem.getNeighbor(), desiredItem, visitedNodes);
}

And use it like this (You'll need to adapt this to your code):

List<Item> items;
List<List<Item>> result = new List<List<Item>>();

for (Item item : items) {   
    List<Item> pathToDesired = depthFirstSearch(item, desiredItem, new LinkedList<Item>());

    if (pathToDesired != null) {
        results.add(pathToDesired);
    }
}

result will contain all paths to the desired item.

Upvotes: 1

Related Questions