373 lines
17 KiB
Java
373 lines
17 KiB
Java
package DirectedGraphJava;
|
|
import java.util.HashMap;
|
|
import java.util.Iterator;
|
|
import java.util.ArrayList;
|
|
|
|
public class ui {
|
|
private DirectedGraph graph = new DirectedGraph();
|
|
public ui(){
|
|
|
|
}
|
|
public void run(){
|
|
Integer command;
|
|
while(true){
|
|
if(this.graph.numVertices() == 0)
|
|
System.out.println("Graph is empty");
|
|
System.out.println();
|
|
System.out.println("1. Load graph from file");
|
|
System.out.println("2. Save graph to file");
|
|
System.out.println("3. Generate a graph");
|
|
System.out.println("4. Add a vertex");
|
|
System.out.println("5. Remove a vertex");
|
|
System.out.println("6. Add an edge");
|
|
System.out.println("7. Remove an edge");
|
|
System.out.println("8. Get in degree");
|
|
System.out.println("9. Get out degree");
|
|
System.out.println("10 Get cost");
|
|
System.out.println("11. Set cost");
|
|
System.out.println("12. Get number of vertices");
|
|
System.out.println("13. Get number of edges");
|
|
System.out.println("14. Get vertices");
|
|
System.out.println("15. Get edges");
|
|
System.out.println("16. Get inbounds");
|
|
System.out.println("17. Get outbounds");
|
|
System.out.println("18. Get all");
|
|
System.out.println("19. Get shortest path to all vertices");
|
|
System.out.println("20. Get shortest path to a vertex");
|
|
System.out.println("21. Get shortest cost path to a vertex");
|
|
System.out.println("22. Get topological sort");
|
|
System.out.println("23. Get highest cost path to a vertex");
|
|
System.out.println("0. Exit");
|
|
System.out.print("Command: ");
|
|
command = Integer.parseInt(System.console().readLine());
|
|
System.out.println();
|
|
switch(command){
|
|
case 1: {
|
|
System.out.print("File name: ");
|
|
String fileName = System.console().readLine();
|
|
try{
|
|
this.graph = Main.read_from_file(fileName);
|
|
}
|
|
catch(Exception e){
|
|
System.out.println("Error: " + e.getMessage());
|
|
}
|
|
break;
|
|
}
|
|
case 2: {
|
|
System.out.print("File name: ");
|
|
String fileName = System.console().readLine();
|
|
try{
|
|
Main.write_to_file(this.graph, fileName);
|
|
}
|
|
catch(Exception e){
|
|
System.out.println("Error: " + e.getMessage());
|
|
}
|
|
break;
|
|
}
|
|
case 3: {
|
|
System.out.print("Number of vertices: ");
|
|
Integer numVertices = Integer.parseInt(System.console().readLine());
|
|
System.out.print("Number of edges: ");
|
|
Integer numEdges = Integer.parseInt(System.console().readLine());
|
|
try{
|
|
this.graph = Main.random_graph(numVertices, numEdges);
|
|
}
|
|
catch(Exception e){
|
|
System.out.println("Error: " + e.getMessage());
|
|
}
|
|
break;
|
|
}
|
|
case 4: {
|
|
System.out.print("Vertex: ");
|
|
Integer vertex = Integer.parseInt(System.console().readLine());
|
|
try{
|
|
this.graph.addVertex(vertex);
|
|
}
|
|
catch(Exception e){
|
|
System.out.println("Error: " + e.getMessage());
|
|
}
|
|
break;
|
|
}
|
|
case 5: {
|
|
System.out.print("Vertex: ");
|
|
Integer vertex = Integer.parseInt(System.console().readLine());
|
|
try{
|
|
this.graph.removeVertex(vertex);
|
|
}
|
|
catch(Exception e){
|
|
System.out.println("Error: " + e.getMessage());
|
|
}
|
|
break;
|
|
}
|
|
case 6: {
|
|
System.out.print("Vertex 1: ");
|
|
Integer vertex1 = Integer.parseInt(System.console().readLine());
|
|
System.out.print("Vertex 2: ");
|
|
Integer vertex2 = Integer.parseInt(System.console().readLine());
|
|
System.out.print("Weight: ");
|
|
Integer weight = Integer.parseInt(System.console().readLine());
|
|
try{
|
|
this.graph.addEdge(vertex1, vertex2, weight);
|
|
}
|
|
catch(Exception e){
|
|
System.out.println("Error: " + e.getMessage());
|
|
}
|
|
break;
|
|
}
|
|
case 7: {
|
|
System.out.print("Vertex 1: ");
|
|
Integer vertex1 = Integer.parseInt(System.console().readLine());
|
|
System.out.print("Vertex 2: ");
|
|
Integer vertex2 = Integer.parseInt(System.console().readLine());
|
|
try{
|
|
this.graph.removeEdge(vertex1, vertex2);
|
|
}
|
|
catch(Exception e){
|
|
System.out.println("Error: " + e.getMessage());
|
|
}
|
|
break;
|
|
}
|
|
case 8: {
|
|
System.out.print("Vertex: ");
|
|
Integer vertex = Integer.parseInt(System.console().readLine());
|
|
try{
|
|
System.out.println("In degree: " + this.graph.inDegree(vertex));
|
|
}
|
|
catch(Exception e){
|
|
System.out.println("Error: " + e.getMessage());
|
|
}
|
|
break;
|
|
}
|
|
case 9: {
|
|
System.out.print("Vertex: ");
|
|
Integer vertex = Integer.parseInt(System.console().readLine());
|
|
try{
|
|
System.out.println("Out degree: " + this.graph.outDegree(vertex));
|
|
}
|
|
catch(Exception e){
|
|
System.out.println("Error: " + e.getMessage());
|
|
}
|
|
break;
|
|
}
|
|
case 10: {
|
|
System.out.print("Vertex 1: ");
|
|
Integer vertex1 = Integer.parseInt(System.console().readLine());
|
|
System.out.print("Vertex 2: ");
|
|
Integer vertex2 = Integer.parseInt(System.console().readLine());
|
|
try{
|
|
System.out.println("Cost: " + this.graph.weight(vertex1, vertex2));
|
|
}
|
|
catch(Exception e){
|
|
System.out.println("Error: " + e.getMessage());
|
|
}
|
|
break;
|
|
}
|
|
case 11: {
|
|
System.out.print("Vertex 1: ");
|
|
Integer vertex1 = Integer.parseInt(System.console().readLine());
|
|
System.out.print("Vertex 2: ");
|
|
Integer vertex2 = Integer.parseInt(System.console().readLine());
|
|
System.out.print("Weight: ");
|
|
Integer weight = Integer.parseInt(System.console().readLine());
|
|
try{
|
|
this.graph.weight(vertex1, vertex2, weight);
|
|
}
|
|
catch(Exception e){
|
|
System.out.println("Error: " + e.getMessage());
|
|
}
|
|
break;
|
|
}
|
|
case 12: {
|
|
System.out.println("Number of vertices: " + this.graph.numVertices());
|
|
break;
|
|
}
|
|
case 13: {
|
|
System.out.println("Number of edges: " + this.graph.numEdges());
|
|
break;
|
|
}
|
|
case 14: {
|
|
System.out.println("Vertices: ");
|
|
for(Iterator<Integer> vertex = this.graph.vertices(); vertex.hasNext();){
|
|
System.out.println(vertex.next());
|
|
}
|
|
break;
|
|
}
|
|
case 15: {
|
|
System.out.println("Edges: ");
|
|
for(Iterator<Pair<Pair<Integer, Integer>,Integer>> edge = this.graph.edges(); edge.hasNext();){
|
|
Pair<Pair<Integer, Integer>,Integer> e = edge.next();
|
|
System.out.println(e.first.first + " " + e.first.second + " " + e.second);
|
|
}
|
|
break;
|
|
}
|
|
case 16: {
|
|
System.out.print("Vertex: ");
|
|
Integer vertex = Integer.parseInt(System.console().readLine());
|
|
System.out.println("Inbounds: ");
|
|
for(Iterator<Integer> inbounds = this.graph.inbounds(vertex); inbounds.hasNext();){
|
|
Integer e = inbounds.next();
|
|
System.out.println(e);
|
|
}
|
|
break;
|
|
}
|
|
case 17: {
|
|
System.out.print("Vertex: ");
|
|
Integer vertex = Integer.parseInt(System.console().readLine());
|
|
System.out.println("Outbounds: ");
|
|
for(Iterator<Integer> outbounds = this.graph.outbounds(vertex); outbounds.hasNext();){
|
|
Integer e = outbounds.next();
|
|
System.out.println(e);
|
|
}
|
|
break;
|
|
}
|
|
case 18:{
|
|
System.out.println("Inbounds: ");
|
|
for(Iterator<Integer> vertex = this.graph.vertices(); vertex.hasNext();){
|
|
Integer v = vertex.next();
|
|
System.out.print(v);
|
|
System.out.print(": ");
|
|
for(Iterator<Integer> inbounds = this.graph.inbounds(v); inbounds.hasNext();){
|
|
Integer e = inbounds.next();
|
|
System.out.print(e);
|
|
System.out.print(" ");
|
|
}
|
|
System.out.println();
|
|
}
|
|
System.out.println();
|
|
System.out.println("Outbounds: ");
|
|
for(Iterator<Integer> vertex = this.graph.vertices(); vertex.hasNext();){
|
|
Integer v = vertex.next();
|
|
System.out.print(v);
|
|
System.out.print(": ");
|
|
for(Iterator<Integer> outbounds = this.graph.outbounds(v); outbounds.hasNext();){
|
|
Integer e = outbounds.next();
|
|
System.out.print(e);
|
|
System.out.print(" ");
|
|
}
|
|
System.out.println();
|
|
}
|
|
System.out.println();
|
|
System.out.println("Edges: ");
|
|
for(Iterator<Pair<Pair<Integer, Integer>,Integer>> edge = this.graph.edges(); edge.hasNext();){
|
|
Pair<Pair<Integer, Integer>,Integer> e = edge.next();
|
|
System.out.println(e.first.first + " " + e.first.second + " " + e.second);
|
|
}
|
|
break;
|
|
}
|
|
case 19:{
|
|
System.out.println("Enter a vertex: ");
|
|
Integer vertex = Integer.parseInt(System.console().readLine());
|
|
HashMap<Integer, Pair<Integer, Integer>> distances = this.graph.shortestPath(vertex);
|
|
for(Iterator<Integer> vertex2 = this.graph.vertices(); vertex2.hasNext();){
|
|
Integer v = vertex2.next();
|
|
System.out.println("Distance from " + vertex + " to " + v + ": " + distances.get(v).second);
|
|
System.out.println("Path: ");
|
|
if(this.graph.path(vertex, v).isEmpty()){
|
|
System.out.println("No path");
|
|
continue;
|
|
}
|
|
for(Iterator<Integer> path = this.graph.path(vertex, v).iterator(); path.hasNext();){
|
|
Integer p = path.next();
|
|
System.out.print(p);
|
|
System.out.print(" ");
|
|
}
|
|
System.out.println();
|
|
}
|
|
break;
|
|
}
|
|
case 20:{
|
|
System.out.println("Enter a vertex: ");
|
|
Integer vertex = Integer.parseInt(System.console().readLine());
|
|
System.out.println("Enter a second vertex: ");
|
|
Integer vertex2 = Integer.parseInt(System.console().readLine());
|
|
HashMap<Integer, Pair<Integer, Integer>> distances = this.graph.shortestPath(vertex, vertex2);
|
|
System.out.println("Distance from " + vertex + " to " + vertex2 + ": " + distances.get(vertex2).second);
|
|
System.out.println("Path: ");
|
|
if(this.graph.path(vertex, vertex2).isEmpty()){
|
|
System.out.println("No path");
|
|
break;
|
|
}
|
|
for(Iterator<Integer> path = this.graph.path(vertex, vertex2).iterator(); path.hasNext();){
|
|
Integer p = path.next();
|
|
System.out.print(p);
|
|
System.out.print(" ");
|
|
}
|
|
System.out.println();
|
|
break;
|
|
}
|
|
case 21:{
|
|
System.out.println("Enter a vertex: ");
|
|
Integer vertex = Integer.parseInt(System.console().readLine());
|
|
System.out.println("Enter a second vertex: ");
|
|
Integer vertex2 = Integer.parseInt(System.console().readLine());
|
|
ArrayList<Integer> path = this.graph.costPathDynamic(vertex, vertex2);
|
|
if(path.isEmpty()){
|
|
System.out.println("No path");
|
|
break;
|
|
}
|
|
System.out.println("Path: ");
|
|
for(Iterator<Integer> p = path.iterator(); p.hasNext();){
|
|
Integer v = p.next();
|
|
System.out.print(v);
|
|
System.out.print(" ");
|
|
}
|
|
Integer cost = 0;
|
|
for(Integer i=0; i<path.size()-1; i++){
|
|
cost += this.graph.weight(path.get(i), path.get(i+1));
|
|
}
|
|
System.out.println();
|
|
System.out.println("Cost: " + cost);
|
|
break;
|
|
}
|
|
case 22:{
|
|
ArrayList<Integer> topologicSort = this.graph.TopoSort();
|
|
if(topologicSort == null){
|
|
System.out.println("Graph is not a DAG");
|
|
break;
|
|
}
|
|
System.out.println("Topological Sort: ");
|
|
for(Iterator<Integer> vertex = topologicSort.iterator(); vertex.hasNext();){
|
|
Integer v = vertex.next();
|
|
System.out.print(v);
|
|
System.out.print(" ");
|
|
}
|
|
System.out.println();
|
|
break;
|
|
}
|
|
case 23:{
|
|
System.out.println("Enter a vertex: ");
|
|
Integer vertex = Integer.parseInt(System.console().readLine());
|
|
System.out.println("Enter a second vertex: ");
|
|
Integer vertex2 = Integer.parseInt(System.console().readLine());
|
|
ArrayList<Integer> path = this.graph.highestCostPathDAG(vertex, vertex2);
|
|
if(path == null || path.isEmpty()){
|
|
System.out.println("No path");
|
|
break;
|
|
}
|
|
System.out.println("Path: ");
|
|
for(Iterator<Integer> p = path.iterator(); p.hasNext();){
|
|
Integer v = p.next();
|
|
System.out.print(v);
|
|
System.out.print(" ");
|
|
}
|
|
Integer cost = 0;
|
|
for(Integer i=0; i<path.size()-1; i++){
|
|
cost += this.graph.weight(path.get(i), path.get(i+1));
|
|
}
|
|
System.out.println();
|
|
System.out.println("Cost: " + cost);
|
|
break;
|
|
}
|
|
|
|
case 0:{
|
|
System.exit(0);
|
|
}
|
|
default: {
|
|
System.out.println("Invalid option");
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|