Map coloring algorithm functional implementation in python

Question

I'm an autodidact working on map coloring algorithms with backtracking, see chapter 2 of this book.

I tested this implementation with success but I'm still unsure whether it is tricking me somewhere, or if I could improve it.

Color = int

def paint(graph: dict[Node, list[Node]]) -> list[tuple[Node, Color]]:
    """An interface."""

    def init(nodes: list[Node]) -> list[tuple[Node, Color]]:
        """Starts out with no colors assigned"""
        return [(n, -1) for n in nodes]

    def is_legal(color: Color, node: Node, ns: list[tuple[Node, Color]]) -> bool:
        """True if parent's color is different from childrens' color"""
        for child in graph[node]:
            if (child, color) in ns:
                return False
        return True

    def _paint(i: int, ns: list[tuple[Node, Color]], max_colors: int):
        """Helper function"""
        if i == len(ns):
            return ns  # we did it
        if i < 0:
            # tried everything possible but nope
            return _paint(0, init(sorted_adjacent), max_colors + 1)
        node, color = ns[i]
        if color + 1 == max_colors:
            return _paint(i - 1, ns, max_colors)  # backtrack
        ns[i] = (node, color + 1)
        if is_legal(color + 1, node, ns):
            return _paint(i + 1, ns, max_colors)  # go to next node
        else:
            return _paint(i, ns, max_colors)  # try with next color

    sorted_adjacent = sorted(graph.keys(), key=lambda r: -len(graph[r]))
    return _paint(0, init(sorted_adjacent), 2)

This is the rest of the code, with an example graph input, which is defined as a simple dictionary with nodes as keys, and a list of nodes (the adjacent regions) as values:

class Node:
    def __init__(self, s: str):
        self.s = s

    def __repr__(self):
        return f"Node('{self.s}')"


if __name__ == "__main__":
    graph_ = {
        (n1 := Node("1")): [(n2 := Node("2"))],
        n2: [n1, (n3 := Node("3")), (n4 := Node("4")), (n5 := Node("5")), (n6 := Node("6"))],
        n3: [n2, n4],
        n4: [n2, n3, n5],
        n5: [n2, n4, n6],
        n6: [n2, n5],
    }
    output = paint(graph_)

Answer 1

meaningful identifier

class Node:
    def __init__(self, s: str): ...

Fine, we can read this as "s of string".

But wouldn't you like to offer a friendlier identifier, perhaps name ?

nit: In init(), rather than n (number?) prefer the longer

        return [(node, -1) for node in nodes]

In general, it's hard to go wrong by saying for thing in plural_things.

Similarly, ns could become nodes.

OTOH, aliasing integer as Color was very nice, thank you.

nested functions

I recommend you avoid nested def's, for these reasons:

1. The shared namespaces produce the same coupling troubles that lead to globals being so reviled.
2. It's hard to separately unit test those buried hidden functions

In fortran we might say COMMON SORTED_ADJACENT. In python we might prefer to invent a new class, and then refer to self.sorted_adjacent.

docstring

        """Helper function"""

By naming it _paint(), you already pretty much told us that it is a helper function. (And then you buried it by nesting, so it's not like it shall be exported from the module namespace anyway.) Maybe we see the tail wagging the dog here, given that most of the function's body disappeared down into the helper. OIC, it's a recursive helper, with mainline doing the setup, got it.

This is at best a # comment. Please write an English sentence, explaining what the function does, when writing function docstrings. Optionally add a blank line and more information if you feel there's more to say.

I would have been grateful, if you'd written an actual docstring -- some explanation about the strategy would be very helpful here.

color high degree nodes first

    ... key=lambda r: -len(graph[r]))

This is very nice.

Consider turning the anonymous lambda into a named def function. And then the function's docstring might acknowledge Wetherell's hint about

Regions that have many neighbors will probably be hardest to color, since they have the most constraints on them.

---

This code appears to achieve its design goals.

It scores about middle-of-the-road for maintainability, neither great nor terrible.

Answer 2

This is a classic problem in computer science.

Performance Optimization:

Your algorithm uses backtracking, which can be inefficient for large graphs. You might consider optimizing the algorithm for performance. For instance, using more advanced techniques like constraint programming or graph heuristics might improve efficiency.

Enhanced Color Assignment Logic:

The coloring logic can be further refined. For example, you can implement a heuristic that chooses the next color based on the current state of the graph, potentially reducing the number of backtracking steps.

Error Handling and Validation:

Add checks to handle invalid inputs or special cases, such as an empty graph or a graph with a single node.