For example, on the graph
represented by the file:
a b c b d e c b e d c f e f fIt returns [a,b,d,c,e,f] as the path from node a to f even though there are three paths from a to f consisting of three rather than five edges: [a,b,d,f], [a,b,e,f] and [a,c,e,f].
The depth-first with backtracking algorithm considered each of the
branches of the search tree in turn until it found one in which
search of it returned a solution. A naïve approach would be
to search each of the branches to find the best solution from any
of them, and return that. Here is the code to do that, given with its
complete program:
import java.io.*;
import java.util.*;
class UseGraphs5
{
// Path search, depth-first, search all paths for shortest
private static int count;
public static void main(String[] args)
throws IOException
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedReader file;
System.out.print("Enter name of file for graph: ");
file = new BufferedReader(new FileReader(in.readLine().trim()));
Graph1 graph = new Graph1(file);
file.close();
System.out.print("Enter start node: ");
String start = in.readLine().trim();
System.out.print("Enter finish node: ");
String finish = in.readLine().trim();
count=0;
String p = path(start,finish,graph);
System.out.println("Path (after considering "+count+" paths) is: ");
System.out.println(p);
}
public static String path(String start,String finish,Graph1 graph)
{
Cell p = findPath(finish,graph,new Cell(start,null));
if(p==null)
return "No path possible";
else
{
String str = p.first;
p = p.next;
while(p!=null)
{
str=p.first+","+str;
p=p.next;
}
return "["+str+"]";
}
}
private static Cell findPath(String finish,Graph1 graph,Cell done)
{
count++;
if(done.first.equals(finish))
return done;
else
{
Enumeration enum = graph.getLinks(done.first);
Cell bestPath=null;
int bestLength=0;
while(enum.hasMoreElements())
{
String next = (String)enum.nextElement();
if(!member(next,done))
{
Cell p=findPath(finish,graph,new Cell(next,done));
if(p!=null)
if(bestPath==null)
{
bestPath=p;
bestLength=lengthTo(done,p);
}
else
{
int l=lengthTo(done,p);
if(l<bestLength)
{
bestLength=l;
bestPath=p;
}
}
}
}
return bestPath;
}
}
private static int lengthTo(Cell base,Cell p)
{
int count=0;
for(Cell ptr=p; ptr!=base; ptr=ptr.next, count++);
return count;
}
private static boolean member(String node,Cell list)
{
Cell ptr;
for(ptr=list; ptr!=null&&!ptr.first.equals(node); ptr=ptr.next);
return ptr!=null;
}
private static class Cell
{
String first;
Cell next;
Cell(String f,Cell n)
{
first=f;
next=n;
}
}
}
This is not a very efficient way of finding the shortest route
between two nodes. It always searches the whole search tree. Consider
the graph we used previously which had
search tree for a path from node a:
a
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
ab af
/|\ / \
/ | \ / \
/ | \ | |
/ | \ | |
/ | \ | |
/ | \ | |
abc abd abe afe afh
/ | \ \ | |
/ | \ \ | |
/ | \ \ | |
abdc abdf abdg abeg afeg afhe
/ \ |
/ \ |
/ \ |
abdfe abdfh afheg
| |
| |
| |
abdfeg abdfhe
|
|
|
abdfheg
Using this program will cause all 20 paths in the tree to be searched in
the search for a path from a to g.
The only paths that are not searched are those in a subtree whose root
value is a solution path. For example, in the search for a path from
a to b, the paths below
the path [a,b] are not considered, but all
those below [a,f] are.
The whole program was shown to indicate how a count of the number of
paths searched is obtained using a static variable.
The variable, called count, is declared outside any method,
but as it is static there is just one variable which can be accessed by all
methods in the class. It would not make sense to have a variable declared
outside all the methods but non-static in class UseGraphs5
above, since this would be
declaring a field in UseGraphs5 objects, but
UseGraphs5 is a class which gives some static methods
(including a main method enabling it to be used to
initiate a program) and isn't intended to describe a type of object.
Each time the method findPath is called,
count is increased by 1, so at the end of the program it
gives a count of the number of times findPath was called.
This is the nearest Java comes to a global variable, that is a variable which is shared by a whole program. The same warning that is given about global variables in other languages also applies to static variables in Java classes. Because they are a way that method calls can interact without using argument passing and result returning, they can cause confusing interaction, particularly if the global variable is changed in some obscure part of the code. However, usage in carefully defined circumstances such as this may be preferable to more complicated code that would be required to achieve the same effect otherwise.
Note that in comparing paths, this program does not measure complete
path lengths at each call of findPath but only the length
of paths back to the cell they share in common. This is what is done
in lengthTo. Again, this could be implemented iteratively
as given, or recursively as:
private static int lengthTo(Cell base,Cell p)
{
if(p==base)
return 0;
else
return 1+lengthTo(base,p.next);
}
This is still not very efficient, as the length of paths will be measured
at each level of the search tree.
findPath which did not represent a leaf in the search tree
kept its own record of the best path found so far amongst its
descendants. Thus bestPath and bestLength
are local variables and there is a separate bestPath and
bestLength variable for every call of findPath.
But we could have just one bestPath and bestLength
variable, shared by all findPath calls, and updated
whenever any of these calls represents a leaf in the search tree which
represents a shorter path from the start to the finish node than any
found previously in the search of the tree. We have already seen how
a variable which is global to all method calls in a class can be obtained
with count in the previous example. We use that same idea of
a static variable declared outside any method to give a global
bestPath and bestLength variable in the code
below. In this code, findPath no longer works by returning
the shortest path in the branch of the tree it represents, but by
altering the value of the global bestPath and
bestLength. Here is the complete code for the program:
import java.io.*;
import java.util.*;
class UseGraphs7
{
// Path search, depth-first, search all paths for shortest
// Keep global best path so far
// Cut off search of longer paths
private static int count,bestLength;
private static Cell bestPath;
public static void main(String[] args)
throws IOException
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedReader file;
System.out.print("Enter name of file for graph: ");
file = new BufferedReader(new FileReader(in.readLine().trim()));
Graph1 graph = new Graph1(file);
file.close();
System.out.print("Enter start node: ");
String start = in.readLine().trim();
System.out.print("Enter finish node: ");
String finish = in.readLine().trim();
count=0;
String p = path(start,finish,graph);
System.out.println("Path (after considering "+count+" paths) is: ");
System.out.println(p);
}
public static String path(String start,String finish,Graph1 graph)
{
bestPath=null;
findPath(finish,graph,new Cell(start,null),0);
if(bestPath==null)
return "No path possible";
else
{
String str = bestPath.first;
bestPath = bestPath.next;
while(bestPath!=null)
{
str=bestPath.first+","+str;
bestPath=bestPath.next;
}
return "["+str+"]";
}
}
private static void findPath(String finish,Graph1 graph,Cell done,int length)
{
count++;
if(done.first.equals(finish))
checkBest(done,length);
else if(bestPath==null||length==bestLength-1)
{
Enumeration enum = graph.getLinks(done.first);
Cell best=null;
int bestlength=0;
while(enum.hasMoreElements())
{
String next = (String)enum.nextElement();
if(!member(next,done))
findPath(finish,graph,new Cell(next,done),length+1);
}
}
}
private static void checkBest(Cell p,int length)
{
int count=0;
if(bestPath==null||length<bestLength)
{
bestPath=p;
bestLength=length;
}
}
private static boolean member(String node,Cell list)
{
Cell ptr;
for(ptr=list; ptr!=null&&!ptr.first.equals(node); ptr=ptr.next);
return ptr!=null;
}
private static class Cell
{
String first;
Cell next;
Cell(String f,Cell n)
{
first=f;
next=n;
}
}
}
Note also that the length of a path, instead of being calculated at the
time of comparing it with the best path found so far, is given by a
parameter called length in the findPath method,
which gives the depth in the search tree that any partiuclar call of
findPath represents.
Another aspect of this code is that it treats the length of any path found as an upper bound on the length of the shortest path. For example, if we have found a path of length 5 from the given start to finish node, we know it is pointless to search branches of the tree representing paths of length 5 and their descendants as they cannot possibly give us a shorter path than the one we already have. However it is worthwhile searching branches of the tree representing paths shorter than 5 as we may find a shorter one. This is known as branch and bound search.
If we consider the search tree above,
searching this tree left-to-right for a path from a
to g gives [a,b,d,f,e,g] as
the first path found. As this is of length 5, the path for
[a,b,d,f,h,e] and its descendants are not
considered as they cannot possibly give us a path with a shorter length than
5. Later in the search, the path [a,b,d,g] is
found, so bestPath is changed from referring to
[a,b,d,f,e,g] to referring to
[a,b,d,g], and bestLength
is changed from 5 to 3. After this, no further path of length 3 or
greater is considered. So a path which can be guaranteed to be of the
shortest length of any possible path from a
to g in the graph is returned after considering
only 14 paths in the search tree rather than the full 20.
Breadth-first search
The length of a path between two nodes is equal to the depth of that
path in the search tree. So another way of finding a solution which we can
guarantee is a shortest path is to search the tree breadth-first. This
means we consider all paths of a particular length before considering any
paths of a greater length. We have
already seen how breadth first
traversal of a tree can be obtained through the use of a queue. We can use
the same technique to give breadth first traversal of the search
tree for finding the shortest path between two nodes in a graph.
The program for this is give below, with the type Queue
being as given in the class Queue
previously.
import java.io.*;
import java.util.*;
class UseGraphs8
{
// Path search, breadth-first, using queue
// With cycle test
private static int count;
public static void main(String[] args)
throws IOException
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedReader file;
System.out.print("Enter name of file for graph: ");
file = new BufferedReader(new FileReader(in.readLine().trim()));
Graph1 graph = new Graph1(file);
file.close();
System.out.print("Enter start node: ");
String start = in.readLine().trim();
System.out.print("Enter finish node: ");
String finish = in.readLine().trim();
count = 0;
String p = path(start,finish,graph);
System.out.println("Path (after considering "+count+" paths) is: ");
System.out.println(p);
}
public static String path(String start,String finish,Graph1 graph)
{
Cell p = findPath(start,finish,graph);
if(p==null)
return "No path possible";
else
{
String str = p.first;
p = p.next;
while(p!=null)
{
str=p.first+","+str;
p=p.next;
}
return "["+str+"]";
}
}
private static Cell findPath(String start,String finish,Graph1 graph)
{
Queue q = new Queue();
q.join(new Cell(start,null));
while(!q.isEmpty())
{
Cell done = (Cell)q.first();
count++;
if(done.first.equals(finish))
return done;
else
{
q.leave();
Enumeration enum = graph.getLinks(done.first);
while(enum.hasMoreElements())
{
String next = (String)enum.nextElement();
if(!member(next,done))
q.join(new Cell(next,done));
}
}
}
return null;
}
private static boolean member(String node,Cell list)
{
Cell ptr;
for(ptr=list; ptr!=null&&!ptr.first.equals(node); ptr=ptr.next);
return ptr!=null;
}
private static class Cell
{
String first;
Cell next;
Cell(String f,Cell n)
{
first=f;
next=n;
}
}
}
The loop in findPath means we have a queue of paths
starting with the initial node given to the search. Each time round the
loop takes a path from this queue and adds to the queue all the
paths obtained by adding a node linked with an edge to the last node
in the path taken off. The test condition in the loop is when the
queue is empty, but this will only happen if the entire tree has been
searched and no solution found. The return statement in
the loop, executed when the path taken from the front of the queue
ends in the final node given to the search causes the loop and the
while findPath method to be terminated and this path given
as its return value.
The code here has the check to ensure we have a path with no cycles, but if we do have search trees with infinite branches, breadth-first search will not get stuck in an infinite branch before finding a solution to its right in the tree. Thus breadth-first search can be useful where it is otherwise not so easy to eliminate infinite branches from a search tree.
In the above example, breadth-first search will return the solution [a,b,d,g] after searching only 11 paths.
It is also possible to obtain depth-first search by using a stack
instead of a queue to store paths representing partial solutions.
Again, this is using the technique we saw
before, which elimiated recursion by using a stack. Only
findPath in the above
program needs to be changed, to:
private static Cell findPath(String start,String finish,Graph1 graph)
{
Stack st = new Stack();
st.push(new Cell(start,null));
while(!st.isEmpty())
{
Cell done = (Cell)st.top();
count++;
if(done.first.equals(finish))
return done;
else
{
st.pop();
Enumeration enum = graph.getLinks(done.first);
while(enum.hasMoreElements())
{
String next = (String)enum.nextElement();
if(!member(next,done))
st.push(new Cell(next,done));
}
}
}
return null;
}
However this code gives right-to-left rather than left-to-right
search of the search tree, so with the tree
above it will give
[a,f,h,e,g] as its solution for a
path from a to g.
The reason for this is that as a stack has the
LIFO
property, when the descendant paths are added to it, the one added last
(i.e. the rightmost descendant) is the first taken off.
private static Cell findPath(String start,String finish,Graph1 graph)
{
Stack st = new Stack();
st.push(new Cell(start,null));
while(!st.isEmpty())
{
Cell done = (Cell)st.top();
count++;
if(done.first.equals(finish))
return done;
else
{
st.pop();
Enumeration enum = graph.getLinks(done.first);
Stack st1 = new Stack();
while(enum.hasMoreElements())
{
String next = (String)enum.nextElement();
if(!member(next,done))
st1.push(new Cell(next,done));
}
while(!st1.isEmpty())
{
Cell c = (Cell)st1.top();
st1.pop();
st.push(c);
}
}
}
return null;
}
nextElement is
called on it, another paths is returned.
Here is code for a complete program which turns breadth-first search for a path in a graph into an enumeration:
import java.io.*;
import java.util.*;
class UseGraphs12
{
// Path search, breadth first, query for more answers
private static int count;
public static void main(String[] args)
throws IOException
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedReader file;
String reply = "y";
System.out.print("Enter name of file for graph: ");
file = new BufferedReader(new FileReader(in.readLine().trim()));
Graph1 graph = new Graph1(file);
file.close();
System.out.print("Enter start node: ");
String start = in.readLine().trim();
System.out.print("Enter finish node: ");
String finish = in.readLine().trim();
count = 0;
Enumeration enum = new Paths(start,finish,graph);
while(enum.hasMoreElements()&&reply.equals("y"))
{
String p = (String)enum.nextElement();
System.out.println("Path (after considering "+count+" paths) is: ");
System.out.println(p);
System.out.print("Continue (y/n) ? ");
reply = in.readLine().trim();
}
System.out.print("No (more) paths ");
System.out.println("(after considering "+count+" paths)");
}
public static class Paths implements Enumeration
{
String finish;
Graph1 graph;
Queue q;
Cell nextEl;
boolean progressed;
Paths(String start,String f,Graph1 g)
{
finish =f;
graph = g;
q = new Queue();
q.join(new Cell(start,null));
nextEl = null;
progressed=false;
}
public Object nextElement()
{
if(progressed)
progressed=false;
else
nextEl=progress();
return pathToString(nextEl);
}
public boolean hasMoreElements()
{
if(!progressed)
{
nextEl=progress();
progressed=true;
}
return (nextEl!=null);
}
public String pathToString(Cell p)
{
String str = p.first;
p = p.next;
while(p!=null)
{
str=p.first+","+str;
p=p.next;
}
return "["+str+"]";
}
private Cell progress()
{
while(!q.isEmpty())
{
Cell done = (Cell)q.first();
q.leave();
count++;
if(done.first.equals(finish))
return done;
else
{
Enumeration enum = graph.getLinks(done.first);
while(enum.hasMoreElements())
{
String next = (String)enum.nextElement();
if(!member(next,done))
q.join(new Cell(next,done));
}
}
}
return null;
}
private static boolean member(String node,Cell list)
{
Cell ptr;
for(ptr=list; ptr!=null&&!ptr.first.equals(node); ptr=ptr.next);
return ptr!=null;
}
private static class Cell
{
String first;
Cell next;
Cell(String f,Cell n)
{
first=f;
next=n;
}
}
}
}
As you can see, most of the code in the program is in the class
Paths which is nested in the class
UseGraphs12. The current state of the search is
represented by a queue which is referenced by the q field
of a Paths object, which is a subclass of Java's built-in
interface
Enumeration.
However, whereas above the
queue is a local variable in a static method findPath
and so disappears as soon as a solution is found and returned, here it
remains in existence as an attribute of the Paths object.
The method hasMoreElements takes paths from the front
of the queue and puts their immediate descendants onto the back of
the queue until either a solution is found, in which case it returns
true, or the queue becomes empy, in which case
falsenextEl because hasMoreElements
only says whether there are more solutions to be returned, it does not
return them.
The method nextElement returns the solution held in the
field nextEl. However it only does this if
hasMoreElements was called previously. If not, it must do what
the call of hasMoreElements would have done and loop through
taking paths off the queue and putting their descendants on it until it
comes across a new solution. The boolean field progressed
says whether hasMoreElements has been called to obtain
the next element, or not. The main work of processing the queue is
done in a private method called progress which progresses
the search to the point where the next solution is found.
As the enumeration returns solutions as string representations, it
needs its own private Cell class to build up linked
lists for itself to represent paths in the search tree.
An enumeration which gives the solutions as found by depth-first
traversal of the search tree rather than breadth-first can be obtained
by using a stack rather than a queue (the code here employs the
same trick as above to give
left-to-right rather than right-to-left depth-first traversal):
import java.io.*;
import java.util.*;
class UseGraphs13
{
// Path search, depth-first, query for more answers
private static int count;
public static void main(String[] args)
throws IOException
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedReader file;
String reply = "y";
System.out.print("Enter name of file for graph: ");
file = new BufferedReader(new FileReader(in.readLine().trim()));
Graph1 graph = new Graph1(file);
file.close();
System.out.print("Enter start node: ");
String start = in.readLine().trim();
System.out.print("Enter finish node: ");
String finish = in.readLine().trim();
count = 0;
Enumeration enum = new Paths(start,finish,graph);
while(enum.hasMoreElements()&&reply.equals("y"))
{
String p = (String)enum.nextElement();
System.out.println("Path (after considering "+count+" paths) is: ");
System.out.println(p);
System.out.print("Continue (y/n) ? ");
reply = in.readLine().trim();
}
System.out.print("No (more) paths ");
System.out.println("(after considering "+count+" paths)");
}
public static class Paths implements Enumeration
{
String finish;
Graph1 graph;
Stack st;
Cell nextEl;
boolean progressed;
Paths(String start,String f,Graph1 g)
{
finish =f;
graph = g;
st = new Stack();
st.push(new Cell(start,null));
nextEl = null;
progressed=false;
}
public Object nextElement()
{
if(progressed)
progressed=false;
else
nextEl=progress();
return pathToString(nextEl);
}
public boolean hasMoreElements()
{
if(!progressed)
{
nextEl=progress();
progressed=true;
}
return (nextEl!=null);
}
public String pathToString(Cell p)
{
String str = p.first;
p = p.next;
while(p!=null)
{
str=p.first+","+str;
p=p.next;
}
return "["+str+"]";
}
private Cell progress()
{
while(!st.isEmpty())
{
Cell done = (Cell)st.top();
st.pop();
count++;
if(done.first.equals(finish))
return done;
else
{
Enumeration enum = graph.getLinks(done.first);
Stack st1 = new Stack();
while(enum.hasMoreElements())
{
String next = (String)enum.nextElement();
if(!member(next,done))
st1.push(new Cell(next,done));
}
while(!st1.isEmpty())
{
Cell p = (Cell)st1.top();
st1.pop();
st.push(p);
}
}
}
return null;
}
private static boolean member(String node,Cell list)
{
Cell ptr;
for(ptr=list; ptr!=null&&!ptr.first.equals(node); ptr=ptr.next);
return ptr!=null;
}
private static class Cell
{
String first;
Cell next;
Cell(String f,Cell n)
{
first=f;
next=n;
}
}
}
}
The mode of search here - depth-first with backtracking, that returns
a solution but is then suspended so that it can be reawoken and made to
return further solutions if required - is fundamental to the logic
programming language
Prolog.
Last modified: 13th November 2001