Logic for finding all paths from one graph node to another

Question

I have a tricky logic question and I am trying to create an algorithm to solve it, but I am struggling to get my head around it.

Consider this data:

A to B
A to C
A to D
A to E
B to C
B to D
B to E
C to D
C to E
D to E

As you can see this effectively produces a model like so: A - B - C - D - E

You can only go in one direction, (left to right) and what I want to write is an algorithm that can work out all the possible combinations between 2 points i.e.

If I wanted to go from A to E all the possible combinations are like so:

A - E 
A - D - E
A - C - E
A - B - E
A - C - D - E
A - B - D - E
A - B - C - E
A - B - C - D - E

I think that's all.

Could someone help me with the logic to help me work this problem out?

'even better ' - what have you done other than paste your question on here? — Dave Richardson, Nov 01 '12 at 14:23
If we post a solution, there's nothing for you to work out any more... — home, Nov 01 '12 at 14:23
No this is not homework and no I am not asking people to paste the solution, I am asking for assistance from people to help me logically solve this problem. I can write the java, I am just not sure how to logically work this out! — eisenhorn, Nov 01 '12 at 14:28
@user1791562 `or even better post a java solution` actually, you are asking people to paste the solution. ;) — brimborium, Nov 01 '12 at 14:29
If you want to optimize your chance to get good answers, you should show us the effort you have already put into the question. (like some code that you already have written or thoughts about data structure or algorithm.) — brimborium, Nov 01 '12 at 14:30

score 3 · Answer 1 · answered Nov 01 '12 at 14:35

First, think about how you will represent a single "hop": Each node will need a list of its adjacent nodes. Start by building these nodes.

You will also need a way to look up a node from the pool of nodes (by it's name?). Perhaps put them in a Map?

A brute-force algorithm would be to start with the requested node and follow all hops recursively, watching for loops, until you get to the requested end, passing a List -- using it as a push-down stack, to record the path. Each time you reach the requested end, save the contents of the list to a Path collection. If you hit a dead end (no links go to the requested end), back up in your recursion and move on.

Depending on your need for speed, your could expand your data structure to hold some pre-calculated paths.

Try to work that out in pseudo code and then Java.

score 2 · Answer 2 · edited May 23 '17 at 10:29

Your problem is better stated as: "For a given directed graph, list all possible paths that can be taken from a certain node to another node." See Graph Algorithm To Find All Connections Between Two Arbitrary Vertices

You could solve it with recursion:

Paths(NodeSequence start, Node finish, ListOfNodeSequences result) takes a blank list of node sequences as the third argument, and for each Node n that can be reached via one hop from start adds start + n to result if n is finish, and otherwise calls Paths with start + n as the first parameter.

Recursion may not necessarily be the most resource efficient way of solving this problem, but it's not a lot of work to code. The above result assumes you will initialize an empty result variable, which will be modified by the recursive function instead of being returned, so it's a bit weird, but the version I gave should take the least effort.

Incomplete solution (omits irrelevant implementation details):

public class Node {
    public String name;

    public boolean Equals(Node other) {
        throw new NotImplementedException();
    }
};

public class NodeSequence {
    private ArrayList<Node> nodes;

    public NodeSequence() {
        nodes = new ArrayList<Node>();
    }

    public NodeSequence Plus(Node n) {
        // Returns this NodeSequence with n appended to the end
        throw new NotImplementedException();
    }

    public Node Last() {
        throw new NotImplementedException();
    }
}

public void paths(NodeSequence start, Node finish, ArrayList<NodeSequence> results) {
    Node startNode = NodeSequence.Last();

    ArrayList<Node> nextStops;
    // Populate nextStops with every node that is directly after startNode

    // Recursive block
    for (Node n : nextStops) {
        if (n.Equals(finish)) 
            results.Add(start.Plus(n));
        else 
            Paths(start.Plus(n), finish, results);
    }
}

ArrayList<NodeSequence> findAllPaths(Node start, Node finish) {
    ArrayList<NodeSequence> allPaths = new ArrayList<NodeSequence>();

    // This line will take a while
    paths(start, finish, allPaths);

    return allPaths;
}

findAllPaths will give you the result.

Yogendra Singh · Answer 3 · 2012-11-01T15:06:51.047

I think the logic could be as below:

Maintain a list/array of characters e.g.

  char[] chars = {'A','B', 'C', 'D','E'};

Create 3 index variables, begin = 0, end = chars.length-1, index = 0;

Implement 2 nested for loops for each range printing,

  for begin =0 to end
      collect chars[beign]
      for indx end -begin to end
          collect chars[indx]

I think this would do it.

One sample logic could be as below:

 char[] chars = {'A','B', 'C', 'D','E'};
 List<Character> charList = new ArrayList<Character>();
 for (int begin=0; begin <chars.length; begin++){
   for (int index=begin; index <chars.length; index++){
     charList.add(chars[begin]);
     for (int indx1=chars.length-index; indx1 <chars.length-begin; indx1++){
        charList.add(chars[indx1+begin]);
     }
     System.out.println(charList);
     charList.clear();
   }
 }

Which should print results as:

[A]
[A, E]
[A, D, E]
[A, C, D, E]
[A, B, C, D, E]
[B]
[B, E]
[B, D, E]
[B, C, D, E]
[C]
[C, E]
[C, D, E]
[D]
[D, E]
[E]

Logic for finding all paths from one graph node to another

3 Answers3