Find indirect path
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[intE
break;
}
}
}catch (Exception e)
{//Catch exception if any
System.err.println("Error:
System.out.println (queCity.peek());
in.close();
}
System.out.println(result)
return result;
}
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[intE
break;
}
}
}catch (Exception e)
{//Catch exception if any
System.err.println("Error:
System.out.println (queCity.peek());
in.close();
}
System.out.println(result)
return result;
}
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 :)
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 :)
Sorry, discard that - that was of course incorrect
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
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));
}
}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 falseASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
I just got home give me 24hrs and I will get back to you, thanks.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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 :)
ASKER
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?
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
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
ASKER
Ok l starting to plug in the code you two have offered I will get back to you as soon as possible.
ASKER
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.
ASKER
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
==========================
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
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.
> 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.
ASKER
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
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;
}ASKER
the vaiable "a" is a Queue and variable "b" is a HashSet
ASKER
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. :-(
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:)
The advantage, though, that this is the code which I tested on a few examples and got expected results.
ASKER
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.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
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;
}SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
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
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;
}
}ASKER
actually it may be working correctly i am having difficulty assessing it i guess.
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.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Thank you
ASKER
Thanks
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
Open in new window