introduction to object oriented programming eecs 1510

In this assignment, you will build upon the Node and Edge classes from Homework Assignment 8 to create a class representing a graph. I have provided you with the following files:

• NodeEdge.jar: Java archive containing compiled Node and Edge classes (see Homework 8 solution for implementation).
• Graph.java: implementation of an abstract class representing general graphs. Since it is an abstract class, it cannot be used to create objects.
• UndirectedGraph.java: partial implementation of a class representing undirected graphs.
  An undirected graph is a graph that contains only undirected edges. See two examples of undirected graphsshown in Figure 1 below. The UML diagram for the graph classes is shown in Figure 2.Figure 1. Two examples of undirected graphs.

graph1

Bob

graph2

Bob

Zulu

Alice

Charlie

Alice

Charlie

Figure 2. UML diagram for graph classes.

EECS 1510 Spring 2020 Sections 009/011/093 Instructor: Dr. Kevin S. Xu Introduction to Object-Oriented Programming

CLASS SPECIFICATION

The specification of the Graph abstract class is as follows:

Since Graph is an abstract class, no Graph objects can be created. Notice that some of the methods are implemented while others in italic are abstract methods that require the subclass to provide the implementation.

The specification of the UndirectedGraph subclass is as follows:

ADJACENCY LIST

The adjacency list is a way of representing the edges in a graph using ragged arrays. It is actually a list of lists, where the outer list (rows) consists of the nodes in the graph, and the inner list (columns) for each node contains the edges connected to that node, which we call the neighboring edges. For example, graph2in Figure 1 could be represented as shown in Figure 3 below.

Figure 3. Illustration of adjacency list for graph2 in Figure 1.

Notice that the inner lists can contain different numbers of elements because each node may have a different number of edges connected to it. The ith element in the outer list of adjacencyList should correspond to the node in the ith element of nodeArray. In the example adjacency list shown in Figure 3, the elements of nodeArray should be [Alice, Bob, Charlie, Zulu].

List of nodes in the graph.

Constructs an empty graph with no nodes.
Constructs a graph with the given list of nodes.
Returns the list of nodes in the graph.
Returns the index in nodeArray for the node with the given ID. Adds the given node and returns true if successfully added. Removes the given node and returns true if successfully removed. Returns true if node n has the same ID as the current node. Returns the edge with the given source and target nodes.

Adds the given edge and returns true if successfully added. Removes the given edge and returns true if successfully removed. Returns a string representation of the graph.

List of edges in the graph stored as an adjacency list.

Constructs an empty undirected graph with no nodes.
Constructs an undirected graph with the given list of nodes. Returns the list of edges (neighbors) connected to the given node.

Inner lists

Alice: [(Alice, Bob), (Alice, Zulu), (Alice, Charlie)]
Bob: [(Alice, Bob), (Bob, Charlie)]
Charlie: [(Bob, Charlie), (Charlie, Zulu), (Alice, Charlie)] Zulu: [(Alice, Zulu), (Charlie, Zulu)]

Outer list

EECS 1510 Spring 2020 Sections 009/011/093 Instructor: Dr. Kevin S. Xu Introduction to Object-Oriented Programming

SUBMISSION INSTRUCTIONS

A portion of your grade will be assigned based on adherence to OOP practices. Submit only your fully implemented UndirectedGraph.java source file! Do not include a main() method in your submission!

Sample output for the following code block:

// Create nodes_x000D_

ArrayList<Node> allNodes = new ArrayList<>();allNodes.add(new Node(“Alice”));allNodes.add(new Node(“Bob”));allNodes.add(new Node(“Charlie”));allNodes.add(new Node(“Zulu”));

// Create graphs and add nodes to them

UndirectedGraph graph = new UndirectedGraph();graph.addNode(allNodes.get(0));graph.addNode(allNodes.get(1));graph.addNode(allNodes.get(2));
UndirectedGraph graph2 = new UndirectedGraph(allNodes);

// Create edges_x000D_

ArrayList<Edge> allEdges = new ArrayList<>();
allEdges.add(new Edge(graph2.getNode(“Alice”), graph2.getNode(“Bob”)));allEdges.add(new Edge(graph2.getNode(“Bob”), graph2.getNode(“Charlie”)));allEdges.add(new Edge(graph2.getNode(“Alice”), graph2.getNode(“Zulu”)));allEdges.add(new Edge(graph2.getNode(“Charlie”), graph2.getNode(“Zulu”)));allEdges.add(new Edge(graph2.getNode(“Alice”), graph2.getNode(“Charlie”)));

// Add edges to graphs

graph.addEdge(allEdges.get(0));graph.addEdge(allEdges.get(1));
for (int i = 0; i < allEdges.size(); i++)

graph2.addEdge(allEdges.get(i));

// Print node lists and adjacency lists

System.out.println(graph.getNodeArray().toString()); System.out.println(graph.toString()); System.out.println(graph2.getNodeArray().toString()); System.out.println(graph2.toString());

Output:

[Alice, Bob, Charlie]
Alice: [(Alice, Bob)]
Bob: [(Alice, Bob), (Bob, Charlie)]
Charlie: [(Bob, Charlie)]
[Alice, Bob, Charlie, Zulu]
Alice: [(Alice, Bob), (Alice, Zulu), (Alice, Charlie)]
Bob: [(Alice, Bob), (Bob, Charlie)]
Charlie: [(Bob, Charlie), (Charlie, Zulu), (Alice, Charlie)] Zulu: [(Alice, Zulu), (Charlie, Zulu)]

Additional practice problems from the textbook: 11.2 (see attached solution to 10.14 for implementation of the MyDate class), 11.5, 11.9, 11.12, 11.13, 13.3.