Python: Importing a graph

Question

So I have this code here, which basically runs Dijkstra's Algortihm on a graph in Python, and then prints the distance and moves it takes to get from start to end. My problem is, I can't figure out how to import a graph as a .txt file using sys.argv and have it read it and run the algorithm on it. Here is my code, with a graph and start 'a' and end 'b' already filled into it. (It should work).

import sys

def shortestpath(graph,start,end,visited=[],distances={},predecessors={}):
    """Find the shortest path between start and end nodes in a graph"""
    # we've found our end node, now find the path to it, and return
    if start==end:
        path=[]
        while end != None:
            path.append(end)
            end=predecessors.get(end,None)
        return distances[start], path[::-1]
    # detect if it's the first time through, set current distance to zero
    if not visited: distances[start]=0
    # process neighbors as per algorithm, keep track of predecessors
    for neighbor in graph[start]:
        if neighbor not in visited:
            neighbordist = distances.get(neighbor,sys.maxsize)
            tentativedist = distances[start] + graph[start][neighbor]
            if tentativedist < neighbordist:
                distances[neighbor] = tentativedist
                predecessors[neighbor]=start
    # neighbors processed, now mark the current node as visited
    visited.append(start)
    # finds the closest unvisited node to the start
    unvisiteds = dict((k, distances.get(k,sys.maxsize)) for k in graph if k not in visited)
    closestnode = min(unvisiteds, key=unvisiteds.get)
    # now we can take the closest node and recurse, making it current
    return shortestpath(graph,closestnode,end,visited,distances,predecessors)



if __name__ == "__main__":
    graph = {'a': {'w': 14, 'x': 7, 'y': 9},
            'b': {'w': 9, 'z': 6},
            'w': {'a': 14, 'b': 9, 'y': 2},
            'x': {'a': 7, 'y': 10, 'z': 15},
            'y': {'a': 9, 'w': 2, 'x': 10, 'z': 11},
            'z': {'b': 6, 'x': 15, 'y': 11}}
    print(shortestpath(graph,'a','b'))


    """
    Result:
        (20, ['a', 'y', 'w', 'b'])
        """

Now here is the graph that I am trying to import, it is called sample-map.txt:

{'a': {'b': 5, 'c': 8},
'b': {'a': 5, 'd': 6},
'c': {'a': 8, 'd': 2},
'd': {'b': 6, 'c': 2, 'e': 12, 'f': 2},
'e': {'d': 12, 'g': 3},
'f': {'d': 2, 'g': 7},
'g': {'e': 3, 'f':7}}

I just need to figure out how to import it using sys.argv and then have it take the place of the graph already in the .py. Also, being able to use sys.argv to define a starting point and end point would be nice too, something like in the format >python file.py start end sample-map.txt Where

sys.argv[0] is file.py
sys.argv[1] is start
sys.argv[2] is end,
and sys.argv[3]

is the graph I want to import. Thank you!

Answer 1

If sys.argv[3] is the name of the file containing the graph you want to import, you can use ast.literal_eval:

with open(sys.argv[3], "r") as f:
    graph = ast.literal_eval(f.read())
# If you don't trust your users, check that graph is indeed a dict
# and that it has the right structure

Answer 2

You have three options:

1. JSON encoder/decoder: Python dictionaries are quite similar to JSON in format and you can import files specified as dictionaries in json format and then convert them into python dictionary. That could work in your case. Have a close look at json.load(file) method and using something like json.load(sys.argv[3]) could be worth trying. Have a look at http://docs.python.org/2/library/json.html
2. You can alternatively read the entire file using readlines and manually convert lines into a dictionary. More cumbersome but doable
3. [EDIT] I just saw a comment talking about ast.literal_eval. Again, that does not give you a dictionary directly. You will have to write some code to convert it into a dictionary.

Answer 3

I think you want to transfer the content of the file "sample-map.txt" into a dict. If you can ensure that the content of that file obeys the syntax grammer of Python. You can use the code below to do this job:

# sys.argv[3] should be 'sample-map.txt'
graph=eval(open(sys.argv[3],'r').read())  

Answer 4

This version will work:

import sys,json

def shortestpath(graph,start,end,visited=[],distances={},predecessors={}):
  ...
  return shortestpath(graph,closestnode,end,visited,distances,predecessors)

if __name__ == "__main__":

  start_node=sys.argv[1]
  end_node=sys.argv[2]
  filename=sys.argv[3]

  #here we load file text content
  with open(filename,"r") as f:
    cont= f.read()

  #here we convert text content to dict
  graph=json.loads(cont)

  print(shortestpath(graph,start_node,end_node))

You have to use " character instead of ' character to delimit keys & values in "sample-map.txt" file. (to respect JSON syntax)

Like this: { "a": {"b": 5, "c": 8}, "b": {"a": 5, "d": 6}, "c": {"a": 8, "d": 2}, "d": {"b": 6, "c": 2, "e": 12, "f": 2}, "e": {"d": 12, "g": 3}, "f": {"d": 2, "g": 7}, "g": {"e": 3, "f":7} }

If you respect the JSON syntax in the graph text file, when you call your program from a terminal:

python shortestpath.py a b sample-map.txt

You will get the good answer !

>>>(5, ['a', 'b'])