Homework 09 Solution

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.