Building a graph using dictionary

Question

I have an input text file which contains distance between 2 cities shown below

Luebeck Hamburg 63
Hamburg Bremen 116
Hamburg Hannover 153
Hamburg Berlin 291
Bremen Hannover 132
Bremen Dortmund 234
Hannover Magdeburg 148
Hannover Kassel 165
Magdeburg Berlin 166
Berlin Dresden 204
Dresden Leipzig 119
Leipzig Magdeburg 125
Dortmund Duesseldorf 69
Kassel Frankfurt 185
Frankfurt Dortmund 221
Frankfurt Nuremberg 222
Leipzig Nuremberg 263
Dortmund Saarbruecken 350
Saarbruecken Frankfurt 177
Saarbruecken Karlsruhe 143
Karlsruhe Stuttgart 71
Stuttgart Frankfurt 200
Stuttgart Munich 215
Stuttgart Nuremberg 207
Nuremberg Munich 171
Manchester Birmingham 84
Birmingham Bristol 85
Birmingham London 117
END OF INPUT

My dictionary should be like this:

{  
 'luebeck': [('hamburg', '63')], 'dortmund': [('bremen', '234'), ('duesseldorf', '69')]
 'saarbruecken': [('dortmund', '350'), ('frankfurt', '177'), ('karlsruhe', '143')]
  ..
 }

My code is working but it is not efficient and I want to optimize it:

---

def read_file(filename):
    paths = []
    graph = {}
    f = open(filename, 'r')
    for line in f:
        route = line.lower().split()
        paths.append(route)

    # to remove space and end of input
    del paths[-1]
    del paths[-1]

    for path in paths:
        node = path[0]
        if node not in graph:
            graph[node] = {}
            graph[node][path[1]] = int(path[2])
        elif node in path:
            graph[node][path[1]] = int(path[2])
            node = path[1]
            if node not in graph:
                graph[node] = {}
        node = path[1]
        if node not in graph:
            graph[node] = {}
            graph[node][path[0]] = int(path[2])
        elif node in path:
            graph[node][path[0]] = int(path[2])
    return graph

Please tell me if any additional information is required.

Answer 1

I will add to @baot's excellent review:

hoist the IO

As detailed in this talk by Brendan Rhodes, testing your code is easier if you hoist your IO, so I would not let your function read the file, but accept an iterator of lines

defaultdict

instead of all the graph.setdefault, if you make graph a collections.defaultdict, you can use regular indexing

End of Input

if ever the end of input changes, this will crash. I would surround the int() with a try-except, and call the break in there

from collections import defaultdict

def parse_graph(lines):
    graph = defaultdict(list)
    for line in lines:
        try:
            city1, city2, distance = line.split()
            distance = int(distance)
        except ValueError:
            return dict(graph)
        graph[city1].append((city2, distance))
        graph[city2].append((city1, distance))
    return dict(graph)

This can be easily tested with

parse_graph(data.split(\n)

{'Luebeck': [('Hamburg', 63)],
 'Hamburg': [('Luebeck', 63),
  ('Bremen', 116),
  ('Hannover', 153),
  ('Berlin', 291)],
 'Bremen': [('Hamburg', 116), ('Hannover', 132), ('Dortmund', 234)],
 'Hannover': [('Hamburg', 153),
  ('Bremen', 132),
  ('Magdeburg', 148),
  ('Kassel', 165)],
...
}

To call it with a file, you just do

if __name__ == "__main__":
    with open('test.txt', 'r') as file:
        print(parse_graph(file))

dict of dict

a dict of dict is a more logical data structure then a dict of list of tuples

This algorithm can be quite easily change to

def parse_graph_dict(lines):
    graph = defaultdict(dict)
    for line in lines:
        try:
            city1, city2, distance = line.split()
            distance = int(distance)
        except ValueError:
            return dict(graph)
        graph[city1][city2] = distance
        graph[city2][city1] = distance
    return dict(graph)

{'Luebeck': {'Hamburg': 63},
 'Hamburg': {'Luebeck': 63, 'Bremen': 116, 'Hannover': 153, 'Berlin': 291},
 'Bremen': {'Hamburg': 116, 'Hannover': 132, 'Dortmund': 234},
 'Hannover': {'Hamburg': 153, 'Bremen': 132, 'Magdeburg': 148, 'Kassel': 165},
...
}

Answer 2

• To many accumulators, paths and graph, you just need one.
• One for loop to many, you can do everything with one loop.
• open with no close is a no no. Sure you could aruge that the codebase is small and you will just run the function once and then terminate... But it's good practice to always close your file handlers. Instead of using open() and close() you shuold just use with open(filename, 'r') as f:, because with clause take care of close() for you.
• Route is not use anywhere else so no need for it.
• You are doing del paths[-1] twice so you will actually remove one vaild path.
• The for loop is stupidly complex for such a simple problem. I dont even know where to start in my quest of understading it.
  • graph[node][path[0]] doesn't do what you say it does; it makes a dict of dict, and not a list of tuples in a dict as you specified. eg. the code returns {birmingham : {'manchester': 84, 'bristol': 85}} instead of {birmingham : [('manchester', 84), ('bristol', 85)]}.
  • So theres a lot of if else statements in the loop to solve the problem of: "what to do when the dict/list isn't instantiated" . This can be done in a simpler way with dict.setdefault(), this function basically checks if the dict has an list (dict or whatever you want) as a child, and if it dosen't it will instantiate it for you.
• I dont think that's a graph because not everything in that dataset is connected to eachother, its more like a set of graphs.

---

def new_sol(filename):
    graph = {}
    with open(filename, 'r') as f:
        for line in f:
            city1, city2, distance = line.lower().split()
            if distance == "input":
                break
            #what you say you want
            graph.setdefault(city1, []).append((city2,int(distance)))
            graph.setdefault(city2, []).append((city1,int(distance)))
            #same as your code
            #graph.setdefault(city1, {})[city2] = int(distance)
            #graph.setdefault(city2, {})[city1] = int(distance)
    return graph
if __name__ == "__main__":
    print(new_sol("test.txt"))

---

Time analysis

You wanted to optimize the code, so lets us do an time analysis to see if there is some thing we can optimize in our algorithms, or if the optimaztion is just in the implementaion.

askers code

• read line: \$O(N)\$
• put line in arr: \$O(1)\$
• iterate over paths: \$O(N)\$
• put the diffrent directions in a dict \$O(2)\$

\$O(N*1+N*2) = O(N*3) = O(N)\$

proposed code

• read line: \$O(N)\$
• put line in arr/dict: \$O(2*(1+1))\$, \$(1+1)\$ comes from lookup/insertion + insertion

\$O(N*4) = O(N)\$

So from a algorithmic standpoint both your code and my code preforme equally well, and that is the fastst we can do it. From an implentaion standpoint my code is a bit faster but as \$N\$ goes toward infinity it dosent really matter.