| CPSC 327 | Data Structures and Algorithms | Spring 2024 |
equals vs ==: the difference here is between "equivalent" and "same". For objects, == compares addresses so a == b is true only if a and b are at the same place in memory i.e. they refer to the same object. For some types there is also a notion of equivalence — imagine dealing the Queen of Hearts from two different decks of cards. These are not the same card as you have two separate cards lying side-by-side on the table, but they are equivalent because they are interchangeable — you don't care which of the two cards is in your hand because it only matters that you have a Queen of Hearts. equals allows for a definition of equivalence in situations like this. Which to use? Use == when object identity is important (it matters which card even if both are the Queen of Hearts) and equals when it isn't (what matters is the Queen of Hearts vs some other suit and value). Vertex and Edge should be compared with == — object identity matters. (The associated object for a vertex or edge should not be used to determine equivalence — while there may be situations where this makes sense, such as when the associated object for a vertex is its label, it is not necessarily true in general. The associated object for a vertex or edge may be its weight, for example, and the weights may not be distinct.)
Only cast when you need to. A guideline: always work with the top-level Vertex, Edge, or Graph types for variables, parameters, and return types unless you need to construct a particular object or call a method specific to a particular implementation.
A superclass should never reference a subclass type. (This breaks design principles.) If a method body in AbstractGraph, for example, needs to create a new vertex or edge object or needs a method specific to an adjacency list or adjacency matrix vertex or edge, that method body shouldn't be in AbstractGraph.
Organization: follow the implementations discussed in class (see the slides!) for what instance variables are needed and where they should go — put things as high in the hierarchy as possible without violating the previous rule (superclasses not referencing subclass types). That means AbstractGraph should have the list of vertices and the list of edges (and bodies for any methods that only access those), AbstractVertex should have the associated object and the degree of the vertex, AbstractEdge should have the associated object and the edge's endpoints, AdjacencyMatrixGraph should have the 2D array (of Edges), AdjacencyMatrixVertex should have the vertex's index in the array, and AdjacencyListVertex should have the vertex's list of incident edges.
Efficiency: for full credit, your implementations needed to have the efficiencies discussed in class (see the slides!). Part of this was using a linked list instead of List, but also avoiding unnecessary computation such as counting the incident edges to compute degree, counting edges to compute the number of edges, searching through a collection of edges to find the endpoints of an edge, searching through all of the vertices to remove a particular edge, searching through all of the edges to find the incident edges for a vertex, using indexOf to determine a vertex's index in the adjacency matrix, etc. Most, if not all, of this can be avoided by following the implementations discussed in class — for example, the vertex storing its degree, an edge storing its endpoints, and a vertex storing its incident edges.
Correctness: when you store counts to save on computation, make sure to remember to update them when necessary! (For example, updating the vertex degree when an edge is inserted or removed.) Also make sure all the tasks for insert and remove operations are covered. In particular, removing a vertex should also remove its incident edges and adding/removing an edge or vertex should update the graph's list of edges/vertices.