Python - Create a graph from a dictionary

Question

so i have a csv file that has the following format:

start_city, end_city, length, time

So I have been able to extract the data from there and convert it into a list of dicts that looks like this,

map_dict = [
  {'start': 'a', 'end': 'b', 'length': 5, 'time': 55},
  {'start': 'a', 'end': 'c', 'length': 8, 'time': 125},
....]

I need to know to convert this into a graph so that i can perform operations like shortest path from one city to another, minimum edges from one city to another etc.

Can anyone tell me how I can convert my list of dicts to a connected graph with edges between them?

Like in the above example, there should be an edge between a -> b and a -> c.

If you can provide a reliable read-up source that'll be helpful too. Thank you.

Answer 1

Check out NetworkX library.

On GitHub: https://github.com/networkx/networkx

Using your example with a few extra points and setting time as the weight:

import numpy as np
import matplotlib.pyplot as plt

G = nx.Graph()
map_dict = [
            {'start': 'a', 'end': 'b', 'length': 5, 'time': 55},
            {'start': 'a', 'end': 'c', 'length': 8, 'time': 125},
            {'start': 'b', 'end': 'c', 'length': 22, 'time': 275},
            {'start': 'c', 'end': 'd', 'length': 16, 'time': 210},
            {'start': 'b', 'end': 'e', 'length': 22, 'time': 14},
            {'start': 'd', 'end': 'e', 'length': 7, 'time': 6}  ]

for pts in map_dict:
    G.add_edge(pts['start'], pts['end'], weight=pts['time'])

# Show the shortest path between points 'a' and 'e'.
path = nx.shortest_path(G, source='a',target='e')
print(path)

path_edges = zip(path, path[1:])
path_edges = set(path_edges)
pos = nx.spring_layout(G)
nx.draw(G, pos, node_color='lawngreen', with_labels = True)
nx.draw_networkx_nodes(G, pos, nodelist=path, node_color='mediumseagreen')
nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='r', width=10)
plt.axis('equal')
plt.show()    

Output: ['a', 'b', 'e']

Answer 2

You are not so far from a solution. First think how you want to represent your graph. A typical datastructure is to build a dictionary with nodes as keys and a list of nodes as values (i.e. your edges).

Here's a simple code that does what you want. The conversion function is create_graph_from_map and I add a function to print the edges so you can verify it works. For simplicity I am using a 3-tuple to represent your edges, but you can also create your own classes for that or use a dict.

map_dict = [
    {'start': 'a', 'end': 'b', 'length': 5, 'time': 55},
    {'start': 'a', 'end': 'c', 'length': 8, 'time': 125},
    {'start': 'b', 'end': 'd', 'length': 10, 'time': 130}
]

def create_graph_from_map(map_dict):
    """convert a dictionary of start/end information into a directed graph"""
    graph = {}
    for info in map_dict:
        start_city = info['start']
        if not start_city in graph:
            graph[start_city] = []
        edge = (info['end'], info['length'], info['time'])
        graph[start_city].append(edge)

    return graph

def show_edges(graph, start_city):
    for edge in graph[start_city]:
        end_city, length, travel_time = edge
        print(F"{start_city} -> {end_city}, length={length}, time={travel_time}")

# main
graph = create_graph_from_map(map_dict)
show_edges(graph, 'a')

This will print

a -> b, length=5, time=55
a -> c, length=8, time=125