Graph coloring(Project1_1)

This project provides implementations for finding the chromatic number of a graph using exact and upper bounding algorithms. The project reads graph data from an external file and applies these algorithms to calculate the chromatic number efficiently.

Features:

• BruteForce Algorithm: Exact approach to find the chromatic number of a graph by trying every possible coloring and choosing variant that uses smallest number of colors.
• DSATUR Algorithm: Heuristic algorithm used as a faster alternative for computing an upper bound for the chromatic number when the brute force approach exceeds the time limit.
• Greedy Algorithm: A simple and fast heuristic algorithm that attempts to assign the smallest possible color to each vertex, coloring verteces one by one, starting from first vertex.
• Time Handling If Bruteforce algorithm runs out of 30 second, we use Upper bound algorithm to calculate chromatic number

Project structure

• Main.java: The place where all calculations to find a chromatic number are processed
• ReadGraph.java: Reads graph and provides data about graph to Main.java in appropriate format
• Graph.txt Stores information about the graph, if you want to find chromatic number for your graph, you should upload information about it to graph.txt

Prerequisites

The things you need before installing the software.

• JVM

Execution

A step by step series of instructions that tell you how to execute a code

Use terminal to execute the code

Navigate from the root directory to src directory:

    cd Chromatic number
    cd src

Run the code

    java Main Ressources/Graph/graph.txt    

Example:

PS C:\Users\Илья\Documents\Java проекты\project1_1> cd Chromatic_number
PS C:\Users\Илья\Documents\Java проекты\project1_1\Chromatic_number> cd src
PS C:\Users\Илья\Documents\Java проекты\project1_1\Chromatic_number\src> javac Main.java ReadGraph.java
PS C:\Users\Илья\Documents\Java проекты\project1_1\Chromatic_number\src> java Main Ressources/Graph/graph.txt           
// Number of vertices = 6
// Expected number of edges = 7
// Reading edge 1
// Edge: 1 2
// Reading edge 2
// Edge: 2 3
// Reading edge 3
// Edge: 3 1
// Reading edge 4
// Edge: 1 4
// Reading edge 5
// Edge: 4 5
// Reading edge 6
// Edge: 5 6
// Reading edge 7
// Edge: 6 4
Chronomatic Number is: 3

Authors

• Gaevskii, Ilia - Provided README Template - Gaevskii, Ilia
  • Bär, Olaf - Provided README Template - är, Olaf
  • Garot, François - Provided README Template - Garot, François
  • Goldin, Leah - Provided README Template - Goldin, Leah
  • Høilund, Edvard - Provided README Template - Høilund, Edvard
  • Kálmánczhelyi, Anna - Provided README Template - Kálmánczhelyi, Anna
  • Popescu, Bianca - Provided README Template - Popescu, Bianca

Sources

• Constructive Algorithms for Graph Colouring/www.baeldung.com
• introduction to graph coloring/geeksforgeeks.org
• Use of ChatGPT for understanding of the execution time and brute force method
• Source for understanding time handling problem/Oracle documentain
• Dsatur/Wikipedia