Finding an optimal orientation and the oriented diameter of a given graph - Python

Question

I am wanting to specify a graph (a collection of vertices and edges) and find the optimal orientation of that graph. The graph has 7 vertices and its (undirected) edges are: (1, 3), (1, 7), (1, 5), (1, 6), (1, 4), (2, 4), (2, 5), (2, 6), (2, 7), (3, 5), (3, 7), (3, 6), (4, 6)

An orientation of an undirected graph is an assignment of a direction to its every edge. An optimal orientation is an orientation that maximizes reachability (A vertex v is reachable from a vertex u if there is a path from u to v).

Furthermore, I want to find the numerical value of the oriented diameter of that graph.

The distance between two vertices u and v in a graph (or digraph) G is the length of a shortest path from u to v in G. The maximum of all the distances between two vertices in a graph (or digraph) G is called the diameter of G. The oriented diameter of G is the smallest diameter among all strong orientations of G.

I have written code in Python, but I get an error message and cannot figure out how to correct my code. I have attached a picture of the error message I get. I don't know if my code is the best either, so any suggestions are most welcome.

Here is my code:

from collections import defaultdict
from queue import Queue

def find_orientation(graph):
    # Initialize with arbitrary orientation
    orientation = {edge: 1 for edge in graph}

    # Flag to keep track of whether any improvement was made
    improved = True

    while improved:
        improved = False

        for edge in graph:
            u, v = edge

            # Reverse the direction of the edge
            orientation[edge] *= -1

            # Compute the number of connected pairs
            num_connected_pairs = count_connected_pairs(graph, orientation)

            if num_connected_pairs > 0:
                # If the orientation improves reachability, keep the change
                improved = True
            else:
                # Revert the direction change
                orientation[edge] *= -1

    return orientation

def count_connected_pairs(graph, orientation):
    num_connected_pairs = 0

    for vertex in graph.keys():
        visited = set()
        queue = Queue()
        queue.put(vertex)

        while not queue.empty():
            u = queue.get()
            visited.add(u)

            for v in graph[u]:
                if orientation[(u, v)] == 1 and v not in visited:
                    queue.put(v)
                    num_connected_pairs += 1

    return num_connected_pairs

def compute_oriented_diameter(graph, orientation):
    diameter = 0

    for vertex in graph.keys():
        distance = bfs(graph, orientation, vertex)
        diameter = max(diameter, max(distance.values()))

    return diameter

def bfs(graph, orientation, start):
    distance = {vertex: float('inf') for vertex in graph.keys()}
    distance[start] = 0

    queue = Queue()
    queue.put(start)

    while not queue.empty():
        u = queue.get()

        for v in graph[u]:
            if orientation[(u, v)] == 1 and distance[v] == float('inf'):
                distance[v] = distance[u] + 1
                queue.put(v)

    return distance

# Undirected graph represented as an adjacency list
graph = defaultdict(list)
edges = [(1, 3), (1, 7), (1, 5), (1, 6), (1, 4), (2, 4), (2, 5), (2, 6), (2, 7), (3, 5), (3, 7), (3, 6), (4, 6)]

for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)

# Find the orientation that maximizes reachability
orientation = find_orientation(graph)

print("Edge Orientation:")
for edge, direction in orientation.items():
    u, v = edge
    if direction == 1:
        print(f"{u} -> {v}")
    else:
        print(f"{v} -> {u}")

# Compute the oriented diameter of the graph
diameter = compute_oriented_diameter(graph, orientation)
print("Oriented Diameter:", diameter)

error message