CS340 Final Project 2

DirectedGraph.java

import java.io.*;
import java.util.*;

public class DirectedGraph {
    private class VertexNode {
        private String name; //the name of the vertex. Vertex names are unique
        private VertexNode nextV; //reference to the next vertex in the vertex list
        private EdgeNode edges; //the head of the list of edges coming out of the vertex

        private VertexNode(String n, VertexNode v) {
            name = n;
            nextV = v;
            edges = null;
        }
    }

    private class EdgeNode {
        private VertexNode vertex1; //references the vertex node of the first vertex of the edge
        private VertexNode vertex2; //references the vertex node of the second vertex of the edge
        private EdgeNode nextE; //the next edge in the edge list

        private EdgeNode(VertexNode v1, VertexNode v2, EdgeNode e) {
            vertex1 = v1;
            vertex2 = v2;
            nextE = e;
        }
    }

    private VertexNode vertices; //head of the list of vertices
    private int numVertices;

    public DirectedGraph() {
        vertices = null;
        numVertices = 0;
    }

    public void addVertex(String s) {
        //insert a new vertex into the vertex list
        //the vertex list is kept sorted in ascending order (base on the name)
        VertexNode temp = vertices, prev = null;
        while (temp != null && temp.name.compareTo(s) < 0) {
            prev = temp;
            temp = temp.nextV;
        }
        if (prev == null) {
            vertices = new VertexNode(s, null);
            return;
        }
        prev.nextV = new VertexNode(s, null);
    }

    public void addEdge(String n1, String n2) {
        //n1 and n2 are names of vertices that form the edge e.g. (A,B)
        //PRE: the vertices with names n1 and n2 have already be added
        var temp = vertices;
        while (!temp.name.equals(n1)) temp = temp.nextV;

        var temp2 = vertices;
        while (!temp2.name.equals(n2)) temp2 = temp2.nextV;

        EdgeNode edge = temp.edges;
        if (edge == null) {
            temp.edges = new EdgeNode(temp, temp2, null);
            return;
        }

        while (edge.nextE != null) edge = edge.nextE;

        edge.nextE = new EdgeNode(temp, temp2, null);
    }

    public void printGraph() {
        //Print the graph with the format shown on the next slide
        var temp = vertices;
        while(temp != null){
            System.out.print(temp.name);
            var edge = temp.edges;
            while(edge != null){
                System.out.print(" " + edge.vertex2.name);
                edge = edge.nextE;
            }
            System.out.println();
            temp = temp.nextV;
        }
    }

    public static void main(String args[]) throws IOException {
        //The main method can be used to test your implementation
        //DO NOT CHANGE THIS CODE
        BufferedReader b = new BufferedReader(new FileReader(args[0]));
        DirectedGraph g = new DirectedGraph();
        String line = b.readLine();
        Scanner scan = new Scanner(line);
        while (scan.hasNext()) {
            g.addVertex(scan.next());
        }
        line = b.readLine();
        while (line != null) {
            scan = new Scanner(line);
            g.addEdge(scan.next(), scan.next());
            line = b.readLine();
        }
        g.printGraph();
    }
}