9. Graph
In this lab you will implement the linked list graph representation seen in class.
The class inherits from the interface Graph see in class.
1package graph;
2
3import java.util.*;
4
5/** Interface to specify a Graph ADT.
6 * A graph is a set of vertices and a set of edges.
7 * Vertices are represented by integers from 0 to n − 1.
8 * Edges are ordered pairs of vertices.
9 * Each implementation of the Graph interface should
10 * provide a constructor that specifies the number of
11 * vertices and whether the graph is directed.
12 */
13public interface Graph {
14
15 // Accessor Methods
16 /** Return the number of vertices.
17 @return The number of vertices
18 */
19 int getNumV();
20
21 /** Determine whether this is a directed graph.
22 @return true if this is a directed graph
23 */
24 boolean isDirected();
25
26 /** Insert a new edge into the graph.
27 @param edge The new edge
28 */
29 void insert(Edge edge);
30
31 /** Determine whether an edge exists.
32 @param source The source vertex
33 @param dest The destination vertex
34 @return true if there is an edge from source to dest
35 */
36 boolean isEdge(int source, int dest);
37
38 /** Get the edge between two vertices.
39 @param source The source vertex
40 @param dest The destination vertex
41 @return The edge between these two vertices or null if there is no edge
42 */
43 Edge getEdge(int source, int dest);
44
45 /** Return an iterator to the edges connected to a given vertex.
46 @param source The source vertex
47 @return An Iterator<Edge> to the vertices connected to source
48 */
49 Iterator<Edge> edgeIterator(int source);
50
51 /** Read source and destination vertices and weight (optional) for each edge from a file
52 @param scan The Scanner associated with the file
53 */
54 default void loadEdgesFromFile(Scanner scan) {
55 String line;
56 while (scan.hasNextLine()) {
57 line = scan.nextLine();
58 if (!line.isBlank()) {
59 String[] tokens = line.split("\\s+");
60 int source = Integer.parseInt(tokens[0]);
61 int dest = Integer.parseInt(tokens[1]);
62 double weight = 1.0;
63 if (tokens.length == 3) {
64 weight = Double.parseDouble(tokens[2]);
65 }
66 insert(new Edge(source, dest, weight));
67 }
68 }
69 }
70}
9.1. Edge Representation
As discussed during the lectures, we need a class to represent an edge of the graph.
Complete the following class:
1/**
2 * An Edge represents a relationship between two
3 * vertices.
4 */
5public class Edge {
6 // Data Fields
7 /** The source vertex */
8 private final int source;
9 /** The destination vertex */
10 private final int dest;
11 /** The weight */
12 private final double weight;
13
14 // Constructor
15 /** Construct an Edge with a source of from
16 * and a destination of to. Set the weight to 1.0.
17 * @param source - The source vertex
18 * @param dest - The destination vertex
19 */
20 public Edge(int source, int dest) {
21 }
22 /** Construct a weighted edge with a source
23 * of from and a destination of to. Set the
24 * weight to w.
25 * @param source - The source vertex
26 * @param dest - The destination vertex
27 * @param w - The weight
28 */
29 public Edge(int source, int dest, double w) {
30 }
31 // Methods
32 /** Get the source
33 * @return The value of source
34 */
35 public int getSource() {
36 }
37 /** Get the destination
38 * @return The value of dest
39 */
40 public int getDest() {
41 }
42 /** Get the weight
43 * @return the value of weight
44 */
45 public double getWeight() {
46 }
47 /** Return a String representation of the edge
48 * @return A String representation of the edge
49 */
50 @Override
51 public String toString() {
52 }
53 /** Return true if two edges are equal. Edges
54 * are equal if the source and destination
55 * are equal. Weight is not considered.
56 * @param obj The object to compare to
57 * @return true if the edges have the same source
58 * and destination
59 */
60 @Override
61 public boolean equals(Object obj) {
62 if (obj instanceof Edge) {
63 Edge edge = (Edge) obj;
64 return (source == edge.source && dest == edge.dest);
65 } else {
66 return false;
67 }
68 }
69 /** Return a hash code for an edge. The hash
70 * code is the source shifted left 16 bits
71 * exclusive or with the dest
72 * @return a hash code for an edge
73 */
74 @Override
75 public int hashCode() {
76 return (source << 16) ^ dest;
77 }
9.2. Graph - LinkedList Representation
In this part you will try to implement the Linked List representation of a graph.
We already implemented a few methods, so you just need to complete the one remaining.
As remainder, the part already completed is given below.
1import java.util.*;
2
3/** A ListGraph implements the Graph interface using an
4 array of lists to represent the edges.
5 */
6public class ListGraph implements Graph {
7
8 // Data Fields
9 /** The number of vertices */
10 private final int numV;
11 /** An indicator of whether the graph is directed (true) or not (false)
12 */
13 private final boolean directed;
14 /** An array of Lists to contain the edges that
15 originate with each vertex.
16 */
17 private LinkedList<Edge>[] edges;
18 /** Construct a graph with the specified number of vertices and directionality.
19 @param numV The number of vertices
20 @param directed The directionality flag
21 */
22 public ListGraph(int numV, boolean directed) {
23 this.numV = numV;
24 this.directed = directed;
25 edges = new LinkedList[numV];
26 for (int i = 0; i < numV; i++) {
27 edges[i] = new LinkedList<Edge>();
28 }
29 }
30}
9.3. Test
Before going further we need to make sure the implementation works.
The graph interface has a method to read a file and create the graph associated to it, so you will need to create a new file and copy/paste the following:
7
0,1
0,3
0,4
0,5
1,0
1,2
1,3
1,4
1,6
2,1
2,3
2,5
2,6
3,0
3,1
3,2
3,4
3,5
3,6
4,0
4,1
4,3
4,5
5,0
5,2
5,3
5,4
5,6
6,1
6,2
6,3
6,5
Make sure that the graph that you obtain is the same.