I am trying to create an undirected graph given a text file of airports and the cost to each other airport its connected to. The file is in the format, for example: LAX DFW 1000 MSY 250... where lax is a vertex(departing airport) and dfw is another vertex(arriving airport) adjacent to lax and its edge length is 1000. I attempted to create an adjacency list where all the departing airports are Vertex objects stored in an array list and each element in that array has another array list connected to it, where the elements in the connected array are also Vertex objects. Each Vertex object has a name field and edge length field. Here is a sample of what I have so far:
import java.io.*;
import java.util.*;
public class ShortestPath
{
public ArrayList<Vertex> vertices;
//new Vertex
private static class Vertex
{
public int edgeLength;
public ArrayList<Vertex> connected; //list of connected vertices
public String name;
public Vertex(String s)
{
name = s;
}
}
public ShortestPath() throws FileNotFoundException
{
readFile();
}
private void readFile() throws FileNotFoundException
{
File f = new File("airports.txt");
Scanner input = new Scanner(f);
this.vertices = new ArrayList<Vertex>();
while(input.hasNextLine())
{
String line = input.nextLine();
Scanner scan = new Scanner(line); //scanner for the current line
String str = scan.next();
Vertex from = findVertex(str);
if (from == null)
{
from = new Vertex(str);
vertices.add(from);
}
from.connected = new ArrayList<Vertex>();
while(scan.hasNext())
{
String s = scan.next();
Vertex ver = findVertex(s);
if (ver == null)
{
ver = new Vertex(s);
this.vertices.add(ver);
}
ver.edgeLength = scan.nextInt();
from.connected.add(ver);
//if I use this line, it prints out exactly how the graph should be
// System.out.println(from.name + " to " + ver.name + " is " + ver.edgeLength);
}
}
} //end readFile()
public static void main(String[] args)
{
try
{
ShortestPath sp = new ShortestPath();
for(Vertex v: sp.vertices)
{
System.out.println(v.name);
for (Vertex e: v.connected)
{
System.out.print(" to " + e.name + " is " + e.edgeLength);
}
System.out.println();
}
} catch (FileNotFoundException e)
{
e.printStackTrace();
}
}
}
Here is what I am getting when I run this (this is not correct):
ATL
to BOS is 250 to DFW is 59 to MOB is 59
BOS
to ATL is 59 to DFW is 59
DFW
to ATL is 59 to AUS is 59 to BOS is 250 to HOU is 59 to LAX is 100 to LIT is 59 to MSY is 128 to OKC is 59 to SHV is 59 to SFO is 100
MOB
to ATL is 59
AUS
to DFW is 59 to HOU is 59 to SAT is 59
HOU
to AUS is 59 to DFW is 59 to SAT is 59
SAT
to AUS is 59 to HOU is 59
LAX
to DFW is 59 to SFO is 100
LIT
to DFW is 59
MSY
to DFW is 59
OKC
to DFW is 59
SHV
to DFW is 59
SFO
to DFW is 59 to LAX is 100
If I uncomment the System.out.println line in readFile(), it gives this, which is the way it should be if you were to draw the graph by hand:
ATL to BOS is 250
ATL to DFW is 250
ATL to MOB is 59
AUS to DFW is 59
AUS to HOU is 59
AUS to SAT is 59
BOS to ATL is 250
BOS to DFW is 250
DFW to ATL is 250
DFW to AUS is 59
DFW to BOS is 250
DFW to HOU is 128
DFW to LAX is 1000
DFW to LIT is 59
DFW to MSY is 128
DFW to OKC is 59
DFW to SHV is 59
DFW to SFO is 1200
HOU to AUS is 59
HOU to DFW is 128
HOU to SAT is 59
LAX to DFW is 1000
LAX to SFO is 100
LIT to DFW is 59
MOB to ATL is 59
MSY to DFW is 128
OKC to DFW is 59
SAT to AUS is 59
SAT to HOU is 59
SFO to DFW is 1200
SFO to LAX is 100
SHV to DFW is 59
I can't seem to figure out why I am getting the wrong output. any help is appreciated!