Description
SCENARIO:
In this homework, you will create a new abstract class named AbstractGraphExtended by extending
AbstractGraph abstract class of the book. The new abstract class will provide new features by
implementing the methods described below.
public int addRandomEdgesToGraph (int edgeLimit);
This method selects a random number between 0 and edgeLimit then adds that much edges to calling
graph. The source and destination vertices of edges will be random again. The inserted edges will be
directed or undirected according to calling graph (If graph is directed, new edges will be directed vice
versa). The weights of edges will be set to 1. It will return number of inserted edges.
public int [] breadthFirstSearch (int start);
This method performs a breadth first search on calling graph starting from vertex start and returns an
array which contains the predecessor of each vertex in the breadth-first search tree. It will work for
both directed and undirected graphs.
public Graph [] getConnectedComponentUndirectedGraph ();
This method finds connected components in a graph, creates ListGraph or MatrixGraph instances for
each connected component and returns them in a Graph array. If this method is called from a ListGraph
instance, then connected components will be ListGraph instances. Same thing will happen for
MatrixGraph instance. The method will only work for undirected graphs.
A connected component is a set of vertices that is reachable from anyone to all others in the set. Your
goal is to find all connected components in a graph, put each of them to new graph instances with their
edges then return it. Here is an example, suppose the input graph is the one below:
This is just a single graph with 5 different connected components. So, you will find and return 5
graphs. Hint: If you are tired of homeworks, eat some bread for energy.
public boolean isBipartiteUndirectedGraph ();
This method returns true if calling graph instance is bipartite graph, false otherwise. A bipartite
graph is a graph whose vertices can be divided into two independent sets, U and V such that every
edge (u, v) either connects a vertex from U to V or a vertex from V to U. Here is an example of bipartite
graph:
Like previous method, this one will also work for only undirected graphs. Hint: Maybe eating bread
again will be good.
public void writeGraphToFile (String fileName);
This method will do the reverse of createGraph method in the AbstractGraph abstract class and write
number of vertices, source and destination vertex of each edge in a file. An example file output will be
like this:
9
0 1
0 3
1 2
1 4
1 5
2 5
3 6
4 6
4 7
5 7
6 8
7 8
First line indicates number of vertices in graph, other lines represent edges of the graph. For example,
there is an edge from 0 to 1, 0 to 3 and 1 to 2 etc. Don’t write weights of edges.
You will test each of your methods using both ListGraph and MatrixGraph classes of book by creating
instances of them in main method. These classes will extend AbstractGraphExtended abstract class
which you implemented instead of AbstractGraph abstract class of book.
Test each method two times by reading two different graphs from two different files. You can use
createGraph method of book to read graphs from file. Write the result graphs to files by using the
writeGraphToFile method (do not test writeGraphToFile method exclusively) for testing first and third
methods. Output the result of second and fourth methods to console. You will follow this test
procedure for both ListGraph and MatrixGraph. Don’t use big graphs, at most 10 vertices will be
enough.
You will send us an IntelliJ IDEA project that includes
– Main class and AbstractGraphExtended abstract class that you implemented
– Input graph files for your tests
– Edge class, Graph interface, AbstractGraph abstract class, ListGraph and MatrixGraph classes.
They are all added to zip file.
And of course your report where you explained the implemented new methods.
RESTRICTIONS:
– Can be only one main class in project
– Only using classes and libraries from Graphs chapter of your book is allowed. Don’t use any
other third part library.
GENERAL RULES:
– For any question firstly use course news forum in moodle, and then the contact TA.
– You can submit assignment one day late and will be evaluated over twenty percent (%20).
– Register github student pack and create private project and upload your projects into github.
– Your appeals are considered over your github project process.
TECHNICAL RULES:
– Use given CSE222-VM to develop and test your homeworks (your code must be working on
CSE222-VM), CSE222-VM download link will be given on Moodle.
– Implement clean code standarts in your code;
o Classes, methods and variables names must be meaningful and related with the
functionality.
o Your functions and classes must be simple, general, reusable and focus on one topic.
o Use standart java code name conventions.
REPORT RULES:
– Add all javadoc documentations for classes, methods, variables …etc. All explanation must be
meaningful and understandable.
– You should submit your homework code, javadoc and report to Moodle in a
studentid_hw#.tar.gz file.
– Use the given homework format including selected parts:
Detailed system requirements
The Project usecase diagrams (extra points)
Class diagrams
Other diagrams
Problem solutions approach x
Test cases x
Running command and results x
GRADING :
– No error handling : -50
– No inheritance : -95
– No javadoc documentation : -50
– No report : -90
– Disobey restrictions : -100
– Cheating : -200
– Your solution is evaluated over 100 as your performance.