x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 457

# 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;

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);
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
CrazyOne
• 15
• 9
• 6
5 Solutions

Commented:

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"));
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();
}

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);

}

}

}

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++){

}
for (int j=0; j<a2.size(); j++){

}
return a3;
}

}
``````
0

Commented:
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

Commented:
Sorry, discard that - that was of course incorrect
0

Commented:

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

Commented:

Perhaps this one looks awkward,
but still works, at least I tested it for the
``````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"));
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();
}

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);
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++){

}
for (int j=0; j<a2.size(); 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 false
``````

0

IT Business Systems Analyst / Software DeveloperCommented:
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)
{
boolean pathFound = false

{
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
}
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

Author Commented:
I just got home give me 24hrs and I will get back to you, thanks.
0

Commented:

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"));

for(int j=0; j<num; j++){
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();
}

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);
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++){

}
for (int j=0; j<a2.size(); 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])));
}

}
``````

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
=========================
``````

Result:

``````java IndirectPath 1 3
1 3 Connected:  true
``````

0

Commented:

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

Author Commented:
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

IT Business Systems Analyst / Software DeveloperCommented:
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

Author Commented:
Ok l starting to plug in the code you two have offered I will get back to you as soon as possible.
0

Author Commented:
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

Author Commented:
Ok here is what is confusing me

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

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
{
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

IT Business Systems Analyst / Software DeveloperCommented:
Sorry, as I said in the post, what I posted was more pseudocode, so the line

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

Author Commented:
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());
boolean pathFound = false;
while(!pathFound && !a.isEmpty())
{
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
{
}
}
return false;
}
``````
0

Author Commented:
the vaiable "a" is a Queue and variable "b" is a HashSet
0

Author Commented:
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

Commented:

I have not so young mind either, so we have a chance to understand each other:)
0

Commented:
The advantage, though, that this is the code which I tested on a few examples and got expected results.
0

Author Commented:
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

IT Business Systems Analyst / Software DeveloperCommented:
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

Author Commented:
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);
//retrieve the the first line which will be the number of cities
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;
}

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--;
a.offer(startCity);

boolean pathFound = false;
while(!pathFound && !a.isEmpty())
{
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
{
}
}
}
return false;
}
``````
0

IT Business Systems Analyst / Software DeveloperCommented:
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

Author Commented:
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 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);
//retrieve the the first line which will be the number of cities
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;
}

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--;
a.offer(start);

boolean pathFound = false;
while(!pathFound && !a.isEmpty())
{
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
{
}
}
}
return false;
}

}
``````
0

Author Commented:
actually it may be working correctly i am having difficulty assessing it i guess.
0

IT Business Systems Analyst / Software DeveloperCommented:
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

Author Commented:
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

Author Commented:
Thank you
0

Author Commented:
Thanks
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.