Fixed length path finding in python with naive graph colour coding

python-naive-graph-colour-coding.py

"""
A naive implementation of graph colour coding: https://en.wikipedia.org/wiki/Color-coding
Inspired by this stack overflow answer by Julian "jubueche" Büchel: https://stackoverflow.com/a/45535671/11754606

This gist attempts to find a route of a given length, between two nodes in a graph.
This is a naive implementation that very often fails for route lengths near the maximum possible.
For example, a 22-node route between Talidor and Wah'Norr is possible, but often fails to be generated, even within 2000 graph colourations.

The approach is effectively a depth first search with stochastic constraints.

The example graph given here is the star map from Galaxy on Fire 2: https://galaxyonfire.wiki.gg/wiki/Map#/media/File:Gof2_supernova_map.png
Written for the BountyBot Legacy project: https://github.com/GOF2BountyBot/GOF2BountyBot-Legacy/tree/legacy
"""

from dataclasses import dataclass
from random import randint
from typing import Dict, List, Optional, Tuple

@dataclass
class Node:
    name: str
    neighbours: List[str]


def tryFindColourfulPath(
    curr: Node,
    start: Node,
    end: Node,
    coloured: Dict[str, Tuple[int, Node]],
    route: Dict[int, Tuple[int, Node]],
    desiredLength: int
) -> Tuple[bool, List[Node]]:
    """Recursively try to find a partial, non-cyclical path, of length `desiredLength`, 
    from `start` to `end`, with the partial path beginning at `curr`.

    :param curr: The current node
    :type curr: Node
    :param start: The route start
    :type start: Node
    :param end: The route end
    :type end: Node
    :param coloured: The coloured graph
    :type coloured: Dict[str, Tuple[int, Node]]
    :param route: The route so far, from `start` to `curr`
    :type route: Dict[int, Tuple[int, Node]]
    :param desiredLength: The desired route length
    :type desiredLength: int
    :return: A bool indicating whether a route was found, alongside the successful route (if found)
    :rtype: Tuple[bool, List[Node]]
    """
    if len(route) + 2 == desiredLength:
        if end.name not in curr.neighbours:
            return (False, [])
        
        intermediaryRoute = [s[1] for s in sorted(route.values(), key=lambda pair: pair[0])]
        return (
            True, # answer was found
            [start] + intermediaryRoute + [end] # the final route
        )
    
    for neighbourName in curr.neighbours:
        neighbour = coloured[neighbourName]
        if neighbour[0] not in route and neighbour[1] is not start and neighbour[1] is not end:
            routeCopy = {k: (v[0], v[1]) for k, v in route.items()}
            routeCopy[neighbour[0]] = (len(route), neighbour[1])
            neighbourResult = tryFindColourfulPath(neighbour[1], start, end, coloured, routeCopy, desiredLength)
            if neighbourResult[0]:
                return neighbourResult

    return (False, [])


def pathOfLength(
    graph: Dict[str, Node], 
    startName: str, 
    endName: str, 
    length: int, 
    maxIterations: Optional[int] = None
) -> Optional[Tuple[int, List[Node]]]:
    """Try to find a non-cyclical path of length `length` through `graph`, from `startName` to `endName`.

    :param graph: The graph to navigate through
    :type graph: Dict[str, Node]
    :param startName: The starting node
    :type startName: str
    :param endName: The ending node
    :type endName: str
    :param length: The route length to find
    :type length: int
    :param maxIterations: An optional limit to the number of graph colourings to attempt, defaults to `length * 40`
    :type maxIterations: Optional[int], optional
    :return: The successful route alongside the number of graph colourations attempted, if a successful route could be found
    :rtype: Optional[Tuple[int, List[Node]]]
    """
    start = graph[startName]
    end = graph[endName]
    for attemptNumber in range(maxIterations or length * 40):
        # colour nodes
        coloured = {k: (randint(1, length), v) for k, v in graph.items()}
        # traverse
        attempt = tryFindColourfulPath(start, start, end, coloured, {}, length)
        if attempt[0]:
            return (attemptNumber, attempt[1])
    return None


allNodes = [
    # Terran
    Node("Aquila", ["Wolf-Reiser", "Loma", "Union"]),
    Node("Augmenta", ["Weymire", "Magnetar", "V'Ikka", "Buntta"]),
    Node("Beidan", []),
    Node("Buntta", ["Suteo", "Behén", "Augmenta", "V'Ikka", "Pescal Inartu", "Pan"]),
    Node("Magnetar", ["Union", "Oom'Bak", "V'Ikka", "Augmenta"]),
    Node("Pan", ["Buntta", "Pescal Inartu"]),
    Node("Pescal Inartu", ["Pan", "Buntta"]),
    Node("Prospero", ["Union", "Vulpes"]),
    Node("Union", ["Loma", "Aquila", "Prospero", "Magnetar", "Weymire"]),
    Node("Vulpes", ["Prospero", "Oom'Bak"]),
    Node("Wolf-Reiser", ["Aquila"]),
    
    # Vossk
    Node("K'Ontrr", ["S'Kolptorr", "Ni'Mrrod", "Me'Enkk", "Wah'Norr"]),
    Node("Me'Enkk", ["Ni'Mrrod", "K'Ontrr"]),
    Node("Ni'Mrrod", ["K'Ontrr", "Me'Enkk", "Wah'Norr"]),
    Node("Oom'Bak", ["Magnetar", "Vulpes", "S'Kolptorr", "V'Ikka"]),
    Node("S'Kolptorr", ["K'Ontrr", "Oom'Bak", "V'Ikka"]),
    Node("V'Ikka", ["Augmenta", "Buntta", "Magnetar", "Oom'Bak", "S'Kolptorr"]),
    Node("Wah'Norr", ["K'Ontrr", "Ni'Mrrod"]),
    Node("Y'Mirr", []),
    
    # Nivelian
    Node("Behén", ["Nesla", "Suteo", "Weymire", "Buntta"]),
    Node("Paréah", ["Nesla"]),
    Node("Nesla", ["Behén", "Paréah", "Weymire", "Shima", "Eanya"]),
    Node("Suteo", ["Behén", "Buntta"]),
    Node("Weymire", ["Augmenta", "Behén", "Union", "Nesla", "Shima"]),
    
    # Midorian
    Node("Eanya", ["Nesla", "Ginoya"]),
    Node("Ginoya", ["Talidor", "Eanya"]),
    Node("Loma", ["Shima", "Union", "Aquila"]),
    Node("Mido", []),
    Node("Talidor", ["Ginoya"]),
    
    # Neutral
    Node("Alda", []),
    Node("Her Jaza", []),
    Node("Shima", ["Loma", "Weymire", "Nesla"]),
    Node("Skavac", []),
    Node("Skor Terpa", [])
]

GRAPH: Dict[str, Node] = {n.name: n for n in allNodes}


result = pathOfLength(GRAPH, "Shima", "Union", 10)
if result is not None:
    print(f"Answer found in {result[0] + 1} iterations:", ", ".join(s.name for s in result[1]))
else:
    print("Answer not found.")