Find the number of unique nodes in a graph in Python

Question

Given a graph with the format (source, destination, weight):

graph = [
    (1, 2, 2),
    (1, 3, 7),
    (2, 3, 1),
]

I need to assign num_nodes to be the number of unique nodes in the given graph. This is for a Bellman Ford algorithm.

The code I have so far (that is relevant to this question) is as such:

def bellman_ford(graph, source):
    # Find the number of unique nodes in the graph
    # Start
    num_nodes = 0
    uniquevalues = list(set(i for j in graph for i in j))
    for item in uniquevalues:
        num_nodes = num_nodes + 1
    # End

    # Initialize distance vector with infinity and set distance to self is 0
    # Start
    distance = {i : float("Inf") for i in uniquevalues}
    distance[source] = 0
    # End

In my attempt it lists all the unique values of the graph, including the weight values. This obviously causes problem with the output, where it thinks the weight of an edge is a node.

I also had to create uniquevalues to account for initializing the distance vector needing something iterable to assign nodes their distance as infinity. I'm open to suggestions if there are better ways to go about that.

Answer 1

Since it is known that the last item in each tuple in the input list of a graph is not a node, you can unpack the tuple and discard the last item in each iteration before you build a new set. Use the len function to obtain the size of the set for your desired count of unique nodes:

graph = [
    (1, 2, 2),
    (1, 3, 7),
    (2, 3, 1),
]
unique_nodes = {node for *nodes, _ in graph for node in nodes}
num_nodes = len(unique_nodes) # num_nodes becomes 3