Graphs

Print Cheatsheet

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, and isDirected 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 in inputData and sets edges to an empty ArrayList
an .addEdge() method that takes a vertex and weight and adds an edge to edges
a .removeEdge() method that takes a vertex and removes it from edges
a .getEdges() method that returns the edges 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, and weight instance variables
a constructor that takes in and sets values for the instance variables
a .getStart() method that returns start
a .getEnd() method that returns end
a .getWeight() method that returns weight

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;
  }
	
}