Python-Lab/graphColoring.py at main · SathvikShetty1/Python-Lab · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
from collections import defaultdict


class Graph:
    def __init__(self, subjects):
        self.subjects = subjects
        self.graph = defaultdict(list)

    def add_edge(self, subject1, subject2):
        self.graph[subject1].append(subject2)
        self.graph[subject2].append(subject1)

    def graph_coloring(self):
        color_map = {}
        available_colors = set(range(1, len(self.subjects)+1))
        for subject in self.subjects:
            used_colors = set()
            for neighbor in self.graph[subject]:
                if neighbor in color_map:
                    used_colors.add(color_map[neighbor])

            available_colors = available_colors - used_colors

            if available_colors:
                color_map[subject] = min(available_colors)
            else:
                color_map[subject] = len(available_colors) + 1
                available_colors.add(color_map[subject])
        return color_map

    def get_minimum_time_slots(self):
        color_map = self.graph_coloring()
        return max(color_map.values())


subjects = ['Math', 'Physics', 'Chemistry', 'Biology']
students = {
    'Math': ['Alice', 'Bob', 'Charlie'],
    'Physics': ['Alice', 'Charlie', 'David'],
    'Chemistry': ['Bob', 'Charlie,' 'Eve'],
    'Biology': ['Alice', 'David', 'Eve']
}

graph = Graph(subjects)
graph.add_edge('Math', 'Physics')
graph.add_edge('Math', 'Chemistry')
graph.add_edge('Physics', 'Chemistry')
graph.add_edge('Physics', 'Biology')

minimun_time_slots = graph.get_minimum_time_slots()
print(f"Minimum time slots required: {minimun_time_slots}")

"""
Minimum time slots required: 3
"""