I have a nearly fully functional program but I am not able to format the output correctly. I am in desperate need of help as my project is past due already.
I am a student working on a program that reads in a simple text file and creates a graph object of nodes from the input file. I am then, supposed to use a heap class to build the nodes into a Min-heap. Finally I am supposed to call a heap sort method to sort the nodes (preferably in descending order)
I believe that my methods are correct and that my data is being correctly built into a min heap and is being correctly sorted. The only problem I am having is formatting the output which should be simple but for some reason isn't. The idea is this:
my graph object contains 2 arrayLists the first is the unordered node list that was created from the input text file. The second is a blank arrayList that I am trying to copy nodes one at a time.
I am trying to use a for loop or a while loop to first copy one single node into the empty ArrayList then call my build heap method to build a Min heap of only 1 element, then call my sort method to sort the heap of 1 element. Then, I want to copy in a second node and again build a min heap of 2 elements and then call my sort method on the 2 element heap. Then, copy in a third node and build the heap with 3 nodes, and then call the sort on the 3 element heap, and so on and so forth until all elements have been copied into the array list and the full heap is built and the sort method is called on all elements.
My 3 element test file looks like this:
~ val X Y Z
Xerxes 0 ~ ~ ~
York -1 ~ ~ ~
Zardoz 1 ~ ~ ~
My 6 element test file looks like this:
~ val A B C D E F
Alfa 4 ~ ~ ~ ~ ~ ~
Bravo 6 ~ ~ ~ ~ ~ ~
Charlie -3 ~ ~ ~ ~ ~ ~
Delta -6 ~ ~ ~ ~ ~ ~
Echo 0 ~ ~ ~ ~ ~ ~
Foxtrot 55 ~ ~ ~ ~ ~ ~
the output should look something like this:
Heaps:
X
YX
YXZ
HeapSort:
YXZ
XZY
ZXY
I am using several "test" files including one with 3 elements and one with 6 elements.
My classes are as follows:
import java.io.*;
public class DelivB {
File inputFile;
File outputFile;
PrintWriter output;
Graph g;
public DelivB( File in, Graph gr ) {
inputFile = in;
g = gr;
// Get output file name.
String inputFileName = inputFile.toString();
String baseFileName = inputFileName.substring( 0, inputFileName.length()-4 ); // Strip off ".txt"
String outputFileName = baseFileName.concat( "_out.txt" );
outputFile = new File( outputFileName );
if ( outputFile.exists() ) { // For retests
outputFile.delete();
}
try {
output = new PrintWriter(outputFile);
writeGraphInfo(output);
//System.out.println("=============================\n" + "testing testing testing Deliv B Class");
}
catch (Exception x ) {
System.err.format("Exception: %s%n", x);
System.exit(0);
}
//System.out.println( "DelivB: To be implemented");
//System.out.println("\nDeliv B Class ++++++++++++++++++++++++++++++++++");
}
public Graph getG() {
return g;
}
public void setG(Graph g) {
this.g = g;
}
/** Read the file containing the Strings, line by line, then process each line as it is read.
**/
public void writeGraphInfo( PrintWriter output ) {
try {
// output the graph information.
// I chose to output it to the console as well as the file for debugging purposes.
System.out.println( "\n\n=========================================================================\n\n");
System.out.println( g );
output.println( g );
}
catch (Exception x ) {
System.err.format("ExceptionInner: %s%n", x);
System.exit(0);
}
output.close();
}
}
// NEXT CLASS
//===================================================
import java.util.*;
// A node of a graph for the Spring 2018 ICS 340 program
public class Node {
String name;
String val; // The value of the Node
String abbrev; // The abbreviation for the Node
ArrayList<Edge> outgoingEdges;
ArrayList<Edge> incomingEdges;
public Node( String theAbbrev ) {
setAbbrev( theAbbrev );
val = null;
name = null;
outgoingEdges = new ArrayList<Edge>();
incomingEdges = new ArrayList<Edge>();
}
public String getAbbrev() {
return abbrev;
}
public String getName() {
return name;
}
public String getVal() {
return val;
}
public ArrayList<Edge> getOutgoingEdges() {
return outgoingEdges;
}
public ArrayList<Edge> getIncomingEdges() {
return incomingEdges;
}
public void setAbbrev( String theAbbrev ) {
abbrev = theAbbrev;
}
public void setName( String theName ) {
name = theName;
}
public void setVal( String theVal ) {
val = theVal;
}
public void addOutgoingEdge( Edge e ) {
outgoingEdges.add( e );
}
public void addIncomingEdge( Edge e ) {
incomingEdges.add( e );
}
}
//NEXT CLASS ==================================================
//import java.util.*;
// Edge between two nodes
public class Edge {
String label;
Node tail;
Node head;
public Edge( Node tailNode, Node headNode, String theLabel ) {
setLabel( theLabel );
setTail( tailNode );
setHead( headNode );
}
public String getLabel() {
return label;
}
public Node getTail() {
return tail;
}
public Node getHead() {
return head;
}
public void setLabel( String s ) {
label = s;
}
public void setTail( Node n ) {
tail = n;
}
public void setHead( Node n ) {
head = n;
}
}
//NEXT CLASS ===================================================
import java.util.*;
public class Heap
{
int heapSize;
Graph gr;
ArrayList<Node> unordered_nodelist;
ArrayList<Node> ordered_nodelist;
Node dummy = new Node("dummy node");
//constructor for heap object with the following attributes:
//a graph object and an int representing the size of an arraylist of nodes
public Heap(Graph g)
{
unordered_nodelist = g.getNodeList();
heapSize = unordered_nodelist.size();
ordered_nodelist = new ArrayList<Node>();
//for (int i = 0; i < heapSize; i++)
//ordered_nodelist.add(dummy);
//probably don't need this graph variable
gr = g;
}
//getters and setters
public ArrayList<Node> getUnordered_nodelist() {
return unordered_nodelist;
}
public void setUnordered_nodelist(ArrayList<Node> unordered_nodelist) {
this.unordered_nodelist = unordered_nodelist;
}
public ArrayList<Node> getOrdered_nodelist() {
return ordered_nodelist;
}
public void setOrdered_nodelist(ArrayList<Node> ordered_nodelist) {
this.ordered_nodelist = ordered_nodelist;
}
public int getHeapSize() {
return heapSize;
}
public void setHeapSize(int heapSize) {
this.heapSize = heapSize;
}
//heap methods
public int Parent(ArrayList<Node> A, int i)
{
//if (i == 1)
//return (Integer)null;
if (i%2 != 0)
return i/2;
else
return (i-1)/2;
}
public int Left(ArrayList<Node> A, int i)
{
//while (A.get(i).getVal() != null && A.get(i).getName() != null)
//{
//if (2*i < heapSize)
return (2*i)+1;
//else
//return (Integer)null;
//}
}
public int Right(ArrayList<Node> A, int i)
{
//if ((2*i)+1 < heapSize)
return 2*i+2;
//else
//return (Integer)null;
}
public void Heapify(ArrayList<Node> A, int i)
{
Node smallest;
Node temp;
int index;
int l = Left(A,i);
int r = Right(A,i);
while (A.get(i).getVal() != null && A.get(i).getName() != null)
{
if (l <= heapSize-1 && Integer.parseInt(A.get(l).getVal()) < Integer.parseInt(A.get(i).getVal()))
{
//left child is smaller
smallest = A.get(l);
index = l;
}
else
{
//parent node is smaller
smallest = A.get(i);
index = i;
}
if (r <= heapSize-1 && Integer.parseInt(A.get(r).getVal()) < Integer.parseInt(smallest.getVal()))
{
//right child is smaller
smallest = A.get(r);
index = r;
}
if (index != i)
{
//if the smallest element is not the parent node
//swap the smallest child with the parent
temp = A.get(i);
A.set(i, A.get(index));
A.set(index, temp);
//recursively call heapify method to check next parent/child relationship
Heapify(A, index);
}
}
}
//method to construct min heap from unordered arraylist of nodes
public void Build_min_Heap(ArrayList<Node> A)
{
for (int k = 0; k<A.size()-1; k++)
{
//while (A.get(k).getVal() != null && A.get(k).getName() != null)
//{
int i;
int heapSize = A.size();
for (i = (heapSize/2); i>=0; i--)
{
Heapify(A, i);
System.out.print(gr.toString2()+"\n");
}
//}
}
}
//decreases the value of a given node, used with insert method
public void heap_Decrease_Key(ArrayList<Node> A, int i, int key)
{
Node parent;
Node child;
Node temp;
if (key > i)
{
System.out.println("error key must be less than i");
//break;
}
A.get(i).setVal(Integer.toString(key));
while(i>0 && Integer.parseInt(A.get(Parent(A,i)).getVal()) > Integer.parseInt(A.get(i).getVal()) )
{
parent = A.get(Parent(A,i));
child = A.get(i);
temp = parent;
//take the child node and place it in the parent node's place
A.set(Parent(A,i), child);
//take the parent node and place it in the child node's place
A.set(i, temp);
}
}
//method to sort in descending order, a min heap
public void heap_Sort(ArrayList<Node> A)
{
Node temp;
for (int k = 0; k<A.size()-1; k++)
{
//while (A.get(k).getVal() != null && A.get(k).getName() != null)
//{
Build_min_Heap(A);
System.out.println(gr.toString2()+"\n");
for(int i = A.size()-1; i >= 1; i--)
{
//exchange a[1] with a[i]
temp = A.get(0);
A.set(0, A.get(i));
A.set(i, temp);
//decrement heapSize
heapSize--;
//recursive heapify call
Heapify(A, 0);
}
//}
}
}
public Node heap_Extract(ArrayList<Node> A)
{
Node min;
min = A.get(0);
A.set(0, A.get(heapSize-1));
//decrement heapSize
heapSize--;
Heapify(A, 0);
return min;
}
public void heap_Insert(ArrayList<Node> A, int key)
{
heapSize++;
A.get(heapSize-1).setVal(Integer.toString(2147483647));
heap_Decrease_Key(A, heapSize-1, key);
}
public String toString()
{
String s = "Graph g.\n";
//s += "Heaps: \n";
if ( ordered_nodelist.size() > 0 )
{
//for loop to traverse an ArrayList of Nodes
for(Node n : ordered_nodelist)
{
//output string to print each node's character abbreviation
String t = n.getAbbrev();
s = s.concat(t);
}
}
return s;
}
}
//NEXT CLASS =================================================
import java.util.*;
public class Heap
{
int heapSize;
Graph gr;
ArrayList<Node> unordered_nodelist;
ArrayList<Node> ordered_nodelist;
Node dummy = new Node("dummy node");
//constructor for heap object with the following attributes:
//a graph object and an int representing the size of an arraylist of nodes
public Heap(Graph g)
{
unordered_nodelist = g.getNodeList();
heapSize = unordered_nodelist.size();
ordered_nodelist = new ArrayList<Node>();
//for (int i = 0; i < heapSize; i++)
//ordered_nodelist.add(dummy);
//probably don't need this graph variable
gr = g;
}
//getters and setters
public ArrayList<Node> getUnordered_nodelist() {
return unordered_nodelist;
}
public void setUnordered_nodelist(ArrayList<Node> unordered_nodelist) {
this.unordered_nodelist = unordered_nodelist;
}
public ArrayList<Node> getOrdered_nodelist() {
return ordered_nodelist;
}
public void setOrdered_nodelist(ArrayList<Node> ordered_nodelist) {
this.ordered_nodelist = ordered_nodelist;
}
public int getHeapSize() {
return heapSize;
}
public void setHeapSize(int heapSize) {
this.heapSize = heapSize;
}
//heap methods
public int Parent(ArrayList<Node> A, int i)
{
//if (i == 1)
//return (Integer)null;
if (i%2 != 0)
return i/2;
else
return (i-1)/2;
}
public int Left(ArrayList<Node> A, int i)
{
//while (A.get(i).getVal() != null && A.get(i).getName() != null)
//{
//if (2*i < heapSize)
return (2*i)+1;
//else
//return (Integer)null;
//}
}
public int Right(ArrayList<Node> A, int i)
{
//if ((2*i)+1 < heapSize)
return 2*i+2;
//else
//return (Integer)null;
}
public void Heapify(ArrayList<Node> A, int i)
{
Node smallest;
Node temp;
int index;
int l = Left(A,i);
int r = Right(A,i);
while (A.get(i).getVal() != null && A.get(i).getName() != null)
{
if (l <= heapSize-1 && Integer.parseInt(A.get(l).getVal()) < Integer.parseInt(A.get(i).getVal()))
{
//left child is smaller
smallest = A.get(l);
index = l;
}
else
{
//parent node is smaller
smallest = A.get(i);
index = i;
}
if (r <= heapSize-1 && Integer.parseInt(A.get(r).getVal()) < Integer.parseInt(smallest.getVal()))
{
//right child is smaller
smallest = A.get(r);
index = r;
}
if (index != i)
{
//if the smallest element is not the parent node
//swap the smallest child with the parent
temp = A.get(i);
A.set(i, A.get(index));
A.set(index, temp);
//recursively call heapify method to check next parent/child relationship
Heapify(A, index);
}
}
}
//method to construct min heap from unordered arraylist of nodes
public void Build_min_Heap(ArrayList<Node> A)
{
for (int k = 0; k<A.size()-1; k++)
{
//while (A.get(k).getVal() != null && A.get(k).getName() != null)
//{
int i;
int heapSize = A.size();
for (i = (heapSize/2); i>=0; i--)
{
Heapify(A, i);
System.out.print(gr.toString2()+"\n");
}
//}
}
}
//decreases the value of a given node, used with insert method
public void heap_Decrease_Key(ArrayList<Node> A, int i, int key)
{
Node parent;
Node child;
Node temp;
if (key > i)
{
System.out.println("error key must be less than i");
//break;
}
A.get(i).setVal(Integer.toString(key));
while(i>0 && Integer.parseInt(A.get(Parent(A,i)).getVal()) > Integer.parseInt(A.get(i).getVal()) )
{
parent = A.get(Parent(A,i));
child = A.get(i);
temp = parent;
//take the child node and place it in the parent node's place
A.set(Parent(A,i), child);
//take the parent node and place it in the child node's place
A.set(i, temp);
}
}
//method to sort in descending order, a min heap
public void heap_Sort(ArrayList<Node> A)
{
Node temp;
for (int k = 0; k<A.size()-1; k++)
{
//while (A.get(k).getVal() != null && A.get(k).getName() != null)
//{
Build_min_Heap(A);
System.out.println(gr.toString2()+"\n");
for(int i = A.size()-1; i >= 1; i--)
{
//exchange a[1] with a[i]
temp = A.get(0);
A.set(0, A.get(i));
A.set(i, temp);
//decrement heapSize
heapSize--;
//recursive heapify call
Heapify(A, 0);
}
//}
}
}
public Node heap_Extract(ArrayList<Node> A)
{
Node min;
min = A.get(0);
A.set(0, A.get(heapSize-1));
//decrement heapSize
heapSize--;
Heapify(A, 0);
return min;
}
public void heap_Insert(ArrayList<Node> A, int key)
{
heapSize++;
A.get(heapSize-1).setVal(Integer.toString(2147483647));
heap_Decrease_Key(A, heapSize-1, key);
}
public String toString()
{
String s = "Graph g.\n";
//s += "Heaps: \n";
if ( ordered_nodelist.size() > 0 )
{
//for loop to traverse an ArrayList of Nodes
for(Node n : ordered_nodelist)
{
//output string to print each node's character abbreviation
String t = n.getAbbrev();
s = s.concat(t);
}
}
return s;
}
}
//NEXT CLASS ===============================================
import java.util.*;
public class Graph {
ArrayList<Node> nodeList;
ArrayList<Edge> edgeList;
public Graph() {
nodeList = new ArrayList<Node>();
edgeList = new ArrayList<Edge>();
}
public ArrayList<Node> getNodeList() {
return nodeList;
}
public ArrayList<Edge> getEdgeList() {
return edgeList;
}
public void addNode( Node n ) {
nodeList.add( n );
}
public void addEdge( Edge e ) {
edgeList.add( e );
}
//overridden toString() method to output both Nodes and the edges incumbent upon them
public String toString() {
String s = "Graph g.\n";
if ( nodeList.size() > 0 ) {
//for loop to traverse an ArrayList of Nodes
for( Node n : nodeList ) {
//output string to print basic labels for each node
String t = "\nNode " + n.getName() + ", abbrev " + n.getAbbrev() + ", value " + n.getVal() + "\n";
s = s.concat(t);
//for loop to traverse an ArrayList of outgoing Edges incumbent upon
//the given node in each iteration of the outer for loop
for(Edge a : n.getOutgoingEdges()){
//output String to print data about each outgoing edge
String q = n.getName() + " has edge to: " + a.getHead().getName() + " labeled: " + a.getLabel() + "\n";
s = s.concat(q);
}
//for loop to traverse an ArrayList of incomming Edges incumbent upon
//the given node in each iteration of the outer for loop
for(Edge a : n.getIncomingEdges()){
//output string to print data about each incomming edge
String r = n.getName() + " has edge from: " + a.getTail().getName() + " labeled: " + a.getLabel() + "\n";
s = s.concat(r);
}
}
s = s.concat("\n");
}
return s;
}
public String toString2()
{
String s = "Graph g.\n";
if ( nodeList.size() > 0 )
{
//for loop to traverse an ArrayList of Nodes
for( Node n : nodeList )
{
//output string to print each node's mnemonic
String t = n.getAbbrev();
s = s.concat(t);
}
}
return s;
}
}
//NEXT CLASS ==============================================
import javax.swing.*;
import java.io.*;
import java.util.*;
import java.awt.*;
import java.awt.event.*;
/** ProgramA simply reads a file containing rows of space-separated Strings,
** your assignment is to print out those strings interpreted as a graph.
**
** @author
** Mike Stein
**/
public class Prog340 extends JPanel implements ActionListener {
private static final long serialVersionUID = 1L; // Keep Eclipse happy.
File inputFile;
File outputFile;
PrintWriter output;
JFileChooser fileChooser;
Graph g;
Heap h;
String[] comboBoxList; // For putting names in Combo Box
/** The main method instantiates a Prog340 class, which includes giving you a choice of things to do.
** The only one active now will be reading the graph file and having you parse it.
**
** @param args
** - Not used
**
** @throws FileNotFoundException
** - Thrown if the file selected is not found. Shouldn't happen with a FileChooser.
**/
public static void main(String[] args) throws FileNotFoundException {
javax.swing.SwingUtilities.invokeLater(new Runnable() {
public void run() {
createAndShowGUI();
}
});
}
/** Create and show the GUI.
** For thread safety, this method should be invoked from the event-dispatching thread.
**/
private static void createAndShowGUI() {
// Create and set up the window
JFrame frame = new JFrame("Prog340");
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
// Create and set up the content pane.
JComponent newContentPane = new Prog340();
newContentPane.setOpaque(true);; // content panes must be opaque
frame.setContentPane(newContentPane);;
// Display the window.
frame.pack();
frame.setVisible(true);
}
/** The constructor creates a new ProgramA object, and sets up the input and output files.
**/
public Prog340() {
super( new BorderLayout() );
try {
// I like the colorful FileChooser.
UIManager.setLookAndFeel(UIManager.getSystemLookAndFeelClassName());
System.out.println( "Look and feel set.");
}
catch (Exception e) { // exit on exception.
System.err.format("Exception: %s%n", e);
System.exit(0);
}
fileChooser = new JFileChooser();
fileChooser.setDialogTitle("Choose a file");
// Start looking for files at the currect directory, not home.
fileChooser.setCurrentDirectory(new File("."));
inputFile = null;
g = new Graph();
// Select the action
comboBoxList = new String[8];
comboBoxList[0] = new String("prog340: Select file and read graph");
comboBoxList[1] = new String("Deliv A: Write Graph Info");
comboBoxList[2] = new String ("Deliv B: Run Heap methods on selected file");
comboBoxList[3] = new String ("Deliv C: TBD");
comboBoxList[4] = new String ("Deliv D: TBD");
comboBoxList[5] = new String ("Deliv E: TBD");
comboBoxList[6] = new String ("Deliv F: TBD");
comboBoxList[7] = new String ("exit");
JComboBox actionList = new JComboBox( comboBoxList );
actionList.setName("Action List");
actionList.setSelectedIndex(0);
actionList.addActionListener( this );
add( actionList, BorderLayout.PAGE_START );
}
// Listen to the Combo Box
public void actionPerformed( ActionEvent e ) {
JComboBox cb = (JComboBox)e.getSource();
String actionName = (String)cb.getSelectedItem();
int actionIndex = cb.getSelectedIndex();
switch( actionIndex ) {
case 0:{
g = new Graph();
readGraphInfo( g );
break;
}
case 1:
DelivA dA = new DelivA( inputFile, g );
break;
case 2:
{
int numElements = 1;
int j =0;
int k;
//rewritten switch statement case to make DelivB combo box work
g = new Graph();
readGraphInfo( g );
DelivB dB = new DelivB(inputFile, g);
h = new Heap(g);
System.out.println("unordered list: \n");
System.out.println(g.toString());
System.out.println("==========================================");
//h.Build_min_Heap(h.getOrdered_nodelist());
for (j = 0; j <= h.getHeapSize(); j++)
//while (j <= h.getHeapSize())
//for (Node n : h.getOrdered_nodelist())
{
//copy node elements from unordered arraylist to new empty arraylist
h.getOrdered_nodelist().add(h.getUnordered_nodelist().get(j));
System.out.println("unordered node list size is: " + h.getUnordered_nodelist().size()+ "\n");
System.out.println("ordered node list size is: " + h.getOrdered_nodelist().size());
System.out.println("\nvalue of j is: " + j + "\n");
System.out.println("Heaps: \n");
h.Build_min_Heap(h.getOrdered_nodelist());
System.out.println("after build heap call: \n" );
System.out.println(h.toString());
//System.out.println("\ngraph class toString method: \n");
//System.out.println(g.toString() + "\n");
//System.out.println(g.toString2());
System.out.println("HeapSort: \n");
h.heap_Sort(h.getOrdered_nodelist());
System.out.println("after heapsort call: \n");
System.out.println(h.toString());
j++;
//System.out.println("\n graph class toString method: \n");
//System.out.println(g.toString() + "\n");
//System.out.println(g.toString2());
//System.out.println("the"+j+"th element in the original array is: \n"+h.getOrdered_nodelist().get(j).getAbbrev());
//System.out.println("the"+j+"th element in the new array is: \n"+h.getUnordered_nodelist().get(j).getAbbrev());
//System.out.println("\n after build heap method call, the output is as follows: " + g.toString());
}
break;
}
case 3:
DelivC dC = new DelivC( inputFile, g );
break;
case 4:
DelivD dD = new DelivD( inputFile, g );
break;
case 5:
DelivE dE = new DelivE( inputFile, g );
break;
case 6:
DelivF dF = new DelivF( inputFile, g );
break;
case 7:
System.out.println( "Goodbye");
System.exit(0);
default:
System.out.println( "Invalid choice" );
System.exit(0);
}
}
/** Read the file containing the Strings, line by line, then process each line as it is read.
**/
public void readGraphInfo( Graph g ) {
try {
if (fileChooser.showOpenDialog(null) == JFileChooser.APPROVE_OPTION) {
// Instantiate the selected input and output files.
inputFile = fileChooser.getSelectedFile();
System.out.println( "Chosen file = " + inputFile + "\n");
}
// read text file
Scanner sc = new Scanner( inputFile );
// First line special: It contains "~", and "val", and the nodes with the edges.
String firstLine = sc.nextLine();
String[] splitString = firstLine.split( " +" );
// Ignore first two fields of first line, Every other field is a node.
for ( int i = 2; i < splitString.length; i++ ) {
Node n = new Node( splitString[i] );
g.addNode( n );
}
// Every other line gives the name and value of the Node, and any edges.
int nodeIndex = 0;
ArrayList<Node> nodeList = g.getNodeList();
while ( sc.hasNextLine() ) {
String nextLine = sc.nextLine();
splitString = nextLine.split(" +");
Node n = nodeList.get( nodeIndex );
n.setName( splitString[0] );
n.setVal( splitString[1] );
for ( int i = 2; i < splitString.length; i++ ) {
if ( !splitString[i].equals("~") ) {
Node head = nodeList.get(i-2);
Edge e = new Edge( n, head, splitString[i] );
g.addEdge( e );
n.addOutgoingEdge( e );
head.addIncomingEdge( e );
}
}
nodeIndex++;
}
sc.close();
}
catch (Exception x) {
System.err.format("ExceptionOuter: %s%n", x);
}
}
}