Assignment #7
– Graph
Objectives:
The
main objectives of this assignment is:
·
Understand
Graph ADT
·
Implement
Graph ADT using Adjacency List structure
The Assignment:
Implement AdjListGraph.java
You can implement the vertex’s adjacency
list with a doubly linked list or a hash map. I encourage you to use the hashmap. The text book has some
code using the hash map.
Important Notes:
·
Be
sure to include Time Complexity annotation and TCJ comments for each method.
Use n to represent the number of vertices and m to represent the number of
edges in the graph. The cost can be expressed with more than one variables,
expressions, functions, like O(n+m),
O(m log n), O(deg(v)), etc.
Getting Started:
- Download and import the
following zip file: Assignment7.zip. For
Eclipse:
- Open
Eclipse
- Choose
"File → Import".
- Select
the "General" category.
- Pick
"Existing Projects into Workspace"
- Click
on "Next"
- Select
the button for "Select Archive File" and browse to/select the
zip file.
- Click
on "Finish"
- You will need to create
your own classes (an implementation of Vertex and an implementation Edge,
for example). You should feel free to copy over ANY data structures to
this project that you have written during the semester. However, do NOT
modify the net.datastructures package. Put all
your extra classes in the cs2321 package.
Submission:
First, look at the
following checklist:
- Have
you tested every method in some way?
- Do
you ever import from java.util. If so, be sure you
only import allowed components (like Iterator,
Exceptions, etc.). Unless the assignment specifically mentions it is
permissible, you should never include any of Java's native data
structures.
- Do
all your methods have a @TimeComplexity indicator?
- Do
you provide adequate TCJ comments to prove your
time complexity?
- Is
the indentation easily readable? You can have Eclipse correct indentation
by highlighting all code and select "Source → Correct
Indentation".
- Are
comments well organized and concise?
- Does
the program meet all required interfaces?
- Have
you tested every method in some way?
If you have reviewed
your code and all the criteria on the checklist are acceptable, follow the
submission procedure.
Grading Criteria:
- Correctly implementing
the graph type: 80 points. If you didn’t use Adjacency List/Ajacency Map, you will get 50% of what you got from
the autograder test cases.
- Correct documentation of
time complexity: 10 points
- Clear concise code with
good commenting: 10 points
Q&A:
·
Do
I get same points no matter which one (EdgeList, AdjacencyList/AjacencyMap, Adjcacency Matrix) I
implement?
o
No.
You will get 50% if you didn’t implement the Adjacency List/AjacencyMap.