All Non-Cyclic Paths In A Directed Graph Between Source & Destination Using Memoization

Question

I'm working on a research problem which involves storing all non-cyclic paths from a source vertex to a destination vertex in a general directed graph (may or may not be cyclic). The input consists of a directed graph, a source vertex and a destination vertex.

I've written a method in Java to perform this action. I've used the concept of memoization, by storing all non-cyclic paths from a source vertex to the destination, so that if I ever reach the same vertex during my method's recursive calls, I can just use the stored 'Routes', and save lots of computation.

I'm going wrong somewhere in the recursive step of my algorithm (I think), and I've spent some time thinking what could be the mistake, but I'm unable to find that out. I'd appreciate any help in this regard. Thanks in advance!

Oh, and if anyone wants any clarification regarding the purpose of any of the blocks of code, please comment!

I've basically used DFS in my approach to solve the problem. My code is as follows:

//'allEdges' is an ArrayList of all edges of the input graph

/*'Route' is a class that stores the 'src', 'dest' and 'edgeIndices' of 'allEdges'
that comprise the route from 'src' to 'dest'*/

/*'hashMap' is a HashMap<Integer, ArrayList<Route>>. It maps an integer source vertex
 to a list of all routes from that vertex to the actual destination vertex to which
the method is initialized from main()*/


static void findPaths(int source, int dest)
{
    int i,j,k;
    for(i=0;i<allEdges.size();i++)
    {
        if(allEdges.get(i).getStartNode()==source)
        {
            ArrayList stack = new ArrayList();
            stack.add(i);   //pushing edge index to stack
            if(allEdges.get(i).getEndNode()==dest)
            {
                ArrayList<Route> list1 = hashMap.get(source);   

                if(list1!=null)
                {
                    list1.add(new Route(source,dest,stack));
                    hashMap.put(source, list1);
                }
                else
                {
                    ArrayList<Route> list2 = new ArrayList();
                    list2.add(new Route(source,dest,stack));
                    hashMap.put(source, list2);
                }

            }
            else
            {
                int nextNode = allEdges.get(i).getEndNode();
                ArrayList<Route> temp = hashMap.get(nextNode);
                if(temp!=null)
                {
    for1:           for(j=0;j<temp.size();j++)
                    {
                        ArrayList path = temp.get(j).getEdgeIndices();

                        for(k=0;k<path.size();k++)
                        {
                            int edgeIndex = (int)path.get(k);
                            Edge ed = allEdges.get(edgeIndex);
                            if(ed.getStartNode()==source)
                            {
                                continue for1;
                            }
                        }

                        stack.addAll(path);

                        ArrayList<Route> list3 = hashMap.get(source);
                        if(list3!=null)
                        {
                            list3.add(new Route(source,dest,stack));
                            hashMap.put(source,list3);
                        }
                        else
                        {
                            ArrayList<Route> list4 = new ArrayList();
                            list4.add(new Route(source,dest,stack));
                            hashMap.put(source,list4);
                        }


                        stack.removeAll(path);
                    }
                }
                else
                {
                    findPaths(nextNode, dest);
                }
            }    
        } 
    }

}

EDIT 1:

For the following input graph:

Number of vertices = 5

Source Vertex = 1

Destination Vertex = 5

Directed edges: 1 -> 2, 1 -> 3, 1 -> 4, 2 -> 4, 4 -> 5

All the paths from 1 to 5 are:

1 -> 2 -> 4 -> 5

1 -> 4 -> 5

The output 'hashMap' on calling findPaths(1, 5) is as follows:

For vertex '1', the 'hashMap' has just one 'Route' stored, and that route has only one 'Edge': 1 -> 4

For vertex '2', the 'hashMap' has no 'Route's stored, i.e., it maps to 'null'.

For vertex '3', the 'hashMap' has no 'Route's stored, i.e., it maps to 'null'.

For vertex '4', the 'hashMap' has just one 'Route' stored, and that route has only one 'Edge': 4 -> 5

For vertex '5', the 'hashMap' has no 'Route's stored, i.e., it maps to 'null'.

Clearly, the 'hashMap' is storing wrong 'Route's.

EDIT 2:

Ok, so after making the modifications that Brainstorm suggested, the program works for acyclic graphs. I'm looking to make it work for cyclic graphs as well. I tried out a couple of inputs and interestingly, I noted that with the modifications suggested by Brainstorm, the program works for some cyclic graphs if the cyclic edges belong to the end of the ArrayList 'allEdges'. In other words, the order in which the edges appear in the input makes a difference, which isn't ideal.

Now, I've realized that I forgot to label the nodes which are currently 'in process' in the recursion, and hence the code got stuck in infinite recursive call sequences. So what I did was to create a global stack inProcess, which would contain the nodes which are acting as source in one of the recursive calls, so that the same node is not traversed again during the processing of those recursive calls. But I still don't get the right output. Here's the modification I did:

INITIAL CODE BLOCK:

if(temp==null)
{
   findPaths(nextNode,dest);
   temp = hashMap.get(nextNode);
}

NOW MODIFIED THE ABOVE BLOCK TO THE FOLLOWING:

if(temp==null)
{

      if(!inProcess.contains(nextNode))
      {
           inProcess.add(nextNode);
           findPaths(nextNode,dest);
           inProcess.remove(inProcess.indexOf(nextNode));
           temp = hashMap.get(nextNode);
      }
      else
      {
           continue main_for1;  //main_for1 labels the very first for() loop of this method
      }


}

I feel that this modification is insufficient in some way. Can anyone tell me what's wrong and correct me?

Anyone? At the very least, can someone suggest better tags to get faster replies? — Ricky
– Ricky, Commented Jul 8, 2013 at 16:34
What does it do that indicates to you that it's not working as you want it to? It would be good to have an example of input and expected vs. actual output. — Brainstorm
– Brainstorm, Commented Jul 8, 2013 at 17:12

Brainstorm · Accepted Answer · 2013-07-08 19:09:03Z

1

I think I've fixed it! I found two problems. First: Just before the recursive call (before the if-else) we have the code:

int nextNode = allEdges.get(i).getEndNode();
ArrayList<Route> temp = hashMap.get(nextNode);

Then if temp is null it jumps to the recursive call but after the recursive call hashMap.get(nextNode) could return something non-null. So that you'd want to execute the part after the if statement. I fixed it like this:

      int nextNode = currentEdge.getEndNode();
      ArrayList<Route> temp = hashMap.get(nextNode);
      if(temp==null) {
           findPaths(nextNode, dest);
           temp = hashMap.get(nextNode);
      }

      if(temp!=null) {
 for1:     for(j=0;j<temp.size();j++) {
       //...

The second problem I found was here:

stack.addAll(path);

ArrayList<Route> list3 = hashMap.get(source);
if(list3!=null) {
    list3.add(new Route(source,dest,stack));
    hashMap.put(source,list3);
} else {
    ArrayList<Route> list4 = new ArrayList();
    list4.add(new Route(source,dest,stack));
    hashMap.put(source,list4);
}

stack.removeAll(path);

Notice that stack is added before the insertion of a route into the hashmap and removed from after. That same stack is referenced by the route object created in the if-else statements so that changes what is saved there. What you want is to make a copy like this:

ArrayList<Route> list3 = hashMap.get(source);
ArrayList<Integer> copy = new ArrayList<Integer>(stack);
if(list3!=null) {
    list3.add(new Route(source, dest,copy));
    hashMap.put(source,list3);
} else {
    ArrayList<Route> list4 = new ArrayList<Route>();
    list4.add(new Route(source, dest, copy));
    hashMap.put(source,list4);
}
stack.removeAll(path);

The entire function is listed below. Sorry for messing up the formatting.

static void findPaths(int source, int dest) {
    int i, j, k;
    for (i = 0; i < allEdges.size(); i++) {
        Edge currentEdge = allEdges.get(i);
        if (currentEdge.getStartNode() == source) {
            ArrayList<Integer> stack = new ArrayList<Integer>();
            stack.add(i); // pushing edge index to stack
            if (currentEdge.getEndNode() == dest) {
                ArrayList<Route> list1 = hashMap.get(source);

                if (list1 != null) {
                    list1.add(new Route(source, dest, stack));
                } else {
                    ArrayList<Route> list2 = new ArrayList<Route>();
                    list2.add(new Route(source, dest, stack));
                    hashMap.put(source, list2);
                }

            } else {
                int nextNode = currentEdge.getEndNode();
                ArrayList<Route> temp = hashMap.get(nextNode);
                if (temp == null) {
                    findPaths(nextNode, dest);
                    temp = hashMap.get(nextNode);
                }

                if (temp != null) {
                    for1: for (j = 0; j < temp.size(); j++) {
                        ArrayList<Integer> path = temp.get(j)
                                .getEdgeIndices();

                        for (k = 0; k < path.size(); k++) {
                            int edgeIndex = (int) path.get(k);
                            Edge ed = allEdges.get(edgeIndex);
                            if (ed.getStartNode() == source) {
                                continue for1;
                            }
                        }

                        stack.addAll(path);
                        ArrayList<Integer> copy = new ArrayList<Integer>(stack);
                        ArrayList<Route> list3 = hashMap.get(source);
                        if (list3 != null) {
                            list3.add(new Route(source, dest,copy));
                        } else {
                            ArrayList<Route> list4 = new ArrayList<Route>();
                            list4.add(new Route(source, dest, copy));
                            hashMap.put(source, list4);
                        }
                        stack.removeAll(path);
                    }
                }
            }
        }
    }
}

answered Jul 8, 2013 at 19:09

Brainstorm

1,2008 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Ricky Over a year ago

I just tested your function with the same input mentioned. It is now giving the right output, but give me some time to read through your answer.

Ricky Over a year ago

Indeed, the method doesn't work for cyclic graphs. java.lang.StackOverflowError on running the program.

Brainstorm Over a year ago

Ok. Maybe I've misunderstood what the output is supposed to be. I get this output, where a->b is an edge from node a to node b: 1: (1->2,2->4,4->5), (1->4,4->5) 2: (2->4,4->5) 4: (4->5)

Ricky Over a year ago

The output that you've just written in the above comment is right, but that's for an acyclic graph as input. I changed the input graph and made it cyclic. For the cyclic one, there's an infinite number of java.lang.StackOverflowError popping up on the screen.

Ricky Over a year ago

Try the following graph: 1->2, 1->3, 2->4, 3->4, 2->3, 3->2

|

Eric Kim · Accepted Answer · 2013-07-08 17:18:34Z

0

I think your problem might be the first line of the main else statement:

int nextNode = allEdges.get(i).getEndNode();

What exactly does this do? It seems to me that it would return null when you are going through the paths the first time, when you haven't figure out the end node of i.

answered Jul 8, 2013 at 17:18

Eric Kim

415 bronze badges

1 Comment

Ricky Over a year ago

Not really. allEdges is just the ArrayList storing all the edges, which are objects of a class named Edge that I created. I've tested whether it contains all the edges by printing, and they're all there. And the index i runs from 0 to allEdges.size() - 1. So, getEndNode() will always return some value. Never a null.

Collectives™ on Stack Overflow

All Non-Cyclic Paths In A Directed Graph Between Source & Destination Using Memoization

2 Answers 2

6 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related