Breadth first search with java

[Ant_Magma]

Magma, i need more detail to understand what your asking. What are you trying to implement with an ArrayList??

I'm trying to implement the queue using ArrayList..

BFS's are implemented using Queues. ArrayLists can be used as queues. But actually on second inspection, LinkedLists are probably better.

But with queues, wont i have another problem, pointers/markers to worry?

[Ant_Magma]

Or to make things easier & prevent any confusion, can u guys explain the pseudo code assuming a sample of A,B,C,D with A as the starting node.

With a sample of 4 cities and A as starting node, i would get 3! solutions..
1. ABCD
2. ABDC
3. ACBD
4. ACDB
5. ADBC
6. ADCB

[evlich]

Java has a built in class called LinkedList which encapsulates all the funcitonality of LinkedLists and hides all of the details from you. So you can just make the calls to addFirst() removeFirst() and isEmpty() and the particular way that those methods are implemented is not necessary.

So now for the example. Lets just do an example of 3 cities A, B, and C. The forth city will just be a bit longer.

1. Enqueue "A"
2. Check to see if the queue is empty
3. Remove the first element of the queue (in this case "A")
4. Since "A" is not a completed path, enqueue "AB" and "AC" (all the cities not in the path appended to the end of the path.
5. Check to see if the queue is empty
6. Remove the first element of the queue (in this case "AB")
7. Since "AB" is not a completed path, enqueue "ABC" ("C" is the only city not already in the path)
8. Check to see if the queue is empty
9. Remove the first element of the queue (in this case "AC")
10. Since "AC" is not a completed path, enque "ACB" ("B" is the only city not already in the path)
11. Check to see if the queue is empty
12. Remove the first element from the queue (in this case "ABC")
13. Since "ABC" is a completed path, find its length by summing the distances A-B, B-C, and C-A.
14. Check the path distance against the shortest path (since there is none, we say this is a better solution, so we set the shortest path equal to "ABC", and the shortest path length equal to the length of the path)
15. Check to see if the queue is empty
16. Remove the first element from the queue (in this case "ACB")
17. Since "ABC" is a completed path, find its length by summing the distances A-C, C-B, and B-A.
18. Check the path distance against the shortest path. If this path is shorter, update the shortest field, otherwise don't do anything.
18. Check to see if the queue is empty
19. Since the queue is empty we are done and the optimal path is stored as the shortest path.

Note that the pseudo code I gave you implments this with a while loop. The steps that check to see if the queue is empty (2,5,8,11,15,18) are simply the loop condition.

Hope this helps.

[Ant_Magma]

Sorry for the late reply evlich, i've been held up with another assignment

7. Since "AB" is not a completed path, enqueue "ABC" ("C" is the only city not already in the path)

Just to confirm. At line 7, the header pointer will be pointing at AC, and ABC will be enqueued behind it right?

Question:
1. How does the loop determine whether or not the element popped from the queue is a complete path?
2. How does the loop determine whether or not has a city been already included in the path and prevent errors like ABB or ACC?
3. At the else part of the while loop, it compares the cities to see whether or not are they already part of the path. Where does it get the complete list of cities?
4. The paths ABC & ACB, are they stored as a single string in the linked list? or as separate elements? If a single string, then wont trying to add a C to a AB string be a problem?
5. The linkedlist provided in java does not have the method, isEmpty(), so how do i implement the while loop condition?

[Ant_Magma]

I'm currently using the java book Absolute Java by Walter Savitch. In his linkedlist chapter, he writes about how to create our own linkedlist class.

In my case, i want to follow customwoodtek's suggestion and use the linkedlist provided by java, but it is not state in the book how..so i assume:

	LinkedList list=new LinkedList();
	list.add("A");
	System.out.println("The first element is: " +list.getFirst());

Is it correct? Well, i've tried compiling and it works ok, however this msg appears after i compile it in msdos

Note: Test.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

What does it mean?

[evlich]

Question Answers:
1) Completed paths are always the length of the number of cities.
2) We prevent duplicates by, before appending a city to the end, making sure that the character representing that city is not alreay in the string.
3) The string that you are looking at is the complete path, i.e. AB is the complete path (with one city left to go) where A and B have been visited.
4) Each element in the linked list represents a unique path. So ABC and ACB would be stored in different elements in the linked list.
5) The LinkedList class does have an isEmpty() method, (it is inherited from AbstractCollection).

You get that operation because you are not using the generic version of LinkedList and are using java 5.0. Since the only thing that you will be storing in the LinkedList is strings, you can change your code to the following:

LinkedList<String> queue = new LinkedList<String>();

When you do queue.add(), the value passed will be checked to make sure it is a String and when you do queue.getFirst() the value will be cast to a String. The warning you don't really have to worry about and generics can get a little complex, especially if you are just starting out, so you should probably ignore the warning.

[Ant_Magma]

The following is my code based on the pseudo code. When i tried to run it, an error msg "Exception in thread "main" java.lang.OutOfMemoryError: Java heap space" pops up..what's wrong?

import java.util.LinkedList;

public class Test{
    public static void main(String[] args){
	String cities="ABC";
	LinkedList<String> list=new LinkedList<String>();

	list.add("A");

	while(!list.isEmpty()){
		String current=list.removeFirst();
		if(current.length()==3){
			calculate(current);
		}else{
			for(int i=0;i<cities.length();i++){
				for(int j=0;j<current.length();j++){
					if(current.charAt(j)!=cities.charAt(i))
						current=current + cities.charAt(i);
						list.addLast(current);
				}
			}
		}

	}

	}
	public static void calculate(String a){}

}

[evlich]

import java.util.LinkedList;

public class Test{
    public static void main(String[] args){
	String cities="ABC";
	LinkedList<String> list=new LinkedList<String>();

	list.add("A");

	while(!list.isEmpty()){
		String current=list.removeFirst();
		if(current.length()==3){
			calculate(current);
		}else{
			for(int i=0;i<cities.length();i++){
				for(int j=0;j<current.length();j++){
					if(current.charAt(j)!=cities.charAt(i)) {
						list.addLast(current+cities.charAt(i));
                                        }
				}
			}
		}

	}

	}
	public static void calculate(String a){}

}

You don't ever want to modify the value of current inside the loop after the first place, so I removed the current = currrent + ... You can simply do that inline like shown. Also, you are doing a lot more adding then you should be (which is why you are maxxing out memory). Your implementation adds the city each time it finds a character that it not the search character as opposed to once if it is not in the string. By the way, string searching is built into java. The inside for-loop in the else clause can be rewritten as:

if( current.indexOf(cities.charAt(i)) != -1 ) {
  list.addLast(current+cities.charAt(i));
}

Hope this helps.

[Ant_Magma]

Your implementation adds the city each time it finds a character that it not the search character as opposed to once if it is not in the string.

Can u explain?

And i don't understand the difference between

list.addLast(current+cities.charAt(i));

and

{
current=current + cities.charAt(i);
list.addLast(current);
}

You are doing alot of adding than you should be...

Please explain...

[Ant_Magma]

I'VE DONE IT!!!

import java.util.LinkedList;
import java.util.ArrayList;

public class Test3{
    public static void main(String[] args){
	String cities="ABCD";
	ArrayList<String> solution=new ArrayList<String>();
	LinkedList<String> list=new LinkedList<String>();

	list.add("A");

	while(!list.isEmpty()){
		//System.out.println("First element to be popped: " +list.getFirst());
		String current=list.removeFirst();
		if(current.length()==cities.length()){
			//calculate(current);
			solution.add(current);
		}else{
			for(int i=0;i<cities.length();i++){
				if(current.indexOf(cities.charAt(i))==-1){
					list.addLast(current+cities.charAt(i));
				}
			}
		}

	}


	for(int i=0;i<solution.size();i++){
		System.out.println("The possible paths are:");
		System.out.println(i+ ": " +solution.get(i));
	}

	}
	public static void calculate(String a){}

}

There is 1 last part. I wish to write a method calculate() which takes in the String path, and calculates the distance of the path from a distance array matrix. However d problem is with 10 cities i would have 9! possible solutions. So i wish to implement the calculate method so that the solution array would have a size of 10. And whenever a new path is found it'll compare itself with d top10 paths in the solutions array. If it's shorter than any of d paths in d top10, it'll update d solution array with d new path.

How should i start?

[Ant_Magma]

The distance table is like this:

    String[] legends = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J"};
    double[][] distance = {{0.0},
                           {1.3, 0.0},  
                           {2.5, 5.8, 0.0},
                           {3.6, 4.3, 6.3, 0.0},
                           {4.2, 8.9, 4.5, 7.1, 0.0},
                           {5.9, 6.7, 8.1, 8.6, 7.6, 0.0},
                           {6.7, 5.4, 7.8, 6.4, 2.4, 4.8, 0.0},
                           {7.1, 2.6, 1.6, 2.1, 3.6, 6.3, 7.1, 0.0},
                           {8.4, 7.1, 3.8, 7.6, 1.2, 7.2, 5.5, 2.6, 0.0},
                           {9.8, 8.6, 1.0, 2.6, 4.5, 1.8, 4.6, 7.5, 9.9, 0.0},
                          };

And the getDistance method defined in the question is like this"

  public double getDistance(int from, int to){
    if(from > to)
      return length[from][to];  
    else
      return length[to][from];
  }

Since my paths are in strings like "ABCD" or "ACBD" etc and the getDistance method operates based on the int of the array. How do i equat the proper numbers to the corresponding cities? ie: A=0 B=1 C=2.....J=9

[d_vinci]

can anyone tell me how to present this BFS algorithm in an applet? for example, a map, just like google map. Issit possible to implement this in an applet and visualize the computed shortest path? is yes, how?