using java, design and code a reference based weighted graph class with vertices

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

Answer :

import java.util.*;

public class Graph<T> {
  
public static final int VISIT_COLOR_WHITE = 1;

  
public static final int VISIT_COLOR_GREY = 2;

  
public static final int VISIT_COLOR_BLACK = 3;

private List<Vertex<T>> verticies;

private List<Edge<T>> edges;

  
private Vertex<T> rootVertex;

  
public Graph() {
verticies = new ArrayList<Vertex<T>>();
edges = new ArrayList<Edge<T>>();
}

public boolean isEmpty() {
return verticies.size() == 0;
}
public boolean addVertex(Vertex<T> v) {
boolean added = false;
if (verticies.contains(v) == false) {
added = verticies.add(v);
}
return added;
}

public void hasVertex(Vertex<T> root) {

this.rootVertex = root;
if (verticies.contains(root) == false)
this.addVertex(root);
}

public boolean addEdge(Vertex<T> from, Vertex<T> to, int cost) throws IllegalArgumentException {

if (verticies.contains(from) == false)
throw new IllegalArgumentException("from is not in graph");
if (verticies.contains(to) == false)
throw new IllegalArgumentException("to is not in graph");

Edge<T> e = new Edge<T>(from, to, cost);
if (from.findEdge(to) != null)
return false;
else {
from.addEdge(e);
to.addEdge(e);
edges.add(e);
return true;
}
}
public void clearMark() {

for (Vertex<T> w : verticies)
w.clearMark();
}

private Vertex<T> from;

private List<Edge<T>> incomingEdges;

private List<Edge<T>> outgoingEdges;
private Vertex<T> to;

private int cost;

private boolean mark;
public Edge(Vertex<T> from, Vertex<T> to) {
this(from, to, 0);
}

public UnboundedQueueInterface<T> getToVertices() {
return to;
}

public void markVertex() {

mark = true;
}

public void clearMarks() {
mark = false;
}

public boolean isMarked() {
return mark;
}

   private String name;

private boolean mark;

private int markState;

private T data;

public boolean addEdges(Edge<T> e) {

if (e.getFrom() == this)
outgoingEdges.add(e);
else if (e.getToVertices() == this)
incomingEdges.add(e);
else
return false;
return true;
}
public void OutgoingEdge(Vertex<T> to, int cost) {
Edge<T> out = new Edge<T>(this, to, cost);
outgoingEdges.add(out);
}
public void IncomingEdge(Vertex<T> from, int cost) {
Edge<T> out = new Edge<T>(this, from, cost);
incomingEdges.add(out);
}

public int weightIs(Vertex<T> dest) {
if (dest == this)
return 0;

Edge<T> e = findEdge(dest);
int cost = Integer.MAX_VALUE;
if (e != null)
cost = e.getCost();
return cost;
}

public int getUnmarked() {

return markState;
}

public void clearMarks() {
mark = false;
}

}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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