From 478693d804680fa6c206ce47159c0740a6f32d51 Mon Sep 17 00:00:00 2001
From: Hong-Phuc Bui <hong-phuc.bui@htwsaar.de>
Date: Mon, 30 Jun 2025 10:10:52 +0200
Subject: [PATCH] greedy funktion
---
stundenplan/src/graphdemo_tests.py | 30 ++++++++++++++++++++++++++++++
stundenplan/src/graphdemo.py | 24 ++++++++++++++++++++++++
2 files changed, 54 insertions(+), 0 deletions(-)
diff --git a/stundenplan/src/graphdemo.py b/stundenplan/src/graphdemo.py
index 9b0ac22..0bf2579 100644
--- a/stundenplan/src/graphdemo.py
+++ b/stundenplan/src/graphdemo.py
@@ -113,3 +113,27 @@
def to_dot(self) -> str:
pass
+
+ def greedy_color(self, vertex_order:[int]) -> dict[int,int]:
+ pass
+
+
+def first_available(color_list:[]) -> int:
+ color_set = set(color_list)
+ count = 0
+ while True:
+ if count not in color_set:
+ return count
+ count += 1# count = count + 1
+ pass
+
+def greedy_color(g:Graph, vertex_order:[int]) -> dict[int,int]:
+ color:dict[int,int] = {}
+ for vertex in vertex_order:
+ used_neighbor_colors = []
+ for nbr in g.adjacent_of(vertex):
+ if nbr in color:
+ used_neighbor_colors.append(color[nbr])
+ color[vertex] = first_available(used_neighbor_colors)
+ pass
+ return color
diff --git a/stundenplan/src/graphdemo_tests.py b/stundenplan/src/graphdemo_tests.py
index 0744753..644c32e 100644
--- a/stundenplan/src/graphdemo_tests.py
+++ b/stundenplan/src/graphdemo_tests.py
@@ -1,6 +1,7 @@
import unittest
from graphdemo import Graph
+from src.graphdemo import greedy_color
class GraphTestCase(unittest.TestCase):
@@ -98,6 +99,35 @@
pass
pass
+ def test_greedy_color(self):
+ g = Graph()
+ g.add_edges(0, [1, 2, 3])
+ g.add_edges(1, [0, 3, 2])
+ g.add_edges(2, [0, 1])
+ g.add_edges(3, [1])
+ print(g)
+ vertices = [1, 3, 0, 2]
+ colors = greedy_color(g, vertices)
+ print(colors)
+
+ def test_greedy_color_2(self):
+ g = Graph()
+ g.add_edges(0, [1,2, 3])
+ g.add_edges(1, [0, 2, 4])
+ g.add_edges(2, [0, 1, 5])
+ g.add_edges(3, [0, 4, 5])
+ g.add_edges(4, [1, 3, 5])
+ g.add_edges(5, [2, 3, 4])
+ print(g)
+ vertices = [0, 3, 4, 2, 5, 1]
+ #vertices = [0, 5, 3, 4, 2, 1]
+ colors = greedy_color(g, vertices)
+ print(colors)
+ for vertex in g.vertices():
+ color = colors[vertex]
+ for nbr in g.adjacent_of(vertex):
+ self.assertNotEqual(color, colors[nbr])
+
if __name__ == '__main__':
unittest.main()
--
Gitblit v1.10.0