Hi, here is my semi-complete program, I have removed the methods that were irrelevant to make things simple. The program is supposed to represent Graphs, and minimal spanning trees. I first have to put edges in a priority queue of type : PQEntry (Below), which are to be sorted by their 'distance'. I have not included the interfaces as they weren't necessary here (all methods are already implemented). There is no compile error, but for example when I run the program, and enter 'mst' (it shoud print the contents of the Priority Queue in the order of their distances), it puts the first few elements in order but fails to do so on the remaining elements. below is a sample run.
graph> init
graph> mst
[(4 5) = 51
, (12 14) = 51
, (7 9) = 70
, (10 11) = 60
, (8 9) = 75
, (7 8) = 100
, (3 4) = 90
, (9 10) = 95
, (4 7) = 151
, (15 16) = 110
, (5 6) = 151
, (11 5) = 600
, (11 12) = 151
, (11 13) = 200
, (12 13) = 100
, (3 7) = 300
, (13 15) = 200
, (13 16) = 200
, (14 15) = 170
, (10 4) = 400
, (14 16) = 251
]
graph>
class PQEntry implements Comparable {
int node1 , node2 , distance;
public PQEntry(int node1 , int node2 , int distance) {
this.node1 = node1;
this.node2 = node2;
this.distance = distance;
}
public int getPriority () {
return distance;
}
public String toString() {
String output = "(" + node1 + " " + node2 + ")" + " = " + distance + "\n" ;
return output;
}
public int compareTo(Object o) {
if(o instanceof PQEntry){
if (getPriority() > ((PQEntry) o).getPriority()) {
return 1;
} else if(getPriority() == ((PQEntry) o).getPriority()) {
return 0;
} else {
return -1;
}
} else {
throw new IllegalArgumentException("o must be an instance of PQEntry");
}
}
}
import java.io.*;
import java.util.*;
class Main {
final static String PROMPT = "graph> ";
static private Graph myGraph = new GraphImp(51);
static void initGraph() {
myGraph.addEdge(3, 4, 90);
myGraph.addEdge(3, 7, 300);
myGraph.addEdge(4, 7, 151);
myGraph.addEdge(4, 5, 51);
myGraph.addEdge(5, 6, 151);
myGraph.addEdge(7, 8, 100);
myGraph.addEdge(7, 9, 70);
myGraph.addEdge(8, 9, 75);
myGraph.addEdge(9, 10, 95);
myGraph.addEdge(10, 4, 400);
myGraph.addEdge(10, 11, 60);
myGraph.addEdge(11, 5, 600);
myGraph.addEdge(11, 12, 151);
myGraph.addEdge(11, 13, 200);
myGraph.addEdge(12, 13, 100);
myGraph.addEdge(12, 14, 51);
myGraph.addEdge(13, 16, 200);
myGraph.addEdge(13, 15, 200);
myGraph.addEdge(14, 15, 170);
myGraph.addEdge(14, 16, 251);
myGraph.addEdge(15, 16, 110);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] input;
String line;
do {
System.out.print(PROMPT);
input = in.nextLine().split(" ");
if (input[0].equalsIgnoreCase("add")) {
if(input.length == 4){
if(!input[1].equals(input[2])) {
myGraph.addEdge(Integer.parseInt(input[1]), Integer.parseInt(input[2]), Integer.parseInt(input[3]));
} else {
System.out.println("Error! A node cannot connect to itself");
}
} else {
System.out.println("Incorrect command format, enter 3 seperate integers after 'add'");
}
} else if(input[0].equalsIgnoreCase("del")) {
if(input.length == 3) {
myGraph.deleteEdge(Integer.parseInt(input[1]), Integer.parseInt(input[2]));
} else {
System.out.println("Incorrect command format, enter two seperate intgers after 'del'");
}
} else if(input[0].equalsIgnoreCase("help") && input.length == 1) {
System.out.println("The available commands are: help, quit, add i j l, del i j, where 'i' is the source node, 'j' is the target node and the 'l' is the length of the edge between them");
} else if(input[0].equalsIgnoreCase("quit") && input.length == 1) {
System.exit(0);
} else if(input[0].equalsIgnoreCase("mst") && input.length == 1) {
int[][] tempMatrix = myGraph.getMatrix();
PriorityQueue<PQEntry> edges = new PriorityQueue<PQEntry>(51);
List<PQEntry> sortedEdges = new LinkedList<PQEntry>();
for(int i = 1; i < 51; i++) {
for(int j = 1; j < 51; j++){
if (tempMatrix[i][j] > 0) {
edges.add(new PQEntry(i, j, tempMatrix[i][j]));
}
}
}
sortedEdges.addAll(edges);
System.out.println(sortedEdges);
} else if(input[0].equalsIgnoreCase("print") && input.length == 1) {
System.out.println(myGraph.toString());
} else if(input[0].equalsIgnoreCase("init") && input.length == 1) {
initGraph();
} else {
System.out.println("unknown Command, enter help for lsit of valid commands");
}
} while(true);
}
}
import java.util.*;
class GraphImp implements Graph {
//contains a two-dimensional array to hold the start vertex, end vertex
//and the distance between the two verteces.
private int [][] matrix;
//constructor, sets the bounds of the two-dimensional array
public GraphImp(int size) {
matrix = new int[size][size];
}
//returns the two-dimensional array to the method calling it
public int[][] getMatrix() {
return matrix;
}
//this method first checks whether the two nodes are within the
//acceptable range and gives an erro if not. It then checks whether an edge exists between the nodes
//if an edge already exists it gives the user an error message, otherwise adds the edge
//to the two-dimensional array at the appropriate position.
public void addEdge(int node1 , int node2 , int distance) {
if(node1 > 0 || node1 < 51 || node2 > 0 || node2 < 51) {
if(matrix[node1][node2] == 0 && matrix[node2][node1] == 0) {
matrix[node1][node2] = distance;
} else {
System.out.println("Error! An edge already exists between the two nodes");
}
} else {
System.out.println("Error! Atleast one of the nodes are out of range, please enter within the range 1 - 51");
}
}
//This method first checks whether the two nodes are within the acceptable range
//if they are not an error message is given, otherwise it checks whether an edge exists
//between the nodes. If there already exists one is prints an error, otherwise it removes
//the corresponding edge.
public void deleteEdge(int node1 , int node2) {
if(node1 > 0 || node2 > 0 || node1 < 51 || node2 < 51) {
if(matrix[node1][node2] != 0 || matrix[node2][node1] != 0) {
matrix[node1][node2] = 0;
matrix[node2][node1] = 0;
} else {
System.out.println("Error! No such edge exists to delete");
}
} else {
System.out.println("Error! Atleast one of the nodes are out of range, please enter within the range 1 - 51");
}
}
//this method
public String toString()
{
String result = "";
for(int j = 0; j < matrix[0].length; j++){
for(int i = 0; i < matrix[0].length; i++){
if (matrix[j]
> 0){
result = result + "(" + j + "," + i + ")" + " = " + matrix[j][i] + "\n";
}
}
}
return result;
}