Solved

Find indirect path

Posted on 2011-03-22
30
440 Views
Last Modified: 2012-05-11
Ok here is my issue. I read from a file the first line represents a column number and the first set of numbers on the left side represent a row number. The row and column numbers represent cities. What I need to do is find out if there is a direct link or path staring from a specific city and ending at a specific city which is entered by the user.

The other numbers:

0 = means the start and end city is the same city
-1= means there is a direct link between the two cities
1 = means there is a direct link between the two cities.


The file
=========================
            1      2      3      4      5

1      0
2      -1      0
3      1      -1      0
4      -1      1      -1      0
5      -1      -1      -1      1      0
=========================


The following code reads in the file and locates the start and end city that the user has entered and returns a 0 or -1 or 1. This code works. The problem is if it is found that there isn’t a direct path “-1” I need to find if there is an indirect path/link.

For Example the user enters that they are starting at City 2 and enters City 5 as the destination City. The following code finds there is a “-1” at the intersect of {2, 5} which mean there isn’t a direct path . However while scanning line(row) 5 there is a path/link(1) from 4 to 5. So now the code needs to check if there is a path/link(1) from 2 to 4, in this case there is. So now we know there is an indirect path/link to City 5 which is it starts at 2 to 4 to 5. What I am having difficulty with is putting the code together to find if there is a indirect path when the code finds a “-1”. Preferably I need to use a Queue or Stack.

private FileInputStream fstream;
private DataInputStream in;
private BufferedReader br;

public int isDirect(int start, int end) throws IOException
   {
        String strLine;
             int counter = 0,
                   result = 0,
                   intStart = start,
                   intEnd = end;
             if (end > start)
             {
                  intStart = end;
                  intEnd = start;
             }
        try
        {
             // Get the object of DataInputStream
            fstream = new FileInputStream(filename);
             in = new DataInputStream(fstream);
              br = new BufferedReader(new InputStreamReader(in));
             //Read File Line By Line
             while ((strLine = br.readLine()) != null)  
             {
                   String[] test = strLine.split(",");
                  counter++;
                  if (counter == intStart + 1)
                  {
                     result = Integer.parseInt(test[intEnd - 1]);
                     break;
                  }
             }
        }catch (Exception e)
        {//Catch exception if any
             System.err.println("Error: " + e.getMessage());
             System.out.println (queCity.peek());
             in.close();
        }
        System.out.println(result);
        return result;
   }
0
Comment
Question by:CrazyOne
  • 15
  • 9
  • 6
30 Comments
 
LVL 47

Expert Comment

by:for_yan
ID: 35194588

I hope this is the part of the code
after we read all ones and zeroes and miunus ones
into array [5][5] and also duplicate elemsnt acros
the diagonal for simplicity
Then method isTherePath(int num1, int num2) should return boolean value

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class IndirectPath {

      int [][] ii = new int[5][5];
          int num = 5;

    public IndirectPath() {



           try {

               //read file into array int [][]

                       /*
                String buff = null;
                DataInputStream in = new DataInputStream(new FileInputStream("c:\\temp\\test\\cities.txt"));
              buff = in.readLine();
             buff = in.readLine();
                buff = in.readLine();
                buff = in.readLine();
                StringTokenizer t = new StringTokenizer(buff);
                t.nextToken();

                     */


            } catch(Exception ex){
                System.out.println("error " + ex.toString());
                ex.printStackTrace();
            }

    }

        public boolean IsTherePath(int num1, int num2){

           
            ArrayList lists = new ArrayList();
            for(int j=0; j<num; j++){
                ArrayList ll = new ArrayList();
                ll.add(new Integer(j));
                lists.add(ll);
            }

             int num = 5;
            for(int j=0; j< num; j++ ){
            for(int jj=0; jj<num; jj++){
                if(ii[j][jj] == 1){
                    ArrayList a1 = (ArrayList) lists.get(j);
                    ArrayList a2 = (ArrayList) lists.get(jj);
                    ArrayList a3 = mergeLists(a1,a2);
                    lists.remove(j);
                    lists.remove(jj);
                    lists.add(3);

                }

            }

            }

            for(int j=0; j<lists.size(); j++){
                ArrayList aa = (ArrayList) lists.get(j);
                if(aa.contains(new Integer(num1)) && aa.contains(new Integer(num2))){
                    return true;

                }


            }

            return false;






        }

  public ArrayList mergeLists(ArrayList a1, ArrayList a2){
        ArrayList a3 = new ArrayList();

      for (int j=0; j<a1.size(); j++){
          a3.add(a1.get(j));

      }
       for (int j=0; j<a2.size(); j++){
         if(!a3.contains(a2.get(j))) a3.add(a2.get(j));

      }
        return a3;
  }

}

Open in new window

0
 
LVL 47

Expert Comment

by:for_yan
ID: 35194636
So if we name cities from 1 to 5
and then make a set of arraylists each conatining one number
and then define method for merging lists - I guess there is such method, but I wriote it for simplicity,
and the go through array of zeros and ones and as soon as we see one,
we merge two arraylists remove both of them and leave only merged list
we'll end up with situation where we have as many arraylists
as there are disconnected groups of cities

Then we are going through each of these lists and checking if it
any of the contains both of our cities which are given to us as parameters.
It is probably not the quickest way but for 5 cities should be fast enough :)

0
 
LVL 47

Expert Comment

by:for_yan
ID: 35194646
Sorry, discard that - that was of course incorrect
0
 
LVL 47

Expert Comment

by:for_yan
ID: 35194813

I guess this is the simplest task of graph theory - find connected subgraphs, therefore JGrapht library will have a solution
for that:

http://jgrapht.sourceforge.net/

Howvere this would be probably an overkill to learn it

0
 
LVL 47

Expert Comment

by:for_yan
ID: 35194971



Perhaps this one looks awkward,
but still works, at least I tested it for the
cionnectoions in your example:
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class IndirectPath {

      int [][] ii;
          int num = 5;

    public IndirectPath() {

              ii =  new int[5][5];

           try {
               ii[0][2] = 1;
               ii[1][3] =1;
               ii[3][4] = 1;
               ii[2][0] = 1;
               ii[3][1] =1;
               ii[4][3] = 1;
               //read file into array int [][]

                       /*
                String buff = null;
                DataInputStream in = new DataInputStream(new FileInputStream("c:\\temp\\test\\cities.txt"));
              buff = in.readLine();
             buff = in.readLine();
                buff = in.readLine();
                buff = in.readLine();
                StringTokenizer t = new StringTokenizer(buff);
                t.nextToken();

                     */


            } catch(Exception ex){
                System.out.println("error " + ex.toString());
                ex.printStackTrace();
            }

    }

        public boolean isTherePath(int num1, int num2){

                                 num1 = num1-1;
                                 num2 = num2-1;
            ArrayList lists = new ArrayList();
            for(int j=0; j<5; j++){
                ArrayList ll = new ArrayList();
                ll.add(new Integer(j));
                lists.add(ll);
            }

             int num = 5;
            for(int j=0; j< num; j++ ){
            for(int jj=0; jj<num; jj++){
                if(ii[j][jj] == 1){
                      int i0 = -1;
                        int j0 = -1;
                    for(int jjj=0; jjj<lists.size(); jjj++){

                        ArrayList aa = (ArrayList) lists.get(jjj);
                        if(aa.contains(new Integer(j)))i0=jjj;
                          if(aa.contains(new Integer(jj)))j0=jjj;

                    }
                    if(i0==j0)continue;
                    else  if(i0>-1 && j0 >-1)
                    {


                    ArrayList a1 = (ArrayList) lists.get(i0);
                    ArrayList a2 = (ArrayList) lists.get(j0);
                    ArrayList a3 = mergeLists(a1,a2);
                        ArrayList lists1 = new ArrayList();
                        for(int pp=0; pp<lists.size(); pp++){
                            if(pp != i0  && pp != j0)lists1.add(lists.get(pp));
                        }
                  //  lists.remove(i0);
                  //  lists.remove(j0);
                    lists1.add(a3);
                        lists = lists1;
                    }

                }

            }

            }

            for(int j=0; j<lists.size(); j++){
                ArrayList aa = (ArrayList) lists.get(j);
                if(aa.contains(new Integer(num1)) && aa.contains(new Integer(num2))){
                    return true;

                }


            }

            return false;






        }

  public ArrayList mergeLists(ArrayList a1, ArrayList a2){
        ArrayList a3 = new ArrayList();

      for (int j=0; j<a1.size(); j++){
          a3.add(a1.get(j));

      }
       for (int j=0; j<a2.size(); j++){
         if(!a3.contains(a2.get(j))) a3.add(a2.get(j));

      }
        return a3;
  }

    public static void main(String [] args){
        IndirectPath id = new IndirectPath();
       System.out.println( "3 5 "  + id.isTherePath(3,5));
    }

}

Open in new window


This is output for this  case; you can change the pairs in the last
line of the main method and check for other pairs
3 5 false

Open in new window


0
 
LVL 35

Accepted Solution

by:
mccarl earned 350 total points
ID: 35195143
Ok, here is some points to think about and then some pseudocode to get you started, leaving it up to you to translate into Java (have a go and let us know if you have problems though)

 - Mirror the data array so that you don't have to always search from smaller numbered city to larger numbered city.
 - Store that data into an actual array in Java, so that you can easily access the elements
 - Create a Queue (or a Stack, it's not really important to the functioning of the algorithm) which will hold the list of cities to search further for a path to the destination (eg. possibly you would use the LinkedList class, but feel free to try other Queue/Stack implementations
 - Also create a Set (such as the HashSet implementation) which will hold the set of cities that you have already checked for a path or that you will check for a path. This will be used to stop you from checking a cities more than once and will therefore stop you from circular loops in your code.

Then do the following...

boolean isIndirectPath(int startCity, destCity)
{
    add startCity to both HashSet and LinkedList
    boolean pathFound = false

    while(!pathFound && !LinkedLIst.isEmpty())
    {
        remove a city from head of LinkedList into currentCity
        pathFound = checkPath(currentCity, destCity);
    }
    return pathFound
}


boolean checkPath(int fromCity, int toCity)
{
    loop through all possible cities (iterator: currentCity)
    {
        if array[fromCity][currentCity] == 1
            if currentCity == toCity                           // we found a path to destination
                return true
            try to add currentCity to the HashSet
              if added, also add to LinkedList
    }
    return false
}


Translating this into more English words to help you understand better, basically we start at the start city and see what direct paths there are, if there is one to the dest city then we have finished and we return true. Otherwise, we add the cities that there are direct paths to, to the search queue ONLY as long as we haven't been there before. And then we loop through each of those new cities to find the direct paths it has. If one is the destination, then we have found a path overall, if not add the direct paths to the search queue (again only if we haven't been there or won't be there, by using the Set), and repeat....


PS. I did actually mock this up in Java and I can confirm that it works (at least for the simple example data that you provided!)
0
 
LVL 44

Author Comment

by:CrazyOne
ID: 35196010
I just got home give me 24hrs and I will get back to you, thanks.
0
 
LVL 47

Assisted Solution

by:for_yan
for_yan earned 150 total points
ID: 35196094

This version will read the file and can be easily changed for different number of cities
(file needs to be changed accordingly)

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class IndirectPath {
  static int numberOfCities = 5;
      int [][] ii;
          int num;

    public IndirectPath() {
                 num = numberOfCities;
              ii =  new int[num][num];

           try {
               /*
               ii[0][2] = 1;
               ii[1][3] =1;
               ii[3][4] = 1;
               ii[2][0] = 1;
               ii[3][1] =1;
               ii[4][3] = 1;
               */

              /*
             //  ii[0][3] = 1;
               ii[3][5] = 1;
               ii[0][5] = 1;
               ii[1][4] = 1;
              //    ii[3][0] = 1;
               ii[5][3] = 1;
               ii[5][0] = 1;
               ii[4][1] = 1;

                   */
               //read file into array int [][]


                String buff = null;
                DataInputStream in = new DataInputStream(new FileInputStream("c:\\temp\\test\\cities.txt"));

              buff = in.readLine();
             buff = in.readLine();

               for(int j=0; j<num; j++){
                   buff = in.readLine();
                   StringTokenizer t = new StringTokenizer(buff);
                   t.nextToken();
                   for(int jj=0; jj<j; jj++){
                       ii[j][jj]=Integer.parseInt(t.nextToken());
                       ii[jj][j]=ii[j][jj];
                   }

               }

                  in.close();   


            } catch(Exception ex){
                System.out.println("error " + ex.toString());
                ex.printStackTrace();
            }

    }

        public boolean isTherePath(int num1, int num2){

                                 num1 = num1-1;
                                 num2 = num2-1;
            ArrayList lists = new ArrayList();
            for(int j=0; j<5; j++){
                ArrayList ll = new ArrayList();
                ll.add(new Integer(j));
                lists.add(ll);
            }

             int num = 5;
            for(int j=0; j< num; j++ ){
            for(int jj=0; jj<num; jj++){
                if(ii[j][jj] == 1){
                      int i0 = -1;
                        int j0 = -1;
                    for(int jjj=0; jjj<lists.size(); jjj++){

                        ArrayList aa = (ArrayList) lists.get(jjj);
                        if(aa.contains(new Integer(j)))i0=jjj;
                          if(aa.contains(new Integer(jj)))j0=jjj;

                    }
                    if(i0==j0)continue;
                    else  if(i0>-1 && j0 >-1)
                    {


                    ArrayList a1 = (ArrayList) lists.get(i0);
                    ArrayList a2 = (ArrayList) lists.get(j0);
                    ArrayList a3 = mergeLists(a1,a2);
                        ArrayList lists1 = new ArrayList();
                        for(int pp=0; pp<lists.size(); pp++){
                            if(pp != i0  && pp != j0)lists1.add(lists.get(pp));
                        }
                  //  lists.remove(i0);
                  //  lists.remove(j0);
                    lists1.add(a3);
                        lists = lists1;
                    }

                }

            }

            }

            for(int j=0; j<lists.size(); j++){
                ArrayList aa = (ArrayList) lists.get(j);
                if(aa.contains(new Integer(num1)) && aa.contains(new Integer(num2))){
                    return true;

                }


            }

            return false;






        }

  public ArrayList mergeLists(ArrayList a1, ArrayList a2){
        ArrayList a3 = new ArrayList();

      for (int j=0; j<a1.size(); j++){
          a3.add(a1.get(j));

      }
       for (int j=0; j<a2.size(); j++){
         if(!a3.contains(a2.get(j))) a3.add(a2.get(j));

      }
        return a3;
  }

    public static void main(String [] args){
        IndirectPath id = new IndirectPath();
       System.out.println( args[0] + " " + args[1]  + " Connected:  " + id.isTherePath(Integer.parseInt(args[0]),Integer.parseInt(args[1])));
    }

}

Open in new window


Input file:

=========================
       1      2      3      4      5
1      0
2      -1      0
3      1      -1      0
4      -1      1      -1      0
5      -1      -1      -1      1      0
=========================

Open in new window


Result:

java IndirectPath 1 3
1 3 Connected:  true

Open in new window





0
 
LVL 47

Expert Comment

by:for_yan
ID: 35196124

The logic is as I described above (ID:35194636) with slight modification:

First we add complementary part of the two-dimensional array to make
it symmetric to simplify further logic.

First we make a set of arraylists each containing only  one number (all cities initially disconnected)
 then define method for merging lists - I guess there is such method, but I wrote it for simplicity,
and then we go through our initial array of zeros and ones and as soon as we see one,
we go through the current set of arraylists and if two indexes  corresponding to one,
belong to the same arraylist we do nothing, if they
belong to different arraylists we merge these lists - then remove both of them and leave
one merged list
we'll end up with situation where we have as many arraylists
as there are disconnected groups of cities

Then we are going through each of these lists and checking if
any of them contains both of our cities which are given to us as parameters
then these two cities are of course connected.
It is probably not the quickest way, as some of the comparisons here
could be eliminated,  but for 5 cities should be fast enough :)
0
 
LVL 44

Author Comment

by:CrazyOne
ID: 35204660
Sorry I havent had a chance work with this yet, hopefully i will tomorrow. However i have looked at what has been posted and I do see that it appears that these will work i just need to plug it in test it. One thing mccarl i havent used HashSets before will it be diffuclt implement?
0
 
LVL 35

Expert Comment

by:mccarl
ID: 35204701
No, a Set is very similar to a List except that you can't have duplicates (which is exactly why we are using it here). It has similar add,get type methods and it is Iterable so you can loop through it if you want.

As I mentioned above, I did actually do this in code to test out my idea, and the guts of it was done in less than 30 lines of code. So no, I wouldn't count that as difficult by any stretch. By the way, I only used the add method of the Set and I only used it twice in the whole code. Oh and I don't use anything HashSet specific, so if you are looking into it, you should really only need to look at the Set interface docs. (http://download.oracle.com/javase/1.5.0/docs/api/java/util/Set.html)
0
 
LVL 44

Author Comment

by:CrazyOne
ID: 35212032
Ok l starting to plug in the code you two have offered I will get back to you as soon as possible.
0
 
LVL 44

Author Comment

by:CrazyOne
ID: 35308184
I have been really sick and this has been the first time i have had a chance to get back to this Q. mccarl could you explain with the LinkList, I am using a Queue, it appears that there will only be one city at a time in the that list is that correct? I am kind of under the gun I was suppose to have this done by the 31st but I got so sick i could not work on it and i need to submit it this tonight by midnight. Like i said i can find if there is a direct path but i am confused on the indirect path.
0
 
LVL 44

Author Comment

by:CrazyOne
ID: 35308560
Ok here is what is confusing me

===========================================
In this line

//remove a city from head of LinkedList into currentCity
        pathFound = checkPath(currentCity, destCity);
===========================================

The currentCity is always the same because when I go to the checkPath() method and I do this

===========================================

//try to add currentCity to the HashSet
             if (HashSet.add(currentCity))
             {
                  Queue.offer(currentCity);
             }
===========================================

The currentCity never changes

For example I choose city 2 as the fromCity and choose 4 as the toCity I pass to the isDirectPath() method this

currentCity = Queue.remove() //which is the startCity
checkPath(currentCity, destCity);

I don’t see where the currentCity variable is ever changed
0
 
LVL 35

Expert Comment

by:mccarl
ID: 35309283
Sorry, as I said in the post, what I posted was more pseudocode, so the line

> remove a city from head of LinkedList into currentCity

was actually meant to be something that you translate into actual code, ie. it was a comment. So it should be something like..

currentCity = citiesToSearchList.remove();

Hence, that is where currentCity variable is changed


By the way, the reference to currentCity in the checkPath method, it a separate local variable that iterates through all cities. It has nothing to do with the currentCity reference in the isIndirectPath method.
0
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
LVL 44

Author Comment

by:CrazyOne
ID: 35309941
i know that line wasnt code and currentCity is a variable, i am just having problems visualizing is it all

mccarl you said
"By the way, the reference to currentCity in the checkPath method, it a separate local variable that iterates through all cities. It has nothing to do with the currentCity reference in the isIndirectPath method."

here is the code i put together and i know i am missing something because i am not getting the expected return


public boolean isIndirectPath(int startCity, int destCity)
   {
	  a.offer(startCity - 1);
	  System.out.println(a.isEmpty());
	  //b.add(startCity);
       //add startCity to both HashSet and LinkedList
       boolean pathFound = false;
       while(!pathFound && !a.isEmpty())
       {
           //remove a city from head of LinkedList into currentCity
    	  int check = currentCity = a.remove();
    	  pathFound = checkPath(check, destCity - 1);
           
       }
       return pathFound;
   }


   public boolean checkPath(int fromCity, int toCity)
   {
	  /*int 	intStart = fromCity,
	  intEnd = toCity;
	  if (toCity < fromCity)
	  {
		 intStart = toCity;
		 intEnd = fromCity;
	  }*/
	  //loop through all possible cities (iterator: currentCity)
	  for (int i = 0; i < map.length; i++)
	  {
		 if (map[fromCity][currentCity] == 1)
			if (currentCity == toCity)                           // we found a path to destination
			   return true;
		 //try to add currentCity to the HashSet
		 //if added, also add to LinkedList
		 if (b.add(i))
		 {
	   	    a.add(i);
		 }
	  }
	  return false;
   }

Open in new window

0
 
LVL 44

Author Comment

by:CrazyOne
ID: 35309950
the vaiable "a" is a Queue and variable "b" is a HashSet
0
 
LVL 44

Author Comment

by:CrazyOne
ID: 35309976
for_yan I been looking at your code as well. I am having difficulty following the logic of it because i have been sick with a Sinus Infection and my 58 year old mind has a very difficult time locking in on things and staying focused. I havent been able to do simple algebraic equatiions the past week let alone decipher code.  :-(
0
 
LVL 47

Expert Comment

by:for_yan
ID: 35309992

Read the explanation ID:35196124 and ask questions - I'll answer.
I have not so young mind either, so we have a chance to understand each other:)
0
 
LVL 47

Expert Comment

by:for_yan
ID: 35310002
The advantage, though, that this is the code which I tested on a few examples and got expected results.
0
 
LVL 44

Author Comment

by:CrazyOne
ID: 35310420
I was remiss in stating that the there will be a variety of maps that can be loaded into the code. there might be a map with as many as 1000 cities. I have built a 2D array that will hold the data of the map. I got a 2 meetings to attend today so when i get back i will only have 3hrs to finish this. i need a ll the help i can get.
0
 
LVL 35

Assisted Solution

by:mccarl
mccarl earned 350 total points
ID: 35311048
What I was meaning is that currentCity in the one method has nothing to do with currentCity in the other. They are not the same variable. If that code you posted compiles, you must have defined currentCity at some higher level. Don't do that, it only needs to be local to each method.

And in fact, your variable "i" in the second method IS your currentCity variable, so just change currentCity on line 31 and 32, to "i" and you should be getting closer to a working solution.

Also, it may have been not so clear from the pseudocode that I posted but the lines 36-39 should be inside the if block from line 31 too.
0
 
LVL 44

Author Comment

by:CrazyOne
ID: 35311281
ok this is the code i have so far and it is not working accurately. i know its close but i am missing something. BTW in the isIndirectPath method i deicrement startCity and destCity by one because the user is goint to be entering numbers from 1 to total amount of cities
public CityPathQueue() 
   {
	  // TODO Auto-generated constructor stub
   }
   
   public CityPathQueue(String infilename)  throws IOException
   {
	  String strLine;
	  int 	intRow = 0,
		 	intSize;
	//for (int i = 0; i < intEnd; i++)
	  try
	  {
		 // Get the object of DataInputStream
		 fstream = new FileInputStream(infilename);
		 in = new DataInputStream(fstream);
		 br = new BufferedReader(new InputStreamReader(in));
		 //retrieve the the first line which will be the number of cities
		 strLine = br.readLine();
		 intSize = Integer.parseInt(strLine);
		 //dimension both arrays
		 visited = new boolean[intSize];
		 map = new int[intSize][intSize];
		 
		 for (int i = 0; i < intSize; i++)
		 {
			visited[i] = false;
		 }
		
		 //Read File Line By Line
		 while ((strLine = br.readLine()) != null)   
		 {
			String[] test = strLine.split(",");
			for (int j = 0; j < test.length; j++)
			{
			   map[intRow][j] = Integer.parseInt(test[j]);
			}
			intRow++;
		 }

	  }catch (Exception e)
	  {//Catch exception if any
		 System.err.println("Error: " + e.getMessage());
		 in.close();
	  }
	  in.close();

   }
   
   public int isDirect(int start, int end)
   {
	  int 	intStart = start,
	 		intEnd = end;
	  //flip the order of the cities if the destination city is less than
	  //the strat city. This way the rest of the map does not need
	  //to filled. Also a 2D array starts cheking at the row and then 
	  //the column so to pass the args correctly the end city
	  //goes into the first dimension of the array.
	  if (end < start)
	  {
		 intStart = end;
		 intEnd = start;
	  }
	  queCity.offer(intStart - 1);
	  visited[intStart - 1] = true;
	  return map[intEnd - 1][intStart - 1];
   }
      
   public boolean isIndirectPath(int startCity, int destCity)
   {
	  startCity--;
	  destCity--;
	  //add startCity to both HashSet and LinkedList
	  a.offer(startCity);
	  b.add(startCity);
      
       boolean pathFound = false;
       while(!pathFound && !a.isEmpty())
       {
           //remove a city from head of LinkedList into currentCity
    	  int check =  a.remove();
    	  System.out.println(check + " " + (destCity));
           pathFound = checkPath(check, destCity);
           
       }
       return pathFound;
   }


   public boolean checkPath(int start, int end)
   {
	  if (end < start)
	  {
		 int temp = start;
		 start = end;
		 end = temp;
	  }
	  //loop through all possible cities (iterator: currentCity)
	  for (int i = 0; i < map.length; i++)
	  {
		 if (map[start][i] == 1)
		 {
			if (i == end)                           // we found a path to destination
			   return true;
			//try to add currentCity to the HashSet
			//if added, also add to LinkedList
			if (b.add(i))
			{
			   System.out.println("Added " + i);
			   a.add(i);
			}
		 }
	  }
	  return false;
   }

Open in new window

0
 
LVL 35

Assisted Solution

by:mccarl
mccarl earned 350 total points
ID: 35311368
As I said, mirroring your array will make your life SO much easier. The problem with the above is that although you are checking and possibly swapping "start" and "end" at lines 92 - 97, you aren't doing that for every value of "i" in the loop before checking the array at line 101. You should either move that reversing logic down to be between lines 100 and 101, (with the associated change of checking/swapping "start" and "i") or you should just mirror the array which means you don't need any of that (or any of lines 54 - 63 either)

And mirroring the array isn't all that hard just change line 36 to

map[intRow][j] = map[j][intRow] = Integer.parseInt(test[j]);

0
 
LVL 44

Author Comment

by:CrazyOne
ID: 35311830
At times it works and at others it doesnt. Case in point with the followin map if i pass 3,4 to the checkPath method it rerturns true even though it shouldnt because the values are all -1

0
-1,0
1,1,0
-1,-1,-1,0
-1,-1,-1,-1,0
-1,-1,-1,1,1,0
1,1,-1,-1,-1,-1,0

BTW i mirror that data as suggested, thanks
public class CityPathQueue {

   private Queue<Integer> queCity =  new LinkedList<Integer>();
   private Queue<Integer> a = new LinkedList<Integer>();
   private HashSet<Integer> b = new HashSet<Integer>();
   private FileInputStream fstream;
   private DataInputStream in;
   private BufferedReader br;
   private int[][] map;
   private boolean[] visited;
   /**
    * 
    */
   public CityPathQueue() 
   {
	  // TODO Auto-generated constructor stub
   }
   
   public CityPathQueue(String infilename)  throws IOException
   {
	  String strLine;
	  int 	intRow = 0,
		 	intSize;
	//for (int i = 0; i < intEnd; i++)
	  try
	  {
		 // Get the object of DataInputStream
		 fstream = new FileInputStream(infilename);
		 in = new DataInputStream(fstream);
		 br = new BufferedReader(new InputStreamReader(in));
		 //retrieve the the first line which will be the number of cities
		 strLine = br.readLine();
		 intSize = Integer.parseInt(strLine);
		 //dimension both arrays
		 visited = new boolean[intSize];
		 map = new int[intSize][intSize];
		 
		 for (int i = 0; i < intSize; i++)
		 {
			visited[i] = false;
		 }
		
		 //Read File Line By Line
		 while ((strLine = br.readLine()) != null)   
		 {
			String[] test = strLine.split(",");
			for (int j = 0; j < test.length; j++)
			{
			   map[intRow][j] = map[j][intRow] = Integer.parseInt(test[j]); 
			}
			intRow++;
		 }

	  }catch (Exception e)
	  {//Catch exception if any
		 System.err.println("Error: " + e.getMessage());
		 in.close();
	  }
	  in.close();

   }
   
   public int isDirect(int start, int end)
   {
	  start--;
	  end--;
	  queCity.offer(start);
	  //visited[intStart - 1] = true;
	  return map[start][end];
   }
   
   public boolean isIndirectPath(int start, int end)
   {
	  start--;
	  end--;
	  //add start to both HashSet and LinkedList
	  a.offer(start);
	  b.add(start);
      
       boolean pathFound = false;
       while(!pathFound && !a.isEmpty())
       {
           //remove a city from head of LinkedList into currentCity
    	  int curr =  a.remove();
           pathFound = checkPath(end, curr);
           
       }
       return pathFound;
   }

   public boolean checkPath(int start, int end)
   {
	  //loop through all possible cities (iterator: currentCity)
	  for (int i = 0; i < map.length; i++)
	  {
		 if (map[start][i] == 1)
		 {
			if (i == end)                           // we found a path to destination
			   return true;
			//try to add currentCity to the HashSet
			//if added, also add to LinkedList
			if (b.add(i))
			{
			   a.add(i);
			}
		 }
	  }
	  return false;
   }

}

Open in new window

0
 
LVL 44

Author Comment

by:CrazyOne
ID: 35311845
actually it may be working correctly i am having difficulty assessing it i guess.
0
 
LVL 35

Expert Comment

by:mccarl
ID: 35311859
No, it isn't working correctly.... because on line 85 you swapped the two parameters??? Why?? Put them back the right way and it should work.
0
 
LVL 44

Assisted Solution

by:CrazyOne
CrazyOne earned 0 total points
ID: 35311893
Yeah i figured it out as well thanks allot, time to close this Q. I appreciate both of your help and time. I am going to split the points 150and 350 points. I am mainly using mccarl’s suggestions because it fit the direction I was needing to go in. Thanks a lot to both of you.
0
 
LVL 44

Author Comment

by:CrazyOne
ID: 35311903
Thank you
0
 
LVL 44

Author Closing Comment

by:CrazyOne
ID: 35349359
Thanks
0

Featured Post

Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

Join & Write a Comment

Java had always been an easily readable and understandable language.  Some relatively recent changes in the language seem to be changing this pretty fast, and anyone that had not seen any Java code for the last 5 years will possibly have issues unde…
Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:
The viewer will learn how to implement Singleton Design Pattern in Java.

747 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now