Adding a Vertex
The Java implementation of a Graph
has an .addVertex()
instance method that takes in data
and creates a new Vertex
, which it then adds to vertices
. The method returns the new Vertex
.
public Vertex addVertex(String data) {
Vertex newVertex = new Vertex(data);
this.vertices.add(newVertex);
return newVertex;
}
Adding an Edge
The Java implementation of a Graph
has an .addEdge()
instance method that takes in vertexOne
, vertexTwo
, and weight
, and returns nothing. It adds an edge from vertexOne
to vertexTwo
, and if the graph is directed, adds an edge from vertexTwo
to vertexOne
. If the graph is weighted, it adds weight
to each edge.
public void addEdge(Vertex vertex1, Vertex vertex2, Integer weight) {
if (!this.isWeighted) {
weight = null;
}
vertex1.addEdge(vertex2, weight);
if (!this.isDirected) {
vertex2.addEdge(vertex1, weight);
}
}
Graph Overview
A Graph
class implemented in Java has the following attributes:
- 3
private
instance variables:ArrayList
vertices
boolean
isWeighted
boolean
isDirected
- a constructor with
vertices
,isWeighted
, andisDirected
parameters that updates the corresponding instance variables appropriately - an
.addVertex()
method that adds a vertex to the graph - a
.removeVertex()
method that removes a vertex from the graph - an
.addEdge()
method that adds an edge to the graph - a
.removeEdge()
method that removes an edge from the graph
import java.util.ArrayList;
public class Graph {
private ArrayList<Vertex> vertices;
private boolean isWeighted;
private boolean isDirected;
public Graph(boolean inputIsWeighted, boolean inputIsDirected) {
this.vertices = new ArrayList<Vertex>();
this.isWeighted = inputIsWeighted;
this.isDirected = inputIsDirected;
}
public Vertex addVertex(String data) {
Vertex newVertex = new Vertex(data);
this.vertices.add(newVertex);
return newVertex;
}
public void addEdge(Vertex vertex1, Vertex vertex2, Integer weight) {
if (!this.isWeighted) {
weight = null;
}
vertex1.addEdge(vertex2, weight);
if (!this.isDirected) {
vertex2.addEdge(vertex1, weight);
}
}
public void removeEdge(Vertex vertex1, Vertex vertex2) {
vertex1.removeEdge(vertex2);
if (!this.isDirected) {
vertex2.removeEdge(vertex1);
}
}
public void removeVertex(Vertex vertex) {
this.vertices.remove(vertex);
}
public ArrayList<Vertex> getVertices() {
return this.vertices;
}
public boolean isWeighted() {
return this.isWeighted;
}
public boolean isDirected() {
return this.isDirected;
}
public Vertex getVertexByValue(String value) {
for(Vertex v: this.vertices) {
if (v.getData() == value) {
return v;
}
}
return null;
}
public void print() {
for(Vertex v: this.vertices) {
v.print(isWeighted);
}
}
}
Graph Constructor
The Java implementation of the Graph
class has a constructor with the following boolean
parameters:
isWeighted
isDirected
It sets the isWeighted
and isDirected
instance variables appropriately, and sets the instance variable vertices
to a new empty ArrayList
of type Vertex
.
public Graph(boolean inputIsWeighted, boolean inputIsDirected) {
this.vertices = new ArrayList<Vertex>();
this.isWeighted = inputIsWeighted;
this.isDirected = inputIsDirected;
}
Graph’s Vertex Class
The Java Graph
class relies on an underlying Vertex
class with the following behaviors:
- a constructor that sets
data
to the passed ininputData
and setsedges
to an empty ArrayList - an
.addEdge()
method that takes avertex
andweight
and adds an edge toedges
- a
.removeEdge()
method that takes avertex
and removes it fromedges
- a
.getEdges()
method that returns theedges
ArrayList
import java.util.ArrayList;
public class Vertex {
private String data;
private ArrayList<Edge> edges;
public Vertex(String inputData) {
this.data = inputData;
this.edges = new ArrayList<Edge>();
}
public void addEdge(Vertex endVertex, Integer weight) {
this.edges.add(new Edge(this, endVertex, weight));
}
public void removeEdge(Vertex endVertex) {
this.edges.removeIf(edge -> edge.getEnd().equals(endVertex));
}
public ArrayList<Edge> getEdges(){
return this.edges;
}
}
Removing a Vertex
The Java implementation of a Graph
has a .removeVertex()
instance method that takes in vertex
and removes it from the list of vertices
. The method returns nothing.
public void removeVertex(Vertex vertex) {
this.vertices.remove(vertex);
}
Graph’s Edge Class
The Java Graph
class relies on an Edge
class with the following properties:
start
,end
, andweight
instance variables- a constructor that takes in and sets values for the instance variables
- a
.getStart()
method that returnsstart
- a
.getEnd()
method that returnsend
- a
.getWeight()
method that returnsweight
public class Edge {
private Vertex start;
private Vertex end;
private Integer weight;
public Edge(Vertex startV, Vertex endV, Integer inputWeight) {
this.start = startV;
this.end = endV;
this.weight = inputWeight;
}
public Vertex getStart() {
return this.start;
}
public Vertex getEnd() {
return this.end;
}
public Integer getWeight() {
return this.weight;
}
}
Graph’s Helper Classes
A Java Graph
relies on underlying Edge
and Vertex
classes.