using java, design and code a reference based weighted graph class with vertices
ID: 3770860 • Letter: U
Question
using java, design and code a reference based weighted graph class with vertices stored in a linked list. your class should implement the following Weighted-GraphInterface.
//----------------------------------------------------------------------------
// WeightedGraphInterface.java by Dale/Joyce/Weems Chapter 9
//
// Interface for a class that implements a directed graph with weighted edges.
// Vertices are objects of class T and can be marked as having been visited.
// Edge weights are integers.
// Equivalence of vertices is determined by the vertices' equals method.
//
// General precondition: Except for the addVertex and hasVertex methods,
// any vertex passed as an argument to a method is in this graph.
//----------------------------------------------------------------------------
package ch09.graphs;
import ch05.queues.*;
public interface WeightedGraphInterface<T>
{
boolean isEmpty();
// Returns true if this graph is empty; otherwise, returns false.
boolean isFull();
// Returns true if this graph is full; otherwise, returns false.
void addVertex(T vertex);
// Preconditions: This graph is not full.
// Vertex is not already in this graph.
// Vertex is not null.
//
// Adds vertex to this graph.
boolean hasVertex(T vertex);
// Returns true if this graph contains vertex; otherwise, returns false.
void addEdge(T fromVertex, T toVertex, int weight);
// Adds an edge with the specified weight from fromVertex to toVertex.
int weightIs(T fromVertex, T toVertex);
// If edge from fromVertex to toVertex exists, returns the weight of edge;
// otherwise, returns a special “null-edge” value.
UnboundedQueueInterface<T> getToVertices(T vertex);
// Returns a queue of the vertices that are adjacent from vertex.
void clearMarks();
// Sets marks for all vertices to false.
void markVertex(T vertex);
// Sets mark for vertex to true.
boolean isMarked(T vertex);
// Returns true if vertex is marked; otherwise, returns false.
T getUnmarked();
// Returns an unmarked vertex if any exist; otherwise, returns null.
}
Explanation / Answer
import java.util.*;
public abstract class AbstractGraph implements Graph {
protected Object[] vertices; // Store vertices
protected List<Integer>[] neighbors; // Adjacency lists
/** Construct a graph from edges and vertices stored in arrays */
protected AbstractGraph(int[][] edges, Object[] vertices) {
this.vertices = vertices;
createAdjacencyLists(edges, vertices.length);
}
/** Construct a graph from edges and vertices stored in ArrayList */
protected AbstractGraph(List<Edge> edges, List vertices) {
this.vertices = vertices.toArray();
createAdjacencyLists(edges, vertices.size());
}
/** Construct a graph from edges and vertices in ArrayList */
protected AbstractGraph(List<Edge> edges, int numberOfVertices) {
vertices = new Integer[numberOfVertices]; // Create vertices
for (int i = 0; i < numberOfVertices; i++) {
vertices[i] = new Integer(i); // vertices is {0, 1, 2, ...}
}
createAdjacencyLists(edges, numberOfVertices);
}
/** Construct a graph from edges in array */
protected AbstractGraph(int[][] edges, int numberOfVertices) {
vertices = new Integer[numberOfVertices]; // Create vertices
for (int i = 0; i < numberOfVertices; i++) {
vertices[i] = new Integer(i); // vertices is {0, 1, 2, ...}
}
createAdjacencyLists(edges, numberOfVertices);
}
/** Create adjacency lists for each vertex */
private void createAdjacencyLists(
int[][] edges, int numberOfVertices) {
// Create a linked list
neighbors = new LinkedList[numberOfVertices];
for (int i = 0; i < numberOfVertices; i++) {
neighbors[i] = new java.util.LinkedList<Integer>();
}
for (int i = 0; i < edges.length; i++) {
int u = edges[i][0];
int v = edges[i][1];
neighbors[u].add(v);
825
}
}
/** Create adjacency lists for each vertex */
private void createAdjacencyLists(
List<Edge> edges, int numberOfVertices) {
// Create a linked list
neighbors = new LinkedList[numberOfVertices];
for (int i = 0; i < numberOfVertices; i++) {
neighbors[i] = new java.util.LinkedList<Integer>();
}
for (Edge edge: edges) {
neighbors[edge.u].add(edge.v);
}
}
/** Return the number of vertices in the graph */
public int getSize() {
return vertices.length;
}
/** Return the vertices in the graph */
public Object[] getVertices() {
return vertices;
}
/** Return the object for the specifed vertex */
public Object getVertex(int v) {
return vertices[v];
}
/** Return the index for the specified vertex object */
public int getIndex(Object vertex) {
for (int i = 0; i < getSize(); i++) {
if (vertex.equals(vertices[i])) {
return i;
}
}
return -1; // If vertex is not in the graph
}
/** Return the neighbors of vertex v */
public java.util.List getNeighbors(int v) {
return neighbors[v];
}
/** Return the degree for a specified vertex */
public int getDegree(int v) {
return neighbors[v].size();
}
/** Return the adjacency matrix */
public int[][] getAdjacencyMatrix() {
int[][] adjacencyMatrix = new int[getSize()][getSize()];
826
for (int i = 0; i < neighbors.length; i++) {
for (int j = 0; j < neighbors[i].size(); j++) {
int v = neighbors[i].get(j);
adjacencyMatrix[i][v] = 1;
}
}
return adjacencyMatrix;
}
/** Print the adjacency matrix */
public void printAdjacencyMatrix() {
int[][] adjacencyMatrix = getAdjacencyMatrix();
for (int i = 0; i < adjacencyMatrix.length; i++) {
for (int j = 0; j < adjacencyMatrix[0].length; j++) {
System.out.print(adjacencyMatrix[i][j] + " ");
}
System.out.println();
}
}
/** Print the edges */
public void printEdges() {
for (int u = 0; u < neighbors.length; u++) {
System.out.print("Vertex " + u + ": ");
for (int j = 0; j < neighbors[u].size(); j++) {
System.out.print("(" + u + ", " +
neighbors[u].get(j) + ") ");
}
System.out.println();
}
}
/** Edge inner class inside the AbstractGraph class */
public static class Edge {
public int u; // Starting vertex of the edge
public int v; // Ending vertex of the edge
/** Construct an edge for (u, v) */
public Edge(int u, int v) {
this.u = u;
this.v = v;
}
}
/** Obtain a DFS tree starting from vertex v */
/** To be discussed in Section 13.6 */
public Tree dfs(int v) {
List<Integer> searchOrders = new ArrayList<Integer>();
int[] parent = new int[vertices.length];
for (int i = 0; i < parent.length; i++)
parent[i] = -1; // Initialize parent[i] to -1
// Mark visited vertices
827
boolean[] isVisited = new boolean[vertices.length];
// Recursively search
dfs(v, parent, searchOrders, isVisited);
// Return a search tree
return new Tree(v, parent, searchOrders);
}
/** Recursive method for DFS search */
private void dfs(int v, int[] parent, List<Integer> searchOrders,
boolean[] isVisited) {
// Store the visited vertex
searchOrders.add(v);
isVisited[v] = true; // Vertex v visited
for (int i : neighbors[v]) {
if (!isVisited[i]) {
parent[i] = v; // The parent of vertex i is v
dfs(i, parent, searchOrders, isVisited); // Recursive search
}
}
}
/** Starting bfs search from vertex v */
/** To be discussed in Section 13.7 */
public Tree bfs(int v) {
List<Integer> searchOrders = new ArrayList<Integer>();
int[] parent = new int[vertices.length];
for (int i = 0; i < parent.length; i++)
parent[i] = -1; // Initialize parent[i] to -1
java.util.LinkedList<Integer> queue =
new java.util.LinkedList<Integer>(); // list used as a queue
boolean[] isVisited = new boolean[vertices.length];
queue.offer(v); // Enqueue v
isVisited[v] = true; // Mark it visited
while (!queue.isEmpty()) {
int u = queue.poll(); // Dequeue to u
searchOrders.add(u); // u searched
for (int w : neighbors[u]) {
if (!isVisited[w]) {
queue.offer(w); // Enqueue w
parent[w] = u; // The parent of w is u
isVisited[w] = true; // Mark it visited
}
}
}
return new Tree(v, parent, searchOrders);
}
/** Tree inner class inside the AbstractGraph class */
/** To be discussed in Section 13.5 */
public class Tree {
828
private int root; // The root of the tree
private int[] parent; // Store the parent of each vertex
private List<Integer> searchOrders; // Store the search order
/** Construct a tree with root, parent, and searchOrder */
public Tree(int root, int[] parent, List<Integer> searchOrders) {
this.root = root;
this.parent = parent;
this.searchOrders = searchOrders;
}
/** Construct a tree with root and parent without a
* particular order */
public Tree(int root, int[] parent) {
this.root = root;
this.parent = parent;
}
/** Return the root of the tree */
public int getRoot() {
return root;
}
/** Return the parent of vertex v */
public int getParent(int v) {
return parent[v];
}
/** Return an array representing search order */
public List<Integer> getSearchOrders() {
return searchOrders;
}
/** Return number of vertices found */
public int getNumberOfVerticesFound() {
return searchOrders.size();
}
/** Return the iterator for a path starting from the root to v */
public java.util.Iterator pathIterator(int v) {
return new PathIterator(v);
}
/** PathIterator inner class inside the tree */
public class PathIterator implements java.util.Iterator {
private Stack<Integer> stack;
/** Construct an iterator for the vertices on the path */
public PathIterator(int v) {
stack = new Stack<Integer>();
do {
stack.add(v);
v = parent[v];
}
while (v != -1);
}
829
/** Has next element in the iterator? */
public boolean hasNext() {
return !stack.isEmpty();
}
/* Get the current element in the iterator and move the
* iterator to point to the next element */
public Object next() {
return vertices[stack.pop()];
}
/* This remove method is defined in the Iterator interface
* do not implement it */
public void remove() {
// Do nothing
}
}
/** Print a path from the root to vertex v */
public void printPath(int v) {
Iterator iterator = pathIterator(v);
System.out.print("A path from " + vertices[root] + " to " +
vertices[v] + ": ");
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
}
/** Print the whole tree */
public void printTree() {
System.out.println("Root is: " + vertices[root]);
System.out.print("Edges: ");
for (int i = 0; i < parent.length; i++) {
if (parent[i] != -1) {
// Display an edge
System.out.print("(" + vertices[parent[i]] + ", " +
vertices[i] + ") ");
}
}
System.out.println();
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.