CODEWITHSUNDEEP
pythondictionary
OnePiece
OnePiece

Reputation: 518

Using nested dictionaries to store user defined graph

I am trying to get the user to enter a graph manually as opposed to using it 'pre-existing' in the code, for use in my Dijkstra's Algorithm.

I have done this but would like some feedback on its implementation and user friendliness. In addition is there a more efficient way of entering a graph into a nested dictionary ? If so how ?.

Key points about code

Many Thanks. Edit: repeat requirement no longer needed.

{'A': {'C': 1, 'B': 5}, 'D': {}, 'B': {'D': 2}, 'C': {'D': 9}}

^ Desired output for nodes also current output.

nodes = {}


def add_node():
    entered_graph = False
    while not entered_graph:
        source_node = input("Enter a source node: ")
        num_neighbours = int(input("Enter how many neighbours this node has"
                                   "including previously entered nodes: "))
        nodes[source_node] = {}
        for neighbour in range(num_neighbours):
            neighbour = input("Enter neighbor node: ")
            distance = int(input("Enter distance from source node to this neighbor node: "))
            nodes[source_node][neighbour] = distance
        end_loop = input("Enter y to finish graph entry: ")
        end_loop = end_loop.lower()
        if end_loop == "y":
            entered_graph = True

add_node()
print(nodes)

Upvotes: 1

Views: 1290

Answers (2)

Aaron
Aaron

Reputation: 11075

Khanacademy has a pretty good page on different ways to represent graphs.

For an undirected graph (a => b and b => a) I would personally look at using an edge list. It can be sorted to improve lookup efficiency, and it is more memory efficient than other methods such as an adjacency table

Upvotes: 0

Patrick Haugh
Patrick Haugh

Reputation: 60984

You really only want users to enter every edge once, then you can just store it twice.

edges = {}
while True:
    edge = input('Enter an edge as Node names separated by a space followed by a number ("exit" to exit): ')
    if edge == 'exit':
        break
    node1, node2, weight = edge.split()
    weight = float(weight)
    if node1 not in edges:
        edges[node1] = {}
    if node2 not in edges:
        edges[node2] = {}
    edges[node1][node2] = weight
    edges[node2][node1] = weight

User enters each edge once as "A B 3.5"

Upvotes: 1

Related Questions