Hello, I\'m suppose to do a Java program (using Netbeans IDE) that involes the a

ID: 3603265 • Letter: H

Question

Hello, I'm suppose to do a Java program (using Netbeans IDE) that involes the augmentation of an adjacency list implementaation of a weighted digraph ADT and the completion of a menu-driven application that uses the ADT. The project involves writing both ADT and client functions (methods) to perform various tasks. Some of the functions (methods) have already been written, which you will see with the provided code. So you will simply have to properly call them. After the project is completed, menu options 1-6 should work. A simplifying assumption is that the wieghts on the edges are non-negative real numbers. The program will have the following text-based user interface as shown below:

When option 1 is selected, the application should generate an incidence matrix of the input simple undirected graph. This option will require completion of the isEdge and countEdges functions (methods). When option 2 is selected, the transistive closure matrix should be generated. This will require the implementation of the isPath function (method). Once you implement the dijkstra non-member function (method), you will be able to execute the third menu option. Both traversal functions (methods) have already been implemented as shown in the provided code. To get options 4 and 5 of the user interface to work properly, you will neeed to invoke them correctly in the application. To get the sixth menu option to work, you will need to call the countEdges function (method). See files for the tasks you will need to complete.

The name of the executable file should be GraphDemo. The input weighted digraph file will be a variation on the DIMACS network flow format described below. DIMACS is the Center for Discrete Mathematics and Theoretical Computer Science based at Rutgers University. The input file is described below:

The input file name is entered as a command line argument. For example, to run your application on a graph file called cities1.wdg, the file name is entered as a command line argument. The assumption is that file is in DIMACS format as described on this handout so no validation is done on the input file. The readGraph function (method) has already been implemented for you and it reads the file whose name you entered as a command line argument and creates a Graph instance. The name of the project should be called GraphDemo.

Below are the enclosed cities1.wdg, cities2.wdg, and the Java source files GraphException.java, GraphAPI.java, Graph.java, GraphDemo.java and City.java. Declare the GraphAPI.java as an interface, but declare the rest of the other source files as classes.

----------------------------------------------------------------------------------------------------

cities1.wdg

-----------------------------------------

cities2.wdg

------------------------------------------------------------------------------------

Graph.java

package graphdemo;
import java.util.ArrayList;
import java.util.function.Function;

/**
* Implementation of an extensible pointer-based adjacency
* list representation of a weighted digraph whose vertices
* hold objects that implement the Comparable interface.
* @param <E> the data type
* @author
* @since
*/
public class Graph<E extends Comparable<E>> implements GraphAPI<E>
{
/*
* number of vertices (size of this graph)
*/
private long order;
/**
* pointer to the list of vertices
*/
private Vertex first;

/**
* A vertex of a graph stores a data item and references
* to its edge list and the succeeding vertex. The data
* object extends the comparable interface.
*/
private class Vertex
{
/**
* pointer to the next vertex
*/
public Vertex pNextVertex;
/**
* the data item
*/
public E data;
/**
* indegree
*/
public long inDeg;
/**
* outdegree
*/
public long outDeg;
/**
* pointer to the edge list
*/
public Edge pEdge;
/**
* Field for tracking vertex accesses
*/
public long processed;
}

/**
* An edge of a graph contains a reference to the destination
* vertex, a reference to the succeeding edge in the edge list and
* the weight of the directed edge.
*/
private class Edge
{
/**
* pointer to the destination vertex
*/
public Vertex destination;
/**
* weight on this edge
*/
public Double weight;
/**
* pointer to the next edge
*/
public Edge pNextEdge;
}
/**
* Constructs an empty weighted directed graph
*/
public Graph()
{
first = null;
order = 0;
}

@Override
public void insertVertex(E obj)
{
Vertex newPtr;
Vertex locPtr;
Vertex predPtr;

newPtr = new Vertex();
newPtr.pNextVertex = null;
newPtr.data = obj;
newPtr.inDeg = 0;
newPtr.outDeg = 0;
newPtr.processed = 0;
newPtr.pEdge = null;

locPtr = first;
predPtr = null;
while (locPtr != null && obj.compareTo(locPtr.data) > 0)
{
predPtr = locPtr;
locPtr = locPtr.pNextVertex;
}
/*key already exist. */
if (locPtr != null && obj.compareTo(locPtr.data)==0)
{
locPtr.data = obj;
return;
}
/* insert before first vertex */
if (predPtr == null)
first = newPtr;
else
predPtr.pNextVertex = newPtr;
newPtr.pNextVertex = locPtr;
order++;
}

@Override
public void deleteVertex(E key)
{
Vertex predPtr;
Vertex walkPtr;
if (isEmpty())
return;
predPtr = null;
walkPtr = first;
while (walkPtr != null && key.compareTo(walkPtr.data) > 0)
{
predPtr = walkPtr;
walkPtr = walkPtr.pNextVertex;
}
if (walkPtr == null || key.compareTo(walkPtr.data) != 0)
return;
/* vertex found. Test degree */
if ((walkPtr.inDeg > 0) || (walkPtr.outDeg > 0))
return;
/* OK to delete */
if (predPtr == null)
first = walkPtr.pNextVertex;
else
predPtr.pNextVertex = walkPtr.pNextVertex;
order--;
}

@Override
public void insertEdge(E fromKey, E toKey, Double weight)
{
Edge tmpEdge;
Edge newEdge;
Edge pred;
Vertex tmpFrom;
Vertex tmpTo;

if (isEmpty())
return;
newEdge = new Edge();
/* check whether originating vertex exists */
tmpFrom = first;
while (tmpFrom != null && fromKey.compareTo(tmpFrom.data) > 0)
tmpFrom = tmpFrom.pNextVertex;
if (tmpFrom == null || fromKey.compareTo(tmpFrom.data) != 0)
return;
/* locate destination vertex */
tmpTo = first;
while (tmpTo != null && toKey.compareTo(tmpTo.data) > 0)
tmpTo = tmpTo.pNextVertex;
if (tmpTo == null || toKey.compareTo(tmpTo.data) != 0)
return;
/*check if edge already exists */
tmpEdge = tmpFrom.pEdge;
while (tmpEdge != null && tmpEdge.destination != tmpTo)
tmpEdge = tmpEdge.pNextEdge;
if (tmpEdge != null && tmpEdge.destination != null)
return;
tmpFrom.outDeg++;
tmpTo.inDeg++;
newEdge.destination = tmpTo;
newEdge.weight = weight;
newEdge.pNextEdge = null;
if (tmpFrom.pEdge == null)
{
tmpFrom.pEdge = newEdge;
return;
}
pred = null;
tmpEdge = tmpFrom.pEdge;
while (tmpEdge != null && tmpEdge.destination != tmpTo)
{
pred = tmpEdge;
tmpEdge = tmpEdge.pNextEdge;
}
if (pred == null)
tmpFrom.pEdge = newEdge;
else
pred.pNextEdge = newEdge;
newEdge.pNextEdge = tmpEdge;
}

@Override
public void deleteEdge(E fromKey, E toKey)
{
Edge tmpEdge;
Edge newEdge;
Edge pred;
Vertex tmpFrom;
Vertex tmpTo;
newEdge = new Edge();
/* find source vertex */
tmpFrom = first;
while (tmpFrom != null && fromKey.compareTo(tmpFrom.data)>0)
tmpFrom = tmpFrom.pNextVertex;
if (tmpFrom == null || fromKey.compareTo(tmpFrom.data) != 0)
return;
/* locate destination vertex */
tmpTo = first;
while (tmpTo != null && toKey.compareTo(tmpTo.data)>0)
tmpTo = tmpTo.pNextVertex;
if (tmpTo == null || toKey.compareTo(tmpTo.data) != 0)
return;
/*check if edge does not exist */
tmpEdge = tmpFrom.pEdge;
pred = null;
while (tmpEdge != null && tmpEdge.destination != tmpTo)
{
pred = tmpEdge;
tmpEdge = tmpEdge.pNextEdge;
}
/* if edge does not exist */
if (tmpEdge == null)
return;
/* update degrees */
if (pred != null)
pred.pNextEdge = tmpEdge.pNextEdge;
tmpFrom.outDeg--;
tmpTo.inDeg--;
}

@Override
public Double retrieveEdge(E fromKey, E toKey) throws GraphException
{
Edge tmpEdge;
Edge newEdge;
Edge pred;
Vertex tmpFrom;
Vertex tmpTo;
newEdge = new Edge();
/* find source vertex */
tmpFrom = first;
while (tmpFrom != null && fromKey.compareTo(tmpFrom.data)>0)
tmpFrom = tmpFrom.pNextVertex;
if (tmpFrom == null || fromKey.compareTo(tmpFrom.data) != 0)
throw new GraphException("Non-existent edge - retrieveEdge().");
/* locate destination vertex */
tmpTo = first;
while (tmpTo != null && toKey.compareTo(tmpTo.data)>0)
tmpTo = tmpTo.pNextVertex;
if (tmpTo == null || toKey.compareTo(tmpTo.data) != 0)
throw new GraphException("Non-existent edge - retrieveEdge().");
/*check if edge does not exist */
tmpEdge = tmpFrom.pEdge;
pred = null;
while (tmpEdge != null && tmpEdge.destination != tmpTo)
{
pred = tmpEdge;
tmpEdge = tmpEdge.pNextEdge;
}
/* if edge does not exist */
if (tmpEdge == null)
throw new GraphException("Non-existent edge - retrieveEdge().");
return tmpEdge.weight;
}

@Override
public E retrieveVertex(E key) throws GraphException
{
Vertex tmp;
if (isEmpty())
throw new GraphException("Non-existent vertex - retrieveVertex().");
tmp = first;
while (tmp != null && key.compareTo(tmp.data) != 0)
tmp = tmp.pNextVertex;
if (tmp == null)
throw new GraphException("Non-existent vertex - retrieveVertex().");
return tmp.data;
}

@Override
public void bfsTraverse(Function func)
{
if (isEmpty())
return;
Vertex walkPtr = first;
while (walkPtr != null)
{
walkPtr.processed = 0;
walkPtr = walkPtr.pNextVertex;
}
ArrayList<Vertex> queue = new ArrayList();
Vertex toPtr;
Edge edgeWalk;
Vertex tmp;
walkPtr = first;
while (walkPtr != null)
{
if (walkPtr.processed < 2)
{
if (walkPtr.processed < 1)
{
queue.add(walkPtr);
walkPtr.processed = 1;
}
}
while (!queue.isEmpty())
{
tmp = queue.remove(0);
func.apply(tmp.data);
tmp.processed = 2;
edgeWalk = tmp.pEdge;
while (edgeWalk != null)
{
toPtr = edgeWalk.destination;
if (toPtr.processed == 0)
{
toPtr.processed = 1;
queue.add(toPtr);
}
edgeWalk = edgeWalk.pNextEdge;
}
}
walkPtr = walkPtr.pNextVertex;
}
}

@Override
public void dfsTraverse(Function func)
{
if (isEmpty())
return;
Vertex walkPtr = first;
while(walkPtr != null)
{
walkPtr.processed = 0;
walkPtr = walkPtr.pNextVertex;
}
ArrayList<Vertex> stack = new ArrayList();
Vertex toPtr;
Edge edgeWalk;
Vertex tmp;
walkPtr = first;
while (walkPtr != null)
{
if (walkPtr.processed < 2)
{
if (walkPtr.processed < 1)
{
walkPtr.processed = 1;
stack.add(0,walkPtr);
}
while (!stack.isEmpty())
{
tmp = stack.get(0);
edgeWalk = tmp.pEdge;
while(edgeWalk != null)
{
toPtr = edgeWalk.destination;
if (toPtr.processed == 0)
{
toPtr.processed = 1;
stack.add(0,toPtr);
edgeWalk = toPtr.pEdge;
}
else
edgeWalk = edgeWalk.pNextEdge;
}
tmp = stack.remove(0);
func.apply(tmp.data);
tmp.processed = 2;
}
}
walkPtr = walkPtr.pNextVertex;
}
}

@Override
public boolean isEmpty()
{
return first == null;
}

@Override
public long size()
{
return order;
}

@Override
public boolean isVertex(E key)
{
Vertex tmp;
if (isEmpty())
return false;
tmp = first;
while (tmp != null && key.compareTo(tmp.data) != 0)
tmp = tmp.pNextVertex;
return tmp != null;
}

/* BEGIN: Augmented Private Auxiliary Methods */

@Override
public boolean isEdge(E fromKey, E toKey)
{
//implement this function
}

@Override
public boolean isPath(E fromKey, E toKey)
{
//implement this method
}

@Override
public long countEdges()
{
//implement this method
}

/* END: Augmented Private Auxiliary Methods */

@Override
public long outDegree(E key) throws GraphException
{
Vertex tmp;
if (isEmpty())
throw new GraphException("Non-existent vertex - outDegree().");
tmp = first;
while (tmp != null && key.compareTo(tmp.data) != 0)
tmp = tmp.pNextVertex;
if (tmp == null)
throw new GraphException("Non-existent vertex - outDegree().");
return tmp.outDeg;
}

@Override
public long inDegree(E key) throws GraphException
{
Vertex tmp;
if (isEmpty())
throw new GraphException("Non-existent vertex - inDegree().");
tmp = first;
while (tmp != null && key.compareTo(tmp.data) != 0)
tmp = tmp.pNextVertex;
if (tmp == null)
throw new GraphException("Non-existent vertex - inDegree().");
return tmp.inDeg;
}
}

-----------------------------------------------------------

GraphAPI.java

package graphdemo;

import java.util.function.Function;

/**
* Describes the fundamental operations of a weighted digraph.
* @param <E> the data type
* @author
* @since
*/
public interface GraphAPI<E extends Comparable>
{
/**
* This method inserts a new vertex whose data item is data in the
* weighted graph. If the key of the data already exists the vertex
* is updated. No two vertices may have the same key.
* @param data - data stored in a vertex.
*/
void insertVertex(E data);

/**
* This method deletes a vertex whose data item is data from the
* weighted graph. If the key of the data does not exist or the
* in-degree or out degree is positive, the weighted graph remains
* unaltered. It the data item exists and the in-degree
* and out-degree are both 0, the vertex is removed from the graph.
* @param key - data stored in a vertex.
*/
void deleteVertex(E key);

/**
* This method inserts a weighted directed edge between two vertices.
* If either key does not exist, the graph remains unaltered. If there
* is already a directed edge between the vertices, its weight is
* updated. If both keys exist and there isn't an edge between the
* vertices, an edge is inserted and the in-degree and out-degree of
* both vertices are updated.
* @param fromKey - data of the originating vertex.
* @param toKey - data of the destination vertex.
* @param weight - weight of the edge between the from and to
* vertices.
*/
void insertEdge(E fromKey, E toKey, Double weight);

/**
* This method removes a weighted directed edge between two vertices.
* If either key does not exist, the method returns and the graph
* remains unaltered. If the edge exists, it is removed from the vertex
* with fromKey to the vertex with toKey. The in-degree and out-degree
* of both vertices are updated.
* @param fromKey - search key of the originating vertex.
* @param toKey - search key of the destination vertex.
*/
void deleteEdge(E fromKey, E toKey);

/**
* This method returns the weight of the directed edge between
* the vertices with fromKey and toKey if the edge exists. If
* the directed edge does not exist, an exception is generated.
* @param fromKey - search key of the originating vertex.
* @param toKey - search key of the destination vertex.
* @return the weight on the edge
* @throws graphdemo.GraphException
*/
Double retrieveEdge(E fromKey, E toKey) throws GraphException;

/**
* This method returns the item stored in the vertex whose key
* is key. If the key does not exist, an exception is generated.
* @param key - search key of the vertex.
* @return
* @throws graphdemo.GraphException
*/
E retrieveVertex(E key) throws GraphException;

/**
* This method applies the visit function to the vertices of
* the graph in breadth-first-search order.
* @param func - the visit function.
*/
void bfsTraverse(Function func);

/**
* This method applies the visit function to the vertices of
* the graph in postorder depth-first-search order.
* @param func - the visit function.
*/
void dfsTraverse(Function func);

/**
* Determine whether the graph is empty.
* @return this function returns true if the graph is empty;
* otherwise, it returns false if the graph contains at least one node.
*/
boolean isEmpty();

/**
* Returns the order of graph.
* @return the number of vertices in the graph
*/
long size();

/**
* Determine whether an item is in the graph.
* @param key search key of the vertex.
* @return true on success; false on failure.
*/
boolean isVertex(E key);

/**
* Determines whether there is an edge between two vertices.
* @return true on success or false on failure.
* @param fromKey - search key of the originating vertex.
* @param toKey - search key of the destination vertex.
*/
boolean isEdge(E fromKey, E toKey);

/**
* Determines whether there is an outdirected path between two
* vertices.
* @param fromKey - search key of the originating vertex.
* @param toKey - search key of the destination vertex.
* @return true on success or false on failure.
*/
boolean isPath(E fromKey, E toKey);

/**
* Determines the number of edges in the graph.
* @return the number of edges.
*/
long countEdges();

/**
* Determines the number of out-directed edges from the vertex
* with the key.
* @param key
* @return out-degree.
* @throws graphdemo.GraphException when the vertex with the specified
* key does not exist
*/
long outDegree(E key) throws GraphException;

/**
* Determines the number of in-directed edges from the vertex
* with the key.
* @param key
* @return in-degree.
* @throws graphdemo.GraphException when the vertex with the specified key
* does not exist
*/
long inDegree(E key) throws GraphException;
}

----------------------------------------------------

GraphDemo.java

package graphdemo;

/**

* A testbed for methods of a weighted digraph and implementations of

* basic graph algorithms.

* @author

* @since

import java.io.*;

import java.util.*;

import java.util.concurrent.atomic.AtomicInteger;

import java.util.function.Function;

import java.util.Comparator;

import java.util.PriorityQueue;

public class GraphDemo

{

public static final Double INFINITY = Double.MAX_VALUE;

public static void main(String []args) throws GraphException

{

if (args.length != 1)

{

System.out.println("Usage: GraphDemo <filename>");

System.exit(1);

}

City c1, c2;

Scanner console;

int menuReturnValue, i,j;

Function<City,PrintStream> f = aCity -> System.out.printf("%-2d %-30s%n",aCity.getKey(),aCity.getLabel().trim());

Graph<City> g = readGraph(args[0]);

long s = g.size();

menuReturnValue = -1;

while (menuReturnValue != 0)

{

menuReturnValue = menu();

switch(menuReturnValue)

{

case 1: //Incidence Matrix

System.out.println();

System.out.println("Incidence Matrix For The Undirected Graph In "+args[0]);

System.out.println();

//Add code here to generate the incidence matrix of the graph

//End code

System.out.println();

break;

case 2: //Transitive Closure Matrix

System.out.println();

System.out.println("Transitive Closure Matrix For The Graph In "+args[0]);

System.out.println();

//Add code here to generate the transitive closure matrix

//End code

System.out.println();

break;

case 3://Dijkstra's Shortest-path algorithm

console = new Scanner(System.in);

System.out.printf("Enter the source vertex: ");

i = console.nextInt();

System.out.printf("Enter the destination vertex: ");

j = console.nextInt();

if (g.isPath(new City(i), new City(j)))

{

System.out.printf("Shortest route from %s to %s:%n",g.retrieveVertex(new City(i)).getLabel().trim(),g.retrieveVertex(new City(j)).getLabel().trim());

System.out.println("=========================================================================================");

double[] dist = new double[(int)g.size()];

int[] pred = new int[(int)g.size()];

//Add code here to print each leg of the trip from the source to the destination

//using the format below, where the columns are left-aligned and the distances

//are displayed to the nearest hundredths.

//For example:

//Baton Rouge -> Gonzales 10.20 mi

//Gonzales -> Metaire 32.00 mi

//Metaire -> New Orleans 7.25 mi

//End code

System.out.println("=========================================================================================");

System.out.printf("Total distance: %f miles.%n%n",dist[dest-1]);

}

else

System.out.printf("There is no path.%n%n");

break;

case 4: //post-order depth-first-search traversal

System.out.println();

System.out.println("PostOrder DFS Traversal For The Graph In "+args[0]);

System.out.println("==========================================================================");

//Add code here to invoke the dfsTraverse method using the function defined above

System.out.println("==========================================================================");

System.out.println();

break;

case 5: //breadth-first-search traversal

System.out.println();

System.out.println("BFS Traversal For The Graph In "+args[0]);

System.out.println("==========================================================================");

//Add code here to invoke the bfsTraverse method using the function defined above

System.out.println("==========================================================================");

System.out.println();

break;

case 6: //number of edges

System.out.println();

System.out.println("The graph has "+g.countEdges()+".");

System.out.println();

break;

case 7: //topoSort (project 4)

// System.out.println();

// System.out.println("Topological Sorting of The Graph In "+args[0]);

// System.out.println("==========================================================================");

// int[] top = new int[(int)g.size()];

// topoSort(g,top);

// for (i=1; i<=g.size(); i++)

// {

// c1 = g.retrieveVertex(new City(top[i-1]));

// f.apply(c1);

// }

// System.out.println("==========================================================================");

// System.out.printf("%n%n");

break;

case 8: //kruskalMST (project 4)

// int[] mstK = new int[(int)g.size()];

// double totalWt = kruskalMST(g,mstK);

// String cityNameA,cityNameB;

// for (i=1; i<=g.size(); i++)

// {

// if (mstK[i-1] == -1)

// cityNameA = "NONE";

// else

// cityNameA = g.retrieveVertex(new City(mstK[i-1])).getLabel().trim();

// cityNameB = g.retrieveVertex(new City(i)).getLabel().trim();

// System.out.printf("%d-%s parent[%d] <- %d (%s)%n",i,cityNameB,i,mstK[i-1],cityNameA);

// }

// System.out.printf("The weight of the minimum spanning tree/forest is %.2f miles.%n%n",totalWt);

break;

default: ;

} //end switch

}//end while

}//end main

/**

* This method reads a text file formatted as described in the project description.

* @param filename the name of the DIMACS formatted graph file.

* @return an instance of a graph.

private static Graph<City> readGraph(String filename)

{

try

{

Graph<City> newGraph = new Graph();

try (FileReader reader = new FileReader(filename))

{

char temp;

City c1, c2, aCity;

String tmp;

int k, m, v1, v2, j, size=0, nEdges=0;

Integer key, v1Key,v2Key;

Double weight;

Scanner in = new Scanner(reader);

while (in.hasNext())

{

tmp = in.next();

temp = tmp.charAt(0);

if (temp == 'p')

{

size = in.nextInt();

nEdges = in.nextInt();

}

else if (temp == 'c')

{

in.nextLine();

}

else if (temp == 'n')

{

key = in.nextInt();

tmp = in.nextLine();

aCity = new City(key,tmp);

newGraph.insertVertex(aCity);

}

else if (temp == 'e')

{

v1Key = in.nextInt();

v2Key = in.nextInt();

weight = in.nextDouble();

c1 = new City(v1Key);

c2 = new City(v2Key);

newGraph.insertEdge(c1,c2,weight);

}

return newGraph;

}

catch(IOException exception)

{

System.out.println("Error processing file: "+exception);

}

return null;

}

/**

* Display the menu interface for the application.

* @return the menu option selected.

private static int menu()

{

Scanner console = new Scanner(System.in);

int option;

{

System.out.println(" BASIC WEIGHTED GRAPH APPLICATION ");

System.out.println("=====================================");

System.out.println("[1] Incidence Matrix (undirected)");

System.out.println("[2] Transitive Matrix");

System.out.println("[3] Single-source Shortest Path");

System.out.println("[4] Postorder DFS Traversal");

System.out.println("[5] BFS Traversal");

System.out.println("[6] Number of Edges");

System.out.println("[7] Topological Sort Labeling");

System.out.println("[8] Kruskal's Minimal Spanning Tree");

System.out.println("[0] Quit");

System.out.println("=====================================");

System.out.printf("Select an option: ");

option = console.nextInt();

if (option < 0 || option > 8)

{

System.out.println("Invalid option...Try again");

System.out.println();

}

else

return option;

}while(true);

}

/**

* an auxiliary method for the topoSort method.

* @param g a weighted directed graph

* @param v current vertex

* @param seen a 1-D boolean matrix of vertices that

* have been marked.

* @param linearOrder a 1-D array containing the

* topologically sorted list.

* @param index current index.

// private static void dfsOut(Graph<City> g, int v, boolean seen[], int linearOrder[],AtomicInteger index) throws GraphException

// {

//implement this method (project 4)

// }

/**

* This method generates a listing of the vertices of a weighted

* directed graph using the reverse dfs topological sorting.

* @param g a weighted directed graph

* @param linearOrder an array in which the topologically sorted

* list is stored.

// private static void topoSort(Graph<City> g, int linearOrder[]) throws GraphException

// {

// //implement this method (project 4)

// }

/**

* auxilliary data structure to store the information

* about an edge for the MST algorithm

private static class EdgeType implements Comparable<EdgeType>

{

/**

* compares edge using weight as the primary key,

* source vertex as the secondary key and destination

* vertex as the tertiary key

* @param another a reference to an edge

* @return -1 when this edge comes before the specified

* edge, 0 if the edges are identical, otherwise 1

public int compareTo(EdgeType another)

{

if (weight < another.weight)

return -1;

if (weight > another.weight)

return 1;

if (source < another.source)

return -1;

if (source > another.source)

return 1;

if (destination < another.destination)

return -1;

if (destination > another.destination)

return 1;

return 0;

}

public double weight;

public int source;

public int destination;

public boolean chosen;

}

/**

* Find the root vertex of the tree in which the specified vertex is;

* for use in Kruskal's algorithm

* @param parent the parent implementation of a subtree of a graph

* @param v a vertex

* @return the root of this subtree

// private static int find(int[] parent, int v)

// {

// //implement this method (project 4)

// }

/**

* This method generates a minimum spanning tree using Kruskal's

* algorithm. If no such MST exists, then it generates a minimum spanning forest.

* @param g a weighted directed graph

* @param parent the parent implementation of the minimum spanning tree/forest

* @return the weight of such a tree or forest.

* @throws GraphException when this graph is empty

* <pre>

* {@code

* If a minimum spanning tree cannot be generated,

* the parent implementation of a minimum spanning tree or forest is

* determined. This implementation is based on the union-find stragey.

* }

* </pre>

// private static double kruskalMST(Graph<City> g, int [] parent) throws GraphException

// {

// //implement this method (project 4)

// }

/**

* This method computes the cost and path arrays using the

* Dijkstra's single-source shortest path greedy algorithm.

* @param g an instance of a weighted directed graph

* @param dist an array containing shortest distances from a source vertex

* @param pred an array containing predecessor vertices along the shortest path

* @throws GraphException on call to retrieveEdge on non-existent edge

private static void dijkstra(Graph<City> g, double[] dist, int[] pred, int source, int destination) throws GraphException

{

//Implement this method

}

------------------------------------------------

GraphException.java

package graphdemo;

/**
* @file GraphException.java
* @author
* @since
* Description: This class reports an exception for the weighted digraph implementation.
*/
public class GraphException extends Exception
{

/**
* Creates a new instance of <code>GraphException</code> without detail
* message.
*/
public GraphException()
{
super();
}

/**
* Constructs an instance of <code>GraphException</code> with the specified
* detail message.
* @param msg the detail message.
*/
public GraphException(String msg)
{
super(msg);
}
}

-----------------------------------------------------------------

City.java

package graphdemo;

/**
* Describes a city with a given name and unique integer identifier
* @author
* @since
*/
public class City implements Comparable<City>
{
/**
* name of label of the city
*/
private String label;
/**
* unique code for this city
*/
private Integer key;

/**
* Creates a city with the specified code and label
* @param aKey unique code for the city
* @param aLabel label for this city
*/
public City(Integer aKey, String aLabel)
{
label = aLabel;
key = aKey;
}

/**
* Creates an anonymous city with the specified code
* @param aKey code for the city
*/
public City(Integer aKey)
{
label = " ";
key = aKey;
}

/**
* Gives the label associated with this city
* @return the label of this city
*/
public String getLabel()
{
return label;
}

/**
* Gives the unique code for this city
* @return the code for this city
*/
public Integer getKey()
{
return key;
}

/**
* Compares the code for two cities
* @param another a reference to a city
* @return -1 when the key for this city comes after the
* specified city, 0 when the keys are identical, otherwise, 1.
*/
public int compareTo(City another)
{
return key.compareTo(another.key);
}
}

Explanation / Answer

private long order;
/**
* pointer to the list of vertices
*/
private Vertex first;

/**
* A vertex of a graph stores a data item and references
* to its edge list and the succeeding vertex. The data
* object extends the comparable interface.
*/
private class Vertex
{
/**
* pointer to the next vertex
*/
public Vertex pNextVertex;
/**
* the data item
*/
public E data;
/**
* indegree
*/
public long inDeg;
/**
* outdegree
*/
public long outDeg;
/**
* pointer to the edge list
*/
public Edge pEdge;
/**
* Field for tracking vertex accesses
*/
public long processed;
}

/**
* An edge of a graph contains a reference to the destination
* vertex, a reference to the succeeding edge in the edge list and
* the weight of the directed edge.
*/
private class Edge
{
/**
* pointer to the destination vertex
*/
public Vertex destination;
/**
* weight on this edge
*/
public Double weight;
/**
* pointer to the next edge
*/
public Edge pNextEdge;
}
/**
* Constructs an empty weighted directed graph
*/
public Graph()
{
first = null;
order = 0;
}

@Override
public void insertVertex(E obj)
{
Vertex newPtr;
Vertex locPtr;
Vertex predPtr;

newPtr = new Vertex();
newPtr.pNextVertex = null;
newPtr.data = obj;
newPtr.inDeg = 0;
newPtr.outDeg = 0;
newPtr.processed = 0;
newPtr.pEdge = null;

@Override
public boolean isEmpty()
{
return first == null;
}

@Override
public long size()
{
return order;
}

@Override
public boolean isPath(E fromKey, E toKey)
{
//implement this method
}

@Override
public long countEdges()
{
//implement this method
}

-----------------------------------------------------------

GraphAPI.java

package graphdemo;

import java.util.function.Function;

/**
* Describes the fundamental operations of a weighted digraph.
* @param <E> the data type
* @author
* @since
*/
public interface Grap

Navigate

Hello, I\'m studying for my bio lab practical and was given some practice proble

Hello, I\'m suppose to do an html/css project (and with the use of bootstrap) th

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Hello, I\'m suppose to do a Java program (using Netbeans IDE) that involes the a

Question

Explanation / Answer

Related Questions

Navigate