greedy funktion

Hong-Phuc Bui

5 days ago 478693d804680fa6c206ce47159c0740a6f32d51

greedy funktion

 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

 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()