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

page1image12088
page1image12512
page1image12680
page1image13104
page1image13272
page1image13432
page1image13592
page1image14016
page1image14440
page1image14600
page1image14760
page1image14928

Alice

Charlie

page1image15896
page1image16056
page1image16480
page1image16904
page1image17072
page1image17240
page1image17400

Alice

Charlie

page1image18360
page1image18784
page1image19208
page1image19368
page1image19528
page1image19952
page1image20112
page1image20272

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].

page2image12216

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.

page2image19184
page2image19352

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.

page2image22536

Inner lists

page2image23192
page2image23352
page2image23784
page2image23944

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.