C1M3 generate_graph takes forever

Course Q&A Generative AI for Software Development Introduction to Generative AI for Software Develop
,
1

Even without changing anything, I can’t get the generate_graph function to run.
g = generate_graph(nodes=10, edges =5)
which is a very small graph, takes so long that the lab environment times out before it finishes running.

2

Hi @zyoscovits,

This is weird, it shouldn’t take too long. Can you restart your kernel and try it again? I will try it too, sometimes the Coursera environment gets busy and things can slow down.

Lucas

3

I figured it out. The edges parameter is edges per node, not total edges, and by default the graph is undirected. Also, it tries to add edges to each node sequentially, adding to edges it already has.
So a 10 node undirected graph has 10x9/2 = 45 possible edges, but the algorithm tries to add 5x10 = 50 edges, which is impossible so it gets stuck in an infinite loop.

1 Like
4

I am also seeing this issue, when using generate_graph(5, edges=2). Debugging shows this is possibly due to randomness in below lines, not allowing to skip the loop forever:
" while j == i or j in graph.get_adjacent_vertices(i): # Ensure the edge is not a loop or a duplicate
j = random.randint(0, nodes - 1)"

To me this is quiet consistently reproduced. I used below updated code and its working now:

def generate_graph(nodes, edges=None, complete=False, weight_bounds=(1, 600), seed=None):
“”"
Generates a graph with specified parameters, allowing for both complete and incomplete graphs.

This function creates a graph with a specified number of nodes and edges, with options for creating a complete graph, and for specifying the weight bounds of the edges. It uses the Graph_Advanced class to create and manipulate the graph.

Parameters:
- nodes (int): The number of nodes in the graph. Must be a positive integer.
- edges (int, optional): The number of edges to add for each node in the graph. This parameter is ignored if `complete` is set to True. Defaults to None.
- complete (bool, optional): If set to True, generates a complete graph where every pair of distinct vertices is connected by a unique edge. Defaults to False.
- weight_bounds (tuple, optional): A tuple specifying the lower and upper bounds (inclusive) for the random weights of the edges. Defaults to (1, 600).
- seed (int, optional): A seed for the random number generator to ensure reproducibility. Defaults to None.

Raises:
- ValueError: If `edges` is not None and `complete` is set to True, since a complete graph does not require specifying the number of edges.

Returns:
- Graph_Advanced: An instance of the Graph_Advanced class representing the generated graph, with vertices labeled as integers starting from 0.

Examples:
- Generating a complete graph with 5 nodes:
    generate_graph(5, complete=True)

- Generating an incomplete graph with 5 nodes and 2 edges per node:
    generate_graph(5, edges=2)

Note:
- The function assumes the existence of a Graph_Advanced class with methods for adding vertices (`add_vertex`) and edges (`add_edge`), as well as a method for getting adjacent vertices (`get_adjacent_vertices`).
"""
random.seed(seed)
graph = Graph_Advanced()
if edges is not None and complete:
    raise ValueError("edges must be None if complete is set to True")

for i in range(nodes):
    graph.add_vertex(i)

if complete:
    for i in range(nodes):
        for j in range(i + 1, nodes):
            weight = random.randint(weight_bounds[0], weight_bounds[1])
            graph.add_edge(i, j, weight)
else:
    for i in range(nodes):
        attempts = 0
        max_attempts = 100  # Set a reasonable threshold for attempts
        for _ in range(edges):
            j = random.randint(0, nodes - 1)
            while (j == i or j in graph.get_adjacent_vertices(i)) and attempts < max_attempts:
                j = random.randint(0, nodes - 1)
                attempts += 1
            if attempts >= max_attempts:
                print(f"Warning: Could not find a valid vertex to connect to for vertex {i} after {max_attempts} attempts.")
                break
            weight = random.randint(weight_bounds[0], weight_bounds[1])
            graph.add_edge(i, j, weight)
            attempts = 0  # Reset attempts for the next edge

return graph

@lucas.coutinho you may consider this fix to be added in course.

5

Thanks all,

I have improved the algorithm, now it does not get stuck in an infinite loop and will raise an error if edges > nodes. You may need to refresh your workspace to get the updated file.