implementing adjacency list for graph

Question

I'm given a graph string like this

graph_string = """\
D 3
0 1
1 0
0 2
"""

and my function needs to output that graph as an adjacency list like this

[[(1, None), (2, None)], [(0, None)], []]

but my function is only outputting it like this

[[(2, None)], [], []]

and i am not sure why?

def adjacency_list(graph_str):
    """Takes a graph string and returns the adjacency list"""

    lines = graph_str.splitlines()
    header = lines[0].split()

    if len(header) > 2:
        graph_type, vertices, weight = header[0], header[1], header[2]
    else:
        graph_type, vertices = header[0], header[1]
        weight = None

    edges = lines[1:]
    adj_list = [[] for _ in range(int(vertices))]

    if len(edges) > 0:
        for edge in edges:
            if weight == 'W':
                v1, v2, w = edge.split()
                v1, v2, w = int(v1), int(v2), int(w)
            else:
                v1, v2 = edge.split()
                v1, v2 = int(v1), int(v2)
                w = None
    if graph_type == 'U':
        adj_list[v1] += [(v2, w)]
        adj_list[v2] += [(v1, w)]
    else:
        adj_list[v1] += [(v2, w)]
    return adj_list
    
graph_string = """\
D 3
0 1
1 0
0 2
"""
print(adjacency_list(graph_string))

Md Fahim · Accepted Answer · 2021-04-29 23:35:29Z

The code is fine, except for the indentation of the final if-else. The adjacency list items need to be added immediately after an edge is processed, so that should be inside the for loop (not outside).

The code below is fixed.

def adjacency_list(graph_str):
    """Takes a graph string and returns the adjacency list"""

    lines = graph_str.splitlines()
    header = lines[0].split()

    if len(header) > 2:
        graph_type, vertices, weight = header[0], header[1], header[2]
    else:
        graph_type, vertices = header[0], header[1]
        weight = None

    edges = lines[1:]
    adj_list = [[] for _ in range(int(vertices))]

    if len(edges) > 0:
        for edge in edges:
            if weight == 'W':
                v1, v2, w = edge.split()
                v1, v2, w = int(v1), int(v2), int(w)
            else:
                v1, v2 = edge.split()
                v1, v2 = int(v1), int(v2)
                w = None
                
            if graph_type == 'U':
                adj_list[v1] += [(v2, w)]
                adj_list[v2] += [(v1, w)]
            else:
                adj_list[v1] += [(v2, w)]
    return adj_list
    
graph_string = """\
D 3
0 1
1 0
0 2
"""
print(adjacency_list(graph_string))

Collectives™ on Stack Overflow

implementing adjacency list for graph

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related