hamiltonian path with or tools

hamiltonian_path_or_tools.py

import networkx as nx
from ortools.sat.python import cp_model
from typing import List, Optional
import matplotlib.pyplot as plt


def generate_random_directed_graph(
        num_nodes: int,
        edge_prob: float,
        seed: int | None = None
) -> nx.DiGraph:
    """
    Generates a random directed graph using the Erdős-Rényi model.
    """
    graph = nx.gnp_random_graph(num_nodes, edge_prob, directed=True, seed=seed)
    return graph


def visualize_graph(
        graph: nx.DiGraph,
        plot_title: str = "Random Directed Graph",
        path: Optional[List[int]] = None
) -> None:
    """
    Visualizes the directed graph using Matplotlib, highlighting the path if provided.
    """
    position = nx.spring_layout(graph)  # Positions for all nodes

    plt.figure(figsize=(10, 8))
    nx.draw_networkx_nodes(graph, position, node_size=700, node_color='lightblue')
    nx.draw_networkx_edges(graph, position, arrowstyle='->', arrowsize=20, edge_color='gray')
    nx.draw_networkx_labels(graph, position, font_size=12, font_weight='bold')

    if path:
        # Create edge list for the path
        path_edges = list(zip(path, path[1:]))
        nx.draw_networkx_edges(
            graph, position, edgelist=path_edges, edge_color='red', arrowstyle='->', arrowsize=20, width=2
        )
        # Highlight nodes in the path
        nx.draw_networkx_nodes(
            graph, position,
            nodelist=path,
            node_size=700,
            node_color='lightgreen'
        )

    plt.title(plot_title)
    plt.axis('off')
    plt.tight_layout()
    plt.show()


def find_hamiltonian_path(
        graph: nx.DiGraph,
        origin: int,
        destination: int
) -> list[int] | None:
    """
    Finds a Hamiltonian path from origin to destination in the directed graph using OR-Tools.

    Parameters:
    - graph (nx.DiGraph): The directed graph to search within.
    - origin (int): The starting node.
    - destination (int): The target node.

    Returns:
    - List[int] or None: A list of nodes representing the Hamiltonian path from origin to destination.
                         Returns None if no such path exists.
    """
    if origin not in graph:
        raise ValueError(f"Origin node {origin} does not exist in the graph.")
    if destination not in graph:
        raise ValueError(f"Destination node {destination} does not exist in the graph.")

    num_nodes = graph.number_of_nodes()
    nodes = list(graph.nodes())
    node_indices = {node: idx for idx, node in enumerate(nodes)}

    model = cp_model.CpModel()

    pos = [model.NewIntVar(0, num_nodes - 1, f'pos_{node}') for node in nodes]

    model.AddAllDifferent(pos)

    model.Add(pos[node_indices[origin]] == 0)
    model.Add(pos[node_indices[destination]] == num_nodes - 1)

    # If there is no edge from node i to node j, then node j cannot immediately follow node i in the path
    for i in nodes:
        for j in nodes:
            if i != j and not graph.has_edge(i, j):
                # pos[j] != pos[i] + 1
                model.Add(pos[node_indices[j]] != pos[node_indices[i]] + 1)

    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    if status == cp_model.FEASIBLE or status == cp_model.OPTIMAL:
        # Extract the path based on positions
        path = [0] * num_nodes
        for node in nodes:
            position = solver.Value(pos[node_indices[node]])
            path[position] = node
        return path

    return None


def main():
    number_of_nodes = 8
    edge_probability = 0.4
    random_seed = 42

    directed_graph = generate_random_directed_graph(
        num_nodes=number_of_nodes,
        edge_prob=edge_probability,
        seed=random_seed
    )

    print("Number of nodes:", directed_graph.number_of_nodes())
    print("Number of edges:", directed_graph.number_of_edges())
    print("Nodes:", list(directed_graph.nodes()))
    print("Edges:", list(directed_graph.edges()))

    visualize_graph(directed_graph, plot_title="Erdős-Rényi Random Directed Graph")

    origin_node: int = 0
    destination_node: int = 7

    find_hamiltonian_path(
        graph=directed_graph,
        origin=origin_node,
        destination=destination_node
    )


if __name__ == "__main__":
    main()