roshinc/graph-coloring

Given the list of edges of an undirected graph, find a coloring of this graph

graph-coloring

Team 2

Given the list of edges of an undirected graph, find a coloring of this graph

Question 18

Q18: Given the list of edges of an undirected graph, find a coloring of this graph using the algorithm given in the exercise set of Section 10.8.

From Section 10.8 p.g.743 :

This algorithm can be used to color a simple graph:

First, list the vertices v₁, v₂, v₃,..., v_n in order of decreasing degree so that deg(v₁) ≥ deg(v₂) ≥···≥ deg(v_n).

Assign color 1 to v₁ and to the next vertex in the list not adjacent to v₁ (if one exists), and successively to each vertex in the list not adjacent to a vertex already assigned color 1.

Then assign color 2 to the first vertex in the list not already colored. Successively assign color 2 to vertices in the list that have not already been colored and are not adjacent to vertices assigned color 2.

If uncolored vertices remain, assign color 3 to the first vertex in the list not yet colored, and use color 3 to successively color those vertices not already colored and not adjacent to vertices assigned color 3. Continue this process until all vertices are colored.

Runnig

This program requires Phython 3.6.0+

If you are in the of the program directory you can just do python main.py. It outputs the coloring of four graph that are read form the ./test directory.

Input

We represent a simple graph using an adjacency list, i.e a pair of vertices represents an edge.

Below is a simple graph with 4 edges:

1,2
1,3
3,5
2,4

The program takes a graph as a file. Few examples can be see in the ./test directory which it currently reads form.

Output

For each vertices in the graph we output in the form Vertex VertexName has Color ColorName.

Below is the result of running the program of the graph in the Input section:

Vertex 1 has Color 1
Vertex 5 has Color 1
Vertex 4 has Color 1
Vertex 2 has Color 2
Vertex 3 has Color 2

Examples

simple_one.graph

Test File

We also allow comments in the test file using back-ticks(`) as demonstrated above.

Result

---

simple_two.graph

Test File

Result

---

simple_three.graph

Test File

Result

---

simple_four.graph

Test File

Result

---

Contributions

Ideation:

Finding the algorithm, walking through it on the white-board, deciding how we take the input, determining how we write the input & output.

Who: Gokul Ambigapathy, Roshin Cherian, Lakshmi Priya Hariharan, Sean Lachhander, Siddheshwar Kanagamoorthy

Programing:

1. I/O Reading from file, and make it into a usable format.

   Who: Gokul Ambigapathy, Lakshmi Priya Hariharan

2. Algorithm Programing/Debugging the algorithm, using the data from the previous step to make Vertex objects, and color the graph and show output.

   Who: Roshin Cherian, Sean Lachhander, Siddheshwar Kanagamoorthy

Wrap-Up

Creating more test cases, creating/updating readme, testing, documentation.

Who: Gokul Ambigapathy, Roshin Cherian, Lakshmi Priya Hariharan, Sean Lachhander, Siddheshwar Kanagamoorthy