Created
June 4, 2013 05:22
-
-
Save anonymous/5703772 to your computer and use it in GitHub Desktop.
WOOOOOO Got my shortest path for graph workin
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import graph.Vertex; | |
import java.io.FileNotFoundException; | |
import java.io.FileReader; | |
import java.util.ArrayList; | |
import java.util.Scanner; | |
import java.util.Stack; | |
public class Main { | |
/** | |
* @param args | |
*/ | |
public static void main(String[] args) throws FileNotFoundException | |
{ | |
Scanner scn = new Scanner(new FileReader("vertex.txt"));//create new scanner to read .txt file | |
int numofvertices = scn.nextInt(); //find number of vertexes | |
int start = scn.nextInt(); | |
int end = scn.nextInt(); | |
ArrayList<Vertex> vertices = new ArrayList<Vertex>(); | |
for(int i = 0; i < numofvertices;i++) | |
{ | |
//make a new vertex for how many vertexes were called | |
vertices.add(new Vertex(i)); | |
} | |
//load in matrix line | |
int node1 = scn.nextInt(); | |
int node2 = scn.nextInt(); | |
while (node1 != -1 && node2 != -1) | |
{ | |
Vertex vertex1 = vertices.get(node1); //get vertex from node1 | |
Vertex vertex2 = vertices.get(node2); //get vertex from node2 | |
vertex1.adj.add(vertex2); //give node1's vertex directed adjacentcy to node 2 | |
//load next matrix line | |
node1 = scn.nextInt(); | |
node2 = scn.nextInt(); | |
} | |
for (Vertex vertexOutput : vertices) | |
{ | |
System.out.println(vertexOutput); | |
} | |
System.out.println(); | |
//start destination queue | |
ArrayList<Vertex> vertexQue = new ArrayList<Vertex>(); //create a que of vertexs | |
vertices.get(start).isstartnode = true; //tell the start that it is the starting point | |
vertexQue.add(vertices.get(start)); //get start from original vertex list and place it in the que | |
while(!vertexQue.isEmpty()) | |
{ | |
Vertex parent = vertexQue.remove(0); | |
for(Vertex child : parent.adj) | |
{ | |
if (!child.isstartnode == true) | |
{ | |
child.isstartnode = true; | |
child.destination = parent; | |
vertexQue.add(child); | |
} | |
} | |
} | |
//start ordered traverse | |
Stack<Vertex> vertexStack = new Stack<Vertex>(); //create a new stack of vertexs | |
Vertex currentvertex = vertices.get(end); //select the end node | |
vertexStack.push(currentvertex); //add end node to the top of the stack | |
while(!vertexStack.peek().equals(vertices.get(start))) //while the stack hasnt reached the start node | |
{ | |
currentvertex = currentvertex.destination; //the current vertex becomes the destination vertex | |
vertexStack.push(currentvertex); //push the current vertex onto the stack | |
} | |
while(!vertexStack.isEmpty()) //while the stack isnt empty | |
{ | |
Vertex tempvertex = vertexStack.pop(); //take a vertex off the stack (starting with the start) | |
System.out.print(tempvertex.id); //print it out nicely in order | |
if(!vertexStack.isEmpty()) | |
{ | |
System.out.print("->"); | |
} | |
} | |
System.out.println(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment