This project uses object oriented programming in python with the Pygame module to allow the user to draw graphs and automatically compute whether the graph is k-Colorable and if two graphs are isomorphic.
The following command launches the Pygame instance with set value of k used for computing the k-Coloring.
python main.py <k>Once the instance is launched, the user can do the following actions:
- Click anywhere to create a vertex.
- Click two consecutive vertices to create an edge between them.
- Press
sto switch between the two graphs. - Press
kto compute a k-Coloring for the current graph.- The program will display if a k-Coloring exists, and print a possible coloring to the terminal.
- If there is a possible k-Coloring, the program will also color the corresponding vertices with a valid coloring.
- Press
ito compute if the two drawn graphs are isomorphic.
The Graph Coloring problem is known to be NP-Complete and there is also no known polynomial time algorithm for solving Graph-Isomorphism. Since exact solutions were desired for both of these problems, the algorithms implemented here do not run in polynomial time. To limit runtime issues, the program has a hardcoded maximum vertex count for the graphs, which is set by default to 20 vertices. This value can be changed by changing the MAX_VERTICES global variable at the top of main.py.
The algorithm for k-Coloring iterates through all possible colorings, check each to find a valid k-Coloring. The runtime for computing a k-Coloring on a graph G = (V, E) is
where M is
MAX_VERTICES and |V| is the number of vertices in the graph G.
The algorithm for Graph-Isomorphism iterates through the possible permuations of vertex conversions between the two graphs. As a result, the runtime for computing an isomorphism between graphs G1 = (V1, E1) and G2 = (V2, E2) is where M is
MAX_VERTICES and given that |V| = |V1| = |V2|.
The required modules to run this program:
mathitertoolscopyrandomclickpygame