Difference: CSC122F2022Lab8 ( vs. 1)

Revision 12022-11-14 - cathybareiss

Line: 1 to 1

Added:

>
>

META TOPICPARENT	name="CSC122SylF2022"

Graphs and Coloring

Coloring a graph is the idea of assigning each node a different color than any of its neighbors. It can be a very complex problem (see https://en.wikipedia.org/wiki/Graph_coloring

for more details) especially if the goal is to minimize the number of different colors. That is not our goal (for which you should be thankful). We will cover the idea in lab.

Objectives

Learn to implement graphs
Learn understand some of graph coloring
Improve your testing skill

Assignment

Phase 1:

The software should take the file (specified by the command line argument if time permits). An example of the file is found in the folder for the class.
Assign the colors to the nodes via the algorithm discussed.
Implement the graph via an adjacency list
The maximum number of nodes is 100
Your testing plan needs to include the following (and other test cases as well)
1. A graph with at least 7 nodes and at least 25 edges where the algorithm determines an optimal minimal coloring
2. A graph with at least 7 nodes and at least 25 edges where the algorithm determines a suboptimal minimal coloring.

Phase 2:

Implement your designs
Test and debug your code

Submission instructions for Phase 2

Complete the SDR.
Combine your SDR and all of your .java and testing files into one zip folder
Submit the zip folder on Canvas by the due data specific there.

Restrictions:

You may not use any Internet resources (other than to look up Java syntax) for any algorithms. You must use the algorithm specified in class.
You may use code from this course or last semesters.

View topic | History: r1 | More topic actions...